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?
9
-
3$\begingroup$ Is it clear that this is not research mathematics? Why? $\endgroup$– Douglas ZareCommented May 9, 2013 at 9:48
-
7$\begingroup$ tea.mathoverflow.net/discussion/1591/… $\endgroup$– Douglas ZareCommented May 9, 2013 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 ♦Commented May 9, 2013 at 22:22
-
3$\begingroup$ The question has been reopened. Please use the "edit" link below the question text to revise. $\endgroup$– S. Carnahan ♦Commented May 9, 2013 at 23:43
-
3$\begingroup$ I think this is a hard problem even asymptotically for some values of the parameters. $\endgroup$– Brendan McKayCommented May 10, 2013 at 5:54
|
Show 4 more comments
3 Answers
$\begingroup$
$\endgroup$
2
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.
answered May 10, 2013 at 7:25
-
$\begingroup$ Why "the case $r\le 1/2$ is not interesting"? $\endgroup$ Commented May 11, 2013 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$– user9072Commented May 11, 2013 at 19:33
$\begingroup$
$\endgroup$
2
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)$.
answered May 10, 2013 at 8:48
-
$\begingroup$ This recursion is more efficient than the one I used. $\endgroup$– meijCommented May 10, 2013 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$ Commented May 15, 2013 at 21:29
$\begingroup$
$\endgroup$
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.
