# Probability of an order statistic

If I randomize time points $$T=\{266.14646, 107.28526, 108.89631, 593.03129,\\ 118.10284, 425.60470, 39.02817, 291.90210\}$$ into two groups of equal size, then what is the probability that $T_i$ (the $i$-th time point) will be the 3rd order statistic of the second group?

Given that $T_i$ follows an exponential with rate $\lambda_i$.

I am getting confused to calculate this probability. Especially with what should be the probability that $T_i$ is the 3rd largest value of the 2nd group.

Let's generalize a little: you have $n=8$ data in sorted order, $x_1 \lt x_2 \lt \cdots \lt x_n$, which you wish to divide randomly into groups of size $\alpha=4$ and $\beta=4$. Denote the division by the indicator of $\beta$: this is, in effect, an $n$-digit binary number having exactly $\beta$ ones. (Examples appear below.) In order for $x_i$ to be the $k=3$rd smallest in the second group, we need three things to happen. Binomial coefficients count the number of ways they can happen:

• Digit $i$ of the indicator is $1$. This happens in $1 = \binom{1}{1}$ ways.

• There are exactly $k-1$ $1$'s among digits $1$ through $i-1$. This happens in $\color{red}{\binom{i-1}{k-1}}$ ways.

• There are exactly $\beta-k$ $1$'s among digits $i+1$ through $n$. This happens in $\color{blue}{\binom{n-i}{\beta-k}}$ ways.

These three events are independent because they describe non-overlapping positions in the indicator, so their product is the number of ways of performing the split.

The total number of ways in which the data can be split is given by the binomial coefficient $\binom{n}{\beta}$, each of which is equally likely, whence the chance that $x_i$ is $k$th smallest in the second group is

$$\frac{\color{red}{\binom{i-1}{k-1}} \color{blue}{\binom{n-i}{\beta-k}}}{\binom{n}{\beta}}.$$

(Here and later, red objects denote or count numbers ranked ahead of $x_i$ and blue objects denote or count numbers ranked after $x_i$.)

For example, let $n=8$, $\alpha=4$, $\beta=n-\alpha=4$, and $k=3$ (which is the specific instance in the question). Let's tabulate $i$, the corresponding binomial coefficients, and their product:

i    Choose(i-1,2)    Choose(8-i,4-3)    Product
1                0                  7          0
2                0                  6          0
3                1                  5          5
4                3                  4         12
5                6                  3         18
6               10                  2         20
7               15                  1         15
8               21                  0          0


The total, $0+0+5+12+\cdots+15+0$, is $70$, which is precisely $\binom{8}{4}$, confirming the law of total probability. The interpretations are:

• There is no chance that either $x_1$ or $x_2$ could be the third smallest elements in the second group.

• There are $1\times 5=5$ ways out of $70$ that $x_3$ could be third smallest in the second group, whence the answer to the question about the $T_i$ is $5/70 = 1/14 \approx 7.1$%. In terms of the binary indicators, these five ways can be written

$$\color{red}{11}\ 1\ \color{blue}{10000},\quad \color{red}{11}\ 1\ \color{blue}{01000},\quad \color{red}{11}\ 1\ \color{blue}{00100},\quad \color{red}{11}\ 1\ \color{blue}{00010},\quad \color{red}{11}\ 1\ \color{blue}{00001}.$$

For instance, the fifth indicator $\color{red}{11}\ 1\ \color{blue}{00001}$ identifies $\{\color{red}{x_1}, \color{red}{x_2}, x_3, \color{blue}{x_8}\}$ as the second group.

• There are $3\times 4=12$ ways out of $70$ that $x_4$ could be third smallest in the second group:

$$\color{red}{110}\ 1\ \color{blue}{1000},\quad \color{red}{110}\ 1\ \color{blue}{0100},\quad \color{red}{110}\ 1\ \color{blue}{0010},\quad \color{red}{110}\ 1\ \color{blue}{0001} \\ \color{red}{101}\ 1\ \color{blue}{1000},\quad \color{red}{101}\ 1\ \color{blue}{0100},\quad \color{red}{101}\ 1\ \color{blue}{0010},\quad \color{red}{101}\ 1\ \color{blue}{0001} \\ \color{red}{011}\ 1\ \color{blue}{1000},\quad \color{red}{011}\ 1\ \color{blue}{0100},\quad \color{red}{011}\ 1\ \color{blue}{0010},\quad \color{red}{011}\ 1\ \color{blue}{0001}.$$

• Etc.
• Wow! This is a great answer because you have also shown me the way to think. It has been a great learning experience for me in this site. I should say, your basic is very strong indeed. Cheers! – Blain Waan Jan 19 '13 at 10:29
• If the data have tied observations, so that, $x_1<=x_2<=...<=x_n$ then do the formula change? Do I need to make it a separate question thread? Actually I am facing with some tied observations in my data and trying to figure out what should be done. – Blain Waan Jan 22 '13 at 17:54
• Yes, the answer changes with ties. (I did not mention that because your remark that the $T_i$ have exponential distributions implies ties have no chance of occurring--although as a practical matter a few ties might happen due to the finite precision with which their values are represented.) A similar combinatorial approach will work, but the answer is not quite as easy to derive. Any closed-form formulas will necessarily be at least as complicated as the pattern of ties among the order statistics. In such cases it would be understandable if you went with a simulation solution or approximation. – whuber Jan 22 '13 at 18:10
• Actually before getting the data at hand I knew they were lifetimes, so took exponential as an example. Now I have the data and I can see several ties, because the data are in days. Even there are some lifetimes that are zero!! – Blain Waan Jan 22 '13 at 18:21
• Although I wrote that a general solution could be complicated, a solution specific to your data might be obtainable from the formulas here. All that matters is whether the particular $T_i$ you are interested in has any tied values. If not, the same formulas apply, because there will never be any question as to whether it is the $3$rd ranked value in the second group. If it does have ties, you can sum over the possible ways in which $T_i$ can be tied for third. Because this can get tricky, I recommend checking any such solutions with simulations of small datasets. – whuber Jan 22 '13 at 18:27