The urn contains $1$ white ball and $1$ black ball. We make a sequence of $n$ draws according to the following scheme: we draw a ball, look at it, then return it to the urn and add another ball of the same color. For $j \in \{ 1, 2, . . . , n + 1 \}$, let $p_j$ denote the probability that after $n$ draws the urn contains exactly $j$ white balls. Prove that $p_j = \frac{1}{n + 1}$ for all $j$.
I came up with a recoursive equation describing the number of white balls after n draws.
- $\mathbb{P}_1(j,n) =$ probability that after $n$ draws we have $j$ white balls in the urn,
- $\mathbb{P}_2(b, n-1) =$ probability, that after $n-1$ draws we will draw a black ball from the urn.
The equation goes like this:
$$\mathbb{P}_1(j,n) = \mathbb{P}_2(b, n-1) \cdot \mathbb{P}_1(j,n-1) + \mathbb{P}_2(w, n-1) \cdot \mathbb{P}_1(j-1,n-1)$$
$$\mathbb{P}_1(j,n) = \frac{n-1+2-j}{n-1+2} \mathbb{P}_1(j,n-1) + \frac{j-1}{n-1+2} \mathbb{P}_1(j-1,n-1)$$
$$\mathbb{P}(j,n)_1 = \frac{n-j+1}{n+1} \mathbb{P}_1(j,n-1) + \frac{j-1}{n+1} \mathbb{P}_1(j-1,n-1)$$
Now I would like to substitute the assumed formula: $\mathbb{P}_1(j,n) = \frac{1}{n + 1}$ and check the result, but I can't since we have $\mathbb{P}_1(j-1,n-1)$ in the equation and I don't know how to evaluate that.
Anybody knows how to do that?
Best Answer
There are basically two approaches to solve your problem. One approach is to formulate a $2D$ recursion. It is very tedious to solve it that way. I'll share another solution, which simplifies it and helps in appreciating the problem on a deeper level.
For any $j \in \{ 1, 2, . . . , n + 1 \}$, for any permutation $\pi$ of W and B balls to achieve $j$ number of white balls, denote $P(j, \pi)$ = Probability of the urn containing $j$ white balls by the permutation $\pi$, where $\pi$ is a permutation of $W$ and $B$ of size $n$ having $(j-1)$ number of $W's$ and $(n - j + 1)$ number of $B's$ .
Claim$1$: $P(j ,\pi)$ is independent of $\pi$
Consider $n = 100$, $j = 5$. Let's calculate $P(5, \pi_1)$ where $\pi_1 = WWWWBBBBB....B$. $$P(5, \pi_1) = \frac12 \cdot \frac23 \cdot \frac34 \cdot \frac45 \cdot \frac16 \cdot \frac27 \cdot \frac38 \cdot \frac49 \cdot ... \cdot \frac{96}{101} = \frac{4! \cdot 96!}{101!} = \big({101} \cdot {100 \choose 4}\big)^{-1}$$
Calculate $P(5, \pi)$ for any other possible $\pi$ leading to $j = 5$, notice that the only thing that varies is the order in which the numbers occur in the numerator. This argument can be extended to any $j$. Thus $$P(j,\pi_1) = P(j, \pi_2) = ... = P(j, \pi_k) = \big((n+1)\cdot{n \choose j - 1} \big)^{-1}$$
Claim$2$: $P(j)$ is independent of $j$, in particular, $P(j) = \frac{1}{n + 1}$
Consider the same example as in Claim$1$. How many different $\pi_i's$ are possible for $n = 100, j = 5$? It is of course, the number of ways to choose $4$ objects from $100$, i.e. $100 \choose 4$. From Claim$1$ each of these is equally likely. Hence, for $n = 100, P(5) = {100 \choose 4} \cdot \big({101} \cdot {100 \choose 4}\big)^{-1} = \frac{1}{101}$.
Generalising, the number of different $\pi_i's$ for $n, j = {n \choose j - 1}$, each of which is equally likely by Claim$1$, hence:
$$P(j) = {n \choose j-1 } \cdot P(j, \pi_i)$$ $$=> P(j) = {n \choose j-1 } \cdot \big((n+1)\cdot{n \choose j - 1} \big)^{-1}$$
$$=>\boxed{ P(j) = \frac{1}{n + 1}}$$