Puzzle:
Let S be a set of N numbers.
Permute them into random order. Scan thru the elements in that order.
Each time you encounter a new record max, ring a bell.
So for example, if S={7*,8*,5,3,4,9*}
you would ring the bell 3 times at the *s.
1. This is since the probability the nth number is greater than all n-1 preceding, is 1/n. Hence the expected number of new maxima is ha(N)=HarmonicNumber(N)=∑1≤k≤N (1/k) which is asymptotic (when N is large) to
where γ≈0.5772156649 is the Euler-Mascheroni constant.
2. But we can actually write down the entire probability distribution. The key fact is that the number of permutations of {1,2,...,N} with R successive maxima is given by the "unsigned Stirling Numbers of the first kind" |s(N,R)|=(-1)N-Rs(N,R). Do not confuse these with the signed numbers s(N,R) or with the Stirling numbers of the second kind S(N,R) denoted with a capital S. For more information about s(N,R) see the wikipedia article or NIST handbook. As a generating function formula,
which if we are speaking about unsigned Stirling-type-1s is
One can also compute them via the recurrence
Incidentally, this recurrence is easily proven using the "key fact" above. (Which can be viewed as proving the recurrence, or as proving the key fact provided that we already knew the recurrence.) The corresponding recurrence for the signed Stirling-first-kinds is
Here is a table of |s(N,R)| with N increasing from 0 in the downward direction while R increases from 0 in the rightward direction:
N=0 1
N=1 0 1 Table of |s(N,R)|
N=2 0 1 1
N=3 0 2 3 1
N=4 0 6 11 6 1
N=5 0 24 50 35 10 1
N=6 0 120 274 225 85 15 1
N=7 0 720 1764 1624 735 175 21 1
N=8 0 5040 13068 13132 6769 1960 322 28 1
N=9 0 40320 109584 118124 67284 22449 4536 546 36 1
N=10 0 362880 1026576 1172700 723680 269325 6327 9450 870 45 1
R=0 R=1 R=2 R=3 R=4 R=5 R=6 R=7 R=8 R=9 R=10
Note that the recurrence relates a number in the table to the one directly above it and the one diagonally left & upward. For example, the three italicized numbers in the table obey 50=4·11+6, and every such little triangle of three adjacent numbers also works, such as 175=6·15+85, which allows you to easily expand the table.
So let Prob(R) be the probability that the bell rings R times, 1≤R≤N. Then
3. The variance in the number of maxima is
| N | mean R | variance in R |
|---|---|---|
| 1 | 1. | 0. |
| 2 | 3/2 = 1.5 | 1/4 = 0.25 |
| 3 | 11/6≈1.833333 | 17/36≈0.47222222 |
| 4 | 25/12≈2.08333 | 95/144≈0.6597222 |
| 23=8 | 2.717857143 | 1.190435091 |
| 24=16 | 3.380728993 | 1.796382460 |
| 25=32 | 4.058495195 | 2.444327933 |
| 26=64 | 4.743890904 | 3.114460402 |
| 27=128 | 5.433147093 | 3.795995088 |
| 28=256 | 6.124344963 | 4.483309527 |
| 29=512 | 6.816516535 | 5.173533687 |
| 210=1024 | 7.509175672 | 5.865217691 |
| 211=2048 | 8.202078772 | 6.557632865 |
| 212=4096 | 8.895103897 | 7.250413939 |
The variance appears numerically to obey
where π2/6≈1.6449340668482264, which if so would mean that the probability distribution is sharply peaked around its expectation, e.g. when N→∞ the probability→100% that the number of maxima lies within the interval [0.999, 1.001]·ha(N), or indeed any interval containing 1 can replace [0.999, 1.001].
This indeed is correct, as may be verified from the amazing exact formula
(And this may be shown by a disgusting inductive proof. I hope there is a nicer proof.) These variance results seem to be new, e.g. are not listed in the NIST compilation of facts about Stirling numbers.
We thank Tanya Khovanova, Joel Brewster Lewis, and Victor Miller for the hint. It turns out our "new" variance exact formula was stated by Ned Glick: Breaking records and breaking boards, Amer. Mathematical Monthly 85 (Jan. 1978) 2-26, on page 14. Glick traces the result that the number of maxima is (with probability→1) asymptotic to ln(N), to Alfred Renyi 1962; Renyi also recognized the connection to Stirling numbers. Cris Moore found nice proofs for the variance and third moment and his techniques actually allow expressing any particular moment in closed form, although it gets more mysterious the higher the moment.