# Thread: Marble question - hypergeometric/binomial hybrid

1. ## Marble question - hypergeometric/binomial hybrid

Hi there everyone,

Usually these standard draw x red marbles and y blue marbles from a box questions are no issue but here is a variant and friend asked me which I'm scratching my head about a bit:

You have a box with 10 blue marbles and 5 red marbles. When you draw a blue marble you keep it (without replacement) but when you draw a red marble you put it back in the box (replacement).
When you draw 3 blue marbles the game is over.

What is the average number of marbles expected to be drawn per game?

Now, obviously the drawing process for blue marbles would be a simple hypergeometric distribution if there were no red marbles. But the red marbles are going to skew this.

My initial thoughts were something like this:

- We know that the game is always going to end when we draw the 3rd blue marble so we will always have exactly 2 blue marbles and some number between 0 and infinity or red marbles (should be monitonically decreasing after a certain point).

- P[3 Blues|No Reds] = (10/15) * (9/14) * (8/13) = 0.2637
- P[3B|1R] = ((10C2 * 5C1(the 1 red))/(15C3) ) * (8/13) = 0.3043
- P[3B|2R] = ((10C2 * 6C2)/(16C4)) * (8/13) = 0.2282
- P[3B|3R] = ((10C2 * 7C3)/(17C5)) * (8/13) = 0.15663
- P[3B|4R] = ((10C2 * 8C4)/(18C6)) * (8/13) = 0.1044

Basically it is (combination without repetition -for blues) * (combination with repetition - for reds) / total combination) * (8/13).
Then I would muliply the number of marbles * probability to get expected number of total balls drawn per game.

But this way won't work as the probabilities (although diminishing) are going to total over 1.

Any one have any thoughts on this? Probably something very simple I'm overlooking. I'm stumped all the same!

Thanks very much for any and all help.

2. ## Re: Marble question - hypergeometric/binomial hybrid

You draw a sea of reds, with blues on the i-th, j-th, and n-th (terminating) draws
1<=i < j < n
Ex: i = 4, j = 10, n = 15: R R R B R R R R R B R R R R B

The probabilitiy of such an $(i, j, n)$ string, $Prob(i, j, n)$ is:

$\left(\frac{5}{15}\right)^{i-1} \left(\frac{10}{15}\right) \left(\frac{5}{14}\right)^{j-i-1} \left(\frac{9}{14}\right) \left(\frac{5}{13}\right)^{n-j-1} \left(\frac{8}{13}\right)$

$= \left(\frac{(10)(9)(8)}{(15)(14)(13)}\right) \left( \frac{(5^{i-1})(5^{j-i-1})(5^{n-j-1})}{({15}^{i-1})({14}^{j-i-1})({13}^{n-j-1})} \right)$

$= \left(\frac{24}{91}\right) \left \frac{(5^{n-3})}{({15}^{i-1})({14}^{j-i-1})({13}^{n-j-1})} \right$

$= \left(\frac{24}{91}\right) \left \frac{(5^{n-3})}{({15}^{i-1})({14}^{j-i-1})({13}^{n-j-1})} \right$

$= \left(\frac{24}{91}\right) (5^{n-3}) \left( (15)(14)\left(\frac{14}{15}\right)^i \left(\frac{13}{14}\right)^j \left(\frac{1}{13}\right)^{n-1} \right)$

$= \left(\frac{(24)(15)(14)(13)}{(91)(5^3)}\right) \left(\frac{14}{15}\right)^i \left(\frac{13}{14}\right)^j \left(\frac{5}{13}\right)^{n}$

$= \left(\frac{144}{25}\right) \left(\frac{14}{15}\right)^i \left(\frac{13}{14}\right)^j \left(\frac{5}{13}\right)^{n}$.

Therefore $Prob(i, j, n) = \left(\frac{144}{25}\right) \left(\frac{14}{15}\right)^i \left(\frac{13}{14}\right)^j \left(\frac{5}{13}\right)^{n}$.

Thus $Prob(n) = \sum_{1 \le i < j \le n}Prob(i, j, n)$

$= \sum_{1 \le i < j \le n} \left(\frac{144}{25}\right) \left(\frac{14}{15}\right)^i \left(\frac{13}{14}\right)^j \left(\frac{5}{13}\right)^{n} = \left(\frac{144}{25}\right) \left(\frac{5}{13}\right)^{n} \sum_{1 \le i < j \le n} \left(\frac{14}{15}\right)^i \left(\frac{13}{14}\right)^j$

$= \left(\frac{144}{25}\right) \left(\frac{5}{13}\right)^{n} q(n)$ where $q(n) = \sum_{1 \le i < j \le n} \left(\frac{14}{15}\right)^i \left(\frac{13}{14}\right)^j$.

$q(n)= \sum_{i=1}^{n-1} \sum_{j=i+1}^n \left(\frac{14}{15}\right)^i \left(\frac{13}{14}\right)^j = \sum_{i=1}^{n-1} \left\{ \left(\frac{14}{15}\right)^i \sum_{j=i+1}^n \left(\frac{13}{14}\right)^j\right\}$

$= \sum_{i=1}^{n-1} \sum_{j=i+1}^n \left(\frac{14}{15}\right)^i \left(\frac{13}{14}\right)^j = \sum_{i=1}^{n-1} \left\{ \left(\frac{14}{15}\right)^i \left[\sum_{j=0}^n \left(\frac{13}{14}\right)^j - \sum_{j=0}^i \left(\frac{13}{14}\right)^j \right] \right\}$

$= \sum_{i=1}^{n-1} \left\{ \left(\frac{14}{15}\right)^i \left[\frac{1 - \left(\frac{13}{14}\right)^{n+1}}{1 - \left(\frac{13}{14}\right)} - \frac{1 - \left(\frac{13}{14}\right)^{i+1}}{1 - \left(\frac{13}{14}\right)}\right] \right\}$

$= \frac{1 - \left(\frac{13}{14}\right)^{n+1}}{\left(\frac{1}{1 4}\right)} \sum_{i=1}^{n-1} \left(\frac{14}{15}\right)^i - \sum_{i=1}^{n-1} \left(\frac{14}{15}\right)^i \left(\frac{1 - \left(\frac{13}{14}\right)^{i+1}}{\left(\frac{1}{1 4}\right)}\right)$

$= \left(1 - \left(\frac{13}{14}\right)^{n+1}\right) (14) \left( \frac{1 - \left(\frac{14}{15}\right)^n}{1 - \left(\frac{14}{15}\right)} - 1 \right) - (14) \sum_{i=1}^{n-1} \left(\frac{14}{15}\right)^i \left(1 - \left(\frac{13}{14}\right)^{i+1}\right)$

$= \left(1 - \left(\frac{13}{14}\right)^{n+1}\right) (14) \left( (15)\left(1 - \left(\frac{14}{15}\right)^n\right) - 1 \right) - (14) \sum_{i=1}^{n-1} \left\{ \left( \frac{14}{15} \right)^i - \left( \frac{13}{14} \right) \left( \frac{13}{15} \right)^i \right\}$

$= \left(1 - \left(\frac{13}{14}\right)^{n+1}\right) (14)\left(14 - 15 \left(\frac{14}{15}\right)^n\right) - (14) \sum_{i=1}^{n-1} \left\{\left( \frac{14}{15} \right)^i - \left( \frac{13}{14} \right) \left( \frac{13}{15} \right)^i \right\}$

$= \left(1 - \left(\frac{13}{14}\right)^{n+1}\right) (14)\left(14 - 15 \left(\frac{14}{15}\right)^n\right) - (14) \left\{ \sum_{i=1}^{n-1} \left( \frac{14}{15}\right)^i - \left(\frac{13}{14}\right) \sum_{i=1}^{n-1} \left(\frac{13}{15}\right)^i \right\}$

$= \left(1 - \left(\frac{13}{14}\right)^{n+1}\right) (14)\left(14 - 15 \left(\frac{14}{15}\right)^n\right) - (14) \left\{ \left\(\frac{1-\left(\frac{14}{15}\right)^n}{1-\left(\frac{14}{15}\right)} - 1\right) - \left(\frac{13}{14}\right) \left(\frac{1-\left(\frac{13}{15}\right)^n}{1-\left(\frac{13}{15}\right)} - 1 \right) \right\}$

$= \left(1 - \left(\frac{13}{14}\right)^{n+1}\right) (14)\left(14 - 15 \left(\frac{14}{15}\right)^n\right) - (14) \left\{ \left( (15)\left\(1 - \left(\frac{14}{15}\right)^n\right) - 1\right) - \left(\frac{13}{14}\right) \left(\left(\frac{15}{2}\right) \left(1-\left(\frac{13}{15}\right)^n\right) - 1 \right) \right\}$

$= \left(1 - \left(\frac{13}{14}\right)^{n+1}\right) (14)\left(14 - 15 \left(\frac{14}{15}\right)^n\right) - (14) \left\{ \left( 14- (15)\left(\frac{14}{15}\right)^n\right) - \left(\frac{13}{14}\right) \left(\left(\frac{13}{2}\right)- \left(\frac{15}{2}\right) \left(\frac{13}{15}\right)^n\right) \right\}$

$= \left(1 - \left(\frac{13}{14}\right)^{n+1}\right) (14)\left(14 - 15 \left(\frac{14}{15}\right)^n\right) - (14) \left\{ 14- (15)\left(\frac{14}{15}\right)^n - \left(\frac{13}{14}\right)\left(\frac{13}{2}\right ) + \left(\frac{13}{14}\right) \left(\frac{15}{2}\right) \left( \frac{13}{15}\right)^n \right\}$

$= \left(1 - \left(\frac{13}{14}\right)^{n+1}\right) (14)\left(14 - 15 \left(\frac{14}{15}\right)^n\right) - (14) \left\{ 14 - 15 \left(\frac{14}{15}\right)^n - \frac{169}{28} + \left( \frac{195}{28} \right) \left(\frac{13}{15}\right)^n \right\}$

$= \left(1 - \left(\frac{13}{14}\right)^{n+1}\right) (14)\left(14 - 15 \left(\frac{14}{15}\right)^n\right) - \left\{ 196 - 210 \left(\frac{14}{15}\right)^n - \frac{169}{2} + \left( \frac{195}{2} \right) \left(\frac{13}{15}\right)^n \right\}$

$= (14^2)\left(1 - \left(\frac{13}{14}\right)^{n+1}\right) \left(1 - \left(\frac{14}{15}\right)^{n-1}\right) - \left\{ \frac{392 - 169}{2} - 210 \left(\frac{14}{15}\right)^n + \left( \frac{195}{2} \right) \left(\frac{13}{15}\right)^n \right\}$

$= (14^2) \left\{ 1 - \left(\frac{13}{14}\right)^{n+1} - \left(\frac{14}{15}\right)^{n-1} + \left(\frac{13}{14}\right)^{n+1} \left(\frac{14}{15}\right)^{n-1} \right\} - \frac{221}{2} + 210 \left(\frac{14}{15}\right)^n - \frac{195}{2} \left(\frac{13}{15}\right)^n$

$= 14^2 - 14^2\left(\frac{13}{14}\right)^{n+1} - 14^2\left(\frac{14}{15}\right)^{n-1} + (13)(15)\left(\frac{13}{15}\right)^n - \frac{221}{2} + 210 \left(\frac{14}{15}\right)^n - \frac{195}{2} \left(\frac{13}{15}\right)^n$

$= \frac{392}{2} - 13^2\left(\frac{13}{14}\right)^{n-1} - 14^2\left(\frac{14}{15}\right)^{n-1} + 169\left(\frac{13}{15}\right)^{n-1} - \frac{221}{2} + 196 \left(\frac{14}{15}\right)^{n-1} - \frac{169}{2} \left(\frac{13}{15}\right)^{n-1}$

$= \frac{392 - 221}{2} - 13^2\left(\frac{13}{14}\right)^{n-1} - 14^2\left(\frac{14}{15}\right)^{n-1} + 169\left(\frac{13}{15}\right)^{n-1} + 196 \left(\frac{14}{15}\right)^{n-1} - \frac{169}{2} \left(\frac{13}{15}\right)^{n-1}$

$= \frac{171}{2} - 13^2\left(\frac{13}{14}\right)^{n-1} + (- 196 + 196) \left(\frac{14}{15}\right)^{n-1} + (169 - \frac{169}{2}) \left(\frac{13}{15}\right)^{n-1}$

$= \frac{171}{2} - 169\left(\frac{13}{14}\right)^{n-1} + \frac{169}{2} \left(\frac{13}{15}\right)^{n-1}$

Therefore $q(n) = \frac{171}{2} - 169\left(\frac{13}{14}\right)^{n-1} + \frac{169}{2} \left(\frac{13}{15}\right)^{n-1}$

Have $Prob(n) = \left(\frac{144}{25}\right) \left(\frac{5}{13}\right)^{n} q(n) = \left(\frac{144}{65}\right) \left(\frac{5}{13}\right)^{n-1} q(n)$.

Thus $Prob(n) = \left(\frac{144}{65}\right) \left(\frac{5}{13}\right)^{n-1} \left\{ \frac{171}{2} - 169\left(\frac{13}{14}\right)^{n-1} + \frac{169}{2} \left(\frac{13}{15}\right)^{n-1} \right\}$

$= \left(\frac{144}{65}\right) \left\{ \frac{171}{2} \left(\frac{5}{13}\right)^{n-1} - 169\left(\frac{13}{14}\right)^{n-1} \left(\frac{5}{13}\right)^{n-1} + \frac{169}{2} \left(\frac{13}{15}\right)^{n-1} \left(\frac{5}{13}\right)^{n-1} \right\}$

$= \left(\frac{144}{65}\right) \left\{ \frac{171}{2} \left(\frac{5}{13}\right)^{n-1} - 169\left(\frac{5}{14}\right)^{n-1} + \frac{169}{2} \left(\frac{5}{15}\right)^{n-1} \right\}$

$= \left(\frac{144}{65}\right) \left\{ \frac{171}{2} \left(\frac{5}{13}\right)^{n-1} - 169\left(\frac{5}{14}\right)^{n-1} + \frac{169}{2} \left(\frac{5}{15}\right)^{n-1} \right\}$

$= \left(\frac{144}{65}\right) \frac{171}{2} \left(\frac{5}{13}\right)^{n-1} - 169 \left(\frac{144}{65}\right) \left(\frac{5}{14}\right)^{n-1} + \left(\frac{144}{65}\right) \frac{169}{2} \left(\frac{5}{15}\right)^{n-1}$

$= \left(\frac{72(9)(19)}{65}\right) \left(\frac{5}{13}\right)^{n-1} - \left(\frac{144(13)}{5}\right) \left(\frac{5}{14}\right)^{n-1} + \left(\frac{72(13)}{5}\right) \left(\frac{5}{15}\right)^{n-1}$

Therefore $Prob(n) = \left(\frac{72(9)(19)}{65}\right) \left(\frac{5}{13}\right)^{n-1} - \left(\frac{144(13)}{5}\right) \left(\frac{5}{14}\right)^{n-1} + \left(\frac{72(13)}{5}\right) \left(\frac{1}{3}\right)^{n-1}$.

Therefore $Expectation = \sum_{n=3}^{\infty}nProb(n) = \sum_{n=3}^{\infty}n\left\{ \left(\frac{72(9)(19)}{65}\right) \left(\frac{5}{13}\right)^{n-1} - \left(\frac{144(13)}{5}\right) \left(\frac{5}{14}\right)^{n-1} + \left(\frac{72(13)}{5}\right) \left(\frac{1}{3}\right)^{n-1} \right\}$

But $\sum_{n=1}^{\infty}nr^{n-1} = \frac{1}{(1-r)^2} for |r| < 1$.

So $\sum_{n=3}^{\infty}nr^{n-1} = \frac{1}{(1-r)^2} - 1 - 2r for |r| < 1$.

Thus $Expectation = \sum_{n=3}^{\infty}n\left\{ \left(\frac{72(9)(19)}{65}\right) \left(\frac{5}{13}\right)^{n-1} - \left(\frac{144(13)}{5}\right) \left(\frac{5}{14}\right)^{n-1} + \left(\frac{72(13)}{5}\right) \left(\frac{1}{3}\right)^{n-1} \right\}$

$= \left(\frac{72(9)(19)}{65}\right) \sum_{n=3}^{\infty}n \left(\frac{5}{13}\right)^{n-1} - \left(\frac{144(13)}{5}\right) \sum_{n=3}^{\infty}n \left(\frac{5}{14}\right)^{n-1} + \left(\frac{72(13)}{5}\right) \sum_{n=3}^{\infty}n \left(\frac{1}{3}\right)^{n-1} \right\}$

$= \left(\frac{72(9)(19)}{65}\right) \left\{ \frac{1}{(1-\left(\frac{5}{13}\right))^2} - 1 - 2 \left(\frac{5}{13}\right)\right\} - \left(\frac{144(13)}{5}\right) \left\{ \frac{1}{(1-\left(\frac{5}{14}\right))^2} - 1 - 2\left(\frac{5}{14}\right) \right\} + \left(\frac{72(13)}{5}\right) \left\{ \frac{1}{(1-\left(\frac{1}{3}\right))^2} - 1 - 2 \left(\frac{1}{3}\right)\right\}$

$= \left(\frac{72(9)(19)}{65}\right) \left\{ \left(\frac{13}{8}\right)^2 - \left(\frac{23}{13}\right)\right\} - \left(\frac{144(13)}{5}\right) \left\{ \left(\frac{14}{9}\right)^2 - \left(\frac{12}{7}\right) \right\} + \left(\frac{72(13)}{5}\right) \left\{ \left(\frac{3}{2}\right)^2 - \left(\frac{5}{3}\right)\right\}$

$= \left(\frac{72(9)(19)}{65}\right) \left\{ \left(\frac{13^3}{8^2(13)}\right) - \left(\frac{23(8^2)}{13(8^2)}\right)\right\} - \left(\frac{144(13)}{5}\right) \left\{ \left(\frac{14^2(7)}{9^2(7)}\right) - \left(\frac{12(9^2)}{7(9^2)}\right) \right\} + \left(\frac{72(13)}{5}\right) \left\{ \left(\frac{27}{12}\right) - \left(\frac{20}{12}\right)\right\}$

$= \left(\frac{72(9)(19)}{65}\right) \left\{ \left(\frac{13^3}{8^2(13)}\right) - \left(\frac{23(8^2)}{13(8^2)}\right)\right\} - \left(\frac{144(13)}{5}\right) \left\{ \left(\frac{14^2(7)}{9^2(7)}\right) - \left(\frac{12(9^2)}{7(9^2)}\right) \right\} + \left(\frac{72(13)}{5}\right) \left\{ \left(\frac{27}{12}\right) - \left(\frac{20}{12}\right)\right\}$

$= \left(\frac{72(9)(19)}{65}\right) \left(\frac{13^3 - 23(8^2)}{8^2(13)}\right) - \left(\frac{144(13)}{5}\right) \left(\frac{14^2(7) - 12(9^2)}{9^2(7)}\right) + \left(\frac{72(13)}{5}\right) \left(\frac{7}{12}\right)$

$= \left(\frac{72(9)(19)}{65}\right) \left(\frac{725}{8^2(13)}\right) - \left(\frac{144(13)}{5}\right) \left(\frac{400}{9^2(7)}\right) + \left(\frac{72(13)}{5}\right) \left(\frac{7}{12}\right)$

$= \left(\frac{(9^2)(19)}{65}\right) \left(\frac{725}{8(13)}\right) - \left(\frac{144(13)}{5}\right) \left(\frac{400}{9^2(7)}\right) + \left(\frac{72(13)}{5}\right) \left(\frac{7}{12}\right)$

$= \frac{(9^2)(19)(145)}{(2^3)(13^2)} - \frac{4^2(13)(80)}{(3^2)(7)} + \frac{6(13)(7)}{5}$

$= \frac{ (3^2)(5)(7)(9^2)(19)(145) - (2^3)(5)(13^2)(4^2)(13)(80) + (2^3)(3^2)(7)(13^2)(6)(13)(7) }{ (2^3)(3^2)(5)(7)(13^2) }$

$= \frac{4,313,521}{425,880} \approx 10.1285$

Conclude that the expectation is $= \frac{4,313,521}{425,880} \approx 10.1285$.

(I'm going to double check this later - it took too long. However, it looks like a reasonable result.)

3. ## Re: Marble question - hypergeometric/binomial hybrid

Wow, thats an impressive answer. Thanks for taking the time out to respond, I really appreciate it.

Intuitively I would have thought it would have been slightly lower but I suppose if the Probability[n] does not tend to zero too rapidly it could easily cause the expectation to be higher than first guess. As you said, 10 is a pretty reasonable result.

I'm still reviewing your answer, but I can follow the logic down to P[i,j,n] without a problem. I'll go through the rest of the derivation now.

I'll just add, I'm surprised at how much meat there is in this question. My friend said this was asked at an interview (without a calculator I presume) - this would make me think that there is some recursive trick I'm not thinking of that might solve this quite elegantly but for now this is the best I've seen.

Thanks again

4. ## Re: Marble question - hypergeometric/binomial hybrid

Wow. I never before saw so much LaTeX in a forum post.

I wrote a quick simulation yesterday. I think I got an answer of about 4.68 marbles.

5. ## Re: Marble question - hypergeometric/binomial hybrid

Let's say E(R,B,n) is the expected number of draws required to draw n blue marbles, starting with R red marbles and B blue marbles; so we want to find E(5,10,3).

Starting with 5 reds and 10 blues, with probability 5/15 the first marble drawn is red. We then are then right back where we started, and on average we require a total of 1 + E(5,10,3) draws to draw a total of 3 blues. With probability 10/15, we draw a blue. We then require, on average, a total of 1 + E(5,9,2) draws to complete. So
$E(5,10,3) = \frac{5}{15} [1 + E(5,10,3)] + \frac{10}{15} [1 + E(5,9,2)]$

Now suppose we have 5 red marbles and 9 blue marbles. Reasoning as before,
$E(5,9,2) = \frac{5}{14} [1 + E(5,9,2)] + \frac{9}{14} [1 + E(5,8,1)]$

If we have 5 red marbles and 8 blue marbles,
$E(5,8,1) = \frac{5}{13} [1 + E(5,8,1)] + \frac{8}{13} [1]$

Solving these equations from last to first, we find

$E(5,10,3) = 3370/720 \approx 4.6806$

which is close to the answer found by "a tutor" via simulation.