# 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 ( 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! – user100106 Aug 25 '14 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 – D Poole Aug 25 '14 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 Aug 25 '14 at 10:17 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. – user100106 Aug 25 '14 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 Aug 25 '14 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. – user100106 Aug 25 '14 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 Aug 25 '14 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. – D Poole Aug 26 '14 at 17:20 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. -$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

-