Discrete Order Statistics And Ties

Why Ties Change the Calculation

When observations come from a discrete distribution, several sampled values can be identical. Sorting the sample still defines each rank, but ties are allowed: the first, second, or later order statistic may have the same value. A formula that treats the observations as if they must all be distinct will therefore miss probability mass.

The key distinction is between $P(X_{(k)}\leq x)$, a cumulative probability, and $P(X_{(k)}=a)$, the probability at a particular value $a$. For a discrete distribution, the cdf has jumps. The size of the jump at $a$ is exactly the probability that one observation equals $a$, and the order statistic can have a jump there too.

Definition: Let $X_1,\ldots,X_n$ be independent and identically distributed (iid) discrete random variables. Arrange their observed values in ascending order, retaining repetitions. The $k$th order statistic, denoted $X_{(k)}$, is the value in position $k$, where $1\leq k\leq n$. Thus $X_{(1)}$ is the sample minimum and $X_{(n)}$ is the sample maximum. Repeated values occupy repeated positions.

Write $F_X(x)=P(X_i\leq x)$ for the common parent cdf. At a possible value $a$, define $F_X(a-)=P(X_i<a)$. For a discrete variable, the point mass at $a$ is $F_X(a)-F_X(a-)$. Independence and identical distribution are essential for the binomial formulas below: without independence, the number of observations at or below a threshold need not have a binomial distribution; without identical distributions, its success probabilities can differ.

The Cumulative Probability

The event $X_{(k)}\leq x$ occurs exactly when at least $k$ of the $n$ observations are at most $x$. Each observation has probability $F_X(x)$ of meeting that condition. Consequently, the count of observations at or below $x$ has a binomial distribution with parameters $n$ and $F_X(x)$.

Theorem: For an iid sample of size $n$ with parent cdf $F_X$, the cdf of the $k$th order statistic is $$ P(X_{(k)}\leq x)=\sum_{j=k}^{n}\binom{n}{j}F_X(x)^j\bigl(1-F_X(x)\bigr)^{n-j}. $$ This result holds for discrete, continuous, and mixed distributions. In the discrete case, it gives cumulative probabilities at thresholds; it does not by itself give the probability that the order statistic equals a threshold.

The formula can also be written as one minus the probability that at most $k-1$ observations are at or below $x$. That version can be shorter when $k$ is near $n$. The reason the formula works is an event equivalence, not an assumption that the observations have distinct values:

Translate the rank event.
The $k$th value in ascending order is at most $x$ if and only if at least $k$ sample values are at most $x$.

Model the count.
For each observation, the event $X_i\leq x$ has probability $F_X(x)$. The $n$ indicator variables are independent, so their sum is binomial with parameters $n$ and $F_X(x)$.

Add the possible counts.
The event requires a count of $k,k+1,\ldots,n$. Adding those binomial probabilities gives the stated cdf.

Point Probabilities at a Jump

To find $P(X_{(k)}=a)$, subtract the cdf immediately below $a$ from the cdf at $a$. This subtraction isolates the jump at $a$. It is important to use $F_X(a-)$, not $F_X(a)$, for the lower endpoint: $F_X(a)$ already includes observations equal to $a$.

Theorem: For an atom $a$ of the parent distribution, let $T_{n,k}(p)=\sum_{j=k}^{n}\binom{n}{j}p^j(1-p)^{n-j}$. Then $$ P(X_{(k)}=a)=T_{n,k}\bigl(F_X(a)\bigr)-T_{n,k}\bigl(F_X(a-)\bigr). $$ Equivalently, the event requires fewer than $k$ observations strictly below $a$, while at least $k$ observations are at or below $a$. The difference-of-cdfs formula includes all possible numbers of ties at $a$.

The difference formula follows directly from nested events. Every outcome with $X_{(k)}\leq a-$ also has $X_{(k)}\leq a$; subtracting the former event leaves precisely outcomes with $X_{(k)}=a$. Here $a-$ means the strict threshold $X_{(k)}<a$, not a numerical value that must be chosen just below $a$. This matters when the support has gaps.

Worked Calculations

Worked Example: Finding the Distribution Across Three Atoms

A hypothetical quality-control sample consists of $n=4$ iid devices. Let $X_i$ be the number of calibration corrections needed by device $i$, with $P(X_i=0)=0.20$, $P(X_i=1)=0.50$, and $P(X_i=2)=0.30$. Find the full distribution of $X_{(2)}$, the second-smallest number of corrections.

Method. Calculate the order-statistic cdf at each support value using a binomial tail, then take its jumps to obtain point probabilities. This method allows ties rather than treating the ranks as distinct.

At $0$, $F_X(0)=0.20$. The event $X_{(2)}\leq0$ requires at least two of four devices to need zero corrections:

P(X_{(2)}\leq0)=\binom{4}{2}(0.20)^2(0.80)^2 +\binom{4}{3}(0.20)^3(0.80)+(0.20)^4 =0.1536+0.0256+0.0016=0.1808.

There is no support value below $0$, so $P(X_{(2)}=0)=0.1808$.

At $1$, $F_X(1)=0.20+0.50=0.70$. The probability that at least two observations are at most $1$ is

P(X_{(2)}\leq1) =1-\left[\binom{4}{0}(0.30)^4+\binom{4}{1}(0.70)(0.30)^3\right] =1-(0.0081+0.0756)=0.9163.

Therefore the probability at $1$ is the jump from the cdf at $0$ to the cdf at $1$:

P(X_{(2)}=1)=0.9163-0.1808=0.7355.

At $2$, the cdf is $1$, since every observation is at most $2$. Thus $P(X_{(2)}=2)=1-0.9163=0.0837$. The check is $0.1808+0.7355+0.0837=1.0000$. The middle value has substantial probability because repeated observations at $1$ are allowed.

Worked Example: A Point Mass With Ties at the Target Value

A hypothetical shipment has $n=5$ iid packages. For each package, the recorded category $X_i$ is below, equal to, or above category $a$, with probabilities $0.25$, $0.40$, and $0.35$, respectively. Find the probability that $X_{(3)}=a$.

Method. Use the difference of binomial tails at the jump. The cumulative probability at $a$ is $F_X(a)=0.25+0.40=0.65$; immediately below $a$, it is $F_X(a-)=0.25$.

First calculate $T_{5,3}(0.65)$, the probability that at least three packages are at or below $a$:

T_{5,3}(0.65) =\binom{5}{3}(0.65)^3(0.35)^2 +\binom{5}{4}(0.65)^4(0.35)+(0.65)^5 =0.336415625+0.3123859375+0.1160290625 =0.764830625.

Next calculate $T_{5,3}(0.25)$, the probability that at least three packages are strictly below $a$:

T_{5,3}(0.25) =\binom{5}{3}(0.25)^3(0.75)^2 +\binom{5}{4}(0.25)^4(0.75)+(0.25)^5 =0.087890625+0.0146484375+0.0009765625 =0.103515625.

Subtracting gives $$ P(X_{(3)}=a)=0.764830625-0.103515625=0.661315. $$

The answer is $0.6613$ to four decimal places. This includes outcomes with three, four, or five observations at or below $a$, provided the third order statistic equals $a$. Check: the result is between $0$ and $1$, as a probability must be.

Worked Example: Using Cdf Jumps to Recover Every Rank Value

A hypothetical group of $n=4$ independent sensors has a discrete error score $X_i$ with $P(X_i=1)=0.50$, $P(X_i=4)=0.25$, and $P(X_i=9)=0.25$. Find the distribution of $X_{(3)}$.

Method. Evaluate the binomial tail for the cdf at each distinct score and difference successive cdf values. This also checks that no probability has been lost between support points.

At $1$, $F_X(1)=0.50$. Thus $$ P(X_{(3)}\leq1) =\binom{4}{3}(0.50)^3(0.50)+(0.50)^4 =0.25+0.0625=0.3125. $$ So $P(X_{(3)}=1)=0.3125$.

At $4$, $F_X(4)=0.75$. The cdf is $$ P(X_{(3)}\leq4) =\binom{4}{3}(0.75)^3(0.25)+(0.75)^4 =0.421875+0.31640625=0.73828125. $$ The point probability at $4$ is therefore $0.73828125-0.3125=0.42578125$.

At $9$, the cdf is $1$, so the remaining probability is $P(X_{(3)}=9)=1-0.73828125=0.26171875$. To four decimal places, the distribution is $0.3125$ at $1$, $0.4258$ at $4$, and $0.2617$ at $9$. The unrounded probabilities sum to $1$, confirming the calculation.

Common Mistake: Confusing a Cdf Value With a Point Mass

A frequent error is to calculate $T_{n,k}(F_X(a))$ and report it as $P(X_{(k)}=a)$. That quantity is $P(X_{(k)}\leq a)$, so it includes every possible order-statistic value below $a$ as well as $a$ itself.

For example, in the first worked example, reporting $0.9163$ as $P(X_{(2)}=1)$ is wrong: $0.9163=P(X_{(2)}\leq1)$. The correction is to subtract the cdf below $1$: $0.9163-0.1808=0.7355$. Another tempting shortcut is to count only outcomes with exactly $k$ observations equal to $a$. That omits valid cases with more than $k$ values equal to $a$; the rank event is determined by how many observations are below and at-or-below $a$, not by requiring exactly $k$ ties.

Key takeaway: For a discrete order statistic, first identify the parent cdf immediately below the target and at the target. The point probability is the difference between the two corresponding binomial tails. This jump calculation automatically accounts for every permitted pattern of ties.

Check Your Understanding

For each problem, use the rank event and the cdf jump carefully. Give probabilities to four decimal places where needed.

An iid sample of size $3$ takes values $2$ and $5$, with probabilities $0.40$ and $0.60$. Find $P(X_{(2)}=2)$. (Answer: $0.3520$)
For an iid sample of size $4$, a target value $a$ has $F_X(a-)=0.30$ and $F_X(a)=0.80$. Find $P(X_{(2)}=a)$. (Answer: $0.6245$)
For an iid sample of size $5$, suppose $F_X(a-)=0.20$ and $F_X(a)=0.60$. Find $P(X_{(4)}=a)$. (Answer: $0.3302$)
An iid sample of size $3$ has a discrete parent distribution with $F_X(a-)=0.40$ and $F_X(a)=0.70$. Find the probability that the sample maximum equals $a$. (Answer: $0.2790$)
For an iid sample of size $6$, suppose $F_X(a-)=0.25$ and $F_X(a)=0.50$. Find $P(X_{(2)}=a)$. (Answer: $0.4246$)

What You'll Learn