Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

up vote 1 down vote accepted

( 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

share|improve this answer
    
Your hint was more than enought, thanks! –  user100106 Aug 25 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 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 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).$$

share|improve this answer
    
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 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 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 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 at 8:30
1  
@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 at 17:20

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.