A generalization of the Mabinogion sheep problem of D. Williams

Abstract

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.