2
$\begingroup$

Suppose there is a set S of 1000 elements. Given sets A, B, C, D are subset of S and of cardinality 200, 300, 400, 500 respectively. Suppose further that A,B,C,D are made by drawing elements uniformly and independently from S. What is the expected size of $A\cup B\cup C\cup D$?

I calculated it as follow: take the 200 elements from A, then it covers 20% of S. We can expect 80% of B are not covered. So we have (200+0.8*300)=440 from $A\cup B$. Arguing this way, I got the expected size of $A\cup B\cup C\cup D$ is 832.

Am I right? Can anyone give a formal proof for this?

1 Answers 1

4

The probability that a particular arbitrary element is not selected in the four tries (assuming they are independent) is given by

$(1-\frac{200}{1000})\times(1-\frac{300}{1000})\times(1-\frac{400}{1000})\times(1-\frac{500}{1000})= \frac{8}{10} \frac{7}{10}\frac{6}{10}\frac{5}{10} = 0.168$

Then the probability that it is selected in some try is $p=1-0.168=0.832$

Let $X_k$ be a random variable taking value 1 if the element $k$ was selected, $0$ otherwise. Then, $E(X_k)= p$.

Let $Z = \sum X_k$; then, $E(Z) = \sum E(X_k) = 1000 \; p = 832$ . But $Z$ is just the size of $A\cup B\cup C\cup D$. Thus, we get your result.