1

I have a bowl of $n$ balls numbered $1$ to $n$. I will perform $k$ extractions (with immediate replacement into the bowl after extraction). I want to calculate the probability to have extracted each ball at least once after those $k$ turns.

With inclusion/exclusion principle from Probability to see all 6 numbers on a die after n throws for example, I arrived at:

$$P(n, k) = \sum_{i=1}^{n} (-1)^{n-i} \binom{n}{i} i^k \frac{1}{n^{k}}$$

But this takes forever to calculate for something like $n=50$, $k=1000$. Can I further simplify this equation? Is the equation even correct?

integralette
  • 143
  • do you mean : " $k$ extractions with replacement (upon each extraction)"? – G Cab Nov 28 '19 at 19:49
  • well, it makes more clear that you are are extracting one ball and put it back before extracting the next. You could extract two or three , etc. balls before restoring them, although from the rest of the statement it is clear that $n \le k$ – G Cab Nov 28 '19 at 20:02
  • @GCab Thanks :) I tried to improve the question text. Is that what you meant? – integralette Nov 28 '19 at 20:33
  • yes, now it is more clear – G Cab Nov 28 '19 at 22:50

1 Answers1

2

Your formula is correct. It can't be further simplified, except perhaps by expressing it in terms of the Stirling numbers of the second kind:

$$ \def\stir#1#2{\left\{#1\atop#2\right\}} P(n,k)=\frac{k!}{n^k}\stir kn\;. $$

There are other ways to calculate this probability (for instance by keeping track of the probability distribution over the number of distinct balls seen and updating it $k$ times), but I'd be surprised if any of them took less than the $O(kn)$ steps that evaluating your equation takes.

joriki
  • 238,052