6
$\begingroup$

I was sent a puzzle involving an urn with 128 white balls and 288 black. If the balls are drawn without replacement until the urn is exhausted, what is the probability that a sequence of 10 or more consecutive white balls will be drawn?

I solved this algorithmically using recursion and arrived at ~0.00170843. Simulations match this result well.

Is there a more direct conbinatorial method to answer this kind of question?

$\endgroup$
2
  • $\begingroup$ +1 just for using the tag ball-in-bins. I had no idea such a specific thing existed. $\endgroup$ – recursive recursion Jul 27 '14 at 22:22
  • $\begingroup$ I suspect that since the probability of drawing a white ball changes with each and every turn, and outcomes branch with every turn, that there is not going to be any simple solution to this. it is slightly similar to runs of heads on a biased coin, but again, the bias would change on every flip. $\endgroup$ – user136920 Jul 28 '14 at 5:51
3
$\begingroup$

Suppose that we have $w$ white balls and $b$ black balls, and that they are placed in a random order. Define the indices with black balls to be $1\leq i_1<i_2<\cdots < i_b\leq w+b$. We define the gaps between the black balls to be $$g_1=i_1, \quad g_j=i_j-i_{j-1} \mbox{ for }2\leq j\leq b,\quad \mbox{ and }\ g_{b+1}=(b+w+1)-i_b.$$

Note that these gaps form a composition of the integer $b+w+1$ into $b+1$ parts, and that there is a one-to-one correspondence between random ordering of the colors and such compositions.

For example, if $w=3$ and $b=2$ then the order $BWWBW$ corresponds to the composition $1+3+2$ of $6$ into $3$ parts. In general, $g_1+g_2+\cdots +g_{b+1}=b+w+1.$

Now those orders where the runs of white balls all have size less than $m$ are exactly those where the black gaps are at most $m$. But we can count these with the same formula that tells us how many ways we can roll $b+1$ dice with $m$ sides and get a total of $b+w+1$, i.e.,

$$S:=\sum_{j=0}^{\lfloor w/m\rfloor} (-1)^j {b+1\choose j}{w+b-jm\choose b}.$$

The required probability of at least one run of $m$ or more consecutive white balls is $$P=1-{S\over {b+w\choose b}}.$$

For $w=128$, $b=288$, and $m=10$ this gives $P=.001708427151$.

$\endgroup$
6
  • $\begingroup$ Thanks, Byron - just saw this (did not get notified of answer) - will give it a run to check speed against my recursion, I expect this will be much faster... $\endgroup$ – rasher Aug 2 '14 at 9:15
  • $\begingroup$ Nice - nearly instantaneous! I wonder how difficult this would be to extend to an arbitrary number of draws 1<=D<=B+W and M<=D... $\endgroup$ – rasher Aug 2 '14 at 9:51
  • $\begingroup$ @rasher That seems to be a much harder problem. I have no good ideas, I'm afraid. $\endgroup$ – user940 Aug 3 '14 at 14:40
  • $\begingroup$ actually, turns out the extension is pretty trivial: just enumerate the probabilities of the number of possible successes for the desired number of draws via hypergeometric, then multiply the result of your neat construct for each case by each of the probabilities and sum... presto! $\endgroup$ – rasher Aug 3 '14 at 22:26
  • $\begingroup$ @rasher: Would you mind writing out your solution of your extension in detail? $\endgroup$ – Hans Jul 22 '19 at 21:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.