Mean and variance of the number of record highs

Question

Shuffle n distinct numbers into a uniformly random order and read them left to right. Position k is a record high if its value exceeds every value before it (position 1 is always a record). Let X be the number of record highs. What are E[X] and \mathrm{Var}(X)?

Accepted Answer

Write X = \sum{k=1}^n Ik, where Ik = 1 iff position k is a record high. Marginal probability. Among the first k values, each is equally likely to be the largest, so the k-th is a new record with probability P(Ik = 1) = \frac1k. Hence E[X] = \sum{k=1}^n \frac1k = Hn, the n-th harmonic number (about \ln n + 0.577). The key fact: the Ik are independent. Whether position k is a record depends only on the relative rank of the k-th element among the first k, and these relative-rank events at different positions are independent of one another. (This is the classic "records are independent" result.) …

Mean and variance of the number of record highs

Your answer

More Probability questions