Expected Number and Variance of Records in a Random Permutation

MediumProbability

Reported in interviews at Citi Two Sigma

Problem statement

Draw a uniformly random permutation of $\{1, 2, \ldots, n\}$. Call position $k$ a record if the value at position $k$ is strictly larger than all values at positions $1, 2, \ldots, k-1$ (position 1 is always a record). Let $R_n$ denote the total number of records.

  1. Compute $E[R_n]$ exactly.
  1. Compute $\text{Var}(R_n)$ exactly.
  1. For large $n$, give simple approximations for both and explain the connection to harmonic numbers.
Show hint

Can you write the record count as a sum of simpler random variables, one per position?

Relevant roles: Data Scientist, Applied Scientist and Research Scientist.

Related free problems