Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
Is this a homework question? If yes, then what did you try? –  Dennis Gulko Jul 16 '12 at 17:02
    
Hi, Dennis. It is not a homework question. It is an interesting problem I encountered in my research of randomized algorithm. –  Jin Teng Jul 16 '12 at 17:06
    
In that case, do you want me to elaborate some more on my answer, or you can continue from it by yourself? –  Dennis Gulko Jul 16 '12 at 17:11
    
First thanks for your help. Yes, please, can you show me some more details? –  Jin Teng Jul 16 '12 at 17:18
add comment

1 Answer

up vote 1 down vote accepted

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<...<i_j\leq N}|A_{i_1}\cap...\cap A_{i_j}|$$ 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.

share|improve this answer
    
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? –  Jin Teng Jul 16 '12 at 17:57
    
The order of the rounds also doesn't matter? –  Dennis Gulko Jul 16 '12 at 18:01
    
No, it doesn't. Sorry that I have not made it clear. –  Jin Teng Jul 16 '12 at 18:03
    
@Jin Teng: This time I covered all possible options :-) –  Dennis Gulko Jul 16 '12 at 18:48
    
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. –  Jin Teng Jul 16 '12 at 19:33
show 2 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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