# 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}$$ Mar 18, 2013 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, 2013 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}]]}] Apr 13, 2013 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, 2013 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. Mar 18, 2013 at 20:36
• Is there an expression for the CDF? I checked in the second book, but couldn't find any. Is it possible to use Mathematica to arrive at the answer(CDF), by integrating the pdf?
– AIB
Mar 20, 2013 at 17:58
• @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. Mar 20, 2013 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, 2013 at 7:28