Expected number of new highs in a random ranking

Question

Ten traders finish the year with distinct PnLs, and you review them in a uniformly random order. You call it a "record" each time a trader's PnL exceeds every trader reviewed before them (the first trader is always a record).

What is the expected number of records?

Accepted Answer

Let X be the number of records. For position k in the review order, define Ik = 1 if the k-th trader reviewed beats all k-1 before them (equivalently, is the largest among the first k reviewed). Then X = \sum{k=1}^{10} Ik. Among the first k traders reviewed, each is equally likely to be the largest by symmetry, so the k-th is the largest with probability 	frac{1}{k}: E[Ik] = \frac{1}{k}. By linearity of expectation, E[X] = \sum{k=1}^{10} \frac{1}{k} = H{10} = 1 + 	frac12 + 	frac13 + \cdots + 	frac{1}{10} \approx 2.93. So about 2.93 records on average. For n items the answer is the harmoni…

Expected number of new highs in a random ranking

Your answer

More Probability questions