# Polya's urn scheme from Feller Volume 1

(Feller Volume 1, (5.8.20)) Prove by induction: for any $$m < n$$ the probabilities that the $$m$$th and the $$n$$th drawings produce (black, black) or (black, red) are $$\frac{b(b+c)}{(b+r)(b+r+c)}$$, $$\frac{br}{(b+r)(b+r+c)}$$, respectively. Generalize to more than two drawings.

(Polya's urn scheme) Initially, there are $$b+r$$ balls in the urn. $$b$$ denotes the number of black balls and $$r$$ denotes the number of red balls. This implies that at the first stage, the probability to pick a black ball in the urn is $$\frac{b}{b+r}$$. If the player picks a black ball at the previous stage, then $$c$$ black balls are added to the urn. The case for red balls is the same, and this process is continued.

Let $$B_n$$ be the event that the player picks a black ball at the $$n$$th stage, and $$R_n$$ (red ball) is defined in a similar manner. In the previous exercise, I have proved that $$P(B_n) = b/(b+r)$$ for all $$n$$. Now, I need to compute $$P(B_m \cap B_n)$$ and $$P(B_m \cap R_n)$$ for $$m < n$$.

I am going to show $$P(B_m \cap B_n) = \frac{b(b+c)}{(b+r)(b+r+c)}$$ first. When $$n = m+1$$, $$P(B_m \cap B_{m+1}) = P(B_{m+1} | B_m) P(B_m)$$, and it can be easily shown. Suppose that $$P(B_m \cap B_{m+k}) = \frac{b(b+c)}{(b+r)(b+r+c)}$$. Now, consider $$n = m+k+1$$. We have that $$P(B_{m} \cap B_{m+k+1}) = P(B_{m+k+1} | B_m) P(B_m)$$. We know that $$P(B_m) = b/ (b+r)$$, but I am not sure how to calculate $$P(B_{m+k+1} | B_m)$$. I also know that $$P(B_{m+k+1} | B_{m+1} ) = \frac{b+c}{b+r+c}$$ by the induction hypothesis.

Any help would be appreciated.

Notice that if the formula on $$P(B_m \cap B_n)$$, we would completely determine $$P(B_m \cap R_n)$$ since $$P(B_m \cap B_n) + P(B_m \cap R_n)=P(B_m)$$.

\begin{align} &P(B_m \cap B_{m+k+1})\\&=P(B_{m+k+1} | R_{m+k}, B_m)P(R_{m+k}|B_m)P(B_m) \\&+P(B_{m+k+1} | B_{m+k}, B_m)P(B_{m+k}|B_m)P(B_m) \end{align}

Let's compute the individual terms.

$$P(B_m) = \frac{b}{b+r}.$$

Also, by induction hypothesis,

$$P(R_{m+k}|B_m)=\frac{P(R_{m+k} \cap B_m)}{P(B_m)} = \frac{\frac{br}{(b+r)(b+r+c)}}{\frac{b}{b+r}}=\frac{r}{b+r+c}.$$

We drew a black ball at round $$m$$, also, we know that at round $$m+k$$, there are a total of $$b+r+(m+k-1)c$$ balls, of which $$\frac{r}{b+r+c}\cdot [b+r+(m+k-1)c]$$ of them are red and hence $$\frac{b+c}{b+r+c}\cdot [b+r+(m+k-1)c]$$ of them are blue.

At round $$m+k+1$$, there are a total of $$b+r+(m+k)c$$ balls, the number of blue ball didn't increase if we previously draw a red ball. Hence, we have

$$P(B_{m+k+1}|R_{m+k}, B_m )=\frac{\left( \frac{b+c}{b+r+c}\right) [b+r+(m+k-1)c]}{b+r+(m+k)c}$$

We have $$P(B_{m+k}|B_m)=\frac{b+c}{b+r+c}$$

We drew a black ball at round $$m$$, also, we know that at round $$m+k$$, there are a total of $$b+r+(m+k-1)c$$ balls, of which $$\frac{r}{b+r+c}\cdot [b+r+(m+k-1)c]$$ of them are red and hence $$\frac{b+c}{b+r+c}\cdot [b+r+(m+k-1)c]$$ of them are blue.

At round $$m+k+1$$, there are a total of $$b+r+(m+k)c$$ balls, the number of blue ball increased by $$c$$ if we previously draw a red ball. Hence, we have

$$P(B_{m+k+1}|B_{m+k}, B_m )=\frac{\left( \frac{b+c}{b+r+c}\right) [b+r+(m+k-1)c]+c}{b+r+(m+k)c}$$

Now, we have each individual term and we just have to substitute them back to compute $$P(B_m \cap B_{m+k+1})$$.

\begin{align} &P(B_m \cap B_{m+k+1})\\ &=\frac{\left( \frac{b+c}{b+r+c}\right) [b+r+(m+k-1)c]}{b+r+(m+k)c} \cdot \frac{r}{b+r+c} \cdot \frac{b}{b+r}\\ &+ \frac{\left( \frac{b+c}{b+r+c}\right) [b+r+(m+k-1)c]+c}{b+r+(m+k)c} \cdot \frac{b+c}{b+r+c} \cdot \frac{b}{b+r}\\ &= \left(\frac{b(b+c)}{(b+r)(b+r+c)^2(b+r+(m+k)c)} \right)\cdot\\& \left((b+r+(m+k-1)c )r+(b+r+(m+k-1)c )(b+c) + c(b+r+c)\right) \\ &= \left(\frac{b(b+c)}{(b+r)(b+r+c)(b+r+(m+k)c)} \right)\cdot \left(b+r+(m+k-1)c + c\right) \\ &= \frac{b(b+c)}{(b+r)(b+r+c)} \end{align}