expected value for the number of elements in difference of a random subset and a fixed subset

195 Views Asked by At

I have a set $X=\{1,...,n\}$. Let $A\subseteq X$ be a fixed subset with $|A|=m$. Now, I select $m$ values with replacement from $X$. Let $B$ denotes this random subset and $|B|$ be the random variable for the number of distinct elements in $B$. What is the expected value for the number of distinct elements in $B−A$? Is this true that $$E(|B−A|)=E(|B|)(1−\frac{m}{n})?$$

1

There are 1 best solutions below

5
On BEST ANSWER

The probability that a fixed element is in $B$ is $p=1-(1-1/n)^m$. So the expectation of $|B|$ is $n$ times this $np$ (linearity of expectation). There are $m-n$ elements outside $A$ so the expectation of $|B-A|$ is $(m-n)p$ (linearity of expectation again).