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.


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.

  • $\begingroup$ The mean is right. $\endgroup$ – André Nicolas Oct 2 '12 at 1:22

I will assume that the $n$ distinct integers are in fact $\{ 1, 2, ... n \}$ in some order. This makes no difference to the relevant probabilities.

Interpret the list of numbers as cycle notation describing a permutation of $n$ elements as follows: only write down cycle notation in which the elements of each cycle have been cyclically sorted so that the greatest element is first and the cycles themselves have been sorted by their greatest elements from least to greatest. For example,


describes the permutation


Then the number of distinct running maxima is precisely the number of cycles of the corresponding permutation, so what you want to know is the distribution of the number of cycles of a random permutation of $n$ elements.

The answer is given by the (unsigned) Stirling numbers of the first kind (divided by $n!$). These are the coefficients in the expansion of

$$\frac{z(z + 1)...(z + (n-1))}{n!} = {z + n - 1 \choose n}.$$

As $n \to \infty$, the distribution approaches a normal distribution with mean $\log n + \gamma$ (where $\gamma$ is the Euler-Mascheroni constant) and variance $\sqrt{\log n}$. Proofs of this kind of statement and much more can be extracted from the last section of Flajolet and Sedgewick's Analytic Combinatorics; this particular example is Example IX.9 (p. 644).

| cite | improve this answer | |
  • $\begingroup$ Thank you for your elaborate answer. So P(you encounter k distinct running maxima) = ((k + n - 1) choose n)? Setting k = 1, this gives 1, but this should be 1/n (probability that the largest element is the first in the list). Is ((k + n - 1) choose n) the probability that you see at least k distinct maxima? Thanks. $\endgroup$ – abw333 Oct 2 '12 at 2:06
  • 1
    $\begingroup$ @abw333: no. The probability is the coefficient of $z^k$ in the polynomial ${z + n - 1 \choose n}$. Setting $k = 1$ the only contribution to the $z$ term is $\frac{z(1)(2)...(n-1)}{n!} = \frac{z}{n}$ as expected. $\endgroup$ – Qiaochu Yuan Oct 2 '12 at 2:17
  • $\begingroup$ So, in the case when n = 3, and you have that the array is [3, 1, 2], what permutation would that describe? Thanks. $\endgroup$ – abw333 Oct 2 '12 at 18:47
  • $\begingroup$ @QiaochuYuan: but don't the elements of each cycle have to be in decreasing order? In this case, you can just flip them around and it will work, but will it work in general? $\endgroup$ – abw333 Oct 3 '12 at 1:28
  • $\begingroup$ @abw333: you're right, that isn't in agreement with the convention I used in the answer. I mean $(312)$. (I should clarify in the answer that the cycles should be cyclically sorted so that their greatest element comes first, but in general it won't be possible to cyclically sort a cycle so that all of the elements are in any particular order.) $\endgroup$ – Qiaochu Yuan Oct 3 '12 at 2:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.