Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

up vote 4 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.