1

An urn contains b blue balls and r red balls, b + r total. Balls are withdrawn one at a time without replacement. What is the probability that at some stage the number of blue and red balls are equal.

I've gotten this far:
Either b >= r or r >= b, w.l.o.g. assume b >= r. Then the solution should be a sum of the probabilities that after 2 balls are drawn exactly one is blue, after 4 balls are drawn exactly 2 are blue,..., after 2r balls are drawn exactly r are blue, as:

(bC1)(rC1)/((b+r)C2) + (bC2)(rC2)/((b+r)C4) + ... + (bCr)(rCr)/((b+r)C2r).

Is my reasoning so far correct? Is there a simpler way to understand this problem? If I am correct, does this sum simplify to anything more familiar or easier to work with?

lumcti
  • 293

3 Answers3

2

There is a difficulty with your formula. The expression $$\frac{\binom{b}{1}\binom{r}{1}}{\binom{b+r}{2}}$$ does correctly find the probability that after $2$ withdrawals the number of blue withdrawn is the same as the number of red withdrawn, and $$\frac{\binom{b}{2}\binom{r}{2}}{\binom{b+r}{4}}$$ does the same thing for $4$ withdrawals. However, the two events are not disjoint.

André Nicolas
  • 507,029
1

Instead of that scary sum of ratios of binomial coefficients:

The total number of distinguishable states of the urn is $(b+1)(r+1)$, and this is also the total number of states outside of the urn! The reason for adding $1$ to each factor is that It's possible to have $0$ balls of each color in the urn.
For example if $b=3, r=2$ the states are: $$(3,2),(3,1),(3,0),(2,2),(2,1),(2,0),(1,2),(1,1),(1,0),(0,2),(0,1),(0,0)$$ $$(3+1)(2+1)=12 \space total$$
You want to preserve the difference between the red and blue balls in the urn after any withdraw (This corresponds to having equal number of red and blue balls in your hand):
$$b_n-r_n=b-r$$ The number of states of the urn that correspond to this is $\min{(b,r)}+1$.
For example if $b=3, r=2$: $\space b-r=1$ and the states are:
$$(3,2),(2,1),(1,0)$$ $$\min{(3,2)}+1=2+1=3 \space total$$
Assuming $b \geq r$: $$P=\frac{\min{(b,r)}+1}{(b+1)(r+1)}=\frac{r+1}{(b+1)(r+1)}=\frac{1}{b+1}$$ And generally: $$P=\frac{1}{\max{(b,r)}+1}$$

user76568
  • 4,542
  • Thank you for your answer, but please elaborate. I think I understand what you mean by total distinguishable states, but how do you derive (b + 1)(r + 1) as the number of distinguishable states? And how is r + 1 the number of states that preserve the difference between blue and red balls? – lumcti Feb 07 '14 at 17:02
  • @lumcti your right I did not explain it enough. Editing the question now – user76568 Feb 07 '14 at 17:04
  • @lumcti I did not really derive most of what I'm postulating, because It's common sense. Do note it is easy to derive all of it. Try it. :-) – user76568 Feb 07 '14 at 17:25
  • @AndréNicolas I'd be happy to hear criticism about this answer from you, if you want. – user76568 Feb 07 '14 at 17:28
  • It is the other way around: The number of blue and red balls remaining are equal. – vonbrand Feb 07 '14 at 17:29
  • @vonbrand what? Can you explain a bit more? – user76568 Feb 07 '14 at 17:31
1

Original Poster: You are double counting (i.e. there will be occasions when you have exactly 1 red after drawing 2 and have exactly 2 reds after drawing 4)

The answer is $2\min(b,r)/b+r$.

Without loss of generality, suppose that $b\ge r$, and write $b=r+k$.

I will show that the probability that the number of blues is always more than the number of reds is $\frac{k}{b+r}$, meaning the probability that they are sometimes equal is $\frac{b+r-k}{b+r}=\frac{2r}{b+r}$.

Indeed, I will show more - I will show that if you put $b$ blue balls and $r$ red balls around a circle in any order you choose, then there are exactly $k$ balls you could choose such that starting with that ball and reading clockwise the number of blues always exceeds the number of reds.

Choose any ball. Have a counter that starts at 0. Starting at ball X and continuing clockwise for ever, increment the counter if the ball is blue, and decrement if it is 1.

After you have gone round N times, where N is any positive integer, your counter will be at kN, it will never have been smaller than -r, and thereafter it will never be smaller than kN-r. Therefore there are at least kN-r and at most kN-r times that the counter has been at a value it will {\em never be at again}. Note the counter is at a value it will never be at again if (and only if) the ball you are pointing at is a starting point where the number of blues always exceeds the number of reds. Thus, if there are z such balls, $kN-r\le zr\le kN+r$. Dividing by $N$ gives $k-\frac rN\le z\le k+\frac rN$. Now, letting $N$ tend to infinity shows that $z=k$.

Thus there are $k$ possible starting points. So if you choose any random starting point, it will lead to the number of blues always exceeding the number of reds with probability $\frac k{b+r}$. Since this is true of any ordering of the balls, if you choose a random ordering and then a random starting point, you get the same probability. But this is just the same as choosing the balls randomly.

linguo
  • 113