11
$\begingroup$

Given $m\cdot e$ balls, $b$ of which are black (suppose the rest are white balls). Randomly put the balls into $m$ baskets, with $e$ balls in each basket. What is the probability of the event that every basket has more white balls than black ones?

$\endgroup$
  • 3
    $\begingroup$ Is it clear that this is not research mathematics? Why? $\endgroup$ – Douglas Zare May 9 '13 at 9:48
  • 7
    $\begingroup$ tea.mathoverflow.net/discussion/1591/… $\endgroup$ – Douglas Zare May 9 '13 at 17:52
  • 7
    $\begingroup$ Dear anonymous: I think at least some of the details that you view as irrelevant are in fact important for setting up context. We encourage questioners to include some motivation, e.g., in the "how to ask" page linked at the top of this one. That way, questions are less likely to be mistaken for homework or test questions. $\endgroup$ – S. Carnahan May 9 '13 at 22:22
  • 3
    $\begingroup$ The question has been reopened. Please use the "edit" link below the question text to revise. $\endgroup$ – S. Carnahan May 9 '13 at 23:43
  • 3
    $\begingroup$ I think this is a hard problem even asymptotically for some values of the parameters. $\endgroup$ – Brendan McKay May 10 '13 at 5:54
7
$\begingroup$

let's consider a simpler question: for which values of the parameters does this probability tend to 0 or to 1?

Here are some basic estimates for the case where all the parameters tend to infinity and the ratio $r=\frac{b}{me}$ is fixed (or tends to some value). The case $r\ge \frac12$ is not interesting - clearly there will be some black majorities with high probability. If $r<\frac12$, then the probability of a black majority in a given basket is roughly $$r^{e/2}(1-r)^{e/2} {e \choose e/2} \approx \frac{\big(2\sqrt{r(1-r)}\big)^e}{\sqrt{e}}$$ where the approximation is up to a multiplicative constant. For this approximation to hold we need to assume that $m$ grows quickly enough for the difference between sampling with and without replacement to be negligible. This is certainly the case when $m$ grows exponentially, which is the relevant regime.

In that regime we also have that the results for different baskets are asymptotically pairwise independent, hence we can get an upper and lower using union bound and the second moment method and conclude that when $$m\ll \frac{\sqrt{e}}{\big(2\sqrt{r(1-r)}\big)^e}$$ the probability of a black majority in some cells tends to 0, and when $$m\gg \frac{\sqrt{e}}{\big(2\sqrt{r(1-r)}\big)^e}$$ the probability tends to 1.

$\endgroup$
  • $\begingroup$ Why "the case $r\le 1/2$ is not interesting"? $\endgroup$ – anonymous May 11 '13 at 19:15
  • 1
    $\begingroup$ On quick inspection it seems this is 'flipped' from what it should say. But clearly half the range of r is not interesting (as one simply has not enough of the relevant balls to achieve a majority in each basket). And this does not seem to affect the substance of the answer much (or at all). $\endgroup$ – user9072 May 11 '13 at 19:33
3
$\begingroup$

Since the first bin contains $k$ balls with probability $$\frac{{e\choose k}{me-e\choose b-k}}{{me\choose b}},$$ we get the recursion relation $$p_e(m,b)=\sum_{k=0}^{\lfloor e/2\rfloor}\frac{{e\choose k}{me-e\choose b-k}}{{me\choose b}}p_e(m-1,b-k)$$ with $p_e(m,b)$ denoting the probability that each of the $m$ bins filled with $e$ balls contains at least as many white than black balls where the total number of black balls is $b$ and with the bins filled randomly in an obvious sense. (If we want strict inequality, we have to replace the upper summation-bound $\lfloor e/2\rfloor$ by $\lfloor (e-1)/2\rfloor$.

Using the obvious initial condition $p_e(1,b)=1$ if $b\leq e/2$ (respectively $b$ strictly smaller than $e/2$ if we wish strict inequality) and $p_e(1,b)=0$ otherwise, we can compute $p_e(m,b)$ by an algorithm needing roughly the computation of $2mb+m$ binomial coefficients and having a memory requirement $b$ (by computing $p_e(a+1,0),\dots,p_e(a+1,b)$ using the values $p_e(a,0),\dots,p_e(a,b)$.

$\endgroup$
  • $\begingroup$ This recursion is more efficient than the one I used. $\endgroup$ – meij May 10 '13 at 16:25
  • $\begingroup$ Why did you ignore the part $\sum_{k=\lfloor (e-1)/2\rfloor}^{\min(b,e)}\frac{{e \choose k}{me-e \choose b-k}}{{me \choose b}}$? $\endgroup$ – anonymous May 15 '13 at 21:29
2
$\begingroup$

This isn't a real answer.

You can find some probabilities using a clever loop when the partition(m*e) is not huge, where I am using partition() to mean the integer partition function from number theory. This is still not as clever as a hypothetical closed form answer. I assume that the answer isn't just a binomial coefficient or something, otherwise someone would have already answered it.

Here are some naive calculations for m=3, e=3, followed by less naive, but not closed-form, calculations for m=10, e=10.


m: 3
e: 3

b: 0
nways naive: 362880
nways_fast : 362880
prob: 1

b: 1
nways naive: 362880
nways_fast : 362880
prob: 1

b: 2
nways naive: 272160
nways_fast : 272160
prob: 3 / 4

b: 3
nways naive: 116640
nways_fast : 116640
prob: 9 / 28

b: 4
nways naive: 0
nways_fast : 0
prob: 0

Calculations for m=10, e=10:


m: 10
e: 10

b: 0
prob: 1

b: 1
prob: 1

b: 2
prob: 1

b: 3
prob: 1

b: 4
prob: 1

b: 5
prob: 29875 / 29876

b: 6
prob: 567535 / 567644

b: 7
prob: 63785 / 63826

b: 8
prob: 37531985 / 37593514

b: 9
prob: 45347875 / 45507938

b: 10
prob: 6463929125 / 6507635134

b: 11
prob: 1586911975 / 1605780098

b: 12
prob: 981182104025 / 1000401001054

b: 13
prob: 384868375 / 396669707

b: 14
prob: 1066668675750 / 1115831885791

b: 15
prob: 989247906939375 / 1055576963958286

b: 16
prob: 1489819534516125 / 1631346217026442

b: 17
prob: 19844564270625 / 22459084339538

b: 18
prob: 964555447190625 / 1137829714396594

b: 19
prob: 155522927593125 / 193114800728458

b: 20
prob: 143007636792729375 / 189059389913160382

b: 21
prob: 24103622043759375 / 34374434529665524

b: 22
prob: 75602536926778125 / 118068709906242452

b: 23
prob: 220551587574103125 / 383723307195287969

b: 24
prob: 14932881008409375 / 29517177476560613

b: 25
prob: 4988973826968750000 / 11456881600545026503

b: 26
prob: 4360116559500000 / 11932476001162801

b: 27
prob: 6180351555497625000 / 20750575766022110939

b: 28
prob: 205959103466801625000 / 876984860006092372843

b: 29
prob: 251666129503125000 / 1411735350344467939

b: 30
prob: 5283557104214784375000 / 40794916418904090033283

b: 31
prob: 10699432321455000000 / 119633185979190879863

b: 32
prob: 618306212430000000 / 10623796438306526011

b: 33
prob: 235960695639900000000 / 6682367959694804860919

b: 34
prob: 518835697776900000000 / 26336391370561877981269

b: 35
prob: 2874702717526500000000 / 289700305076180657793959

b: 36
prob: 1506044508147900000000 / 342373087817304413756497

b: 37
prob: 15293171450812500000 / 9253326697764984155581

b: 38
prob: 241217215312500000 / 487017194619209692399

b: 39
prob: 1350816405750000000 / 12774835643473115777543

b: 40
prob: 9455714840250000000 / 779264974251860062430123

b: 41
prob: 0

I was mildly annoyed to not find anything in oeis. Maybe I am bad at searching oeis, or maybe I am doing the math wrong.

$\endgroup$

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.