|
2 |
edited tags
|
||
|
1 |
|
||
How many trial picks expectedly sufficient to cover a sample space?Consider a sequence of independent events where an $r$ element subset of an $n$ element set is picked uniformly randomly (ie. any of the $\begin{pmatrix}n\newline r\end{pmatrix}$ possibilities being equally likely). What is the expected number of subsets one has pick to cover the whole set? Here the terminology means: a sequence of picks $A_1,A_2,\ldots,A_n$ covers the whole set if $|A_1 \cup \cdots \cup A_n| = n$. A sequence $A_1, A_2,\ldots$ succeeds to cover the whole set in $n$ steps, if $A_1,\ldots,A_n$ covers the whole set but $A_1,\ldots, A_{n-1}$ does not. The expected numbers seems to be much higher than one would imagine. But I could not quite come up with a closed form. But chances are, its always a rational number.
|
||||

