A high-water mark in a sequence 
is a value at which the running
maximum increases, with the first value counted as a record. For example, given
a sequence 
with running maxima 
, the high-water marks are 
, which occur at 
, 2, 3, 4, and 8.
For independent identically distributed random variables with a common continuous distribution,
the expected number of high-water marks after 
measurements is the harmonic
number 
.
This can be seen by noting that the first measurement must by definition be a record
(so it contributes 1), the second measurement is equally likely to be higher or lower
than the first (so it contributes 1/2), two of the 
possible orderings of measurements have the third as a
record (so it contributes 
), and so on (Havil 2003, pp. 125-126). A comparison
of the number of records set in 
random trials of 
measurements with 
for 
to 100 is plotted above.
Applying the floor function to the expected number of records gives 
,
which for 
,
2, ... is given by 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, ...
(OEIS A055980). The least number of measurements
whose expected record count is at least 
is
 |
giving for 
,
2, 3, ... the values 1, 4, 11, 31, 83, 227, 616, 1674, 4550, 12367, ... (OEIS A004080), and for 
, 10, 100, ... the corresponding thresholds are 1, 12367,
15092688622113788323693563264538101449859497, ... (OEIS A096618).
