A famous scenario in probability theory devised by George Polya. You start with an urn with r red and g green balls. At each step, a ball is randomly drawn from the urn and replaced. Then, c balls of the same color as the randomly drawn ball are added to the urn. This process is repeated.
Interestingly, the probability of drawing a red ball at any particular step k is r/(r+g), independent of c or k. Other interesting results follow.
Proof by induction:
- Base case: For n=1, clearly P{R1} = r/(r+g)
- Induction Hypothesis: Assume P{Rn} = r/(r+g)
. Prove: P{Rn+1} = r/(r+g).
- P{Rn+1} = P{Rn+1|Rn}P{Rn} + P{Rn+1|Gn}P{Gn} (easily derivable)
- Before the draw at stage n, there are r + g + (n-1)c balls in the urn, rn red and gn green, where rn + gn = r + g + (n-1)c. It is easily seen that P{Rn} = rn/(rn + gn), P{Gn} = gn/(rn + gn), P{Rn+1|Rn} = (rn + c)/(rn + gn + c), and P{Rn+1|Gn} = rn/(rn + gn + c).
- Combining these results, we have P{Rn+1} = ((rn + c)/(rn + gn + c))*(rn/(rn + gn)) + ((rn)/(rn + gn + c))*(gn/(rn + gn)) = rn/(rn + gn.
- By the above and the induction hypothesis we have P{Rn+1} = P{Rn}/(rn + gn) = r/(r + g).