Given a sequence of values 
, the high-water marks are the values at which
the running maximum increases. For example, given
a sequence 
with running maxima 
, the high-water marks are 
, which occur at 
, 2, 3, 4, and 8.
For independent random variables, the expected number of high-water marks after 
measurements is 
. 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.
The number of records after 
measurements is therefore 
, 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 number of measurements needed to obtain 
records is therefore ![[n]](/images/equations/High-WaterMark/Inline18.svg)
, where 
are the values such that
 |
giving for 
,
2, 3, ... the values 1, 4, 11, 31, 83, 227, 616, 1674, 4550, 12367, ... (OEIS A004080), and for 
, 10, 100, ... records are therefore 1, 12367, 15092688622113788323693563264538101449859497,
... (OEIS A096618).
