Home > Riddles > The urn bet
Pólya's urn is a classic of reinforced chance: when a color comes up, it becomes a little more likely to come up again. What is surprising here is the exact way that bias ends up organizing the final distribution.
An urn starts with 1 red and 1 blue ball. In each turn:
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 of the number of red balls are equally probable. Luis says that core values should come out more often.
Who wins the bet? And, more precisely, what is the probability of ending up with exactly \(k\) red balls?
Answer: Maria 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 equiprobable:
$$ \mathbb{P}(R_n=k)=\frac{1}{n+1} \qquad (k=1,2,\dots,n+1). $$ **Proof by induction.** For $n=0$, there can only be 1 red ball, so the statement is true. Now suppose that after $n$ turns the distribution is uniform. We want to calculate the probability of ending up with $k$ red balls after $n+1$ turns. This can happen in two ways: - that after $n$ turns there would be red $k-1$ and a red one is drawn; - or that after $n$ turns there would be red $k$ and a blue one is drawn. Therefore, $$
\mathbb{P}(R_{n+1}=k)
=
\mathbb{P}(R_n=k-1)\frac{k-1}{n+2}
+
\mathbb{P}(R_n=k)\frac{n+2-k}{n+2}.
$$ Using the inductive hypothesis,
$$ \mathbb{P}(R_n=k-1)=\mathbb{P}(R_n=k)=\frac1{n+1}, $$
so
$$ \mathbb{P}(R_{n+1}=k) = \frac1{n+1}\cdot\frac{k-1}{n+2} + \frac1{n+1}\cdot\frac{n+2-k}{n+2} = \frac1{n+2}. $$ That goes for every $k=1,2,\dots,n+2$. Then, also in step $n+1$, the distribution becomes uniform again. So Maria wins the bet. $$
If you enjoyed this one, try more pure-logic riddles, explore this theme, browse the full archive, or read the riddle-solving guide.