Katkat
Back

Find the Expected Number of Record Maxima

WorldquantData Scientist · Technical Screen
MediumData ScientistTechnical ScreenStatistics & Math

Last updated

A permutation of the distinct values `1` through `100` is revealed from left to right. Explain the assumptions and derivation clearly, check edge cases, and show how the result changes when those assumptions no longer hold.

A permutation of the distinct values 1 through 100 is revealed from left to right. Replace the current maximum whenever the revealed value is strictly greater than every earlier value.

  1. What is the expected number of replacements?
  2. Repeat the calculation when the shuffled multiset is 1, 2, ..., 98, 100, 100, where a second copy equal to the current maximum does not count as a replacement.

Constraints & Assumptions

  • Every ordering of the distinct list is equally likely.
  • For the multiset, start from a uniformly random permutation of labeled copies and then ignore the labels on the two 100 values.
  • The first revealed value counts as a replacement.

Hints

Hint 1

Use indicator variables: For each value, ask whether it appears before every strictly larger value.

Follow-up questions

  • What is the asymptotic growth of the expectation?
  • How would a replace-on-greater-or-equal rule change the duplicate case?
  • What is the probability of exactly one replacement in the distinct case?