I wasn't expecting that .......

Probability Level 5

Suppose we have $8$ distinct containers and $8$ indistinguishable balls. The balls are then distributed into the containers such that the distribution is uniform across all possible events. That is, each distribution $(a_{1},a_{2},a_{3},a_{4},a_{5},a_{6},a_{7},a_{8})$ of balls, where $a_{n}$ is the number of indistinguishable balls in the $n$ th container such that $\sum_{n=1}^8 a_{n} = 8$ , is equally likely to occur.

The expected number of containers that have at least one ball in them is $\frac{a}{b}$ , where $a$ and $b$ are positive coprime integers. Find $a + b$ .

The answer is 79.

1 solution

Brian Charlesworth
Aug 6, 2014

To start with, we have that the total number of ways of distributing the balls into the containers is the same as the number of non-negative integer solutions to the equation $a + b + c + d + e + f + g + h = 8$ . This is a 'stars and bars' calculation with solution $\binom{15}{8} = 6435$ .

(See here for a discussion on the 'stars and bars' method: link )

Next, we need to find the weighted average of the number of containers that end up containing at least one ball. To do this, we need to find the number of instances where $k$ containers, for $1 \le k \le 8$ , end up containing at least one ball.

As an example, suppose we are making the calculation for $k = 3$ . We first choose $3$ containers in one of $\binom{8}{3}$ ways. Without loss of generality let these be containers $a, b$ and $c$ . Then we are wanting to find the number of positive integer solutions to the equation $a + b + c = 8$ , which according to the aforementioned link has the solution $\binom{7}{2} = 21$ .

To then find the weighted average of the number of containers that end up containing at least one ball we determine

$\sum_{k=1}^{8} (k * \binom{8}{k} * \binom{7}{k-1})$ ,

and then divide this by $\binom{15}{8}$ . Doing this, we end up with the fraction $\frac{27456}{6435} = \frac{64}{15}$ , giving us $a = 64, b = 15$ and thus $a + b = \boxed{79}$ .

An easier approach would be to use indicator variables, which is often my favorite approach to counting such "convoluted" variables that require something like a Principle of Inclusion and Exclusion counting argument.

Let $I$ be the random variable of the number of urns that are filled.
Let $I_i$ be the indicator variable that the ith urn is filled.
We have $I = \sum I_i$ , and hence by the linearity of expectation, $E(I) = \sum E(I_i)$ .

From stars and bars, we know that the ith urn is empty in ${ 7 + 8 - 1 \choose 7-1 }$ cases, out of a total of ${ 8 + 8 - 1 \choose 8 -1 }$ cases.
Hence $E ( I_i) = 1 - \frac { 14 \choose 6 } { 15 \choose 7 } = \frac{8}{15}$ .
Hence, $E(I) = 8 \times E(I_i ) = \frac{ 64} { 15}$ .

Calvin Lin Staff - 6 years, 6 months ago

Great method! I'm just wondering about the last two lines, though. Since $I$ and $I_{i}$ track empty urns, would it not be that

$E(I_{i}) = \dfrac{\frac{14}{6}}{\frac{15}{7}} = \frac{7}{15}$

$\Longrightarrow E(I) = 8 * E(I_{i}) = \frac{56}{15}$ .

Then the expected number of urns with at least one ball would be

$8 - E(I) = 8 - \frac{56}{15} = \frac{64}{15}$ .

Brian Charlesworth - 6 years, 6 months ago

Right. I changed my definition halfway (from empty to filled), but forgot to update it. I've made the corresponding edit.

Calvin Lin Staff - 6 years, 6 months ago

Why is the probability that the $i$ th urn is empty not $(1-\frac{1}{8})^8$ ?

Abhishek Sinha - 6 years, 6 months ago

Thanks. Those who previously answered $8^8-7^8+8^7 =13109567$ have been marked correct, due to the phrasing of the question.

Calvin Lin Staff - 6 years, 6 months ago

@brian charlesworth In this question, the probability space is not defined clearly. I was looking at your solution and I saw that the distribution you used is "uniform across all possible events". This means that $(8,0,0,0,0,0,0,0,0)$ is as equally likely to occur as $(1,1,1,1,1,1,1,1)$ .

However, if the balls were distributed randomly, then the latter event is $8!$ times more likely to occur. In this scenario, the probability that the ith urn is empty would be $(\frac{ 7}{8} ) ^ 8$ .

Can you clarify this in the question?

Calvin Lin Staff - 6 years, 6 months ago

@Calvin Lin – @Calvin Lin Sigh.... Darn. I've made this particular mistake more often than I'd care to admit. I've adjusted the wording to fit my solution and final answer. Hopefully this will clarify matters. I'm surprised that it took 304 views, 73 attempts and 25 solvers before this ambiguity was caught.

I'm sorry for the oversight. Hopefully I won't make the same mistake again, (probably wishful thinking, but ......).

Brian Charlesworth - 6 years, 6 months ago

I wasn't expecting that .......

The answer is 79.

1 solution

0 pending reports