# How do I solve this probability problem of randomly drawing balls from a urn?

In an urn there are $a$ azure balls and $c$ carmine balls, $ac\ne0$. To begin with, you randomly pick a ball, throw it away, and then each time you randomly pick a ball, if it has the same color with its predecessor, throw it away, otherwise put it back. Then what's the probability that the last one thrown from the urn is azure?

For instance, a possible round:

draw    urn
----------------
AAACCCCC
A       AACCCCC
C       AACCCCC
C       AACCCC
C       AACCC
A       AACCC
C       AACCC
A       AACCC
C       AACCC
C       AACC
C       AAC
C       AA
A       AA
A       A
A       -


In this round, the last one thrown is an azure ball.

-
+1 for azure and carmine :-) –  joriki Sep 24 '12 at 9:56
Repeating a tag in the title is redundant since the tags appear wherever the title appears. The tags indicate the general field of the question, and the title should more specifically summarize the question, e.g. "discarding balls with repeated colours while drawing from an urn" –  joriki Sep 24 '12 at 10:02
I think the drawing procedure of the balls is irrelevant. All that matters is how many of each type you have at the beginning. Thus the probability of the last ball being azure will be $n_a/n$ or $3/8$ for a starting configuration like in your example. –  Raskolnikov Sep 24 '12 at 10:59
@Raskolnikov: Not true IMHO, try simulate it with poker cards, you'll find that even if you begin with 10 azure and 1 carmine, it's not that easy for the last one to be azure. –  Voldemort Sep 24 '12 at 15:58
That's what I did, I simulated it. But apparantly, I have made a mistake in my first attempt because I'm trying again now and obtaining a different result. So forget my earlier comment. –  Raskolnikov Sep 24 '12 at 16:38

As Chris wrote in a comment, the colour of the previously discarded ball must be included in the state. So denote the probability that the last of $a$ azure balls and $c$ carmine balls that gets discarded is azure by $A(a,c)$ if the previously discarded ball was azure, and by $C(a,c)$ if it was carmine. Then

$$A(a,c)=\frac a{a+c}A(a-1,c)+\frac c{a+c}C(a,c)$$

and

$$C(a,c)=\frac a{a+c}A(a,c)+\frac c{a+c}C(a,c-1)\;.$$

Substituting these equations into each other leads to the recurrences

$$A(a,c)=\frac a{a+c}A(a-1,c)+\frac c{a+c}\left(\frac a{a+c}A(a,c)+\frac c{a+c}C(a,c-1)\right)$$

and

$$C(a,c)=\frac a{a+c}\left(\frac a{a+c}A(a-1,c)+\frac c{a+c}C(a,c)\right)+\frac c{a+c}C(a,c-1)\;,$$

which simplify to

$$(a^2+ac+c^2)A(a,c)=(a^2+ac)A(a-1,c)+c^2C(a,c-1)$$

and

$$(a^2+ac+c^2)C(a,c)=a^2A(a-1,c)+(ac+c^2)C(a,c-1)\;,$$

respectively.

The initial conditions are $A(a,1)=1$, $C(1,c)=0$, $A(0,c)=0$ for $c\gt1$ and $C(a,0)=1$ for $a\gt1$.

I don't currently see how to solve this in closed form; I'll compute some values, check OEIS and think about asymptotics when I have more time later on.

-
I don't agree that $A(a,1)=1$. Consider $A(1,1)$. If we pick an azure ball (probability 1/2) then the last ball we throw away will be carmine with probability 1, contradicting $A(a,1)=1$. I think $A(1,1)=1/3$ and $C(1,1)=2/3$. –  Chris Taylor Sep 24 '12 at 13:52
@Chris: You seem to be making an additional assumption that the last ball left in the urn also gets discarded. The question doesn't say that; it only specifies that balls that repeat the previous colour get discarded. –  joriki Sep 24 '12 at 14:01
My interpretation is as follows: Say there is 1 ball of each color. Eventually we will draw two of the same color in a row (wlog say it's $a$). Now the urn has a single $c$ in it. The next draw will be $c$, so we don't discard the ball. The draw after that will also be $c$, so we discard it (because it has the same color as the previous ball - obviously, since it's the same ball) and that is the last ball discarded. In short, I agree with your answer given your interpretation, but I disagree with your interpretation! –  Chris Taylor Sep 24 '12 at 14:29
Chris' interpretation is correct. If there's a ball in the urn, you have to keep drawing. –  Voldemort Sep 24 '12 at 15:51

This is exercise 1.8.25 from Probability and Random Processes by Grimmett and Stirzaker. The answer is 1/2 and can be shown to be true by induction.

-