\problemdata
{induction}
{random variable}
{distribution}
{Eric Ho, S02}
\begin{problem}
Theory Pig has invented a random number generator using a bunch of red
balls, a bunch of green balls, and a bin.  This is how it works.

Initially, there is a red ball and a green ball in the bin.  Theory pig
randomly removes one ball from the bin, and then puts back into the bin
two balls of the same color as the one removed.  Theory pig repeats this
process until there are exactly $n$ balls in the bin.  Define the random
variable
\[
R_n \eqdef \text{  the number of red balls in the bin at the end.}
\]

Theory Pig observes that $R_n$ is a random variable taking integer values
between 1 and $n-1$.  He claims that $R$ has a uniform distribution.
Prove that he's right.

\solution{

By induction on $n \ge 2$, with induction hypothesis
\[
P(n) \eqdef R_n \text{ has a uniform distribution.}
\]

\textbf{Base case} ($n=2$): $R_2$ only takes the value 1, so is uniform on the
integers from 1 to $2-1$, as required.

\textbf{Inductive step}: Assume the distribution for $n$ balls is uniform.
We need to show that when we add the $(n+1)$st ball into the bin, the
distribution is still uniform.

Assume we have $j$ red balls at the end where $1 \le j \le n$.  This is
possible either when we add a green ball to a bin with $j$ red balls, or
when we add a red ball to a bin with $j-1$ red balls.  From inductive
hypothesis, each outcome in the bin with $n$ balls have a $1/(n-1)$
probability.  The chance that we add a green ball to a bin with $j$ red
balls is $(n-j)/n$, whereas the chance that we add a red ball to a bin
with $j-1$ red balls is $(j-1)/n$. The total is therefore:
\[
(\frac{1}{n-1})(\frac{n-j}{n}) + (\frac{1}{n-1})(\frac{j-1}{n}) =
(\frac{1}{n-1})(\frac{n-1}{n}) = \frac{1}{n}.
\]

Because probability of each outcome is the same, the distribution is uniform. 
}
\end{problem}
