2
$\begingroup$

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.

  • 0
    The mean is right.2012-10-02

1 Answers 1

4

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,

$21534678$

describes the permutation

$(21)(534)(6)(7)(8).$

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

  • 0
    @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.)2012-10-03