For a set A, I'm running 8 independent random samples, each with a probability of 1/8=12.5% and is without replacement. I know that the set formed by the union of these 8 samples will be of a size between 12.5% and 100%.

Is there an expected value for the size of this union?

  • $\begingroup$ Yes, and it's easily calculated. But since this is routine bookwork, I have to wonder if this is for a class or something similar. How does this question arise? $\endgroup$
    – Glen_b
    Jul 17 '14 at 17:09
  • 1
    $\begingroup$ Hint (which I will expand on in an answer if you seem to catch on): What happens when you work out the expected size of the complement (the fraction that isn't covered by your samples)? $\endgroup$
    – Glen_b
    Jul 17 '14 at 17:12
  • $\begingroup$ This has nothing to do with class. I'm just sampling tweets from Twitter, and I want to estimate how many parallel streams I need to run to reach some target of coverage. $\endgroup$
    – mossaab
    Jul 17 '14 at 17:14
  • $\begingroup$ My intuition says that in the first sample I'll get 12.5%, in the second 12.5% - (12.5% * 12.5%) and so on. $\endgroup$
    – mossaab
    Jul 17 '14 at 17:24
  • $\begingroup$ When you take each 12.5% sample, is the sampling with replacement or not? Could you get the same thing twice? Also, if possible, what's the size of the total pool? $\endgroup$
    – Glen_b
    Jul 17 '14 at 21:31

If each 12.5% sample is without replacement, then the proportion sampled is $1-(1-1/8)^8$:

The first sampling omits $0.875$ of the total

The second sampling omits $0.875$ of the remainder

The third sampling omits $0.875$ of the remainder

and so on.

The proportion not covered in 8 samplings will be on average $0.875^8$.

Hence the proportion covered will be on average $1-0.875^8=0.6564$.

In general, if you do $k$ samplings of size $n/k$, then as long as $k$ is not too small, the coverage will be close to $1-1/e \approx 0.632$


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.