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

- Prove the expected number of times the bell rings, equals HarmonicNumber(N) = 1+1/2+1/3+...+1/N.
- Compute a formula for the probability the bell rings R times (as a function of R and N). Hint: my formula involves "unsigned Stirling numbers of the first kind."
- What is the variance in the number of bell-rings?

**1.**
This is since the probability
the *n*th 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-R}s(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=01N=10 1Table of |s(N,R)|N=20 1 1N=30 2 3 1N=4066 111N=50 2435 10 150N=60 120 274 225 85 15 1N=70 720 1764 1624 735 175 21 1N=80 5040 13068 13132 6769 1960 322 28 1N=90 40320 109584 118124 67284 22449 4536 546 36 1N=100 362880 1026576 1172700 723680 269325 6327 9450 870 45 1R=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 |

2^{3}=8 | 2.717857143 | 1.190435091 |

2^{4}=16 | 3.380728993 | 1.796382460 |

2^{5}=32 | 4.058495195 | 2.444327933 |

2^{6}=64 | 4.743890904 | 3.114460402 |

2^{7}=128 | 5.433147093 | 3.795995088 |

2^{8}=256 | 6.124344963 | 4.483309527 |

2^{9}=512 | 6.816516535 | 5.173533687 |

2^{10}=1024 | 7.509175672 | 5.865217691 |

2^{11}=2048 | 8.202078772 | 6.557632865 |

2^{12}=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.