Recursive formula to compute the probability the starting player wins

[Kakashi]

Homework Statement

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

Relevant Equations

N/A

Let X be the random variable denoting the number of turns to win the game. X can take the numerical values from 1 to n. The probabilities assigned to the numerical value of the random variable are

$$ P(X=1)= \frac{m}{m+n} $$.
$$ P(X=2)=\frac{m}{m+n-1} $$
$$ P(X=3)=\frac{m}{m+n-2} $$
..
$$ P(X=n)=\frac{m}{m+n-n}=\frac{m}{m}=1 $$

The odd numerical values of X correspond to the events the starting player wins. The recursive formula taking the difference in probabilities of some odd numerical value to realize the pattern

$$ P(X=2k+1)=P(X=k)+\frac{2m}{(m+n-(k-1))(m+n-(k+1))} $$
Where k is odd

 

[PeroK]

Homework Statement: Two players take turns removing a ball from a jar that initially contains m white and n black balls. The first player to remove a white ball wins. Develop a recursive formula that allows the convenient computation of the probability that starting player wins.
Relevant Equations: N/A

Let X be the random variable denoting the number of turns to win the game. X can take the numerical values from 1 to n. The probabilities assigned to the numerical value of the random variable are

$$ P(X=1)= \frac{m}{m+n} $$.
$$ P(X=2)=\frac{m}{m+n-1} $$

For $X = 2$ you also need that the game was not won on the first turn.

 

[Kakashi]

For $X = 2$ you also need that the game was not won on the first turn.

Conditioning on this event the probability of winning on turn 2 given that the game was not won on the first turn is $$ P(X=2)= \frac{n}{m+n} \frac{m}{m+n-1} $$
$$ P(X=3)=\frac{n}{m+n}\frac{n-1}{m+n-1}\frac{m}{m+n-2} $$
If we generalize this argument $$ P(X=k)=P(X=k-1)\frac{n-k+2}{m+n-k+1} $$

 

[PeroK]

I think they want the probability that the first player wins. So, you still have some work to do. That said, it's not clear whether they want some sort of recursion on $m$ and $n$.

 

[Kakashi]

The recursive probability derived gives the probabilty the game ends on turn k and its valid when k>=2. The first player wins if the game ends when X is odd.

$$P(\text{First player wins}) =\sum_{i=0}^{\frac{n}{2}} P(X=2i+1) $$
Since the game ends after all black balls are exhausted.
$$ 2i+1 \leq n+1 $$
$$ i \leq n/2 $$

 

[PeroK]

The recursive probability derived gives the probabilty the game ends on turn k and its valid when k>=2. The first player wins if the game ends when X is odd.

$$P(\text{First player wins}) =\sum_{i=0}^{\frac{n}{2}} P(X=2i+1) $$
Since the game ends after all black balls are exhausted.
$$ 2i+1 \leq n+1 $$
$$ i \leq n/2 $$

That's not an answer. I think what they are looking for is a recursion based on $m, n$.

Let $p(m, n)$ be the probability the first player wins a game with $m$ white and $n$ black balls. Then:
$$p(m, n) = p(W) + p(B)(1- p(m, n-1))$$Where $p(W), p(B)$ is the probablity the first player draws a white or black ball. And, $p(m, n-1)$ is the probably the second player wins, given that the first player drew a black ball.

That gives you a recursion starting from $p(m, 1)$ and calculating $p(m, 2)$ etc.

 

[Kakashi]

Does $$ (1-p(m,n-1)) $$ correspond to the sum of the probabilities that the first player wins odd numbered future turns conditioned on the fact that the first draw was black?

 

[PeroK]

Does $$ (1-p(m,n-1)) $$ correspond to the sum of the probabilities that the first player wins odd numbered future turns conditioned on the fact that the first draw was black?

Yes, if you play a game with $m$ white balls and $n-1$ black balls, then $p(m, n-1)$ is the probability that the first player wins the game.

The recursive formula in post #6 relates the probability in the $m, n$ game to the probability in the $m, n-1$ game.

This is a useful idea in this type of problem. Here's another example:

Suppose two players take turns tossing a coin and the first to throw a Head wins. You can calculate the probability that the first player wins the game using the sum of an infinite series. But, you can also calculate it from a recursive argument. Let $p$ be the probability that the first player wins, then:
$$p = \frac 1 2 + \frac 1 2(1-p)$$You should try to understand the logic here and check that it gives the right answer.