
Advanced Statistics Advanced Probability and Statistics Math Forum 
 LinkBack  Thread Tools  Display Modes 
May 6th, 2018, 09:27 AM  #1 
Newbie Joined: May 2018 From: New York Posts: 1 Thanks: 0  The Mabinogion sheep problem (Martingale)
$\textbf{The Mabinogion sheep problem}$ By David Williams >• There is an flock containing white and black sheep. • At each moment of time 1, 2, 3, . . . one sheep is drawn randomly from the flock, independently of the previous selections. The color of the sheep is observed and the sheep is returned to the flock. •If the drawn sheep is white, one black sheep (if there are any left) is replaced by a white sheep. Similarly, if the drawn sheep is black, one of the remaining white sheep (if any) is replaced by a black sheep. • If all remaining balls are of the same color the process stops. >The controlled system: Suppose now that the system can be controlled at time 0 and after each time sheep has been drawn from the flock: $\textbf{The object is to maximize the expected final number of black sheep}.$ >Policy $\bf{A}$ : at each time of decision, Do nothing if there are more black sheep than white sheep or if no black sheep remain; otherwise, immediately reduce the white population to one less than the black population. >We define the value function $V : Z^{+} × {Z} ^{+} → [0, ∞)$ so that $V (w, b)$ is the expected final number of black sheep under Policy $\bf{A}$ if there are $w$ white sheep and $b$ black sheep at the start. As a result, V has the following properties, >a1) $V(0,b)=b, V(w,0)=0$ . a2) $V(w,b)=V(w1,b)$ whenever $w\ge b>0$ a3) $V(w,b) = \frac{w}{w+b}V(w+1,b1)+\frac{b}{w+b}V(w1,b+1)$ whenever $0<w<b$ >$\textbf{Question (a)}$ : Show that under the policy $\textbf{A}$, $V(W_n,B_n)$ is a martingale w.r.t. filtration $\mathcal{F}$, where $\{W_n,B_n\}$ is number of white and black sheep after $n_{th}$ time. >$\textbf{Question (b)}$ : Suppose $V(w,b) \ge \frac{w}{w+b}V(w+1,b1)+\frac{b}{w+b}V(w1,b+1)$ and $V(w,b) \ge V(w1,b)$ whenever $w\ge0$ and $b \ge 0$. Show that for any other policies, $V(W_n,B_n)$ is a supermartingale w.r.t. filtration $\mathcal{F}$. $\textbf{My attempt}$: $\textbf{The property a1)a3) are what we have known, they are very easy to show.}$ $\textbf{For my proof to Question (a)}$ $E\{V(W_{n+1},B_{n+1})\mathcal{F_n}\} = \frac{W_n}{W_n+B_n}V(W_{n}+1,B_{n}1) + \frac{B_n}{W_n+B_n}V(W_{n}1,B_{n}+1) =V(W_{n},B_{n})$. Therefore, $V(W_{n},B_{n})$ is a martingale w.r.t. $\mathcal{F_n}$ $\textbf{For my proof to Question (b)}$ $E\{V(W_{n+1},B_{n+1})\mathcal{F_n}\} = \frac{W_n}{W_n+B_n}V(W_{n}+1,B_{n}1) + \frac{B_n}{W_n+B_n}V(W_{n}1,B_{n}+1) < V(W_{n},B_{n})$. Therefore, $V(W_{n},B_{n})$ is a supermartingale w.r.t. $\mathcal{F_n}$ Do I miss some points for proving (a) and (b)? Could you help me to check my answer? I am studying martingale and its application. And I am very curious about this question in the textbook. This is a stochastic control problem by David Williams, called The Mabinogion sheep problem. (Williams, David (1991), Probability with martingales, Cambridge Mathematical Textbooks, Cambridge University Press) Thank you so much. Last edited by skipjack; May 6th, 2018 at 03:06 PM. 
May 7th, 2018, 04:49 AM  #2 
Math Team Joined: Oct 2011 From: Ottawa Ontario, Canada Posts: 12,764 Thanks: 860 
Seems to me problem would be more "readable" if something like black and white balls were used. I see an interesting reply to this mess(!) here: https://math.stackexchange.com/quest...roblem/2767552 

Tags 
mabinogion, martingale, problem, sheep, stochastic process, stopping time 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Martingale  mathmari  Advanced Statistics  0  May 21st, 2013 10:23 AM 
Lions and Sheep  PrayForStan  Number Theory  14  November 28th, 2012 05:49 AM 
Martingale System  Observed Results Problem  samloomis  Algebra  5  June 10th, 2011 12:20 PM 
Martingale Problem  j_bloggs  Advanced Statistics  0  March 15th, 2010 12:35 AM 