Order Statistics for Discrete Samples and Ties

Why Ties Change the Rank Calculation

For a continuous distribution, independent observations have probability zero of being equal. A discrete distribution behaves differently: several observations can take the same value with positive probability. Consequently, an order statistic can equal an atom because the sample has accumulated enough observations at or below that atom, even when several observations are tied there.

The useful approach is to count observations in categories. At a candidate value $a$, separate the sample into values strictly below $a$, equal to $a$, and strictly above $a$. The kth ordered value is $a$ precisely when fewer than $k$ observations lie strictly below $a$, but at least $k$ lie at or below $a$. This count-based description keeps ties and rank conventions explicit.

Definitions and Rank Events

Definition: Let $X_1,\ldots,X_n$ be an independent, identically distributed sample from a discrete distribution, and write its ordered observations, with repetitions retained, as $X_{(1)}\le\cdots\le X_{(n)}$. For a real number $a$, define $N_{<a}=\sum_{i=1}^n \mathbf{1}\{X_i<a\}$ and $N_{\le a}=\sum_{i=1}^n \mathbf{1}\{X_i\le a\}$. Then $X_{(k)}<a$ if and only if $N_{<a}\ge k$, $X_{(k)}\le a$ if and only if $N_{\le a}\ge k$, and $X_{(k)}=a$ if and only if $N_{<a}\le k-1$ and $N_{\le a}\ge k$.

Here $\mathbf{1}\{A\}$ equals 1 when event $A$ occurs and 0 otherwise. The observations tied at $a$ occupy the consecutive positions $N_{<a}+1,\ldots,N_{\le a}$ in the ordered sample. Thus a tie does not give one observation a unique position within that block; it gives several positions the same value.

For an atom $a$, let $p_a=P(X_i=a)$, $q_a=P(X_i<a)$, and $r_a=P(X_i>a)$, so $q_a+p_a+r_a=1$. The triple $(N_{<a},\,N_{=a},\,N_{>a})$ has a multinomial distribution with cell probabilities $(q_a,p_a,r_a)$. This is the direct way to account for ties.

Exact Probability at a Discrete Value

Theorem: Under the independent, identically distributed sampling assumptions above, for any atom $a$, $$ P(X_{(k)}=a) = \sum_{i=0}^{k-1}\ \sum_{r=k-i}^{n-i} \frac{n!}{i!\,r!\,(n-i-r)!} q_a^i p_a^r r_a^{\,n-i-r}. $$ A sum with an impossible range is interpreted as zero.

In this formula, $i$ is the number of observations below $a$, and $r$ is the number equal to $a$. The first sum stops at $k-1$, because $k$ or more observations below $a$ would put the kth order statistic strictly below $a$. For each such $i$, the second sum begins at $k-i$, because at least that many observations equal to $a$ are needed to bring the number at or below $a$ up to $k$.

To prove the formula, partition the event $X_{(k)}=a$ according to the possible values of $N_{<a}=i$ and $N_{=a}=r$. By the rank characterization, the allowed pairs are exactly $0\le i\le k-1$ and $k-i\le r\le n-i$. For each pair, independence gives the multinomial probability $$ P(N_{<a}=i,\ N_{=a}=r,\ N_{>a}=n-i-r) = \frac{n!}{i!\,r!\,(n-i-r)!}q_a^i p_a^r r_a^{\,n-i-r}. $$ These events are disjoint as $(i,r)$ varies, and their union is $X_{(k)}=a$. Summing their probabilities proves the result. $\square$

A useful equivalent way to obtain the mass at $a$ is to subtract two cumulative probabilities. Write $F(x)=P(X_i\le x)$ and $F(a-)=P(X_i<a)$. Then $$ P(X_{(k)}=a)=P(X_{(k)}\le a)-P(X_{(k)}<a). $$ The first event counts observations at or below $a$, while the second counts observations strictly below $a$. For an iid sample, each count has a binomial distribution with success probability $F(a)$ or $F(a-)$, respectively. The multinomial expression above makes the tie categories visible; the difference of binomial tails is often shorter to compute.

Worked Example: A Bernoulli Sample and Its Middle Order Statistic

Let $X_1,\ldots,X_5$ be independent Bernoulli random variables with $P(X_i=1)=0.3$ and $P(X_i=0)=0.7$. Find the distribution of $X_{(3)}$.

The third order statistic is 0 exactly when at least three of the five observations are 0. The possible numbers of zeros are 3, 4, and 5, so $$ \begin{aligned} P(X_{(3)}=0) &=\binom{5}{3}(0.7)^3(0.3)^2 +\binom{5}{4}(0.7)^4(0.3) +\binom{5}{5}(0.7)^5\\ &=10(0.343)(0.09)+5(0.2401)(0.3)+0.16807\\ &=0.3087+0.36015+0.16807\\ &=0.83692. \end{aligned} $$ The first term is the probability of exactly three zeros; it is $0.3087$, not $0.1372$. Since the sample values can only be 0 or 1, the third order statistic is either 0 or 1. Therefore $$ P(X_{(3)}=1)=1-0.83692=0.16308. $$ The probabilities sum to $0.83692+0.16308=1$, as required.

Worked Example: A Three-Point Distribution With Ties

Suppose each observation takes values 0, 1, and 2 with probabilities $0.2$, $0.5$, and $0.3$, respectively. For an iid sample of size 4, calculate $P(X_{(2)}=1)$ by counting categories.

For the candidate value 1, the probabilities of being below, equal to, and above it are $0.2$, $0.5$, and $0.3$. Let $i$ be the number of zeros and $r$ the number of ones. The second ordered observation equals 1 if $i\le1$ and $i+r\ge2$.

First take $i=0$. Then $r$ can be 2, 3, or 4: $$ \begin{aligned} P(i=0,\ r\ge2) &=\binom{4}{2}(0.5)^2(0.3)^2 +\binom{4}{3}(0.5)^3(0.3) +(0.5)^4\\ &=6(0.25)(0.09)+4(0.125)(0.3)+0.0625\\ &=0.135+0.15+0.0625=0.3475. \end{aligned} $$

Now take $i=1$. At least one observation must equal 1, and the remaining observations are either ones or twos: $$ \begin{aligned} P(i=1,\ r\ge1) &=\frac{4!}{1!1!2!}(0.2)(0.5)(0.3)^2\\ &\quad+\frac{4!}{1!2!1!}(0.2)(0.5)^2(0.3) +\frac{4!}{1!3!0!}(0.2)(0.5)^3\\ &=12(0.2)(0.5)(0.09) +12(0.2)(0.25)(0.3) +4(0.2)(0.125)\\ &=0.108+0.18+0.1=0.388. \end{aligned} $$ Adding the disjoint cases gives $P(X_{(2)}=1)=0.3475+0.388=0.7355$.

As a check, $F(1)=0.7$ and $F(1-)=0.2$. Thus $P(X_{(2)}=1)$ is the probability that a $\operatorname{Binomial}(4,0.7)$ count is at least 2, minus the corresponding probability for $\operatorname{Binomial}(4,0.2)$: $$ \begin{aligned} P(X_{(2)}=1) &=\left[1-(0.3)^4-4(0.7)(0.3)^3\right]\\ &\quad-\left[6(0.2)^2(0.8)^2+4(0.2)^3(0.8)+(0.2)^4\right]\\ &=(1-0.0081-0.0756)-(0.1536+0.0256+0.0016)\\ &=0.9163-0.1808=0.7355. \end{aligned} $$ The independent calculation agrees.

Strict and Non-Strict Rank Events

Theorem: For an iid sample from a discrete distribution and any real $a$, $$ P(X_{(k)}<a)=\sum_{j=k}^{n}\binom{n}{j}F(a-)^j[1-F(a-)]^{n-j}, $$ and $$ P(X_{(k)}\le a)=\sum_{j=k}^{n}\binom{n}{j}F(a)^j[1-F(a)]^{n-j}. $$

For the strict event, $X_{(k)}<a$ precisely when at least $k$ observations are strictly below $a$. Each observation independently falls below $a$ with probability $F(a-)$, so $N_{<a}$ is binomial with parameters $n$ and $F(a-)$. Summing its probabilities for counts $k,\ldots,n$ proves the first formula. For the non-strict event, replace “strictly below” with “at or below”: $N_{\le a}$ is binomial with parameters $n$ and $F(a)$, giving the second formula. These derivations use only the binomial count probabilities and the rank equivalences in the definition. $\square$

The difference between these formulas is not cosmetic. At an atom, $F(a)$ exceeds $F(a-)$ by $P(X_i=a)$. Replacing one by the other changes which observations count toward the kth position.

Worked Example: Comparing Strict and Non-Strict Events

Let $X_1,X_2,X_3$ be iid with $P(X_i=1)=0.2$, $P(X_i=2)=0.5$, and $P(X_i=3)=0.3$. Find $P(X_{(2)}<2)$, $P(X_{(2)}\le2)$, and $P(X_{(2)}=2)$.

The event $X_{(2)}<2$ requires at least two observations strictly below 2, meaning at least two ones. Hence $$ P(X_{(2)}<2)=\binom{3}{2}(0.2)^2(0.8)+(0.2)^3 =3(0.04)(0.8)+0.008=0.104. $$

The event $X_{(2)}\le2$ requires at least two observations in $\{1,2\}$, a category of probability $0.7$: $$ P(X_{(2)}\le2)=\binom{3}{2}(0.7)^2(0.3)+(0.7)^3 =3(0.49)(0.3)+0.343=0.784. $$

Since $X_{(2)}=2$ is the difference between the non-strict and strict events, $$ P(X_{(2)}=2)=0.784-0.104=0.68. $$

Direct category counting confirms this result. With no ones, at least two twos are needed: the probabilities are $3(0.5)^2(0.3)=0.225$ and $(0.5)^3=0.125$, totaling $0.35$. With exactly one one, at least one two is needed: the probabilities are $6(0.2)(0.5)(0.3)=0.18$ and $3(0.2)(0.5)^2=0.15$, totaling $0.33$. Thus the total is $0.35+0.33=0.68$.

Common Pitfall: Counting Ties as Strictly Below

A frequent error is to treat “the kth observation is at most $a$” as requiring at least $k$ observations strictly below $a$. That condition actually describes $X_{(k)}<a$. Observations equal to $a$ count toward the non-strict event $X_{(k)}\le a$, and they may also be what makes $X_{(k)}=a$.

For example, in the preceding calculation, $P(X_{(2)}<2)=0.104$, while $P(X_{(2)}\le2)=0.784$. The difference, $0.68$, is the probability of equality at 2. Using the strict count for the non-strict event would discard the entire contribution from samples in which the second ordered value is 2.

Likewise, the familiar continuous order-statistic density formula should not be applied to a discrete sample as though its observations could not tie. A discrete order statistic has probability masses at support points. Category counts, or differences of cumulative probabilities, directly give those masses.

Key takeaway: At a candidate atom $a$, first distinguish $N_{<a}$ from $N_{\le a}$. The kth order statistic equals $a$ exactly when $N_{<a}\le k-1$ and $N_{\le a}\ge k$; this criterion handles ties without assigning tied observations artificial unique ranks.

Check Your Understanding

Use strict-below and at-or-below counts to answer each question.

For an iid discrete sample, state the count conditions equivalent to $X_{(k)}<a$, $X_{(k)}\le a$, and $X_{(k)}=a$.
If $P(X_i=a)=0$, how do $F(a)$ and $F(a-)$ compare, and what does that imply about the difference between the strict and non-strict rank events?
Suppose $n=4$, $k=3$, and exactly two observations are strictly below $a$. What minimum number must equal $a$ for $X_{(3)}=a$?
Explain why several observations tied at $a$ occupy a block of ordered positions rather than one uniquely determined position.
For the distribution with probabilities $0.2,0.5,0.3$ at 1, 2, and 3, respectively, identify the binomial success probability used to compute $P(X_{(2)}\le2)$, and explain why it is not the probability of being strictly below 2.