# Probability computation involving order statistics

Let $X_1$, $X_2$.. $X_n$ be iid uniform random variables i.e. $X_i \sim U(0,1)$. We know that the order statistics, $X_{(i)}$ is beta distributed $X_{(k)} \sim B(k,n+1-k)$.

Also let $Y_1$, $Y_2$.. $Y_n$ be another set of uniform random variables i.e. $Y_i \sim U(0,1)$. The order statistics $Y_{(i)}$ are also beta distributed $Y_{(k)} \sim B(k,n+1-k)$.

I'm interested in finding the following probability,

$\Pr(X_{(1)} < Y_{(2)}, X_{(2)} < Y_{(3)})= ?$

The problem here is that the events $E_1 \equiv \{X_{(1)} < Y_{(2)}\}$ and $E_2 \equiv \{X_{(2)} < Y_{(3)}\}$ etc are not independent, and I'm unable to come up with ways to make them independent so as to make use of the known marginal densities.

Is there any simple way to solve this problem? Any pointers to a solution are welcome.

-
Using Mathematica, one can find the answer using Probability[ x1 < y2 && x2 < y3, {Distributed[{x1,x2}, OrderDistribution[{UniformDistribution[],n}, {1, 2}]], Distributed[{y2,y3}, OrderDistribution[{UniformDistribution[], n}, {2, 3}]]}] that gives the answer of $$\Pr\left(X_{(1)} < Y_{(2)}, X_{(2)} < Y_{(3)}\right) = \frac{(5n-4)(n-1)-1}{8(n-1)^2 - 2}$$ –  Sasha Mar 18 '13 at 17:04
In Mathematica, is it possible to use an arrays x[1] and y[2], instead of x1,x2 and y1,y2? It will help to get the general result when an expression such as $\Pr\left(X_{(1)} < Y_{(2)}, X_{(2)} < Y_{(3)},.., X_{(k)} < Y_{(m)}\right)$ need to be evaluated. How else can this be solved for a variable k? –  AIB Apr 13 '13 at 1:27
Yes, it is possible. Direct substitution just works: Probability[ x[1] < y[2] && x[2] < y[3], {Distributed[{x[1], x[2]}, OrderDistribution[{UniformDistribution[], n}, {1, 2}]], Distributed[{y[2], y[3]}, OrderDistribution[{UniformDistribution[], n}, {2, 3}]]}] –  Sasha Apr 13 '13 at 2:22

One solution is to use joint distribution for two order statistics: $$f_{X_{1:n}, X_{2:n}}\left(x_1, x_2\right) = n(n-1) \left(1-x_2\right)^{n-2} \left[ 0 < x_1 < x_2 <1\right]$$ $$f_{Y_{2:n}, Y_{3:n}}\left(y_2, y_3\right) = n(n-1)(n-2) y_2 \left(1-y_3\right)^{n-3} \left[ 0 < y_2 < y_3 <1\right]$$ To evaluate the probability use $$\begin{eqnarray} \Pr\left(X_{1:n}\lt Y_{2:n},X_{2:n}\lt Y_{3:n}\right) &=& \mathbb{E}\left( \Pr\left(X_{1:n}\lt Y_{2:n},X_{2:n}\lt Y_{3:n} \mid Y_{2:n},Y_{3:n}\right) \right) \\ &=& \mathbb{E}\left( F_{X_{1:n},X_{2:n}}\left(Y_{2:n},Y_{3:n}\right)\right) \end{eqnarray}$$ The probability $F_{X_{1:n},X_{2:n}}(y_2,y_3)$ is computed as follows, assuming $0<y_2<y_3<1$ $$\begin{eqnarray} F_{X_{1:n},X_{2:n}}(y_2,y_3) &=& n(n-1) \int_0^{y_3} \mathrm{d}x_2 \int_{0}^{\min(y_2,x_1)} \mathrm{d}x_1 \cdot \left(1-x_2\right)^{n-2} \\&=& 1 - \left(1-y_2\right)^{n} - n y_2 \left(1-y_3\right)^{n-1} \end{eqnarray}$$ Now $$\begin{eqnarray} \Pr\left(X_{1:n}\lt Y_{2:n},X_{2:n}\lt Y_{3:n}\right) &=& 1 - \mathbb{E}\left( \left(1-Y_{2:n}\right)^{n} \right) - n \mathbb{E}\left( Y_{2:n} \left(1-Y_{3:n}\right)^{n-1}\right) \\ &=& 1 - \mathbb{E}\left( Y_{n-1:n}^{n} \right) - n \mathbb{E}\left( Y_{2:n} \left(1-Y_{3:n}\right)^{n-1}\right) \end{eqnarray}$$ The latter integral is easy to evaluate: $$\begin{eqnarray} n \mathbb{E}\left( Y_{2:n} \left(1-Y_{3:n}\right)^{n-1}\right) &=& \int_0^{1} \mathrm{d}y_3 \int_0^{y_3} \mathrm{d} y_2 \cdot n^2(n-1)(n-2) y_2^2 (1-y_3)^{2n-4} \\ &=& \frac{n^2 (n-1)(n-2)}{ \frac{1}{2} (2n)(2n-1)(2n-2)(2n-3)} \int_0^{1} \mathrm{d}y_3 \int_0^{y_3} f_{Z_{3:2n},Z_{4:2n}}\left(y_2,y_3\right) \\ &=& \frac{n(n-2)}{2 (2n-1)(2n-3)} \end{eqnarray}$$ The remaining integral is evaluated using singe statistics density function: $$\mathbb{E}\left( Y_{n-1:n}^{n} \right) = \int_0^1 x^n \cdot n(n-1) x^{n-2} (1-x) \mathrm{d} x = \frac{n(n-1)}{2n(2n-1)} \int_0^1 f_{Y_{2n-1:2n}}(x) \mathrm{d}x = \frac{n-1}{2(2n-1)}$$ Thus $$\Pr\left(X_{1:n}\lt Y_{2:n},X_{2:n}\lt Y_{3:n}\right) = 1-\frac{n-1}{2(2n-1)}-\frac{n(n-2)}{2 (2n-1)(2n-3)}=\frac{(5n-4)(n-1)-1}{2(2n-1)(2n-3)}$$
Thanks a ton!! One more thing, is there a general formula for the joint distribution of k order statistics i.e. $f_{X_{1:n}, X_{2:n} ...X_{k:n}}\left(x_1, x_2, ..., x_k\right)$ , for uniform density? –  AIB Mar 18 '13 at 20:14
@AIB Yes, it reads $$f_{X_{1:n},X_{2:n},\ldots,X_{k:n}}\left(x_1,x_2,\ldots,x_k\right) = \frac{n!}{(n-k)!} (1-x_k)^{n-k} [ 0<x_1<x_2<\ldots<x_k<1]$$ It is easily obtained as a marginal density of the complete order statistics pdf: $$f_{X_{1:n},X_{2:n},\ldots,X_{n:n}}\left(x_1,x_2,\ldots,x_n\right) = n! [ 0 < x_1 < x_2 < \cdots < x_n < 1]$$ There are some good books on order statistics, like this and that. –  Sasha Mar 18 '13 at 20:36
@AIB Do you mean the cdf of all order statistics, i.e. $$\Pr\left(X_{1:n} \leqslant x_1, X_{2:n} \leqslant x_2, \ldots, X_{n:n} \leqslant x_n \right)$$ There is an expression for it in terms of multiple sum that involves products of $F_X$ Look at the page 18 of the first book for the logic of deriving it. –  Sasha Mar 20 '13 at 18:37
Actually, I meant $\Pr\left(X_{1:n} \leqslant x_1, X_{2:n} \leqslant x_2, \ldots, X_{k:n} \leqslant x_k \right)$. This (marginal), I think, can be obtained by setting $x_{k+1}=1,x_{k+2}=1,...x_n=1$ in the cdf of all order statistics. Meanwhile, I am trying to a get a copy of the book from our library. –  AIB Mar 23 '13 at 7:28