Suppose that I iterate over a list of n distinct integers in random order and keep track of the running maximum. What is the probability that the running maximum will take on $k$ distinct values throughout the iterating for $1 \le k \le n$?
For example, $P(\text{take on 1 distinct value}) = \\P(\text{largest element is the first element}) = \\1/n$.
As another example, consider the list (3, 5, 2, 1, 6, 8). While we iterate through it, the distinct running maxima are 3, 5, 6 and 8.
Thanks.
As a side note, I calculated that the expected amount of distinct running maxima is $1 + \frac12 + \frac13 + \cdots + \frac1n$. Assuming this is correct, it can be used as a sanity check.