Distribution of $n$ items among $k$ compartments (tennis game)

47 Views Asked by At

I'm having a little trouble solving this particular exercise.

Before a tennis game the referee randomly distributes $n$ tennis balls among $r$ ball boys with $n \geq r$. Though not precisely specified in the exericse, I assume we can number the ball boys. (evident from the $J \subseteq \{1,\ldots,r\}$ notation)

(a) For each $J \subseteq \{1,\ldots,r\}$, calculate the probability that all ball boys in $J$ do not get a tennis ball.

(b) Using (a) and the sieve formula (Inclusion–exclusion principle) show the probability that at least one ball boy receives no tennis ball is $$ \sum_{k=1}^r (-1)^{k-1} {r \choose k} \left( 1 - \frac{k}{r} \right)^n $$

For (a) my approach is as follows: Consider the example $n=10$ balls and $r=5$ ball boys and let $J = \{1,2,3\}$. Then we can imagine the following sequence $$ 0 0 0 k_1 k_2 $$ where each number from left to right represents the number of balls ball boy $i = 1, \ldots, 5$ receives with the additional condition that $k_1 + k_2 = 10$ and $k_1, k_2 > 0$. Using the stars and bars method we know that the number of possibilities for the above sequence is $$ {n-1 \choose r - |J| - 1} = {9 \choose 1} = 9 $$ and the probability is $$ \frac{{n-1 \choose r - |J| - 1}}{r^n} $$ Can somebody confirm this is right? Is $|\Omega|$ actually $r^n$ in this context? Am I overcomplicating this? The formula from (b) suggests so to me (somehow).

1

There are 1 best solutions below

1
On

The stars and bars method should never be used when computing probabilities. There is no plausible random process which would choose uniformly among the outcomes counted by stars and bars.

(Obvious exception: your random model is "the coach lists all the possible distributions of $n$ balls to $r$ ball boys, and selects one uniformly". That's not what's happening here.)

In this case, judging by the answer to (b), the coach independently assigns each ball to one of the $r$ ball boys. For one ball, the probability that none of the ball boys in the set $J$ get it is $1 - \frac{|J|}{r}$. So the overall probability is $(1 - \frac{|J|}{r})^n$.