A random function $rand()$ return a integer between $1$ and $k$ with the probability $\frac{1}{k}$. After $n$ times we obtain a sequence $\{b_i\}_{i=1}^n$, where $1\leq b_i\leq k$. Set $\mathbb{M}=\{b_1\}\cup\{b_2\}\cdots \cup\{b_n\}$, $\mathbb{N}=\{b_1\}\cup\{b_2\}\cdots \cup\{b_{n-1}\}$,

I want to calclute the probability satisfy the following condition:

$\mathbb{M}=\{1, 2\cdots, k\}$ and $\mathbb{N}\neq\{1, 2\cdots, k\}$.

Denoting the probality with $P(n)$. If $1\leq n< k$, then $P(n)=0$. $P(n)=?$, where $n\geq k$.


The probability that $j$ of the $k$ numbers is excluded is $(1-j/k)^n$ and there are $\binom{k}{j}$ ways to choose those $j$ to be excluded. The generalized inclusion-exclusion principle says that the probability that exactly one of the $k$ numbers is excluded after $n-1$ trials is $$ \sum_{j=1}^k(-1)^{j-1}j\binom{k}{j}\left(1-\frac{j}{k}\right)^{n-1} =k\sum_{j=1}^k(-1)^{j-1}\binom{k-1}{j-1}\left(1-\frac{j}{k}\right)^{n-1} $$ Then the probability to pick the right one to finish on trial $n$ is $1/k$. Thus, the probability that you've just finished on trial $n$ is $$ \sum_{j=1}^k(-1)^{j-1}\binom{k-1}{j-1}\left(1-\frac{j}{k}\right)^{n-1} $$

Another method

In this answer, it is shown that the probability of still having at least one of the $k$ numbers excluded is $$ \sum_{j=1}^k(-1)^{j-1}\binom{k}{j}\left(1-\frac{j}{k}\right)^n $$ Subtracting from $1$, we get that the probability of getting all $k$ numbers by trial $n$ is $$ \sum_{j=0}^k(-1)^j\binom{k}{j}\left(1-\frac{j}{k}\right)^n $$ To get the probability that we get all $k$ numbers on trial $n$, take the difference between this for $n$ and $n-1$: $$ \begin{align} &\sum_{j=0}^k(-1)^j\binom{k}{j}\left[\left(1-\frac{j}{k}\right)^n-\left(1-\frac{j}{k}\right)^{n-1}\right]\\ &=\sum_{j=0}^k(-1)^{j-1}\binom{k}{j}\frac{j}{k}\left(1-\frac{j}{k}\right)^{n-1}\\ &=\sum_{j=1}^k(-1)^{j-1}\binom{k-1}{j-1}\left(1-\frac{j}{k}\right)^{n-1} \end{align} $$


Hint: to succeed, $\Bbb N$ has to be missing exactly one element and $b_n$ has to be that element.

  • $\begingroup$ Tks very mach. I think this hint so public knowlegde. For express the problem more clearly, I discribe it as above. $\endgroup$ – Yuansheng liu Apr 21 '13 at 0:53
  • $\begingroup$ @Yuanshengliu: many of our posters would not have seen that, so it would have been helpful for them. Do you have any thoughts on calculating the probability that $|\Bbb M|=k-1$? I have a recurrence approach for specific $k$, but nothing to offer for general $k$. $\endgroup$ – Ross Millikan Apr 21 '13 at 2:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.