Imagine I have 76 million boxes, and I want to put only 2 particles maximum for each box, I want to find the total numbers of ways (combinations) that involves placing 2 particle in each box given that you have 40,000 particles in total.

I have attempted the question, and Here is my step:

$$\Sigma_{i=1}^{20000} \frac{76000000!}{(2!^{i}1!^{N-i})}$$

Eventually, I would divide this number by 76000000! to compute the probability of placing 2 particles in each box.

To compute the higher order terms, I would also start including the case when some boxes have 3 particles, but the majority has 2 particles.

To convince you that my initial thoughts is correct: Let's imagine a simpler problem with 4 boxes, and only 3 particles.

If you draw all the possible cases with 2 particles maximum for each box you realise placing the first two particles in the same box, you have 4 choices, after that you are left with 3 choices for placing only one particle. So the number of ways for 2 particles maximum in a box is Number of ways = 4!/(2!1!)

  • $\begingroup$ Is your real question "What is the probability that no box has three or more particles?"? If so, it may be about $0.9999990285$ using an "almost independent" argument $\endgroup$ – Henry Mar 14 '17 at 9:03
  • $\begingroup$ If you need the exact value of $n!$ I can tell a way to compute it in $O(n \log^2 n)$ time. However if you need only approximation, you can use Stirling formula. $\endgroup$ – Smylic Mar 14 '17 at 9:07
  • $\begingroup$ Your answer will be slightly less than $76000000^{40000} \approx 3.5\times10^{315232}$ $\endgroup$ – Henry Mar 14 '17 at 9:11
  • $\begingroup$ Meanwhile $76000000! \approx 5 \times 10^{565935456}$. Do you want all the digits? $\endgroup$ – Henry Mar 14 '17 at 9:15
  • $\begingroup$ My real question is what is the probability that each box only has 2 particles? I believe to obtain better approximation, Higher order event can include cases like: most boxes with 2 particles, some with 1 or 3 or 4 particles... But I don't really know if higher order events play a significant role in the probability, it would be nice to calculate them too, but they are more difficult. $\endgroup$ – el psy Congroo Mar 14 '17 at 11:14

Consider one particular box: the number of particles is a binomial random variable with parameters $40000$ and $1/76000000$. So the probability of the number $k$ of particles in the box is $$\displaystyle {\text{particles} \choose k} \frac{(\text{boxes}-1)^{ \text{particles}-k}}{\text{boxes}^{ \text{particles}}}$$ though in practice you will calculate this with logarithms or something pre-programmed.

For example the R code dbinom(0:5, size=particles, prob=1/boxes) gives the following probabilities:

 0            1            2            3            4            5
9.994738e-01 5.260389e-04 1.384278e-07 2.428437e-11 3.195072e-15 3.362897e-19

If you multiply these by the number of boxes, this gives the expected number of boxes with a given number of particles

 0            1            2            3            4            5
7.596001e+07 3.997895e+04 1.052051e+01 1.845612e-03 2.428255e-07 2.555802e-11

i.e. an expected number of fewer than $0.002$ boxes with $3$ or more particles, about $10.52$ boxes with $2$ particles, and so almost $40000-2\times 10.52$ boxes with $1$ particle and about $76000000-40000+10.52$ with no particles

As an approximation, you might set aside the possibility of three or more particles and look at the distribution of the number of boxes with two particles. If you assume each box with $2$ particles is independent of the others (they are not, but they are very close to being independent) and using the 1.384278e-07 probability calculated earlier, you can again use the binomial distribution with parameters of $76000000$ and that probability to find a good approximation to the probability of boxes with exactly $2$ particles. Assuming no boxes with $3$ or more, the number of boxes with exactly $1$ is then $40000$ minus twice the number with $2$, and the number with $0$ being the remainder.

A further approximation could be to use the Poisson distribution as a good approximation to the binomial distribution.


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.