2
$\begingroup$

A combinatorics problem:

There are $N$ balls in total, in every round we randomly pick without replacement $n$ balls ($n < N$), after $k$ rounds, what is the probability that all the $N$ balls are picked at least once? After each round, all the picked balls are placed back into the set. Both the order of ball picking in each round and the order of the $k$ rounds do not matter.

  • 0
    Is this a homework question? If yes, then what did you try?2012-07-16
  • 0
    Hi, Dennis. It is not a homework question. It is an interesting problem I encountered in my research of randomized algorithm.2012-07-16
  • 0
    In that case, do you want me to elaborate some more on my answer, or you can continue from it by yourself?2012-07-16
  • 0
    First thanks for your help. Yes, please, can you show me some more details?2012-07-16

1 Answers 1

1

You can use the inclusion–exclusion principle to count the number of ways to do the $k$ rounds so that each ball is picked at least once:
Denote by $X$ the set of all $k$-rounds without restrictions and denote by $A_i$ the set of all the $k$-rounds in which $i$-th ball isn't picked. We are looking for $e_0=|X\setminus(A_1\cup...\cup A_N)|$.
Denote $$s_0=|X|=\binom{\binom{N}{n}+k-1}{k}, \hspace{10pt} s_j=\sum_{1\leq i_1<... We have $$|A_i|=\binom{\binom{N-1}{n}+k-1}{k}, \hspace{10pt} s_1=\binom{N}{1}\binom{\binom{N-1}{n}+k-1}{k}$$ Since each time we picked $n$ balls out of $N-1$ (since we excluded the $i$-th), and we did this $k$ times, i.e. we count $k$-multisubsets of a set with $\binom{N-1}{n}$ elements.. To get $s_1$, we need to choose the $i$ and then multiply by the size of $A_i$, since the size of $A_i$ does not depend on $i$.
Similarly, $$|A_i\cap A_j|=\binom{\binom{N-2}{n}+k-1}{k}, \hspace{10pt} s_2=\binom{N}{2}\binom{\binom{N-2}{n}+k-1}{k}$$ Since we have to exclude two balls now. Continue in the same fashion to get: $$s_j=\binom{N}{j}\binom{\binom{N-j}{n}+k-1}{k}$$ Be the inclusion–exclusion principle, we have: $$e_0=\sum_{j=0}^N (-1)^js_j=\sum_{j=0}^N (-1)^j\binom{N}{j}\binom{\binom{N-j}{n}+k-1}{k}$$ Then the probability you were looking for is $\frac{e_0}{|X|}$.

Remark: Observe that the sum runs up to $N$. It is possible that you won't have enough balls at some point, but the binomial coefficient will vanish once $n>N-j$, so there is no need to fix the summation limits.

  • 0
    Good attempt! Let me first clarify on two points. First, the order in each round does not matter. Second, the order of the ball sets selected for $k$ rounds does not matter. So the real challenge in this problem is the asymmetry between no replacement in each round and replacement between rounds. You use permutation between rounds instead of combination. I am not sure if it is correct. What do you think?2012-07-16
  • 0
    The order of the rounds also doesn't matter?2012-07-16
  • 0
    No, it doesn't. Sorry that I have not made it clear.2012-07-16
  • 0
    @Jin Teng: This time I covered all possible options :-)2012-07-16
  • 0
    You are really helpful and your approach is inspiring. But still a small problem: there are duplications in $s_1$, $s_2$... Take $s_1$ for example, you may end up choosing the same set of elements when you rule out the first element and when you rule out the second element.2012-07-16
  • 0
    What I am thinking is that your very first attempt might be correct. After all, combinations are a special type of permutations. Do you think it is correct to say $\frac{# of valid combinations}{# of all combinations}=\frac{# of valid permutations}{# of all permutations}$?2012-07-16
  • 0
    @Jin Teng: "still a small problem: there are duplications..." - that's the whole point of inclusion–exclusion! if there where no intersections, the whole sum would be just in one step! read more about it in wikipedia (I gave a link to the relevant page in the answer). About my *answers*: the first was the **correct** answer in case when the order of the rounds **is important**. The current is **correct** assuming the order of rounds is **not important**.2012-07-16