I'm thinking about this competitive programming problem, which was on a contest 3 years ago (link):
We have a bag containing A gold coins and B silver coins, where A, B < 100.
Until the bag contains 100 coins of the same color, we will repeat the following operation:
Operation: Randomly take out one coin from the bag. (Every coin has an equal probability of being chosen.) Then, put back into the bag two coins of the same kind as the removed coin.
We want to find the expected value of the number of times the operation is done. Find the recurrence formula of the expected value.
According to the official commentary, the solution is $$ f(a, b) = \frac{a}{a + b} (f(a + 1, b) + 1) + \frac{b}{a + b} (f(a, b + 1) + 1) $$
but why is this formula correct?
Intuitively it looks (just looks) natural, but I don't know how to prove it.
More formally, let $Y_{a,b}$ be a random variable for the number of rounds if we start with $a,b$ gold balls/silver balls respectively. Let $X$ be the outcome of the first draw. Then $Y_{a,b} = 1+Y_{a+1, b}$ if the first coin is gold, and $Y_{a,b}=1+Y_{a, b+1}$ if the first coin is silver. Then
$$\mathbb{E}(Y_{a,b}) = \mathbb{E}(Y_{a,b}|X=Gold)\Pr[X=Gold] + \mathbb{E}(Y_{a,b}|X=Silver)\Pr[X=Silver] $$ $$= \mathbb{E}(1+Y_{a+1,b}|X=Gold)\Pr[X=Gold] + \mathbb{E}(1+Y_{a,b+1}|X=Silver)\Pr[X=Silver]$$ $$=\mathbb{E}(1+Y_{a+1,b})\Pr[X=Gold] + \mathbb{E}(1+Y_{a,b+1})\Pr[X=Silver]$$ $$=\frac{a}{a+b}\mathbb{E}(1+Y_{a+1,b}) + \frac{b}{a+b}\mathbb{E}(1+Y_{a,b+1}) $$
Can you take it from here?
Remark: $\mathbb{E}(1+Y_{a+1,b}|X=Gold)=\mathbb{E}(1+Y_{a+1,b})$ because conditioned on the first coin being gold (or silver), it does not affect the later rounds since every time we draw the coin independently.