Scan n distinct numbers in uniformly random order, recording every new maximum, including the first item. What is the…
Quant ResearchLevel: IntermediateRecords in a random order
Scan n distinct numbers in uniformly random order, recording every new maximum, including the first item. What is the expected number of records?
Hints
- Ask which of the first k positions holds their maximum.
- Linearity avoids needing independence of record events.
Answer
Item k is the maximum among the first k with probability 1/k by symmetry. Therefore expected records H_n=sum(1/k), approximately log n+gamma. Excluding initialization gives H_n-1.
Source and licence: Lehman, Leighton & Meyer — Mathematics for Computer Science (2018-06-06) · CC-BY-SA-3.0 · answer: Quantoros editorial