Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have a set $S$ of $n$ elements. I select $r$ elements from the set $E_1, E_2, E_3, \ldots, E_r$ that may not be all distinct. I select again $r$ elements from the set $F_1,F_2,F_3,\ldots, F_r$ in a similar manner.

What is the probability $P$ that $E_i = F_j$ for some $i$ and $j$?

I have to prove that this probability is at least one half of the probability that $2r$ randomly chosen elements selected from $S$ are not all distinct.

share|improve this question
@Didier: but if $r=1$, the Probability that 2r randomly chosen elements selected from S are not all distinct is also $1/n$, so we just want $1/n \ge 0.5(1/n)$ which is true –  Ross Millikan Jan 31 '11 at 18:16
"I have to prove" - is this homework? What have you tried so far? –  Yuval Filmus Jan 31 '11 at 18:39
@filmus going through some material regarding the same, i have seen that by using some approximations the two sides can actually be proven to be equal kingklip.aims.ac.za/resources/archive/2009/mile.pdf –  AnkurVijay Jan 31 '11 at 19:31

2 Answers 2

up vote 1 down vote accepted

Take any list of $2r$ elements and randomly permute their order. Suppose that elements $i$ and $j$ were equal before the shuffle. After the shuffle, the probability that these elements are in opposite halves of the list (i.e., one is in the first $r$ positions and the other is in the last $r$ positions) is equal to $r/(2r-1)$. Therefore, given that the original $2r$ elements were not all distinct, the probability that (after shuffling) one of the first $r$ elements is equal to one of the last $r$ elements is at least $r/(2r-1)$ (it is strictly greater if more than one pair of elements is equal). But this conditional probability is just the ratio that is asked for: $$ \frac{P\left[\exists_{i,j}E_i=F_j\right]}{P\left[2r\text{ not distinct}\right]} = P\left[\exists_{i,j}E_i=F_j \vert E, F\text{ not all distinct}\right] \ge \frac{r}{2r-1} > \frac{1}{2}. $$ Note that the size of set $S$ is not used, and neither is the fact that all elements were equally likely. The inequality holds whenever the elements are independent and identically distributed.

share|improve this answer
thanks a lot ... –  AnkurVijay Feb 2 '11 at 19:23

The probability $P$ that you're looking for is equal to the probability that among $2r$ randomly chosen elements, at least two whose indices have different parity are equal. Now consider what happens when, instead of just drawing $2r$ elements, you first draw them and then reorder them randomly (using a permutation from $S_{2r}$). Suppose among the first $2r$ elements there was a pair of equal elements; what is the probability that under the new ordering, these find themselves in positions with opposite parity?

share|improve this answer
A very clever argument. –  Ross Millikan Jan 31 '11 at 18:49
very clever indeed .. i wonder how i can develop this kind of intuition –  AnkurVijay Feb 2 '11 at 19:24

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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