Consider an urn with $b$ black and $r$ red balls. In each step we randomly choose a ball. Then we put it back in and put $c$ balls of the same color in the urn. Let us denote $B_m$ as the event that $m^{\text{th}}$ draw has resulted in black. Then $$\Pr(B_m\cap B_n)=\frac{b(b+c)}{(b+r)(b+r+c)},\forall m \text{ such that }\;m<n$$
How to do this? I tried induction. For $m=1$ this is trivial. Now let us assume it to be true for some $m$. How to extend it to $m+1$? Can someone help? Some other solution is also welcomed. I think induction is not the best way. I think it all depends on breaking it into two disjoint events and use conditional probability. But I just can't do it. Thanks.
[Math] Polya urn scheme probability calculation
probability
Best Answer
Firstly, $$P(B_m \cap B_n) = P(B_n \mid B_m)\,P(B_m).$$
Now use induction to establish the value of each factor on the RHS.
Our first claim is that for all $m \geq 1$: $$P(B_m) = \dfrac{b}{b+r}$$
Initial case, $m=1$: $$P(B_1) = \dfrac{b}{b+r}$$ is obviously true since there are $b$ chances to choose a black ball out of $b+r$ balls.
Now assume the claim is true for $m=k$ for some $k \geq 1$. Then, conditioning on $B_1$,
\begin{eqnarray*} P(B_{k+1}) &=& P(B_{k+1} \mid B_1)\,P(B_1) \,+\, P(B_{k+1} \mid B_1^c)\,P(B_1^c). \end{eqnarray*}
Now, \begin{eqnarray*} P(B_{k+1} \mid B_1) &=& P(B_k) \qquad\mbox{starting with $b+c$ black and $r$ red balls} \\ &=& \dfrac{b+c}{b+r+c} \qquad\mbox{by inductive assumption.} \end{eqnarray*}
Also, \begin{eqnarray*} P(B_{k+1} \mid B_1^c) &=& P(B_k) \qquad\mbox{starting with $b$ black and $r+c$ red balls} \\ &=& \dfrac{b}{b+r+c} \qquad\mbox{by inductive assumption.} \end{eqnarray*}
Therefore, we have,
\begin{eqnarray*} P(B_{k+1}) &=& \dfrac{b+c}{b+r+c} \dfrac{b}{b+r} + \dfrac{b}{b+r+c} \dfrac{r}{b+r} \\ &=& \dfrac{b}{b+r}. \end{eqnarray*}
This proves the case for $m=k+1$ and the inductive proof of the first claim is done.
Our second claim is that for all $n \gt 1$ and $m: 1 \leq m < n$: $$P(B_n \mid B_m) = \dfrac{b+c}{b+r+c}.$$
We use induction on $m$. Initial case is for any $n \gt 1$ and with $m=1$: In proving the first claim we have already shown that $$P(B_n \mid B_1) = \dfrac{b+c}{b+r+c}.$$
Now assume that our second claim is true for any $n \gt 1$ and some $k: 1 \leq k < n$. Conditioning on $B_1$,
$$P(B_n \mid B_{k+1}) = P(B_n \mid B_1 \cap B_{k+1})\,P(B_1 \mid B_{k+1}) \,+\, P(B_n \mid B_1^c \cap B_{k+1})\,P(B_1^c \mid B_{k+1}).$$
Evaluating the four probabilities on the RHS, \begin{eqnarray*} P(B_n \mid B_1 \cap B_{k+1}) &=& P(B_{n-1} \mid B_k) \qquad\mbox{starting with $b+c$ black and $r$ red balls} \\ &=& \dfrac{b+2c}{b+r+2c} \qquad\mbox{by inductive assumption.} \end{eqnarray*}
$\\$ \begin{eqnarray*} P(B_n \mid B_1^c \cap B_{k+1}) &=& P(B_{n-1} \mid B_k) \qquad\mbox{starting with $b$ black and $r+c$ red balls} \\ &=& \dfrac{b+c}{b+r+2c} \qquad\mbox{by inductive assumption.} \end{eqnarray*}
$\\$ \begin{eqnarray*} P(B_1 \mid B_{k+1}) &=& \dfrac{P(B_{k+1} \mid B_1) P(B_1)}{P(B_{k+1})} \\ && \\ &=& \dfrac{b+c}{b+r+c} \dfrac{b}{b+r} \bigg/ \dfrac{b}{b+r} \\ && \qquad\mbox{first factor is by our initial case, the second and third terms by our first claim} \\ && \\ &=& \dfrac{b+c}{b+r+c}. \end{eqnarray*}
$\\$ \begin{eqnarray*} P(B_1^c \mid B_{k+1}) &=& \dfrac{P(B_{k+1} \mid B_1^c) P(B_1^c)}{P(B_{k+1})} \\ && \\ &=& \dfrac{b}{b+r+c} \dfrac{r}{b+r} \bigg/ \dfrac{b}{b+r} \\ && \qquad\mbox{by similar reasoning as previously} \\ && \\ &=& \dfrac{r}{b+r+c}. && \end{eqnarray*}
$\\$ $\\$
Putting these together, we have,
\begin{eqnarray*} P(B_n \mid B_{k+1}) &=& \dfrac{b+2c}{b+r+2c} \dfrac{b+c}{b+r+c} + \dfrac{b+c}{b+r+2c} \dfrac{r}{b+r+c} \\ && \\ &=& \dfrac{b+c}{b+r+c}. \end{eqnarray*}
Thus the claim is true for $m=k+1$ and our induction is complete for our second claim.
Therefore, as required, we have $$P(B_m \cap B_n) = P(B_n \mid B_m)P(B_m) = \dfrac{b(b+c)}{(b+r)(b+r+c)}.$$