Order Statistics from Independent Nonidentical Variables

From an Order Statistic to a Threshold Count

For independent identically distributed observations, order-statistic probabilities can be expressed using a binomial count. When the variables are independent but have different distributions, the same event interpretation still works, but the count need not be binomial. Its success probabilities depend on which variable is being considered. The key is to track those probabilities separately.

Let \(X_1,\ldots,X_n\) be independent real-valued random variables, with CDFs \(F_1,\ldots,F_n\). Write \(X_{(k)}\) for the kth smallest of the \(n\) values, where \(1\leq k\leq n\). For a fixed threshold \(x\), variable \(X_i\) falls at or below the threshold with probability \(F_i(x)\). The event \(X_{(k)}\leq x\) occurs precisely when at least \(k\) of the variables fall at or below \(x\).

Definition: For a fixed \(x\), define \(I_i(x)=\mathbf{1}\{X_i\leq x\}\) and \(N_x=\sum_{i=1}^n I_i(x)\). Then \(N_x\) counts how many variables are at most \(x\), and \(X_{(k)}\leq x\) if and only if \(N_x\geq k\). Independence of the \(X_i\) implies independence of the indicators \(I_i(x)\), with \(P(I_i(x)=1)=F_i(x)\).

The threshold count is a sum of independent Bernoulli indicators, potentially with unequal success probabilities. Summing over the possible subsets of indices gives a direct CDF formula.

Theorem: If \(X_1,\ldots,X_n\) are independent real-valued random variables with CDFs \(F_1,\ldots,F_n\), then for \(1\leq k\leq n\),

F_{X_{(k)}}(x) = P(X_{(k)}\leq x) = \sum_{\substack{A\subseteq\{1,\ldots,n\}\\ |A|\geq k}} \left(\prod_{i\in A}F_i(x)\right) \left(\prod_{i\notin A}[1-F_i(x)]\right).

Here \(A\) represents exactly the indices whose variables are at most \(x\). The formula includes every subset with at least \(k\) indices. An empty product, if one occurs, is defined to equal 1.

Why the Subset Formula Holds

For each subset \(A\) of \(\{1,\ldots,n\}\), consider the event that \(X_i\leq x\) for every \(i\in A\) and \(X_i>x\) for every \(i\notin A\). These events are disjoint as \(A\) varies: an outcome determines exactly which indices satisfy \(X_i\leq x\). Their union over subsets with \(|A|\geq k\) is the event that at least \(k\) values are at most \(x\).

By independence, the probability of the event associated with a particular \(A\) is the product of its individual probabilities. For \(i\in A\), that probability is \(F_i(x)\); for \(i\notin A\), it is \(1-F_i(x)\). Adding the probabilities of the disjoint events gives the displayed formula. This argument needs independence, but does not require identical distributions or continuous CDFs. In particular, the event identity continues to hold if ties can occur.

Worked Example: Four Unequal Threshold Probabilities

Suppose \(X_1,\ldots,X_4\) are independent, and at a particular threshold \(x\) their CDF values are \(0.2, 0.4, 0.6,\) and \(0.8\), respectively. Find \(P(X_{(2)}\leq x)\).

The second smallest value is at most \(x\) if at least two variables are at most \(x\). Let the corresponding probabilities be \(p_1=0.2\), \(p_2=0.4\), \(p_3=0.6\), and \(p_4=0.8\). The complement consists of zero or one threshold crossings.

The probability of zero crossings is \( (1-p_1)(1-p_2)(1-p_3)(1-p_4) =0.8(0.6)(0.4)(0.2)=0.0384.\)

The probability of exactly one crossing is the sum of four disjoint possibilities:

\begin{aligned} P(N_x=1) &=p_1(1-p_2)(1-p_3)(1-p_4)\\ &\quad +(1-p_1)p_2(1-p_3)(1-p_4)\\ &\quad +(1-p_1)(1-p_2)p_3(1-p_4)\\ &\quad +(1-p_1)(1-p_2)(1-p_3)p_4\\ &=0.0096+0.0256+0.0576+0.1536\\ &=0.2464. \end{aligned}

Therefore, \(P(X_{(2)}\leq x)=1-0.0384-0.2464=0.7152.\) The probabilities are not interchangeable: each term reflects which particular variable is the sole one at or below the threshold.

A Recurrence for the Threshold Count

The subset formula is exact, but listing every subset can be cumbersome when \(n\) is large. A recurrence computes the probability of each possible count using one variable at a time.

Theorem: Fix \(x\), and write \(p_i=F_i(x)\). Let \(q_j^{(m)}\) be the probability that exactly \(j\) of \(X_1,\ldots,X_m\) are at most \(x\). Set \(q_0^{(0)}=1\), and set \(q_j^{(m)}=0\) when \(j<0\) or \(j>m\). For \(m=1,\ldots,n\),

q_j^{(m)} = (1-p_m)q_j^{(m-1)} + p_m q_{j-1}^{(m-1)}.

Consequently, \(P(X_{(k)}\leq x)=\sum_{j=k}^n q_j^{(n)}\).

To prove the recurrence, partition the event that exactly \(j\) of the first \(m\) variables are at most \(x\) according to the value of \(I_m(x)\). If \(I_m(x)=0\), the first \(m-1\) variables must contribute exactly \(j\) crossings. Independence gives probability \((1-p_m)q_j^{(m-1)}\). If \(I_m(x)=1\), the first \(m-1\) must contribute exactly \(j-1\), giving \(p_mq_{j-1}^{(m-1)}\). These two cases are disjoint and exhaustive, so their probabilities add. Finally, the event of at least \(k\) crossings is the disjoint union of the events of exactly \(j\) crossings for \(j=k,\ldots,n\), proving the stated sum. \(\square\)

The recurrence works with different \(p_i\) at each step. It can be applied separately at each threshold \(x\), and avoids having to enumerate all \(2^n\) subsets.

Worked Example: The Second Smallest of Three Exponentials

Let \(X_1,X_2,X_3\) be independent exponential random variables with rates \(1,2,3\), respectively. Thus \(F_i(x)=1-e^{-\lambda_i x}\) for \(x\geq0\), where \((\lambda_1,\lambda_2,\lambda_3)=(1,2,3)\). Find the CDF of \(X_{(2)}\), and evaluate it at \(x=\ln 2\).

For \(x\geq0\), put \(p_i=F_i(x)\). At least two of the three variables must be at most \(x\). This happens either when exactly two cross the threshold or when all three do, so

F_{X_{(2)}}(x) =p_1p_2(1-p_3)+p_1(1-p_2)p_3+(1-p_1)p_2p_3+p_1p_2p_3.

Each of the first three terms specifies which variable is above \(x\), and the last term is the event that all three are at or below \(x\). Equivalently, collecting terms gives \(F_{X_{(2)}}(x)=p_1p_2+p_1p_3+p_2p_3-2p_1p_2p_3\). For \(x<0\), the CDF is zero. Substituting \(p_1=1-e^{-x}\), \(p_2=1-e^{-2x}\), and \(p_3=1-e^{-3x}\) gives the CDF for nonnegative \(x\).

At \(x=\ln 2\), the three threshold probabilities are \(p_1=1-2^{-1}=1/2\), \(p_2=1-2^{-2}=3/4\), and \(p_3=1-2^{-3}=7/8\). The four disjoint contributions are \(p_1p_2(1-p_3)=3/64\), \(p_1(1-p_2)p_3=7/64\), \((1-p_1)p_2p_3=21/64\), and \(p_1p_2p_3=21/64\). Their sum is \(52/64=13/16=0.8125\). Thus the probability that the second smallest value is at most \(\ln 2\) is \(13/16\).

Different Distributions Can Produce a Piecewise CDF

When the variables have different supports, their CDFs may change form at different thresholds. The subset formula still applies; the calculation simply needs to respect each variable’s CDF on each interval.

Worked Example: Three Uniform Variables on Different Intervals

Let \(X_1,X_2,X_3\) be independent with \(X_1\sim\operatorname{Uniform}(0,1)\), \(X_2\sim\operatorname{Uniform}(0,2)\), and \(X_3\sim\operatorname{Uniform}(1,3)\). Find the CDF of \(X_{(2)}\).

For \(0\leq x\leq1\), the probabilities of being at most \(x\) are \(p_1=x\), \(p_2=x/2\), and \(p_3=0\). At least two crossings then require both \(X_1\) and \(X_2\) to be at most \(x\), so \(F_{X_{(2)}}(x)=p_1p_2=x^2/2\).

For \(1\leq x\leq2\), the probabilities are \(p_1=1\), \(p_2=x/2\), and \(p_3=(x-1)/2\). Since \(X_1\) is then certainly at most \(x\), the second order statistic is at most \(x\) exactly when at least one of \(X_2,X_3\) is also at most \(x\). Independence gives

F_{X_{(2)}}(x) =1-(1-p_2)(1-p_3) =p_2+p_3-p_2p_3 =\frac{-x^2+5x-2}{4}.

For \(x\geq2\), both \(X_1\leq x\) and \(X_2\leq x\) with probability one, so the second smallest value is at most \(x\) with probability one. For \(x<0\), none of the variables is at most \(x\). Combining the intervals,

F_{X_{(2)}}(x)= \begin{cases} 0, & x<0,\\ x^2/2, & 0\leq x\leq1,\\ (-x^2+5x-2)/4, & 1\leq x\leq2,\\ 1, & x\geq2. \end{cases}

At \(x=1\), both formulas give \(1/2\); at \(x=2\), the middle formula gives \(1\). These checks confirm that the pieces agree at their shared endpoints. For example, at \(x=1.5\), the middle piece gives \((-2.25+7.5-2)/4=0.8125\).

Common Mistake: Using a Binomial Tail

A frequent error is to use the binomial formula for the threshold count without checking that the success probabilities are equal. The binomial distribution applies to a sum of independent Bernoulli variables with a common success probability. Here the indicators are independent, but their probabilities are \(F_i(x)\), which can differ.

For the four probabilities \(0.2,0.4,0.6,0.8\) in the first example, the average is \(0.5\). Treating all four indicators as if they had probability \(0.5\) would give a binomial probability of at least two successes equal to \(1-P(N_x=0)-P(N_x=1)=1-1/16-4/16=11/16=0.6875\), not the correct value \(0.7152\). The average probability does not preserve the distribution of the count. Use the subset formula or the recurrence with each \(F_i(x)\) kept distinct.

Key takeaway: For independent, nonidentically distributed variables, the CDF of \(X_{(k)}\) is the probability of at least \(k\) threshold crossings, with crossing probability \(F_i(x)\) for variable \(i\). Independence permits multiplication within each subset; differing CDFs require retaining the separate probabilities.

Check Your Understanding

Use the threshold-count interpretation to answer these questions.

For three independent variables with \(F_1(x)=0.1\), \(F_2(x)=0.5\), and \(F_3(x)=0.9\), write the subset-sum expression for \(P(X_{(2)}\leq x)\).
Which assumption allows the probability of a specified subset of threshold crossings to be written as a product?
For independent variables with different CDFs, explain why the count of values at most \(x\) need not have a binomial distribution.
State the recurrence for the probability of exactly \(j\) threshold crossings among the first \(m\) variables.
In the uniform example, why is \(P(X_{(2)}\leq x)=1\) for \(x\geq2\)?