9
$\begingroup$

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.

$\endgroup$

4 Answers 4

5
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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).$$

$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$
    – user100106
    Commented Aug 25, 2014 at 1:31
  • $\begingroup$ 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. $\endgroup$
    – Did
    Commented Aug 25, 2014 at 1:50
  • $\begingroup$ 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. $\endgroup$
    – user100106
    Commented Aug 25, 2014 at 2:01
  • $\begingroup$ Actually I meant $P(R_{n+1}\mid X_n,Y_n)$ hence I wrote $P(R_{n+1}\mid X_n,Y_n)$. $\endgroup$
    – Did
    Commented Aug 25, 2014 at 8:30
  • 1
    $\begingroup$ @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. $\endgroup$
    – D Poole
    Commented Aug 26, 2014 at 17:20
1
$\begingroup$

( 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

$\endgroup$
3
  • $\begingroup$ Your hint was more than enought, thanks! $\endgroup$
    – user100106
    Commented Aug 25, 2014 at 2:29
  • $\begingroup$ 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 $\endgroup$
    – D Poole
    Commented Aug 25, 2014 at 2:32
  • $\begingroup$ 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.) $\endgroup$
    – Did
    Commented Aug 25, 2014 at 10:17
0
$\begingroup$

$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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .