Polya’s urn scheme from Feller Volume 1

inductionpolya-urn-modelprobability

(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.

Best Answer

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}

Related Question