3
$\begingroup$

There are $30$ buckets. John throws $20$ balls, each time landing uniformly among the buckets. What is the probability that no bucket contains $\geq 3$ balls?

If the question were $\geq 2$ balls, we could calculate the probability that each bucket has at most $1$ ball, which is $\dfrac{29}{30}\dfrac{28}{30}\cdot\dfrac{11}{30}$.

$\endgroup$
  • 2
    $\begingroup$ The probability to have each bucket at most 1 ball is far less that you do here. It is $(30)_{20}\cdot 30^{-20}$. $\endgroup$ – Masacroso Oct 19 '14 at 23:28
  • 2
    $\begingroup$ @Masacroso I apologize for such a petty question, but what does the notation $(30)_{20}$ denote? $\endgroup$ – Kye W Shi Oct 20 '14 at 3:18
  • 1
    $\begingroup$ Generally it denotes de falling factorial @KyeWShi. It seems, in the question, that the OP said the same in a rare manner using just a point. $\endgroup$ – Masacroso Oct 20 '14 at 11:01
2
$\begingroup$

You must to know the probability for at most a pair of balls in some bucket. For this you must calculate the probabilities for the different distributions with some pair.

For a pair and isolated balls the probability will be $P_2(1)=\frac{(30)_{19}}{30^{20}}\sum_{k=1}^{19} k=\frac{(30)_{19}(20)_2}{30^{20}2}$.

For two pairs and isolated balls $$P_2(2)=\frac{(30)_{18}}{30^{20}}\sum_{k=1}^{18} k\left(\sum_{j=1}^{k-1}j\right)=\frac{(30)_{18}}{30^{20}2}\sum_{k=2}^{18} k^2(k-1)$$

In general

$$P_2(h)=\frac{(30)_{20-h}}{30^{20}}\sum_{k_1=1}^{20-h}k_1\sum_{k_2=1}^{k_1-1}k_2\sum_{k_3=1}^{k_2-1}k_3\sum...;\ \#\{k_i\}=h\in[0,10]_{\Bbb N}$$

We can continue the same for any amount of pairs to the maximum of 10 and after sum all to know the probability to at most pairs, i.e. $P_2=\sum_{h=0}^{10}P_2(h)$. The problem is that this lead to very ugly equations with sums of powers (i.e. need of Falhauber formula and Bernoulli numbers).

You can try to compute this in a CAS or try a Monte-Carlo simulation.

EDIT: an alternative approach maybe evaluate the total number of possible distributions of 20 in 30 positions and after divide the numbers of ways of distribute using at most pairs by this total.

This can be done calculating the coefficient for 20 of this generating function that represent choosing between 0 and 20 balls for every position of 30 different positions

$$f(x)=(1+x+x^2+...+x^{20})^{30}=\left(\sum_{k=0}^{20}x^k\right)^{30}=\left(\frac{1-x^{21}}{1-x}\right)^{30}=\\=\sum_{k=0}^{30}(-1)^k\binom{30}{k}x^{21k}\sum_{j=0}^{\infty}\binom{29+j}{j}x^j$$

The coefficient of 20 is when $20=21k+j\to (k=0) \to j=20$ i.e. the total of different distributions of 20 balls in 30 places is $T=\binom{49}{20}$.

Now I need to know the number of different ways to distribute 20 balls on 30 positions where at most it will be 2 balls in a bucket, i.e., the permutations of three groups: groups of pairs, groups of isolated balls and group of voids buckets. They are

$$C_2=\sum_{k=0}^{10}\binom{30}{10+k,20-2k,k}$$

So from this we have that $1-\frac{C_2}{T}$ is the answer to the question.

EDIT 2: it seems that there is a mistake somewhere because if I evaluate the probability for isolated balls from one approach or the other the number is different. I mean

$$\frac{(30)_{20}}{30^{20}}\neq \frac{(30)_{20}}{(49)_{20}}$$

$\endgroup$
-4
$\begingroup$

Hint:

You could have 20 buckets with 1 ball

or 18 buckets with 1 ball and 1 bucket with 2 balls

or 16 buckets with 1 ball and 2 buckets with 2 balls

etc. Sum it up like in any probability question.

EDIT:
I don't see what's wrong with what I have above. The answer I am pointing out is $$\frac{\sum\limits_{k=0}^{10}\left(\matrix{30\\k}\right)\left(\matrix{30-k\\20-2k}\right)}{\left(\matrix{30+20-1\\ 20}\right)}$$

EDIT 2: For the isolated balls we just need to choose which of the 20 bins to put a ball in, it is simple inclusion-exclusion, so the answer is $$\frac{30\choose 20}{49\choose 20}$$

EDIT 3: I have just written a program to calculate these numbers and have numerically verified that my above reasoning is correct

(define (fact a)
  (if (= a 0) 1
      (* a (fact(- a 1)))))

(define (choose a b)
  (/ (fact a)
     (* (fact b) (fact (- a b)))))

(define (sum a b f)
  (if (= a b) (f a)
      (+ (f a) (sum (+ 1 a) b f))))

(define (how a b n)
  (if (= n 1) (choose a b)
              (sum 0 (floor (/ b n))
                     (lambda (c) (* (choose a c) 
                                    (how 
                                      (- a c)
                                      (- b (* c n))
                                      (- n 1)))))))

Here are the results that verify correctness:

> (choose 49 20)
28277527346376

> (how 30 20 20)
28277527346376


> (- (choose 49 20) (how 30 20 20))
0

as far as the original question

> (how 30 20 2)
1514286194715

> (/ (how 30 20 2) (choose 49 20))
0.0535508701367790686046560...
$\endgroup$
  • 4
    $\begingroup$ wog, I've edited your answer to remove the rant at the end. It was attracting more downvotes. In the future, I'd suggest leaving rants out of your posts as they only attract negative attention. $\endgroup$ – Andy Oct 20 '14 at 15:39

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.