Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
The mean is right. –  André Nicolas Oct 2 '12 at 1:22
add comment

1 Answer

up vote 4 down vote accepted

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

share|improve this answer
    
+1,Thanks for the answer and your previous comment. –  Emmad Kareem Oct 2 '12 at 1:31
    
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. –  abw333 Oct 2 '12 at 2:06
1  
@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. –  Qiaochu Yuan Oct 2 '12 at 2:17
    
So, in the case when n = 3, and you have that the array is [3, 1, 2], what permutation would that describe? Thanks. –  abw333 Oct 2 '12 at 18:47
    
@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? –  abw333 Oct 3 '12 at 1:28
show 1 more comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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