I'm going to try to rewrite my question in a better way:

I have a set of $N$ boxes, and one of those boxes is filled. I sample the boxes with uniform probability and without replacement until I find the filled box. What is the mean and variance for the number of empty boxes I've opened? For example, if $N = 2$, and I open two boxes to find the full box, I've opened one empty box.

My guess is that I need to open $\mu = \frac{N}{2}$ boxes to find the full box. Thus, I need to open $\frac{N}{2}-1$ empty boxes prior to opening the full box. However, because each trial depends on the next, I don't know how to calculate the variance?

I suppose I'd like something like the negative binomial distribution, but where we're sampling without replacement?

Update: Byron Schmuland answers the first part of my question here: Expectation of number of trials before success in an urn problem without replacement

We just need to recast my empty boxes as "red" balls and my full box as a "blue" ball, and ask how many red balls we need to draw before we draw a "blue" ball. However, how might we calculate the variance?

  • $\begingroup$ I would not "use the hypergeometric distribution", rather I would note that the number of empty boxes one must open before finding the filled box is uniformly distributed on 0..N. $\endgroup$ – Did May 5 '13 at 20:29
  • $\begingroup$ Mean: look better. Variance: try. $\endgroup$ – Did May 5 '13 at 21:02
  • $\begingroup$ If $X$ is uniformly distributed on $\{0,1,\ldots,N\}$, what is $E[X]$, say, when $N=2$? Is it $\frac{N+1}2-1$? $\endgroup$ – Did May 5 '13 at 21:34
  • $\begingroup$ Quote: the number of empty boxes I need to open. There are $N$ empty boxes hence $X=N+1$ is impossible. $\endgroup$ – Did May 5 '13 at 21:38
  • $\begingroup$ Why do you erase your comments after I answered them? Why do you modify your post after it was discussed in the comments? Such a heavy (and silent) rewriting is not how the site is supposed to function. $\endgroup$ – Did May 6 '13 at 5:07

Each box is equally likely to be the filled box, so the number of empty boxes opened before you open the fill box is uniformly distributed from $0$ to $N-1$. Thus the expected number of empty boxes opened is $(N-1)/2$, and the variance is

$$ \frac1N\sum_{k=0}^{N-1}k^2-\left(\frac{N-1}2\right)^2=\frac16\frac{(N-1)N(2N-1)}N-\left(\frac{N-1}2\right)^2=\frac{N^2-1}{12}\;. $$

  • $\begingroup$ The variance should be the same for the total number of boxes opened, right? $\endgroup$ – Jack May 5 '13 at 22:38
  • $\begingroup$ @Jack: Yes, only the mean is shifted by $1$ in that case. $\endgroup$ – joriki May 5 '13 at 22:42
  • $\begingroup$ Sorry, one more question if you have the time - how might the mean and variance change if we had multiple filled boxes in the population? $\endgroup$ – Jack May 5 '13 at 22:49
  • 1
    $\begingroup$ @Jack: On your first comment: No, I don't think there's much of a connection there. On your second comment: That's slightly more complicated; I suggest to ask that in a question of its own. $\endgroup$ – joriki May 5 '13 at 22:51

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.