Pólya's urn is a classic example of reinforced randomness: whenever a particular color comes up, it becomes slightly more likely to come up again. The question is whether that cumulative bias distorts the final distribution or whether, counterintuitively, it ends up not mattering.
The urn bet
Riddle statement
A box starts with 1 red ball and 1 blue ball.
On each turn:
1. A ball is drawn at random;
2. It is returned to the box;
3. a new ball of the same color is added.
After \(n\) turns, there will be \(n+2\) balls in total.
Maria bets that, after \(n\) turns, all possible values for the number of red balls are equally likely. Luis says that the middle values should come up more often.
Who wins the bet? And, more precisely, what is the probability of ending up with exactly \(k\) red balls?
Show solution
Solution
Answer: María is right.
If \(R_n\) is the number of red balls after \(n\) turns, then the possible values are \(1, 2, \dots, n+1\), and they are all equally likely:
Proof by induction.
For \(n=0\) there can only be 1 red ball, so the statement is trivially true.
Suppose that after \(n\) turns the distribution is uniform. We want to calculate \(\mathbb{P}(R_{n+1}=k)\) for \(k=1,2,\dots,n+2\).
This can happen in two ways:
that after \(n\) turns there were \(k-1\) reds and a red is drawn (possible when \(k \geq 2\));
that after \(n\) turns there were \(k\) reds and a blue is drawn (possible when \(k \leq n+1\)).
At the extremes, \(k=1\) only admits the second case and \(k=n+2\) only the first; in both, the subsequent count is the same. Therefore:
Applying the inductive hypothesis—where every term that exists is equal to \(\frac{1}{n+1}\), and out-of-range terms are equal to \(0\)—:
This holds for every \(k=1,2,\dots,n+2\), so the distribution remains uniform at step \(n+1\).
So Maria wins the bet.