# A procedure for sampling from a bag (A question from A First Course In Probability by Ross)

A bag contains $a$ white and $b$ black balls. Balls are chosen from the bag according to the following method:

1. A ball is chosen at random and is discarded.

2. A second ball is then chosen. If its color is different from that of the preceding ball, it is replaced in the bag and the process is repeated from the beginning. If its color is the same, it is discarded and we start from step 2.

In other words, balls are sampled and discarded until a change in color occurs, at which point the last ball is returned to the urn and the process starts anew. Let $P_{a,b}$ denote the probability that the last ball in the bag is white. Prove that $P_{a,b}=0.5$

Hint: Use induction on $k=a+b$.

I tried doing this and got :

Denote the probability that in step 2 the 2 balls were in the same color by $p$, then with probability $p$ we are returning to step 1 with $k-2$ balls and with probability $1-p$ we are returning to step 1 with $k-1$ . From the induction hypothises we get that:

$P_{a,b}=0.5p + 0.5(1-p)=0.5$.

Did I do this right ?

-
Two $\TeX$ comments: a) Variables are of course italicized in general, but it's particularly important for $a$ because it's easy to mistake it for an indefinite article otherwise. b) You had P_a,_b, which produces $P_a,_b$ which looks weird because it's a comma of normal size at normal height between two smaller and lower subscripts -- you can use curly braces to get a compound subscript: P_{a,b} produces $P_{a,b}$. –  joriki Apr 13 '12 at 10:05
@joriki - I didn't know that, thanks! –  Belgi Apr 13 '12 at 10:10
@joriki - this is a part of the question, not my summary –  Belgi Apr 13 '12 at 10:56
Sorry, the previous comment was wrong; I deleted it. I had adopted your misreading of the two-step description. Your reasoning (apart from the fact that it doesn't treat the base cases) seems to assume that step $2$ returns to step $1$ in either case. In fact, it return to step $2$, not to step $1$ in one of the cases. –  joriki Apr 13 '12 at 11:24

No. Hint: Try using any other number instead of $0.5$; the proof will "work" just the same.

[Edit:]

Since the problem is incompletely stated and there was some confusion in the comments due to your apparent misreading of step $2$, here's a complete solution.

Note that step $2$ doesn't return to step $1$ in both cases, as you seem to have assumed; it gets repeated until a different colour is drawn.

We need to add the assumption that $a$ and $b$ are positive; if one of them is zero the probability clearly cannot be $1/2$.

The base case is $k=2$, i.e. $a=b=1$. In this case the probability is $1/2$ by symmetry.

Now assume that the claim holds for all $k'\lt k$. (This is called complete induction or strong induction, as opposed to the form of induction where the claim is only assumed for one value of $k$.) Three different things can happen by the time we return to step $1$. We can exhaust the white balls, we can exhaust the black balls, or we can get a colour change and return the last ball. In the last case, the probability is $1/2$ by the induction hypothesis. Thus, the overall probability is $1/2$ if the two other cases are equally likely. The probability of exhausting the white balls is $1$ in $\binom{a+b}a$, and the probability of exhausting the black balls is $1$ in $\binom{a+b}b$; since these two binomial coefficients are equal, the probabilities of exhausting either colour are indeed the same.

-
What is the problem with my reasoning ? –  Belgi Apr 13 '12 at 10:09
@Belgi: There are two parts to a proof by induction; you provided only one of them. –  joriki Apr 13 '12 at 10:10
The base case is for $k=1,2$, but it's easy to check them..but why is the $0.5$ wrong ? –  Belgi Apr 13 '12 at 10:11
@Belgi: No-one said that the $0.5$ is wrong. Your reasoning was wrong because you supplied an incomplete proof that purported to show that the result is $0.5$ whereas it could in fact have been used to "show" that the result is any number. The fact that it's easy to check the base cases doesn't mean that they're not part of the proof. –  joriki Apr 13 '12 at 10:13
@Belgi: The claim is in fact wrong for $k=1$, and for any case with $a=0$ or $b=0$; obviously the probability cannot be $0.5$ in those cases. There seems to be a missing assumption in the problem statement that $a$ and $b$ are positive integers. That means that you can't actually solve this using only induction over $k$, since you also have to deal with the possibility that you might exhaust one of the colours. You need to treat that as a base case and then use induction on $a$ and $b$. –  joriki Apr 13 '12 at 10:26