Probability of winning a turn-based game with a random element

Question

I am preparing for a programming exam on probability theory and I stumbled across a question I can't solve.

Given a bag, which contains some given amount of white stones $w$ and some given amount of black stones $b$, two players take turns drawing stones uniformly at random from the bag. After each player's turn a stone, chosen uniformly at random, vanishes, and only then does the other player take their turn. If a white stone is drawn, the player, who has drawn it, instantly loses and the game ends. If the bag becomes empty, the player, who played second, wins.

What is the overall probability that the player, who played second, wins?

I assume it's a dynamic programming question, though I can't figure out the recursion formula. Any help would be greatly appreciated. :)

Example input: $w$ = 3, $b$ = 4, then the answer is, I believe, 0.4, which I arrived at after computing by hand all possible ways for the game to go, so not very efficient.

Answer 1

Let us denote by $\Pr(w, b)$ the probability of P2 winning given its their turn and there are $w$ white stones and $b$ black stones remaining and similarly we write $\overline\Pr(w, b)$ for the probability of P2 winning given it is P1's turn.

From the rules of the game we get that any of the following cases can occur in P2's turn (assuming that enough stones are left):

1. White is drawn and P2 loses. This happens with probability $w / (w + b)$.
2. Black is drawn and a white stone vanishes. The probability for this is $b / (w + b) \cdot w / (w + b - 1)$.
3. Black is drawn and a black stone vanishes. We find the probability for this to be $b / (w + b) \cdot (b - 1) / ( w + b - 1)$.

If it is P1's turn to play we find similar cases:

1. White is drawn and P2 wins. This happens with probability $w / (w + b)$.
2. Black is drawn and a white stone vanishes. The probability for this is $b / (w + b) \cdot w / (w + b - 1)$.
3. Black is drawn and a black stone vanishes. We find the probability for this to be $b / (w + b) \cdot (b - 1) / ( w + b - 1)$.

We can now factor $\Pr$ and $\overline\Pr$ using our case distinctions and some simple probability theory: $$ \begin{align*} \Pr(w, b) &= \Pr(\text{Case 1.2}) \cdot \overline\Pr(w - 1, b - 1) + \Pr(\text{Case 1.3}) \cdot \overline\Pr(w, b - 2), \\ \overline\Pr(w, b) &= \Pr(\text{Case 2.1}) + \Pr(\text{Case 2.2}) \cdot\Pr(w - 1, b - 1) + \Pr(\text{Case 2.3}) \cdot \Pr(w, b - 2) \end{align*} $$ Note that we can combine these 2 equations to find a recursive formula for $\Pr$ (which I will not type out here for brevity). Coupling these with the initial values $\Pr(w, b)$ where $w + b \leq 4$ (which can be precomputed) will give us an algorithmic way to find the desired probability.