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 and 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).