How many trial picks expectedly sufficient to cover a sample space? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T15:39:10Z http://mathoverflow.net/feeds/question/13171 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/13171/how-many-trial-picks-expectedly-sufficient-to-cover-a-sample-space How many trial picks expectedly sufficient to cover a sample space? amaanush 2010-01-27T19:52:44Z 2010-01-28T00:59:04Z <p>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).</p> <p>What is the expected number of subsets one has pick to cover the whole set?</p> <p>Here the terminology means: a sequence of picks $A_1,A_2,\ldots,A_n$ <em>covers the whole set</em> 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.</p> <p>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.</p> http://mathoverflow.net/questions/13171/how-many-trial-picks-expectedly-sufficient-to-cover-a-sample-space/13184#13184 Answer by Tal K for How many trial picks expectedly sufficient to cover a sample space? Tal K 2010-01-27T20:41:56Z 2010-01-27T20:51:26Z <p>This process will cover the set faster than making $r$ random selections of a single element at each step ("sampling with replacement", producing a multiset of $r$ not-necessarily-distinct elements instead of a set of $r$ distinct elements). The latter is taking $r$ steps at a time in the Coupon Collector process which takes $n * log(n)$ steps. So we need at least $(n/r) * log(n)$ steps on average. This should be a close approximation when $n/r$ is large and within a bounded (not necessarily constant) factor of the truth when $n/r$ is bounded. The case when $n=2r$ is close to the "20 questions" problem of Erdos and Renyi.</p> http://mathoverflow.net/questions/13171/how-many-trial-picks-expectedly-sufficient-to-cover-a-sample-space/13186#13186 Answer by Zev Chonoles for How many trial picks expectedly sufficient to cover a sample space? Zev Chonoles 2010-01-27T20:47:38Z 2010-01-27T21:22:12Z <p>EDIT: While the $r=1$ case is the easiest, I thought it would be helpful to work it out anyway. I get that the expected number of picks necessary for $r=1$ is $nH_n$, where $H_n$ is the $n$th harmonic number, which is in line with Tal K's answer since $H_n\approx\ln(n)$.</p> <p>Suppose the total number of elements covered by our picks so far is $k$. If we calculate the expected number of picks it will take to get to $k+1$, then we simply take the sum of our result from $k=0$ to $k=n-1$. There are $n-k$ elements we still need to hit, so there is an $\frac{n-k}{n}$ probability of having $k+1$ covered after 1 pick, $\frac{n-k}{n}(\frac{k}{n})$ probability of having $k+1$ covered after exactly 2 picks, and in general $\frac{n-k}{n}(\frac{k}{n})^j$ probability of going to $k+1$ after exactly $j$ picks. Thus, the expected number of picks to go from $k$ covered to $k+1$ covered is $(\frac{n-k}{n})\sum_{j=1}^\infty k(\frac{k}{n})^{k-1}$, which by the standard derivative trick we know is $(\frac{n-k}{n})\frac{1}{(1-\frac{k}{n})^2}=\frac{n}{n-k}$. Thus the expected number of picks of 1 element subsets necessary to cover an $n$ element set is $\sum_{k=0}^{n-1}\frac{n}{n-k}=n\sum_{k=1}^n\frac{1}{k}=nH_n$.</p> http://mathoverflow.net/questions/13171/how-many-trial-picks-expectedly-sufficient-to-cover-a-sample-space/13217#13217 Answer by Douglas Zare for How many trial picks expectedly sufficient to cover a sample space? Douglas Zare 2010-01-28T00:52:01Z 2010-01-28T00:59:04Z <p>The expected number of picks needed equals the sum of the probabilities that at least $t$ picks are needed, which means that $t-1$ subsets left at least one value uncovered. We can use inclusion-exclusion to get the probability that at least one value is uncovered.</p> <p>The probability that a particular set of $k$ values is uncovered after $t-1$ subsets are chosen is </p> <p>$$\Bigg(\frac{n-k \choose r}{n \choose r}\Bigg)^{t-1}$$</p> <p>So, by inclusion-exclusion, the probability that at least one value is uncovered is </p> <p>$$\sum_{k=1}^n {n \choose k}(-1)^{k-1}\Bigg(\frac{n-k \choose r}{n \choose r}\Bigg) ^{t-1}$$</p> <p>And then the expected number of subsets needed to cover everything is </p> <p>$$\sum_{t=1}^\infty \sum_{k=1}^n {n \choose k}(-1)^{k-1} \Bigg(\frac{n-k \choose r}{n \choose r}\Bigg)^{t-1}$$</p> <p>Change the order of summation and use $s=t-1$:</p> <p>$$\sum_{k=1}^n {n \choose k}(-1)^{k-1} \sum_{s=0}^\infty \Bigg( \frac{n-k \choose r}{n \choose r}\Bigg)^s$$</p> <p>The inner sum is a geometric series.</p> <p>$$\sum_{k=1}^n {n \choose k} (-1)^{k-1}\frac{n \choose r}{{n \choose r}-{n-k \choose r}}$$ </p> <p>$${n \choose r} \sum_{k=1}^n (-1)^{k-1}\frac{n \choose k}{{n \choose r}-{n-k \choose r}}$$</p> <p>I'm sure that should simplify further, but at least now it's a simple sum. I've checked that this agrees with the coupon collection problem for $r=1$.</p> <p>Interestingly, Mathematica "simplifies" this sum for particular values of $r$, although what it returns even for the next case is too complicated to repeat, involving EulerGamma, the gamma function at half-integer values, and PolyGamma[0,1+n].</p>