4
$\begingroup$

Question1: I found 30 boxes. In 10 boxes i found 15 balls. In 20 boxes i found 0 balls. Afer i collected all 15 balls i put them randomly inside the boxes.

How much is the chance that all balls are in only 10 boxes or less?

Question2: I found 30 boxes. In 10 boxes i found 15 balls. In 20 boxes i found 0 balls. In two of the boxes i could find 3 balls. (So in one box has to be 2 balls and in the other seven boxes have to be 1 ball.) Afer i collected all 15 balls i put them randomly inside the boxes.

How much is the chance that i find in only 2 boxes 6 balls or more?

I wrote a c# programm and tried it 1 million times. My solution was: With a chance of 12,4694% all balls are in 10 boxes or less.

$\endgroup$
1
$\begingroup$

Random trials/Monte Carlo simulations are notoriously slow to converge, with an expected error inversely proportional to the square root of the number of trials.

In this case it is not hard (given a programming language that provides big integers) to do an exact count of cases. Effectively the outcomes are partitions of the 15 balls into some number of boxes (we have thirty boxes to work with, so at least half will be empty).

I wrote a Prolog program to do this (Amzi! Prolog has arbitrary precision integers built in), and got the following results:

$$ Pr(\text{10 or fewer boxes occupied}) = \frac{59486359170743424000}{30^{14}} \approx 0.124371 $$

$$ Pr(\text{2 boxes hold 6 or more balls}) = \frac{30415369655816064000}{30^{14}} \approx 0.063591 $$

The reason I'm dividing by $30^{14}$ in these probabilities is because I normalized the counting to begin with one case where a ball is in one box. If we counted that as thirty cases, we'd need to divide by $30^{15}$. So this keeps the totals slightly smaller. Each ball we add increases the total number of cases by a factor of $30$.

I wrote a recursive rule to build cases for $n+1$ balls from cases for $n$ balls. The first few cases have the following counts:

 /* case(Balls,Partition,LengthOfPartition,Count) */ 
 case(1,[1],1,1).   /* Count is nominally 1 to begin */
 case(2,[2],1,1).
 case(2,[1,1],2,29).
 case(3,[3],1,1).
 case(3,[1,2],2,87).
 case(3,[1,1,1],3,812).   /* check: for Sum = 3, sum of Count is 900 */

The number of cases generated is modest enough for a desktop, daunting to manage by hand. For $n=15$ there are $176$ partitions. It simplified the Prolog code to maintain the partitions as lists in ascending order.

$\endgroup$
  • $\begingroup$ I checked out with a c# program. I simulated the problem with random numbers and counted: How often I find 6 ore more balls in only 2 boxes. 1000000-times tried: Pr(2 boxes hold 6 or more balls) = 0,063491%. Thanks alot! $\endgroup$ – Simon Aug 4 '14 at 13:39
  • $\begingroup$ Simulation is easier to program than the recursive/exact counting, but as briefly mentioned, getting an extra digit of accuracy may well require a hundred times as many trials because of the random walk phenomenon. $\endgroup$ – hardmath Aug 4 '14 at 13:42
4
$\begingroup$

Solution of Question 1:

This is an occupancy problem with $n=30$ boxes and $k=15$ balls.

Let's first consider the expected number of empty boxes. That is much easier to obtain. The exact answer is $30(1-1/30)^{15}=18.04.$ This is approximately $30/\sqrt e.$ See the answer by Mr.Spot to this question:

Making 400k random choices from 400k samples seems to always end up with 63% distinct choices, why?

The probability of exactly $j$ empty boxes is, for $n-k\le j\le n-1$:

$$P(j)={n \choose j}\sum_{m=0}^{n-j}(-1)^m {n-j \choose m}\left(1-\frac{j+m}n\right)^k $$

See this:

http://probabilityandstats.wordpress.com/2010/04/04/a-formula-for-the-occupancy-problem/

For $n=30$ and $k=15:$

$P(20)$ to $P(24)$ is $0.096,0.024,0.0036,0.00029,0.000013,....$

and the probability of at least $20$ empty cells = 0.124371

Solution of Question 2:

You throw 15 balls into 30 boxes. What is the probability of the following result:

2 triple, 1 double and 7 single occupancy boxes and the rest empty.

$${30 \choose 2} {28 \choose 1}{27 \choose 7}\frac{15!}{3!3!2!1!^7}\frac{1}{30^{15}} $$ $$=\frac{(30)(29)...(21)}{30^{15}2!1!7!}\frac{15!}{3!3!2!1!^7} $$ First we select the 2 different boxes for the triples; of the 28 remaining boxes we select 1 for the double; of the 27 remaining boxes we select 7 for the singles. Then the multinomial coefficient gives the number of ways to assign the 15 balls to those particular boxes and there are $30^{15}$ equally likely ways to throw the 15 balls into the 30 boxes.

$\endgroup$
  • $\begingroup$ Thanks a lot for answering the question and for giving me tips to understand the topic. The answer fits to my program. Expected number of empty boxes: I did 11*6+295*7 ... 14246*15=11956971 (Numbers posted in comment ant11). 11956971/1000000=11.956971. 30-ans=18.043029. I also checked the formula in wolfram alpha and i got the same numbers. Now i will write a program about question2. I think this is easy to solve (approximately) with a program. And i will take a look at "formula for the occupancy problem". Maybe i can improve my understanding about this topic. $\endgroup$ – Simon Jul 27 '14 at 17:14
  • $\begingroup$ I tried your formula for each combination and got nearly the same numbers. In comparison to the other combination, one had a larger difference. If you get 15 boxes with balls (1 ball each box), i had the chance of 1,4246%. If i do formula with wolfram alpha i use this text: (30 choose j) (sum ((-1)^m)*((30-j) choose m)*(1-((j+m)/30))^15, m=0 to 10) , j=15 | (15 stands for 15 free boxes --> 15 boxes not empty). I got the solution: 0,02291 = 2,291%. I used the same formula for j=15,16...29. I estimated the numbers as 2,9910%. All 15 numbers added i got 1,015827. Normally i should get 1. $\endgroup$ – Simon Jul 28 '14 at 15:00
  • $\begingroup$ Ok i tried again 2 times. Now i rounded all nombers down. I tried your formula for j= 15,16...29. My solution: 15=0,029910305; 16=0,092823631; 17=0,236474423; 18=0,307416722; 19=0,224830457; 20=0,096214657; 21=0,024288697; 22=0,003562779; 23=0,000292277; 24=0,000012534; 25=0; 26=0; 27=0; 28=0; 29=0; All numbers added = 1,015826482. I think you may need a different formula for the upper limit 15 are empty. $\endgroup$ – Simon Jul 28 '14 at 15:50
  • $\begingroup$ Ok, the right formula is in your link: probabilityandstats.wordpress.com/2010/04/04/…. In this case we need another formula: If there are exactly j empty cells, then the k balls are placed in the remaining n-j cells and these remaining n-j cells are all occupied. Great job! Thank you. $\endgroup$ – Simon Jul 28 '14 at 20:42
  • $\begingroup$ P(15)=0.0141 which explains why your sum is not 1. $\endgroup$ – Mr.Spot Jul 29 '14 at 3:39
0
$\begingroup$

I will assume the balls and boxes are indistinguishable.

The first problem is: If I distribute $15$ balls among $30$ boxes, what is the probability that at most $10$ boxes contain a ball?

First, the fact that there are $30$ boxes does not matter, since they are indistinguishable. So we only need to consider the problem as if there were $15$ boxes.

Second, we'll solve the problem by finding the probability that more than $10$ boxes contain a ball, and subtract that number from $1$.

There is exactly $1$ to occupy $15$ boxes with $15$ balls: $\{1,1,1\cdots\}$

There is also exactly $1$ way to occupy $14$ boxes with $15$ balls, since, again, the boxes are indistinguishable: $\{2,1,1\cdots\}$

There are $2$ ways to occupy $13$ boxes: $\{3,1,1\cdots\}$ or $\{2,2,1,1\cdots\}$

There are $3$ ways to occupy $12$ boxes, and $5$ ways to occupy $11$ (you can and should verify these numbers).

Finally, how many ways could we distribute $15$ balls over $15$ boxes? This number is exactly equal to $p(15)=176$, where $p(n)$ is the partition function.

So the answer to problem 1 is $1-(1+1+2+3+5)/176=164/176\approx93.2\%$

EDIT: I believe this answer is drastically different from the one obtained by your program for the following reason: you might have meant, in your problem statement, "what is the probability all $15$ balls are contained in $10$ particular boxes?" This significantly changes the question; in particular, the total number of boxes being $30$ is now relevant. Let me know if this is the misunderstanding.

$\endgroup$
  • 2
    $\begingroup$ There is no good reason to use a probability model in which all partitions are equally likely. A more natural model has us throwing the balls one at a time, with all $30$ boxes equally likely. $\endgroup$ – André Nicolas Jul 25 '14 at 20:14
  • $\begingroup$ Let us say we got 30 machines. Rob is telling you: "Hey ant11, we got 15 disruptions last year". Another guy says: "two machines had 3 disrupions, one machine had 2 disruptions and the other seven machines had 1 disruption. Ant11 you are good at maths. What do you think about this. If all machines would be indistinguishable, what chance it would have that only 10 machines had all 15 disruptions?" You think the solution should be easy. $\endgroup$ – Simon Jul 25 '14 at 20:23
  • 1
    $\begingroup$ Meanwhile you think about it, the boss comes and asks you:" Hey ant11, two machines got together 6 disruptions. That sounds like they will have many disruptions more next year. What is the chance if all 30 machines are indistinguishable, that they are more than 6 disruptions in only two machines. Maybe it was just bad luck." I think there are 30 boxes is relevant. $\endgroup$ – Simon Jul 25 '14 at 20:23
  • $\begingroup$ My last time i wrote a programm was two years ago. Maybe i made a mistake. Here you can see my solution: 1000000 tryed: 1-5: 0-times: 0,0% 6: 11-times: 0,0011% 7: 295-times:0,00295% 8: 3585-times: 0,3585% 9: 24383-times: 2,4383% 10: 96420-times: 9,6420% 11: 225081-times: 22,5081% 12: 307109-times: 30,7109% 13: 236556-times: 23,6556% 14: 92314-times: 9,2314% 15: 14246-times: 1,4246% $\endgroup$ – Simon Jul 25 '14 at 20:32
  • $\begingroup$ After that i added the numbers: 11+295+3585+24383+96420=124694. 124694/1000000=0,124694. --> 12,4694% 10 or less machines if all are indistinguishable $\endgroup$ – Simon Jul 25 '14 at 20:43

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.