Rank Probabilities from Threshold Counts

From Order Statistics to Threshold Counts

An event about an order statistic can often be decided without finding its density. To determine whether \(X_{(r)}\) is below a threshold \(t\), count how many observations fall at or below \(t\): the event occurs exactly when at least \(r\) observations do. With several order statistics and thresholds, this idea leads to a finite collection of count constraints and a multinomial probability calculation.

Throughout, let \(X_1,\ldots,X_n\) be independent and identically distributed random variables with a continuous distribution function \(F\). Write \(X_{(1)}\le\cdots\le X_{(n)}\) for their order statistics. Continuity ensures that any fixed threshold has probability zero of being an observation, so endpoint choices do not change the probabilities below. The method uses only the probabilities assigned by \(F\) to threshold-defined intervals.

Definition: Given ordered thresholds \(t_1<\cdots<t_m\), partition the real line into the categories \((-\infty,t_1]\), \((t_1,t_2],\ldots,(t_{m-1},t_m]\), and \((t_m,\infty)\). Let \(N_j\) be the number of sample observations in category \(j\), and let \(p_j\) be its probability. Thus \(N_1+\cdots+N_{m+1}=n\), with \(p_1+\cdots+p_{m+1}=1\).

The cumulative count through threshold \(t_j\) is \(N_1+\cdots+N_j\). This count determines the order-statistic comparisons at that threshold:

X_{(r)}\le t_j \quad\Longleftrightarrow\quad N_1+\cdots+N_j\ge r.

The complementary comparison is just as useful: \(X_{(r)}>t_j\) exactly when at most \(r-1\) observations are at or below \(t_j\). For an interval condition, both sides of the interval give a count constraint. In particular,

t_{j-1}<X_{(r)}\le t_j \quad\Longleftrightarrow\quad N_1+\cdots+N_{j-1}<r\le N_1+\cdots+N_j.

The Multinomial Count Formula

Each observation independently falls into exactly one of the threshold categories. The vector of category counts therefore has a multinomial distribution. For nonnegative integers \(n_1,\ldots,n_{m+1}\) summing to \(n\),

P(N_1=n_1,\ldots,N_{m+1}=n_{m+1}) = \frac{n!}{n_1!\cdots n_{m+1}!} \prod_{j=1}^{m+1}p_j^{n_j}.

To see the formula, first fix one particular assignment of the \(n\) labelled observations to categories, with \(n_j\) observations assigned to category \(j\). Independence gives that assignment probability \(\prod_j p_j^{n_j}\). The number of distinct assignments with those counts is \(n!/(n_1!\cdots n_{m+1}!)\): permuting the \(n\) observations gives \(n!\) orders, while permutations within each category do not change the assignment. Summing the equal assignment probabilities gives the stated count probability.

Theorem: Suppose an event \(A\) involving order statistics can be expressed as a set \(S\) of nonnegative integer count vectors \((n_1,\ldots,n_{m+1})\), each summing to \(n\), by using the cumulative-count equivalences above. Then

P(A)= \sum_{(n_1,\ldots,n_{m+1})\in S} \frac{n!}{n_1!\cdots n_{m+1}!} \prod_{j=1}^{m+1}p_j^{n_j}.

Proof: The count-vector events in the sum are disjoint: a sample has exactly one vector of category counts. By the assumed translation, their union is precisely \(A\). Apply the multinomial probability formula to each vector and add the probabilities of these disjoint events. \(\square\)

This theorem gives a systematic route: write the threshold probabilities, translate each order-statistic condition into inequalities on cumulative counts, and sum over every count vector meeting those inequalities. The examples show how to carry out the translation and the arithmetic.

Worked Example: One Order Statistic Below and Another Above

Let \(n=6\), and choose \(a<b\) such that \(F(a)=1/3\) and \(F(b)=2/3\). Find \(P(X_{(2)}\le a,\ X_{(5)}>b)\).

Use the three categories \((-\infty,a]\), \((a,b]\), and \((b,\infty)\). Their probabilities are \(1/3,1/3,1/3\). Write their counts as \(N_1,N_2,N_3\). The first condition requires \(N_1\ge2\). The second requires \(N_1+N_2\le4\), since at most four observations can be at or below \(b\) if the fifth order statistic is above \(b\). Thus the allowed counts have \(2\le N_1\le4\) and \(0\le N_2\le4-N_1\), with \(N_3=6-N_1-N_2\).

Every allowed count vector has probability \(\frac{6!}{N_1!N_2!N_3!}(1/3)^6\). The multinomial coefficients for the allowed vectors are:

\begin{aligned} N_1=2 &: \quad \frac{6!}{2!0!4!}+\frac{6!}{2!1!3!}+\frac{6!}{2!2!2!}=15+60+90=165,\\ N_1=3 &: \quad \frac{6!}{3!0!3!}+\frac{6!}{3!1!2!}=20+60=80,\\ N_1=4 &: \quad \frac{6!}{4!0!2!}=15. \end{aligned}

The total coefficient is \(165+80+15=260\). Therefore,

P(X_{(2)}\le a,\ X_{(5)}>b) =260\left(\frac13\right)^6 =\frac{260}{729}.

The count constraints also confirm that the event is possible: for example, counts \((2,0,4)\) satisfy both conditions.

Worked Example: Two Order Statistics in Separate Intervals

Let \(n=5\), with thresholds \(a<b<c\) satisfying \(F(a)=0.2\), \(F(b)=0.6\), and \(F(c)=0.9\). Find the probability that \(X_{(2)}\in(a,b]\) and \(X_{(5)}\in(b,c]\).

The four category probabilities are \(0.2,0.4,0.3,0.1\). Let the corresponding counts be \(N_1,N_2,N_3,N_4\). The first order statistic condition is \(N_1<2\le N_1+N_2\). The second is \(N_1+N_2<5\le N_1+N_2+N_3\). Since there are only five observations, the last inequality forces \(N_4=0\) and \(N_1+N_2+N_3=5\). Together the constraints say \(N_1\le1\) and \(2\le N_1+N_2\le4\).

For \(N_1=0\), the allowed triples \((N_2,N_3,N_4)\) are \((2,3,0),(3,2,0),(4,1,0)\). Their probabilities are

\begin{aligned} 10(0.4)^2(0.3)^3&=0.0432,\\ 10(0.4)^3(0.3)^2&=0.0576,\\ 5(0.4)^4(0.3)&=0.0384. \end{aligned}

These sum to \(0.1392\). For \(N_1=1\), the allowed triples are \((1,3,0),(2,2,0),(3,1,0)\). Their probabilities are

\begin{aligned} 20(0.2)(0.4)(0.3)^3&=0.0432,\\ 30(0.2)(0.4)^2(0.3)^2&=0.0864,\\ 20(0.2)(0.4)^3(0.3)&=0.0768. \end{aligned}

These sum to \(0.2064\). No other count vectors satisfy the constraints, so the requested probability is \(0.1392+0.2064=0.3456\).

Worked Example: A Lower Bound and an Upper Bound

Let \(n=7\), and suppose \(F(a)=0.4\) and \(F(b)=0.8\), where \(a<b\). Find \(P(X_{(3)}>a,\ X_{(5)}\le b)\).

The categories \((-\infty,a]\), \((a,b]\), and \((b,\infty)\) each have probability \(0.4,0.4,0.2\), respectively. Write their counts as \(N_1,N_2,N_3\). The event requires \(N_1\le2\) and \(N_1+N_2\ge5\). Thus \(N_1=i\) can be \(0,1,2\), and for each \(i\), \(N_2=j\) ranges from \(5-i\) to \(7-i\). With \(N_3=7-i-j\), the contribution for each pair \((i,j)\) is

\frac{7!}{i!j!(7-i-j)!}(0.4)^{i+j}(0.2)^{7-i-j}.

To add the terms exactly, write \(0.4=2/5\) and \(0.2=1/5\), so the common denominator is \(5^7=78125\). The numerator contributions, grouped by \(i\), are

\begin{aligned} i=0 &: \quad 21(2^5)+7(2^6)+2^7=672+448+128=1248,\\ i=1 &: \quad 105(2^5)+42(2^6)+7(2^7)=3360+2688+896=6944,\\ i=2 &: \quad 210(2^5)+105(2^6)+21(2^7)=6720+6720+2688=16128. \end{aligned}

The total numerator is \(1248+6944+16128=24320\). Consequently,

P(X_{(3)}>a,\ X_{(5)}\le b) =\frac{24320}{78125}=0.311296.

For a quick direction check, the first condition permits no more than two observations below \(a\), while the second requires at least five observations below \(b\). The count ranges used above express both requirements.

A Reliable Calculation Strategy

For a more complicated event, the arithmetic can be organized before any probabilities are calculated. The count constraints are the essential step; once they are correct, the multinomial formula supplies each term.

List the thresholds in order.
Use them to form disjoint intervals covering the real line, then find each interval probability from \(F\).

Translate each condition.
At a threshold \(t\), \(X_{(r)}\le t\) means the cumulative count is at least \(r\); \(X_{(r)}>t\) means it is at most \(r-1\).

Enumerate feasible counts.
Require nonnegative integer counts summing to \(n\), and retain exactly those satisfying all translated inequalities.

Sum multinomial probabilities.
For each feasible vector, multiply its multinomial coefficient by the corresponding category probabilities raised to their counts.

Common Mistake: Reversing the Count Inequality

A frequent error is to say that \(X_{(r)}>t\) requires at least \(r\) observations to be at or below \(t\). That reasoning reverses the order: if at least \(r\) observations are at or below \(t\), then the \(r\)th order statistic is at or below \(t\), not above it. The correct condition is that at most \(r-1\) observations are at or below \(t\).

Another tempting shortcut is to treat the counts in different categories as independent. They are not independent: their sum is fixed at \(n\). The multinomial probability includes that constraint and the combinatorial factor counting all arrangements. Use the multinomial formula for the joint count vector rather than multiplying separate count probabilities.

Key takeaway: Order-statistic events at fixed thresholds are cumulative-count events. After partitioning the sample space into threshold intervals, exact probabilities follow by summing multinomial probabilities over the count vectors that satisfy the event.

Check Your Understanding

Translate each event into a condition on cumulative threshold counts before attempting any calculation.

For \(n=8\), express \(X_{(4)}>t\) as an inequality involving the number of observations at or below \(t\).
For \(a<b\), express \(a<X_{(3)}\le b\) using counts in \((-\infty,a]\) and \((-\infty,b]\).
If \(F(a)=0.25\) and \(F(b)=0.70\), what are the probabilities of the three categories \((-\infty,a]\), \((a,b]\), and \((b,\infty)\)?
For an event requiring \(X_{(2)}\le a\) and \(X_{(4)}>b\), with \(a<b\), state the two cumulative-count constraints.
Why must the joint category counts be handled with a multinomial distribution rather than as independent counts?

Rank Probabilities from Threshold Counts

What You'll Learn