The CDF of the Kth Order Statistic

From a Rank Event to a Count

An order statistic is determined by the rank of an observation, but its distribution can be found by asking a counting question. For a fixed threshold $x$, the event that the $k$th smallest observation is at most $x$ occurs precisely when at least $k$ observations in the sample are at most $x$. In an iid sample, the number of observations meeting this threshold has a binomial distribution. This converts a rank event into a finite sum of binomial probabilities.

This approach is useful because it works for any common distribution $F$, whether the distribution is continuous, discrete, or mixed. Continuity is not needed: observations may tie, and the counting argument still applies.

Definition: Let $X_1,\ldots,X_n$ be an iid sample from a distribution with CDF $F$. Write $X_{(1)}\leq X_{(2)}\leq\cdots\leq X_{(n)}$ for the sample values arranged in nondecreasing order, counting repetitions. For an integer $k$ with $1\leq k\leq n$, $X_{(k)}$ is the $k$th order statistic. Its CDF is $F_{X_{(k)}}(x)=P(X_{(k)}\leq x)$.

The notation allows equal values: if several observations tie, each occupies a place in the ordered list. At a threshold $x$, let $N_x$ denote the number of sample observations that are at most $x$:

N_x=\sum_{i=1}^n \mathbf{1}_{\{X_i\leq x\}}.

Here $\mathbf{1}_{\{X_i\leq x\}}$ equals 1 when $X_i\leq x$ and 0 otherwise. Each indicator has probability $F(x)$ of equaling 1. Independence makes these indicators independent, so $N_x$ has a binomial distribution with parameters $n$ and $F(x)$.

The Binomial-Tail Formula

Theorem: If $X_1,\ldots,X_n$ are iid with CDF $F$, then for every real $x$ and every $k\in\{1,\ldots,n\}$, $$ F_{X_{(k)}}(x) =P(X_{(k)}\leq x) =\sum_{j=k}^{n}\binom{n}{j}F(x)^j[1-F(x)]^{n-j}. $$ Equivalently, $$ F_{X_{(k)}}(x) =1-\sum_{j=0}^{k-1}\binom{n}{j}F(x)^j[1-F(x)]^{n-j}. $$

Proof. For any realized sample, $X_{(k)}\leq x$ if and only if at least $k$ of the $n$ observations are at most $x$. Indeed, if the $k$th ordered value is at most $x$, then the first $k$ ordered values are all at most $x$. Conversely, if at least $k$ observations are at most $x$, then the $k$th value in nondecreasing order cannot exceed $x$. Thus

\{X_{(k)}\leq x\}=\{N_x\geq k\}.

For each $i$, $P(X_i\leq x)=F(x)$. By independence, the indicators in $N_x$ are independent Bernoulli random variables with success probability $F(x)$, hence $N_x\sim\operatorname{Binomial}(n,F(x))$. Summing the binomial probabilities for counts $j=k,\ldots,n$ gives the first formula. The complementary event is $N_x\leq k-1$; subtracting its probability from 1 gives the second formula. This proof uses only the iid assumption and the definition of a CDF, so it also covers distributions with atoms. $\square$

The first sum is the binomial upper tail: there must be at least $k$ observations on or below the threshold. The complementary form can be shorter when $k$ is close to $n$, because it sums only the counts from 0 to $k-1$. In either form, the binomial success probability is $F(x)$, not $x$ itself.

Worked Example: A Uniform Sample and the Third Order Statistic

Let $X_1,\ldots,X_5$ be iid Uniform$(0,1)$. Find $P(X_{(3)}\leq 0.4)$.

For a Uniform$(0,1)$ variable, $F(x)=x$ for $0\leq x\leq1$, so $F(0.4)=0.4$. The third order statistic is at most 0.4 exactly when at least three of the five observations are at most 0.4. Therefore,

\begin{aligned} P(X_{(3)}\leq 0.4) &=\sum_{j=3}^{5}\binom{5}{j}(0.4)^j(0.6)^{5-j}\\ &=10(0.4)^3(0.6)^2+5(0.4)^4(0.6)+(0.4)^5\\ &=10(0.064)(0.36)+5(0.0256)(0.6)+0.01024\\ &=0.2304+0.0768+0.01024\\ &=0.31744. \end{aligned}

Thus the probability is $0.31744$. As a check, the complementary event is that at most two observations are at most 0.4. Its probability is $1-0.31744=0.68256$, so the two possibilities sum to 1.

Worked Probabilities at Specific Thresholds

Worked Example: An Exponential Sample at Its Median Threshold

Let $X_1,\ldots,X_4$ be iid exponential random variables with rate 2, so $F(x)=1-e^{-2x}$ for $x\geq0$. Find $P(X_{(2)}\leq (\log 2)/2)$.

At $x=(\log 2)/2$, the CDF of one observation is $F(x)=1-e^{-2(\log 2)/2}=1-e^{-\log 2}=1-\tfrac12=\tfrac12$. The second order statistic is at most this threshold when at least two of the four observations are at most it. Hence

\begin{aligned} P\left(X_{(2)}\leq \frac{\log 2}{2}\right) &=\sum_{j=2}^{4}\binom{4}{j}\left(\frac12\right)^j \left(\frac12\right)^{4-j}\\ &=\frac{6}{16}+\frac{4}{16}+\frac{1}{16}\\ &=\frac{11}{16}=0.6875. \end{aligned}

The same result can be checked from the complementary event: at most one observation is at or below the threshold, with probability $\binom40/16+\binom41/16=5/16$. Therefore the desired probability is $1-5/16=11/16$.

Worked Example: A Discrete Sample With Ties

Suppose $X_1,X_2,X_3$ are iid Bernoulli random variables with $P(X_i=0)=0.7$ and $P(X_i=1)=0.3$. Find $P(X_{(2)}\leq0)$.

This distribution has an atom at 0, and ties are possible. Its CDF at 0 is $F(0)=P(X_i\leq0)=0.7$. The second order statistic is at most 0 precisely when at least two sample values equal 0. The formula gives

\begin{aligned} P(X_{(2)}\leq0) &=\binom32(0.7)^2(0.3)+(0.7)^3\\ &=3(0.49)(0.3)+0.343\\ &=0.441+0.343\\ &=0.784. \end{aligned}

This also follows by listing the possible counts of zeros: exactly two zeros has probability $0.441$, and exactly three zeros has probability $0.343$. A tie at zero does not invalidate the rank event; it contributes according to how many observations are at or below the threshold.

Interval Probabilities and Continuity

Once the CDF of the order statistic is known, probabilities over intervals follow from the defining properties of a CDF. For any real numbers $a<b$,

Result: For any iid sample as above, $$ P(a<X_{(k)}\leq b)=F_{X_{(k)}}(b)-F_{X_{(k)}}(a). $$ If the common CDF $F$ is continuous, then $F_{X_{(k)}}$ is continuous and $P(X_{(k)}=x)=0$ for every real $x$.

Proof. The event $\{X_{(k)}\leq a\}$ is contained in $\{X_{(k)}\leq b\}$. Their difference is exactly $\{a<X_{(k)}\leq b\}$. Subtracting their probabilities proves the interval formula. For the continuity claim, define the polynomial

g_k(u)=\sum_{j=k}^{n}\binom{n}{j}u^j(1-u)^{n-j},\qquad 0\leq u\leq1.

A polynomial is continuous, and the main formula says $F_{X_{(k)}}(x)=g_k(F(x))$. If $F$ is continuous, this composition is continuous. For any real-valued random variable $Y$, $P(Y=x)=F_Y(x)-F_Y(x-)$, where $F_Y(x-)$ is the left limit of its CDF. Continuity makes this difference zero for $Y=X_{(k)}$, proving the claim. $\square$

The converse is not asserted: if the common distribution has atoms, the order statistic can also have point masses. The Bernoulli example demonstrates this directly. The formula remains valid in both cases, but one must keep the threshold event inclusive when using $F(x)=P(X_i\leq x)$.

Common Mistakes and Why the Formula Matters

The binomial-tail representation matters because it separates the rank mechanism from the particular sampling distribution. First calculate the single-observation probability $F(x)$; then the sample size and the rank determine which binomial tail to use. The same calculation applies at every threshold, producing the entire CDF rather than just one probability.

Using fewer than $k$ observations. The event $X_{(k)}\leq x$ requires at least $k$ observations at or below $x$, not exactly $k$. Counts larger than $k$ also satisfy the event, which is why the sum runs through $n$.
Using the wrong tail. The complement is “at most $k-1$ observations are at or below $x$,” not “at least $k$ observations are above $x$” without checking the boundary. The complementary count formulation avoids ambiguity.
Replacing $F(x)$ by $x$. This is valid only for a particular distribution and range, such as Uniform$(0,1)$. In general, the success probability is $F(x)$.
Assuming observations cannot tie. Ties do not break the count argument. For distributions with atoms, use $F(x)=P(X_i\leq x)$ and retain the inclusive inequality.

For example, the incorrect claim that $X_{(k)}\leq x$ requires exactly $k$ observations below the threshold omits the cases with $k+1,\ldots,n$ such observations. Those cases are part of the event, not an exception. The correction is to count all outcomes with $N_x\geq k$, or equivalently subtract the probabilities for $N_x=0,\ldots,k-1$ from 1.

Check Your Understanding

Use the count interpretation before substituting into a binomial sum.

For an iid sample of size 6, express the event $X_{(4)}\leq x$ in terms of the number of observations at or below $x$.
Write the binomial-tail formula for $F_{X_{(2)}}(x)$ when the sample size is 5.
If $F(x)=0.3$, $n=3$, and $k=2$, calculate $P(X_{(2)}\leq x)$.
Why does the formula remain valid when the common distribution is discrete and observations can tie?
If $F$ is continuous, what does continuity of $F_{X_{(k)}}$ imply about $P(X_{(k)}=x)$?