3
$\begingroup$

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.

  • 0
    @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 http://kingklip.aims.ac.za/resources/archive/2009/mile.pdf2011-01-31

2 Answers 2

1

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.

3

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?

  • 0
    very clever indeed .. i wonder how i can develop this kind of intuition2011-02-02