In his well-known textbook Probability with Martingales, David Williams (1991) introduces the Mabinogion sheep problem in which there is a magical flock of sheep, some black, some white. At each stage n=1,2,..., a sheep (chosen randomly from the entire flock, independently of previous events) bleats; if this bleating sheep is white, one black sheep (if any remain) instantly becomes white; if the bleating sheep is black, one white sheep (if any remain) instantly becomes black. No births or deaths occur. Suppose that one may remove any number of white sheep from the flock at (the end of) each stage n=0,1,.... The object is to maximize the expected final number of black sheep. By applying the martingale optimality principle, Williams showed that the problem is solvable and admits a simple nice solution. In this paper we consider a generalization of the Mabinogion sheep problem with two parameters 0≤p, q≤1, denoted M(p,q), in which at each stage, when the bleating sheep is white (black, respectively), a black (white, respectively) sheep (if any remain) instantly becomes white (black, respectively), with probability p (q, respectively) and nothing changes with probability 1-p (1-q, respectively). Note that the original problem corresponds to (p,q)=(1,1). Following Williams' approach, we solve the two cases (p,q)=(1,1/2) and (1/2,1) which admit simple solutions.

The preferential attachment network with fitness is a dynamic random graph model. New vertices are introduced consecutively and a new vertex is attached to an old vertex with probability proportional to the degree of the old one multiplied by a random fitness. We concentrate on the typical behaviour of the graph by calculating the fitness distribution of a vertex chosen proportional to its degree. For a particular variant of the model, this analysis was first carried out by Borgs, Chayes, Daskalakis and Roch. However, we present a new method, which is robust in the sense that it does not depend on the exact specification of the attachment law. In particular, we show that a peculiar phenomenon, referred to as Bose–Einstein condensation, can be observed in a wide variety of models. Finally, we also compute the joint degree and fitness distribution of a uniformly chosen vertex.