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?
Expectation of the cardinality of the intersection of subsets
5
$\begingroup$
probability
discrete-mathematics
permutations
-
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
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$.
-
0Same. $ $ $ $ $ $ – 2011-09-07