Expected number of record highs in a random sequence
Asked at Jane Street
You read distinct numbers one at a time in a uniformly random order. A value is a record if it is larger than everything before it (the first value is always a record).
What is the expected number of records?
Show a hint
The -th value is a record exactly when it is the largest of the first values seen. By symmetry, how likely is that?
Your answer
This one is open-ended. Work it through, then check your reasoning against the full solution.