# Probability of finding $m$ or more cells empty

I asked I question here trying to obtain clarification about how to follow a hint. In spite of the fine answers I received there, the hint doesn't look very helpful. I'd like to know a hint for the following problem or a way to use the hint I already have.

The probability $p_{m}(r,n)$ of finding exactly $m$ cells empty placing $r$ balls into $n$ cells is $$p_{m}(r,n)=\frac{1}{n^{r}}\binom{n}{m}A(r,n-m)=\binom{n}{m}\sum_{\nu=0}^{n-m}(-1)^{\nu}\binom{n-m}{\nu}\left(1-\frac{m+\nu}{n}\right)^{r}$$

From such probability, conclude that the probability $x_{m}(r,n)$ of finding $m$ or more cells empty equals

$$\binom{n}{m}\sum_{\nu=0}^{n-m}(-1)^{\nu}\binom{n-m}{\nu}\left(1-\frac{m+\nu}{n}\right)^{r}\frac{m}{m+v}$$

HINT: Evaluate $x_{m}(r,n)-p_{m}(r,n)$.

Without using the hint, I tried to find the pattern for $p_{m}$, $p_{m+1}$, etc with the goal of factoring each term and sum over something recognizable, but I couldn't find a way to factor the last term (for example, to factor $(n-m-1-\nu)^{r}$ into some terms including the original expression $(n-m-\nu)^{r}$...I don't think it is possible. Furthermore, I don't think that strategy is going to produce the answer I'm looking for.

-
What is $p_m(r,n)$? – Aryabhata Dec 28 '10 at 6:32
@Moron: I believe its the probability of finding exactly $m$ cells empty. – PEV Dec 28 '10 at 6:35
@Trevor: I see, it seems to match the page you linked in your answer too. – Aryabhata Dec 28 '10 at 6:48
@Moron: Trevor is right, however, the question is to find $x_{m}(r,n)$, that is, the probability of finding $m$ or more empty cells. – Robert Smith Dec 28 '10 at 6:55
@Robert: You also have to specify what $m$, $r$ and $n$ are, along with what the experiment is. Also, If $m=0$, the formula you have implies $x_m(r,n)=0$ and so the probability of $0$ or more cells being empty is $0$. That does not look right. – Aryabhata Dec 28 '10 at 7:03

See the following (Theorem 2). This gives the probability that exactly $m$ cells are empty. You could probably modify this to get the multiplicative factor $\frac{m}{m+v}$.

-
Curiously, I already knew that link. However, the problem asks for the probability of finding $m$ or more empty cells. The final expression from the link you mention is basically the starting point $p_{m}(r,n)$ in the original post. – Robert Smith Dec 28 '10 at 7:00

To use Feller's original notation. Let $E_m(r,n)$ be the number of distributions leaving exactly $m$ cells empty, then we have $$p_m(r,n)=n^{-r}\binom{n}{k}A(r,n-m)$$ as the corresponding probability ($A$ is to be defined)

Now, we need compute the probability $x_m(r,n)$ of finding $m$ or more cells empty.

Now, the probability that $m$ or more cells are empty is given by $x_m = p_m + p_{m+1} + \cdots + p_{n}$. Now, observe the reason why the hint was given: $x_{m+1} = x_m - p_m$ (i.e., $m+1$ or more cells being empty is the same as $\ge m$ cells being empty minus exactly $m$ cells being empty).

So for a sanity test, you could plug in the value of $x_m(r,n)$ given, and verify whether $x_{m}(r,n)-x_{m+1}(r,n)=p_m(r,n)$ holds (with the appropriate boundary cases).

The deeper underlying reason for this hint is that Feller probably wants you to figure out an inclusion-exclusion type argument. If I get time, I will write out the details. But the above should be a sufficiently detailed hint?

-
Thanks for your answered. Yes, I get the part $x_{m+1}=x_{m}-p_{m}$ (that's what I would have expected to obtain when I asked the simplification question in the other post). However, I don't know about 'inclusion-exclusion type' of argument (related to en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle ?). By the way, Moron noticed that $m=0$ produces $x_{0}(r,n)=0$ which is contradictory. – Robert Smith Dec 28 '10 at 22:42

I was working my way through Feller when I came across the same problem and tried googling the answer. This post was the first entry in the search.

You probably already figured it out by now that the equation given is probably the equation for the complementary event that fewer than m cells are empty.

Edit: I was wrong, tried it for 4 balls and 4 cells with m = 1. It didn't yield 24 as would be expected if it were the complementary function. I have no idea what the formula feller intended to put is.

edit 2: the formula works, it just doesn't work for m = 0 because you'll be dividing by zero for v=0. Just prove the formula by induction over m. Subtract the two summations and replace v-1 by a new summation.

-