2
$\begingroup$

The book asks the question:

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 ?

  • 0
    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}$.2012-04-13
  • 0
    @joriki - I didn't know that, thanks!2012-04-13
  • 0
    @joriki - this is a part of the question, not my summary2012-04-13
  • 0
    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.2012-04-13

1 Answers 1

5

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.

  • 0
    What is the problem with my reasoning ?2012-04-13
  • 0
    @Belgi: There are two parts to a proof by induction; you provided only one of them.2012-04-13
  • 0
    The base case is for $k=1,2$, but it's easy to check them..but why is the $0.5$ wrong ?2012-04-13
  • 0
    @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.2012-04-13
  • 0
    @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$.2012-04-13
  • 0
    Yes, you are right. thank you for your time and help!2012-04-13
  • 0
    "A bag contains a white and b black balls" meaning $a,b$ are positive integers. (Indeed the case a=b=0 is wrong). for k=1 but not a=b=0 - if you assume that in probability 0.5 the ball is white and with probability 0.5 the ball is black the claim is still true.2012-04-13
  • 0
    @Belgi: a) As I said, italicizing $a$ is particularly important since it looks like an indefinite article the way you're writing it. b) In general mathematical usage, "a bag contains $a$ white balls" doesn't imply that $a$ is positive. Unless the book states such an assumption in general somewhere else, I would consider it an error, at least an unfortunate ambiguity not to state that assumption. c) There's nothing in the statement about $a$ and $b$ having random values. The randomness is in the drawing, and $a$ and $b$ have certain values; what you're stating is a completely different problem.2012-04-13
  • 0
    @Belgi: I've edited my answer to provide a complete answer and hopefully clear up some of the confusion. My comment above that you can't use induction on $k$ was also based on your apparent misreading of step $2$; as the updated answer shows, (complete) induction on $k$ works under a correct reading of the problem statement.2012-04-13