# Expected coverage of a set of random samples

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?

• 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? – Glen_b Jul 17 '14 at 17:09
• 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)? – Glen_b Jul 17 '14 at 17:12
• 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. – mossaab Jul 17 '14 at 17:14
• 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. – mossaab Jul 17 '14 at 17:24
• 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? – 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$