4

Two players take turns removing a ball from a jar that initially contains $w$ white and $b$ black balls. The first player to remove a white ball wins. Develop a recursive formula that allows the convenient computation of the probability that the starting player wins.

Solution: Let $P(b, w)$ be the probability that the starting player wins when the jar initially contains $w$ white and $b$ black balls. We have, using the total probability theorem,

$\Large{\color{red}{[}}$ $P(b, w) = \frac{w}{b + w} + \frac{b}{b + w}[ \, 1 - P(b - 1, w) \,] = 1- \frac{b}{b + w}P(b - 1, w) \, \Large{\color{red}{]}}$.

The probabilities $P(1,w), P(2,w), ..., P(n,w)$ can be calculated sequentially using ths formula, starting with the initial condition $P(0,w) = 1$.

How do you derive the expression inside the red brackets? Since the question postulates the starting player to win, I was thinking: $P(b, w) = P($a white ball is chosen on the 1st turn, or on the 3rd turn, or on the 5th or ...).

Source: P57, 1.21, An Intro to Pr, 2nd Ed, D Bertsekas & J Tsitsiklis

  • It would seem that there is a "$1-{}$" missing after the second equals sign (which is just doing algebra). Also it would seem to have to be $P(0,w)=1$ at the end; in fact $P(b,0)$ is undefined since without white balls nobody can win. – Marc van Leeuwen Nov 19 '13 at 13:36
  • @MarcvanLeeuwen: Thank you for the observation. I fixed the typo for which I apologise. Could you please direct me to the $P(b,0)$ in my OP and edit; I can't seem to see it? –  Nov 19 '13 at 14:55
  • There was no $P(b,0)$ but there was $P(w,0)$. However, the first number is the number of black balls, so if $P(w,0)$ were really meant, it would have been better to call it $P(b,0)$. But in fact the arguments were inverted instead; I've corrected that now. – Marc van Leeuwen Nov 19 '13 at 15:48
  • @MarcvanLeeuwen: Many thanks. –  Nov 20 '13 at 04:18

4 Answers4

5

This formula says:
$I.$ either the starting player (call him $F$) wins in first move $(\frac{w}{b+w})$
$II.$ or $F$ draws a black ball $\frac{b}{b+w}$ AND the second player (label him $S$) has to lose.

In other words, $P(b,w) =$ Pr($F$ picks a white ball) + Pr($F$ picks a black ball)$\times$Pr($S$ loses)

Now, need Pr($S$ loses). Since the question provides only a probability for the winner, and imparts no other information on the loser, thus consider Pr($S$ loses) = $1 - Pr(S$ wins). What's $Pr(S$ wins)?
In case II, $F$ went first and drew a black ball.

Subsequently, at $S$'s turn, $b - 1$ & $w$ remain.
In other words, $S$ (and NOT $F$) is now the starting player in a game that begins with $b-1$ black balls and $w$ white ones !
Thus, $Pr(S$ wins) is exactly $P(b-1, w)$,
because $S$ can now be considered as the starting player in a game that begins with $b-1$ black balls and $w$ white ones.

Thus, Pr($S$ loses) = $1 - P(b-1, w)$.

mm-aops
  • 4,195
  • 1
    Prof van Leeuwen graciously emended my OP so I've edited your post and upvoted. Please let me know of any concerns and whether this edit's OK. I colour in red something I don't register; what was it supposed to be? –  Nov 20 '13 at 04:17
  • yeah, that's precisely what I meant. thanks for the edit, the formatting looks much better now. the 'o' you marked red is just a typo – mm-aops Nov 20 '13 at 12:11
  • You're welcome. Thanks for your response. Upvoted! –  Nov 20 '13 at 13:15
  • @mm-aops but how is that probability calculated that way and there is a probability that the first player draws other black ball after the second player lost also – Mohamed Osama Oct 18 '15 at 21:45
1

I am sure this recursion is just saying that on the first draw either a white ball is drawn by the first player (with probabilty $\frac w{b+w}$), which gives a score $1$ for the first player, or a black ball is drawn (with probabilty $\frac b{b+w}$) after which the game has one fewer black ball (whence the $b-1$), and the roles of the players are inversed, so the probability for the (now) first player to win the new game gives the the probability (under this scenario) for the original first player to loose, whence the subtraction from$~1$ for the second term.

Marc van Leeuwen
  • 115,048
1

Incidentally, the green can be derived intuitively and not algebraically: $\color{green}{P(b, w)} = \frac{w}{b + w} + \frac{b}{b + w}[ \, 1 - P(b - 1, w) \,] \color{green}{= 1- \frac{b}{b + w}P(b - 1, w)} $.

The event that $F$ wins with $b$ black and $w$ white balls = the complement of the event that:
first, $F$ first picks a black ball (so $F$ loses)
after which, with $b-1$ black and $w$ balls remaining,
$S$ picks a white ball out of the $b-1$ black and $w$ white balls (so he wins).

  • Nice explanation, is that question hard and somehow difficult level or it's just me ? – Mohamed Osama Oct 17 '15 at 16:10
  • @MohamedOsama I cannot remember now, sorry, but at least it was NOT intuitive to me. Allow me to return to you if I revisit this. –  Oct 17 '15 at 16:44
0

A way to understand recursive expression is to plug in values starting from base value and see how the expression evolves:

$$\begin{align} &\mathbf{P}(m, 0) = 1 \\ &\mathbf{P}(m, 1) = \frac{m}{m+1} + \frac{1}{m+1}(1-\mathbf{P}(m,0)) = \frac{m}{m+1} + \frac{1}{m+1} \cdot 0 \\ &\mathbf{P}(m, 2) = \frac{m}{m+2} + \frac{2}{m+1} \cdot \frac{1}{m+1} \\ &\ldots \end{align}$$

  • When there is no black ball, probability that starting player wins is $1$

  • When there is $1$ black ball, starting player selects one of the $m$ white balls to win or selects the $1$ black ball so that remaining jar has $0$ black ball and 2nd player will win for sure.

  • When there are $2$ black balls, starting player selects one of the $m$ white balls to win or selects one of the $2$ black balls and the left $1$ black ball in the jar and 2nd play selects that black ball left no black ball in the jar and starting player wins in next turn.

    $\ldots$

To actually derive a recursive expression. One must see the recursive pattern. A general approach is：

  • Starting from special cases and assuming some simple specific values like $\#\text{black balls} = 1, 2, 3$ and write down the expressions.
  • Recognize general and recursive patterns from those expressions
  • Define base case and find rule of the induction by symbolically summarizing the patterns you see from the few special expressions

In a very general sense, the key to solve problems with symbolic tools such as drawing, language or mathematics is to convert the challenge of interpreting real world issues for which human brain was evolved to a challenge of pattern recognition for which symbolic tools were invented.

englealuze
  • 101
  • 3