A stream of 100 distinct values arrives in a uniformly random order. A value is a record if it exceeds everything seen before it. What is the expected number of records, and what is the standard deviation of that count?

A stream of 100 distinct values arrives in a uniformly random order. A value is a record if it exceeds everything seen before it. What is the expected number of records, and what is the standard deviation of that count?

Approach: Write the count as a sum of indicators, one per position, find each indicator's probability by a symmetry argument, then use the classical fact that these particular indicators are independent.

5.187. Let I_k be the indicator that the k-th arrival is a record. The largest of the first k values is equally likely to sit in any of those k positions, so P(I_k = 1) = 1/k. The expected number of records is therefore the harmonic number H_100 = 5.187. These indicator variables are independent for a uniform ordering, so the variance is sum (1/k)(1 - 1/k) = H_100 - 1.635 = 3.552, giving a standard deviation of 1.88. Records grow logarithmically, so doubling the stream to 200 values adds only log 2 = 0.69 records on average, and observing 9 records in 100 draws sits about two standard deviations above the mean, with 11 the three sigma point.

Follow-up: What is the probability that the stream produces no record after the very first value?

Key concepts: indicator variables, harmonic number, records, independence of indicators.