The following problem is exercise 1.6 in the first edition of Upfal and Mitzenmacher's Probability and Computing.
Consider the following balls-and-bin game. We start with one black
ball and one white ball in a bin. We repeatedly do the following:
choose one ball from the bin uniformly at random, and then put the
ball back in the bin with another ball of the same color. We repeat
until there are n balls in the bin. Show that the number of white
balls is equally likely to be any number between 1 and n –
1.
What is the flaw in the argument below?
My Attempt
Define $E(n, i)$ as the event that there are $i$ white balls when there are $n$ balls in the bin. Then our goal is to show $\Pr(E(n, i)) = \frac{1}{n – 1}$ for all $i \in [n-1]$, and we proceed by induction on $n$. We also define $E_j$ for $j > 2$ as the event that the $j$th ball added to the bin is white (we consider the first two balls added as the initial white and black balls prior to drawing).
Base Case:
Suppose $n = 3$. Then
$$\Pr(E(3, 1)) = \Pr(\bar{E_3}) = \frac{1}{2} = \frac{1}{n-1}$$
and
$$\Pr(E(3, 2)) = \Pr(E_3) = \frac{1}{2} = \frac{1}{n-1}$$
Induction Step:
Assume as our induction hypothesis that $\Pr(E(n-1, i)) = \frac{1}{n-2}$ for all $i \in [n-2]$, and let $n > 3$. Then by the law of total probability,
$$\Pr(E(n, i)) = \Pr(E_n \cap E(n, i)) + \Pr(\bar{E_n} \cap E(n, i))$$
The event "there are $i$ white balls among $n$ balls and the $n$th ball added is white is the same as the event "there are $i-1$ white balls among $n-1$ balls and the $n$th ball added is white". A similar restatement is possible if the $n$th ball is black, thus:
$$= \Pr(E_n \cap E(n – 1, i – 1)) + \Pr(\bar{E_n} \cap E(n – 1, i))$$
Applying Bayes' law:
$$= \Pr(E_n | E(n – 1, i – 1))\Pr(E(n – 1, i – 1)) + \Pr(\bar{E_n} | E(n – 1, i))\Pr(E(n – 1, i))$$
Since the each ball is selected uniformly at random among the balls already in the bin:
$$= \frac{i-1}{n-1}\Pr(E(n – 1, i – 1)) + \frac{n-i}{n – 1}\Pr(E(n – 1, i))$$
Applying the induction hypothesis:
$$= \frac{i-1}{n-1}\frac{1}{n-2} + \frac{n-i}{n – 1}\frac{1}{n-2}$$
$$= \frac{1}{n-2}(\frac{i-1}{n-1} + \frac{n-i}{n – 1})$$
$$= \frac{1}{n-2}$$
To complete the induction I needed to obtain $\Pr(E(n, i)) = \frac{1}{n-1}$ instead, so where did I go wrong in my proof? A simple indication of my mistake without just giving me the full answer to the question would be greatly appreciated.
Best Answer
You miscalculated $\operatorname{Pr}\left(\overline{E_n}\mid E(n-1,i)\right)$ in the displayed line before Applying the induction hypothesis: it should be $\frac{(n-1)-i}{n-1}$, so that you end up with
$$\frac1{n-2}\left(\frac{i-1}{n-1}+\frac{n-1-i}{n-1}\right)=\frac1{n-1}\,.$$