Order statistics: probability of second highest order statistic higher than first order statistic

Question

Assume I have two bins with n items each iid drawn from the same F. How can I formulate the probability that the second-highest order statistic of the first bin is higher than the highest-order statistic of the other bin?

Answer 1

Assuming that $F$ is continuous, one has $2n$ distinct items and one asks the probability that marking $n$ of these chosen randomly yields that two given items are marked. The probability that the first item is marked is $1/2$. Conditionally on this event, one must mark $n-1$ items amongst $2n-1$ hence the conditional probability that the second item is marked is $(n-1)/(2n-1)$.

Thus, the probability that the two highest valued items are in the first bin is $(n-1)/(2(2n-1))$.

Answer 2

Since you ask for just the formulation, I will just give you a suggestion on how I would set up the problem. Say $X_1,\ldots,X_n$ are in the first bin, and $Y_1,\ldots,Y_n$ are in the second bin. Then the probability we are after is $P[X_{(2)} > Y_{(1)}]$. Note that we cannot replace $X_{(2)}$ with $Y_{(2)}$ even though they are independent and have the same distribution.

You may compute as an exercise that if $F$ is absolutely continuous (i.e. the random variables have a density $f$), then the pdf of $X_{(k)}$ or $Y_{(k)}$ in general is $$ g_{(k)}(y) = \frac{n!}{(k-1)!(n-k)!}[F(y)]^{k-1}[1-F(y)]^{n-k}f(y). $$

Since $Y_{(1)}$ and $X_{(2)}$ are independent it follows that they have the joint density $$ g(x,y)=g_{(2)}(x)g_{(1)}(y) $$ and so $$ P[X_{(2)} > Y_{(1)}] = \int_{-\infty}^\infty\int_y^\infty g(x,y)dxdy $$ has been reduced to an elementary computation.

If $F$ is not absolutely continuous a more careful approach must be taken.