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?

  • $\begingroup$ What does it mean for two permutations to be independent? And when you say "permutation", you just mean subset, right? (as it doesn't seem that the order of the elements is considered). And under what probability distribution are you asking for the expectation? $\endgroup$ – Gerry Myerson Sep 7 '11 at 4:24
  • $\begingroup$ @Gerry: I've come to assume that whenever someone says something like "random" or "independent" without specifying what they mean, they're implicitly referring to a distribution that's uniform in some natural way. But I agree it would be much preferable to specify that. $\endgroup$ – joriki Sep 7 '11 at 4:28
  • $\begingroup$ @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. $\endgroup$ – Narwe Sep 7 '11 at 14:00

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$.

  • $\begingroup$ Nicely done. ${}$ $\endgroup$ – Gerry Myerson Sep 7 '11 at 6:12
  • $\begingroup$ Same. $ $ $ $ $ $ $\endgroup$ – Did Sep 7 '11 at 8:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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