Average intersection size

Question

I have a set of K elements randomly taken N at a time M times; and I want to know the expected average intersection size. How can I do this?

Answer 1

If I understand the question correctly, you want to know the expected cardinality of the intersection of the $M$ sets. Let the $K$ elements be $x_1,x_2,\dots,x_K$ and for $i=1,2,\dots,K,$ let $X_i$ be a random variable which is $1$ if $x_i$ is in the intersection and $0$ if it is not. Then we want to compute $$E\left(\sum_{i=1}^KX_i\right)=\sum_{i=1}^KE(X_i)$$ by linearity of expectation.

Take it from here.

Answer 2

Hint: The $M$ times does not matter, just consider a pair of subsets. What is the probability that one element in the first subset is in the second subset? The expected overlap is the sum of this over all the elements, which is just $K$ times the chance for one element.