Sequential Relative Ranks and Independent Uniform Codes

From an Arrival Sequence to a Rank Code

Suppose observations arrive one at a time. When the $i$th value is observed, its position among the first $i$ values is available immediately, even though its position in the eventual full sample may change as more observations arrive. Recording that position at each arrival produces a sequential code for the sample’s ordering.

The distinction between an observation’s rank so far and its final rank is essential. Final ranks must occupy every position exactly once, so they are constrained. The sequential ranks have a different structure: under iid continuous sampling, each is uniform on its own range, and all are independent. Together, they still preserve the complete ordering information.

Definition: Let $X_1,\ldots,X_n$ be distinct observations. For $i=1,\ldots,n$, the sequential relative rank of $X_i$ is $$ R_i=1+\sum_{j=1}^{i-1} I(X_j<X_i), $$ where $I(A)=1$ if $A$ holds and $I(A)=0$ otherwise. Thus $R_i$ is the rank of $X_i$ among $X_1,\ldots,X_i$, with rank 1 assigned to the smallest value and rank $i$ to the largest. In particular, $R_1=1$.

For a continuous distribution, ties have probability zero, so these ranks are defined without a tie-breaking rule with probability one. The result below assumes $X_1,\ldots,X_n$ are iid from a continuous distribution. Identical distribution matters as well as continuity: it makes every ordering of the labels equally likely.

Worked Examples: Calculating and Decoding the Code

Worked Example: Computing Sequential Ranks from Data

Consider observations arriving in this order: $X_1=4.2,\ X_2=1.7,\ X_3=5.1,\ X_4=3.0,\ X_5=2.4$. Find the sequential relative ranks.

The first observation has rank $R_1=1$. Among the first two values, $1.7$ is the smaller, so $R_2=1$. The third value, $5.1$, is larger than both earlier values, giving $R_3=3$. Among the first four values, the order is $1.7,3.0,4.2,5.1$, so $R_4=2$. Among all five so far, $2.4$ is second-smallest, so $R_5=2$.

The code is therefore $(R_1,R_2,R_3,R_4,R_5)=(1,1,3,2,2)$. Notice that $R_1=1$ is fixed, while $R_i$ always belongs to $\{1,\ldots,i\}$.

Worked Example: Recovering the Full Ordering from a Code

Decode the code $(1,1,3,2,2)$. Keep an ordered list of observation labels, from smallest value to largest value. Start with label 1: the list is $[1]$. Insert each new label $i$ into position $R_i$ in the current list.

For $i=2$, insert label 2 in position 1 to obtain $[2,1]$. For $i=3$, insert label 3 in position 3 to obtain $[2,1,3]$. For $i=4$, insert label 4 in position 2 to obtain $[2,4,1,3]$. For $i=5$, insert label 5 in position 2 to obtain $[2,5,4,1,3]$.

The final list says $X_2<X_5<X_4<X_1<X_3$. Hence the final ranks of $X_1,\ldots,X_5$ are $(4,1,5,3,2)$. These agree with the original data: sorting $1.7,2.4,3.0,4.2,5.1$ gives labels $2,5,4,1,3$.

The insertion rule works because, before observation $i$ arrives, the ordered list contains exactly the labels $1,\ldots,i-1$. Its rank $R_i$ specifies the one position where label $i$ belongs in the enlarged list. Conversely, starting with a complete ordering, restrict it to labels $1,\ldots,i$ at each stage; the position of label $i$ in that restricted ordering recovers $R_i$. These two operations are inverse to each other.

Independence and Uniformity

Theorem: If $X_1,\ldots,X_n$ are iid from a continuous distribution, then $$ R_i\sim \operatorname{Uniform}\{1,\ldots,i\},\qquad i=1,\ldots,n, $$ and $R_1,\ldots,R_n$ are mutually independent. The vector $(R_1,\ldots,R_n)$ is in one-to-one correspondence with the full ordering of the observations.

Here a discrete uniform distribution on $\{1,\ldots,i\}$ assigns probability $1/i$ to each of the $i$ possible ranks. For $i=1$, this is the degenerate distribution $P(R_1=1)=1$. We prove the theorem by relating the code to the equally likely orderings of an iid continuous sample.

Write an ordering as a list of labels $(\sigma_1,\ldots,\sigma_n)$, meaning $X_{\sigma_1}<\cdots<X_{\sigma_n}$. Because the distribution is continuous, ties have probability zero. Thus the $n!$ possible strict orderings are disjoint and exhaust the sample space up to a probability-zero event. Since the observations are iid, relabeling them does not change their joint distribution. All $n!$ ordering events consequently have equal probability, and each has probability $1/n!$.

Start with a code.
Choose $r_i\in\{1,\ldots,i\}$ for each $i=1,\ldots,n$. Begin with the list $[1]$, then insert label $i$ in position $r_i$ for each successive $i$.

Obtain one ordering.
Each insertion is unique, so the procedure produces exactly one ordering of all $n$ labels.

Reverse the construction.
Given an ordering, restrict it to labels $1,\ldots,i$ and record the position of label $i$. This recovers exactly one $r_i$ at every step.

The code-to-ordering map is therefore a bijection. There are $1\cdot2\cdots n=n!$ possible code vectors, since coordinate $i$ has $i$ possible values. Each code vector corresponds to exactly one ordering, so each code vector has probability $1/n!$. In particular, for any allowed $r_1,\ldots,r_n$,

P(R_1=r_1,\ldots,R_n=r_n) =\frac{1}{n!} =\prod_{i=1}^{n}\frac{1}{i}.

To verify mutual independence directly, take any subsets $A_i\subseteq\{1,\ldots,i\}$. Summing the joint probability over the code vectors with $r_i\in A_i$ gives

P(R_1\in A_1,\ldots,R_n\in A_n) =\frac{\prod_{i=1}^{n}|A_i|}{n!} =\prod_{i=1}^{n}\frac{|A_i|}{i} =\prod_{i=1}^{n}P(R_i\in A_i).

This is the defining factorization for mutual independence. Taking all coordinates except $i$ to have their full ranges also gives $P(R_i=r)=1/i$ for every $r\in\{1,\ldots,i\}$, proving the stated marginal distributions. The bijection establishes the encoding claim. $\square$

Worked Example: Probability of a Particular Full Ordering

For four observations from a continuous iid distribution, find the probability that their increasing order of labels is $(3,1,4,2)$; that is, $X_3<X_1<X_4<X_2$.

Recover the code by considering prefixes of labels. With label 1 alone, the list is $[1]$, so $R_1=1$. Restricting the target order to labels 1 and 2 gives $[1,2]$, so label 2 is inserted in position 2 and $R_2=2$. Restricting to labels 1, 2, and 3 gives $[3,1,2]$, so $R_3=1$. The full order places label 4 in position 3, giving $R_4=3$.

Thus the code is $(1,2,1,3)$. By independence and uniformity, the probability of this code, and therefore of the specified ordering, is

P(R_1=1,R_2=2,R_3=1,R_4=3) =1\cdot\frac12\cdot\frac13\cdot\frac14 =\frac{1}{24}.

This equals $1/4!$, as it must: every ordering of four iid continuous observations has the same probability.

What the Code Does—and Does Not—Say

The code is useful because it turns a random ordering into a sequence of independent coordinates with simple finite supports. For example, probabilities of restrictions on several sequential ranks can be calculated by multiplying their marginal probabilities. It also gives a lossless representation: knowing all $R_i$ is equivalent to knowing the full ordering of the observation labels.

The final ranks are different variables. If $\Pi_j$ denotes the rank of $X_j$ among all $n$ observations, then $(\Pi_1,\ldots,\Pi_n)$ must be a permutation of $1,\ldots,n$. Those coordinates cannot be mutually independent. For $n=2$, for instance, $\Pi_1+\Pi_2=3$ with probability one. Do not transfer the independence result for $R_i$ to $\Pi_j$.

The assumptions also matter. Continuity ensures there are no ties, while identical sampling ensures all label orderings are equally likely. With independent but nonidentically distributed observations, ties may still be absent, but the ordering probabilities generally differ. For example, if $X_1$ is concentrated near a much smaller range than $X_2$, the event $X_1<X_2$ need not have probability $1/2$; then $R_2$ is not uniform on $\{1,2\}$.

Common Pitfalls

Confusing sequential ranks with final ranks. $R_i$ uses only $X_1,\ldots,X_i$. Later observations can change $X_i$'s final rank, but they do not change $R_i$.
Claiming a rank can take any value from 1 to $n$. The support of $R_i$ is $\{1,\ldots,i\}$, not $\{1,\ldots,n\}$.
Assuming independence from the definition alone. The ranks are functions of overlapping sets of observations. Their independence follows from the equal-likelihood ordering argument and the bijection, not merely from being defined at different times.
Ignoring the sampling assumptions. Continuity rules out ties; the iid assumption supplies exchangeability and equal probabilities for the orderings.

Key takeaway: For an iid continuous sample, the sequential relative ranks form independent discrete uniforms with supports $\{1\},\{1,2\},\ldots,\{1,\ldots,n\}$. Inserting each new label at its recorded rank reconstructs the sample’s complete ordering.

Check Your Understanding

Use the definitions and insertion rule to answer these questions.

For observations $X_1=6,\ X_2=2,\ X_3=5,\ X_4=8$, calculate $(R_1,R_2,R_3,R_4)$.
What is the support and probability mass function of $R_5$ under iid continuous sampling?
Decode the code $(1,2,1,4)$ into the increasing order of labels.
For $n=3$, calculate the probability of the code $(1,1,2)$.
Why does the theorem not imply that the final ranks of the observations are independent?