Skip to main content
added 20 characters in body
Source Link
Roland Bacher
  • 17.9k
  • 3
  • 45
  • 113

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 containcontains at least as many white than black balls where the total number of black balls is $b$ and with the bins filled uniformlyrandomly 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)$.

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 contain at least as many white than black balls where the total number of black balls is $b$ and with the bins filled uniformly. (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)$.

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

Source Link
Roland Bacher
  • 17.9k
  • 3
  • 45
  • 113

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 contain at least as many white than black balls where the total number of black balls is $b$ and with the bins filled uniformly. (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)$.