5
$\begingroup$

Let A be a set of n distinct elements, and let A' and A'' be independent permutations of A, where |A'| = |A''| = k. What is the expectation for |A' ∩ A''| for any given k <= n?

  • 0
    @Gerry Yes, I really just mean subset. I'd actually written the question originally without the use of the word 'permutation' at all, and then edited it in after reading some similar questions. My mistake. Also, as joriki suggested, I was thinking of a uniform distribution.2011-09-07

1 Answers 1

10

By linearity of expectation, the expectation value is $n$ times the probability that any given element of $A$ is in both sets. The probability for that is $(k/n)^2$, so the desired expectation value is $k^2/n$.

  • 0
    Same. $ $ $ $ $ $2011-09-07