1
$\begingroup$

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.

  • 0
    What is $p_m(r,n)$?2010-12-28
  • 0
    @Moron: I believe its the probability of finding exactly $m$ cells empty.2010-12-28
  • 0
    @Trevor: I see, it seems to match the page you linked in your answer too.2010-12-28
  • 0
    @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.2010-12-28
  • 0
    @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.2010-12-28
  • 0
    @Moron: I added what $m$, $r$ and $n$ are. You're right. It doesn't look right. To calculate the probability of finding $m$ or more cells empty should be $\sum_{m=0}^{n} p_{m}(r,n)$, right?2010-12-28
  • 0
    @Robert: Yes, you need to add the $p_m$s, that looks right.2010-12-28
  • 0
    @Moron: Alright, but that doesn't look (to me, at least) as a closed form. Almost every term depends on $m$ and most of these terms depend on $\nu$ also.2010-12-28
  • 0
    @Robert: Yes, I was only confirming your $\sum_{m=0}^{n} p_m(r,n)$. Looks like your source (I am guessing a book) has the formula for $x_m(r,n)$ wrong, as it seems to give incorrect result for $m=0$. You are right, that is not closed form.2010-12-28
  • 0
    @Moron: Yes, it could be wrong. The source is Feller's book 'An Introduction to Probability Theory and its applications'. Do you think I should ask for a closed form to such a problem? (taking for granted that the proposed answer is wrong).2010-12-28
  • 0
    @Robert: Maybe it is just a typo. Does the book have an errata? Asking for a closed might get you no answers, as it might be a hard problem.2010-12-28
  • 0
    @Moron: To my knowledge, no. There is just an errata for the second edition, but that doesn't help. The one I'm reading is the third edition. Oh, damn. I hate to leave problems unresolved.2010-12-28

2 Answers 2