Expected Number of Records in a Random Permutation

The expected number of record highs in a random permutation of n items equals the nth harmonic number, about 4.5 for a shuffled 52 card deck.

For a uniformly random permutation of n distinct items, the expected number of records, positions where the item is larger than everything that came before it, equals the nth harmonic number. For a shuffled 52 card deck dealt one card at a time, that works out to about 4.54 new highs on average over the course of the deal, a small number that grows only logarithmically as n increases.

Take a uniformly random ordering of n distinct values, say a shuffled deck read from top to bottom, or a random permutation of the numbers one through n. A record, sometimes called a left-to-right maximum, occurs at any position where the value there exceeds every value that appeared before it in the sequence. The first position is always a record by default, since nothing came before it.

The question treats the whole ordering as random, so the position and number of records both vary from one shuffle to the next, and the expected number of records is an average taken over every one of the n factorial equally likely orderings.

Define an indicator for each position i that equals one if the item in position i is a record. The key observation is that among the first i items in the sequence, in a uniformly random permutation, every one of those i items is equally likely to be the largest of the i, purely by symmetry, since the random ordering treats all i items interchangeably.

The item in position i is specifically a record only when it happens to be the largest among the first i items, which happens with probability one over i. This does not depend on what values are actually involved, only on the fact that all orderings of any i items are equally likely.