Marble question - hypergeometric/binomial hybrid

**drama** · October 5th 2012, 02:48 AM

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.

**johnsomeone** · October 5th 2012, 05:07 AM

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.)

**drama** · October 6th 2012, 12:49 PM

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

**a tutor** · October 6th 2012, 01:29 PM

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.

**awkward** · October 8th 2012, 09:53 AM

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.

Thread: Marble question - hypergeometric/binomial hybrid

LinkBack

Thread Tools

Display

Marble question - hypergeometric/binomial hybrid

Re: Marble question - hypergeometric/binomial hybrid

Re: Marble question - hypergeometric/binomial hybrid

Re: Marble question - hypergeometric/binomial hybrid

Re: Marble question - hypergeometric/binomial hybrid

Similar Math Help Forum Discussions

Binomial, Geometric, Negative Binomial, Hypergeometric Distribution

binomial and hypergeometric probability distributions

Hypergeometric distribuion or binomial distribution?

Difference between binomial distribution and geometric, hypergeometric etc

Binomial->hypergeometric->poisson

Search Tags