# Pólya's urn scheme, proof using conditional probability and induction

Problem

An urn contains $B$ blue balls and $R$ red balls. Suppose that one extracts successively $n$ balls at random such that when a ball is chosen, it is returned to the urn again along with $c$ extra balls of the same color. For each $n \in \mathbb N$, we define $R_n=\{\text{the n-th ball extracted is red}\}$, and $B_n=\{\text{the n-th ball extracted is blue}\}.$

Prove that $P(R_n)=\dfrac{R}{R+B}$.

I thought of trying to condition the event $R_n$ to another event in order to use induction. For example, if $n=2$, I can express $$P(R_2)=P(R_2|R_1)P(R_1)+P(R_2|B_1)P(B_1)$$$$=\dfrac{R+c}{R+B+c}\dfrac{R}{R+B}+\dfrac{R}{R+B+c}\dfrac{B}{R+B}$$$$=\dfrac{R}{R+B}.$$

Now, suppose the formula is true for $n$, I want to show it is true for $n+1$.

So, $P(R_{n+1}=P(R_{n+1}|R_n)P(R_n)+P(R_{n+1}|B_n)P(B_n)$$=P(R_{n+1}|R_n)P(R_n)+P(R_{n+1}|B_n)(1-P(R_n)$$$$=P(R_{n+1}|R_n)\dfrac{R}{R+B}+P(R_{n+1}|B_n)(1-\dfrac{R}{R+B}).$$ I am having some difficulty trying to calculate$P(R_{n+1}|R_n)$and$P(R_{n+1}|B_n)$. I would appreciate if someone could complete my answer or suggest me how can I finish the proof if what I've done up to now is correct. ## 4 Answers I would actually still advocate the approach suggested here with a small change in the way it is presented: $$P(R_1)=\frac{R}{R+B}$$, now we need to prove that $$P(R_n)=P(R_{n+1})$$. $$P(R_{n+1})=P(R_{n+1}|R_n)P(R_n)+P(R_{n+1}|B_n)(1-P(R_n))$$ $$X_n$$, the number of red balls in the urn at step $$n$$, is $$P(R_n)T_n$$, where $$T_n$$ is the total number of balls on step $$n$$ which is deterministic. $$P(R_{n+1}|R_n)=\frac{T_nP(R_n)+c}{T_n+c}$$ $$P(R_{n+1}|B_n)=\frac{T_nP(R_n)}{T_n+c}$$ $$P(R_{n+1})=\frac{T_nP(R_n)+c}{T_n+c}P(R_n)+\frac{T_nP(R_n)}{T_n+c}(1-P(R_n))=P(R_n)$$. The approach does not use mathematical expectations, it can be considered as an advantage because this problem is often given to students before the study mathematical expectations. The key is to condition by the composition of the urn at time$n$, say$X_n$red balls and$Y_n$blue balls, since $$P(R_{n+1}\mid X_n,Y_n)=Z_n,\qquad Z_n=X_n/(X_n+Y_n).$$ Obviously,$X_0=R$,$Y_0=B$, and, for every$n$, $$X_n+Y_n=R+B+nc,$$ which is deterministic. Conditionally on$(X_n,Y_n)$, one adds$c$red balls with probability$Z_n$and zero otherwise, hence $$E(X_{n+1}\mid X_n,Y_n)=X_n+cZ_n=(X_{n+1}+Y_{n+1})Z_n,$$ which implies $$E(Z_{n+1}\mid X_n,Y_n)=Z_n.$$ In particular, for every$n$, $$P(R_{n+1})=E(Z_n)=Z_0=R/(R+B).$$ • Sorry but I couldn't follow you. What probability is$P(R_{n+1}\mid X_n,Y_n)$? I mean, is the probability of getting a red ball in the$n+1$extraction knowing that...? (What it means$X_n,Y_n$?). Also, I don't understand what the notation$E(...)$stands for. Commented Aug 25, 2014 at 1:31 • Well... X_n and Y_n are defined in the answer (first sentence), P( | ) is conditional probability (you use it in your question) and E( ) is expectation. – Did Commented Aug 25, 2014 at 1:50 • Oh, I think I've misundertood what you've meant with$P(R_{n+1}\mid X_n,Y_n)$, I suppose you mean$P(R_{n+1}\mid X_n)$or$P(R_{n+1}\mid Y_n)$. I haven't seen expectation yet, if it occurs to you how could I complete the solution with my approach, you can add it to your original answer. Commented Aug 25, 2014 at 2:01 • Actually I meant$P(R_{n+1}\mid X_n,Y_n)$hence I wrote$P(R_{n+1}\mid X_n,Y_n)$. – Did Commented Aug 25, 2014 at 8:30 • @user100106 Did is conditioning on {\em both}$X_n$and$Y_n$, i.e. conditioning on the outcome at the end of the$n$th step (which Arturios didn't do, but needed to). As an aside, since$X_n+Y_n=B+R+cn$, conditioning on one or both of$X_n$and$Y_n$gives the same information. Commented Aug 26, 2014 at 17:20 ( After reading the comments bellow and consulting with a teacher I realized that this hint, as well as the link posted bellow, are in essence incorrect if one does not intend to solve the problem using random variables. I will not delete this answer so it can serve for future reference, but the OP should untag this answer since it is not correct) Hint: Suppose that just before the n-th extraction there are$ r_n $red balls and$b_n$blue balls. Then$ P(R_n) = \dfrac{r_n}{r_n + b_n} \ $and$ \ P(R_{n + 1} | R_n) = \dfrac{r_n + c}{r_n + b_n + c} \ $. Similarly you can write down the other probabilities in your sum in terms of$r_n $and$b_n$. Now try to factor out$P(R_n)$and use your inductive hypothesis. If you are still stuck after trying to apply the hint I posted above, this link might be helpful: http://everything2.com/title/Polya+urn+scheme • Your hint was more than enought, thanks! Commented Aug 25, 2014 at 2:29 • The number of balls before the$n$th extraction is random. You will need to condition on the number of balls at step$n$for this approach Commented Aug 25, 2014 at 2:32 • The formula for$P(R_n)$cannot hold (except for$n=0$) since the LHS is a number and the RHS is a (non degenerate) random variable. (Kind of repeating @DPoole's comment since, apparently, it did not go through.) – Did Commented Aug 25, 2014 at 10:17$P(R_1)=\frac{r}{r+b}$and$P(B_1)=\frac{b}{r+b}$Applying theorem of total probability we have : \begin{eqnarray*} P(R_2)&=&P(R_2|R_1)P(R_1)+P(R_2|B_1)P(B_1)\\ &=& \frac{r+1}{r+b+1}\frac{r}{r+b}+\frac{r}{r+b+1}\frac{b}{r+b}\\ &=&\frac{r}{r+b} \end{eqnarray*} Now we prove for$P(R_3)$Again apply theorem of total probability: \begin{eqnarray*} P(R_3)&=&P(R_3|R_1)P(R_1)+P(R_3|B_1)P(B_1) \end{eqnarray*} Now question is what is$P(R_3|R_1)$and$P(R_3|B_1)$? We will show$P(R_3|R_1)=P(R_2|R_1)=\frac{r+1}{r+b+1}$. How? -- It is as follows: Apply theorem of total probability on conditional probability. \begin{eqnarray*} P(R_3|R_1)&=&P(R_3\cap R_2|R_1)+P(R_3\cap B_2|R_1)\\ &=& P(R_3|R_2\cap R_1)P(R_2|R_1) + P(R_3|B_2 \cap R_1)P(B_2|R_1)\\ &=& \frac{r+2}{r+b+2}\frac{r+1}{r+b+1}+\frac{r+1}{r+b+2}\frac{b}{r+b+1}\\ &=&\frac{r+1}{r+b+1} \end{eqnarray*} Same way one can show$P(R_3|B_1)=\frac{r}{r+b+1}$. Now under the induction hypothesis we have :$P(R_{n-1}|R_1)=\frac{r+1}{r+b+1}$and$P(R_{n-1}|B_1)=\frac{r}{r+b+1}\$

Therefore,

\begin{eqnarray*} P(R_{n})&=& P(R_{n-1}| R_1)P(R_1) + P(R_{n-1}| B_1)P(B_1)\\ &=& \frac{r+1}{r+b+1}\frac{r}{r+b}+\frac{r}{r+b+1}\frac{b}{r+b}\\ &=&\frac{r}{r+b} \end{eqnarray*}

This is a classic example of Markov Chain