Published 13 September 2026

Records in a permutation

Reveal a uniformly random ordering of the distinct ranks one through n. Here larger ranks are better. A record high is a rank larger than every one previously revealed. The first rank is always a record, but records become rarer as more competitors accumulate.

How many should we expect? The answer grows like the logarithm of n, rather than a fixed fraction of n. We can derive the mean without enumerating all n-factorial permutations, and then calculate the entire count distribution.

Reveal the record process

Filled squares identify record highs in the revealed prefix. Open circles are ranks that fail to beat the previous maximum. Increasing the reveal count retains the same underlying permutation. Changing n creates a new permutation of a different set of ranks; it does not append observations to the old one.

The theoretical chart describes the total number of records before any ranks are observed. Likewise, the harmonic expectation for the revealed length is unconditional. It is not a forecast that ignores the information in the actual displayed ranks. Once the overall maximum has appeared, for example, we know there can be no more records.

One indicator per position

Let Iᵢ equal one when position i is a record and zero otherwise. Among the first i positions, symmetry makes each position equally likely to hold their largest rank. Consequently P(Iᵢ = 1) = 1/i. The total number of records Rₙ is their sum, so linearity of expectation gives

E[Rₙ] = 1 + 1/2 + 1/3 + ... + 1/n = Hₙ.

Independence is not needed for that expectation argument. For n = 3 the mean is 11/6. The six permutations have record counts one, one, two, two, two, and three, producing that same mean. For n = 100 the expected count is approximately 5.187378, even though a perfectly increasing ordering would set one hundred records.

Why the indicators are independent

There is a useful stronger fact for a uniform permutation of distinct ranks. Describe each arriving rank by its relative position among the first i ranks. That relative position can be any integer from one to i. Every permissible sequence of these relative positions corresponds to exactly one permutation: reconstruct the relative order by successive insertion, then assign the final ranks.

Uniformity over permutations therefore makes these relative positions independent and uniform on their respective sets. A record occurs exactly when the relative position is i. Thus the record indicators are independent Bernoulli variables with different success probabilities 1/i.

This does not mean the actual rank values are independent, or that knowing an absolute maximum provides no information. Independence of the record indicators concerns their unconditional joint distribution under uniform random ordering.

Build the count distribution

Let qᵢ(k) be the probability of k records in the first i positions. Start with q₀(0) = 1. The next position either fails to set a record or adds one, giving

qᵢ(k) = (1 − 1/i) qᵢ₋₁(k) + (1/i) qᵢ₋₁(k−1).

This recurrence generates the chart. Its coefficients are also the unsigned Stirling numbers of the first kind divided by n!. Independence gives variance equal to the sum of (1/i)(1 − 1/i), or Hₙ minus the sum of reciprocal squares. At n = 3 the count probabilities are 1/3, 1/2, and 1/6 for one, two, and three records.

Stanley’s Enumerative Combinatorics, section 1.3 and the exercises on permutation records, connects left-to-right maxima, permutation cycles, and record indicators. Continue to the secretary problem to see why recognizing a record and deciding to stop on it are different tasks.