Pólya’s Urn, but No Induction

Question

Recall Pólya’s Urn: Initially there is 1 red and 1 blue ball in an urn. In each step, we select a ball from the urn uniformly at random, and then put it back together with a new ball of the same color. Therefore after n steps, there are n + 2 balls in the urn. Suppose that after n steps there are r + 1 red and b + 1 blue balls, where r + b = n. Show that $\frac{r}{(r + b)}$ is the conditional probability that a red ball was selected in the first step. Fully justify your answer.

Hint: Let $C_1$ be the color of the first ball selected. Let $R_n$ the number of red balls after n steps. Explain why $$P(R_n = r+1|C_1 = R) = 2\binom{n-1}{r-1}\frac{r!b!}{(n+1)!}$$ and $$ P(R_n = r+1|C_1 = B) = \frac{b}{r}P(R_n = r+1|C_1 = R)$$

I'm familiar with normal urn and red/blue ball problems, but this one has me confused in a few ways...Where did the equations in the "hint" come from? How do the hint equations for the $C_1$ case help lead us to finding $\frac{r}{(r + b)}$ is the conditional probability? The problem is also asking me to "argue directly" rather than use induction. And then "apply Bayes Rule." Any help or direction with this problem would be very much appreciated!

Answer 1

Some direction:

For the first equation in the hint, you are given that at step $1$ you pick and add a red ball. You need the probability that, in the remaining $n-1$ steps, you will pick and add exactly $r-1$ red balls. First you need to choose which $r-1$ steps will be red; then you need to find the probability of picking that exact situation.

For the second equation in the hint, calculate using the same method, then relate it to $P(R_n=r+1|C_1=R)$.

Once you have the relation in the second equation, forget about the first equation, and now apply Bayes' Rule to calculate $P(C_1=R|R_n=r+1)$. You'll see that the $P(R_n=r+1|C_1=R)$ terms cancel.

Good luck!

Answer 2

@BallBoy already fully answered your question, but here is a (IMHO) more interesting proof.

Consider a specific sequence of draws to get to $(r+1, b+1)$ final state, e.g. $(C_1, C_2, C_3, \dots) = (R, B, R, \dots)$ etc. Can you prove that (somewhat surprisingly) each such sequence is equally likely?

Once you prove that, the problem becomes: you have $r$ red balls and $b$ blue balls and randomly line them up. What is the probability the first ball is red? Clearly the answer is just ${r \over r+b}$.