(Hardish) Combinatorics problem: how often are consecutive balls the same colour?

• Aug 9th 2012, 05:43 AM
sirdakka
(Hardish) Combinatorics problem: how often are consecutive balls the same colour?
Hi all, first post, and not entirely sure it belongs here, but the problem seems hard enough to me!

I have a bag containing X red balls and Y blue balls.

Balls are withdrawn one at a time until no balls remain.

What is the expected number of times that two blue balls are withdrawn in a row?

(E.g. in: r b b r b r r b b b b, there are 4 b-b events)

Is it possible to work out a general formula?
• Aug 9th 2012, 05:44 PM
awkward
Re: (Hardish) Combinatorics problem: how often are consecutive balls the same colour?
This is easier to work out via probability theory rather than combinatorics.

Let's say $T_i = 1$ if the ith and (i+1)th balls are both blue,
$= 0$ otherwise.

Then $\Pr(A_i = 1) = \frac{X}{X+Y} \cdot \frac{X-1}{X+Y-1}$ for $i = 1, 2, 3, \dots X+Y-1$.

So the expected number of times two blue balls are drawn in a row is
$E(\sum T_i) = \sum E(T_i) = \sum \Pr(T_i = 1)$
$= (X+Y-1) \cdot \frac{X}{X+Y} \cdot \frac{X-1}{X+Y-1} = \frac{X(X-1)}{X+Y}$

Here we have used the theorem that E(X+Y) = E(X) + E(Y). It's important to realize that this theorem holds even if X and Y are not independent. That is good for us here, because the $T_i$'s are not independent.
• Aug 10th 2012, 01:26 AM
sirdakka
Re: (Hardish) Combinatorics problem: how often are consecutive balls the same colour?

I realize now that I also require the variance, which I am currently trying to work out, but as a neuroscience student I am struggling somewhat.

Is there any chance you could help me out once again?
• Aug 10th 2012, 02:44 AM
sirdakka
Re: (Hardish) Combinatorics problem: how often are consecutive balls the same colour?
Also, the variances for the cases in which a red follows a blue, a blue follows a red and a red follows a red.
• Aug 10th 2012, 06:05 PM
awkward
Re: (Hardish) Combinatorics problem: how often are consecutive balls the same colour?
Quote:

Originally Posted by sirdakka

I realize now that I also require the variance, which I am currently trying to work out, but as a neuroscience student I am struggling somewhat.

Is there any chance you could help me out once again?

It's more involved, but the technique in my previous post can be extended to find the variance. Here is the idea. Consider the sum
$\sum_{i < j} T_i T_j$, where $T_i$ is defined as before. This sum is equal to the number of pairs of blue-blue pairs; so if $Z$ is the number of blue-blue pairs, then
$\binom{Z}{2} = \sum_{i < j} T_i T_j$
so
$\frac{Z^2 - Z}{2} = \sum_{i < j} T_i T_j$
whence
$Z^2 = Z + 2 \sum_{i < j} T_i T_j$
so
$E(Z^2) = E(Z) + 2 E \left( \sum_{i < j} T_i T_j \right)$

We already know E(Z) from the previous post; so if we can find $E \left( \sum_{i < j} T_i T_j \right)$ then we can find E(Z^2).
Once we know E(Z) and E(Z^2), we can find var(Z) from the equation $var(Z) = E(Z^2) - E(Z)^2$.

So consider the expected number of pairs of blue-blue pairs. Let's say (i, i+1) and (j, j+1) are one such pair, where i < j. There are two possibilities: i+1 = j and i+1 < j.

In the first case (i+1 = j), the probability of occurrence is
$\frac{X}{X+Y} \cdot \frac{X-1}{X+Y-1} \cdot \frac{X-2}{X+Y-2}$
There are $X+Y-2$ such pairs.

In the second case (i+1 < j), the probability of occurrence is
$\frac{X}{X+Y} \cdot \frac{X-1}{X+Y-1} \cdot \frac{X-2}{X+Y-2} \frac{X-3}{X+Y-3}$
There are $\binom{X+Y-1}{2} - (X+Y-2) = \frac{(X+Y-2) (X+Y-3)}{2}$ such pairs.

Therefore
$E \left( \sum_{i < j} T_i T_j \right) = (X+Y-2) \cdot \frac{X}{X+Y} \cdot \frac{X-1}{X+Y-1} \cdot \frac{X-2}{X+Y-2}$
$+ \frac{(X+Y-2) (X+Y-3)}{2} \cdot \frac{X}{X+Y} \cdot \frac{X-1}{X+Y-1} \cdot \frac{X-2}{X+Y-2} \cdot \frac{X-3}{X+Y-3}$
which can be simplified to
$E \left( \sum_{i < j} T_i T_j \right) = \frac{X (X-1)^2 (X-2)}{2 (X+Y) (X+Y-1)}$

Taken together with previous remarks, you now have enough information to calculate the variance.