Suppose we want to compute the constant e (the basis of the natural exponential) in a probabilistic way, similar to the Buffon needle experiment that leads to a probability directly related to π; how should we proceed? (Of course, the game is only valid if we restrict in some way to solutions where the experiment itself is described without using e; otherwise, picking a real number between, say 0 and 3, uniformly and independently and checking whether it is at most e will lead to an uninteresting solution).
There’s at least two ways that I know of, one of which I learnt only recently from looking at a paper of Rényi in the journal Annales Scientifiques de l’Université Clermont-Ferrand 2, the archives of which were recently added to the outstanding Numdam collection.
But first, the one I already knew: it is based on the probability that a random (uniformly chosen) permutation σ in Sn has at least one fixed point. Indeed, using the inclusion-exclusion formula, one gets that this probability is exactly
$latex p_n=1-\frac{1}{2!}+\frac{1}{3!}-\cdots +(-1)^{n-1}\frac{1}{n!}$
and so
$latex \lim_{n\rightarrow +\infty}{p_n}=1-\frac{1}{e}.$
From the Strong Law of Large Numbers, it follows that this limit can be obtained (almost surely) by taking larger and larger values of n, and repeating the experiment of drawing independently and uniformly at random a permutation of n letters, and calculating the proportion of those that have a fixed point. However, note that I’m hiding something in this informal description: to be sure to have convergence almost surely, we must be careful to determine how many experiments to do with each n — otherwise, the convergence may fail to hold.
Another objection from the point of view of the analogy with Buffon’s needle, is that we are not repeating the same experiment here: we need to change the size of the permutations to reach the limit.
Here’s then Rényi’s process: consider an arbitrary experiment with result described by a real-valued random variable with a continuous density (e.g., picking a real number in [0,1] uniformly according to Lebesgue measure), and consider independent random variables distributed in this way
$latex X_1,\ X_2,\ldots, X_n,\ $
Then, among the sequence of values observed in such a sample, say that an index k corresponds to a rising point (élément saillant is the terminology used by Rényi, in French) if
$latex X_k=\max_{1\leq j\leq k}{X_j}.$
Almost surely, there will be infinitely many rising points and corresponding indices, denoted
$latex 1=\nu_1<\nu_2<\cdots <\nu_n<\cdots$
which are clearly themselves random variables. Here is Rényi’s theorem:
We have almost surely
$latex \lim_{k\rightarrow +\infty}{\sqrt[k]{\nu_k}}=e.$
(Rényi observes the amusing possibility of seeing this as analogue of the Buffon needle, but of course his paper contains more than this and is more interesting than this…).
The fact that the answer is universal among all possible (repeated) experiences with continuous density is maybe surprising, but in fact easy to see: if F is the distribution function, then
$latex Y_n=F(X_n)$
are independent random variables now uniformly distributed on [0,1], and the rising points for this new sequence are the same as those for the original one (since F is increasing).
Rényi’s proof is quite short, after the following re-interpretation: instead of studying νk, consider the “dual” random variables
$latex \mu_N=|\{n\leq N\,\mid\, X_n \text{ is a rising point}\}|$
which is at most k if and only if νk is strictly larger than N. Then the result is equivalent with
$latex \lim_{N\rightarrow +\infty}{\frac{\mu_N}{\log N}}=1$
almost surely. But Rényi observes that if we write
$latex \mu_N=\varepsilon_1+\cdots+\varepsilon_N$
where the i-th summand is the characteristic function of the event “Xi is a rising point”, then (somewhat surprisingly) those summands are independent Bernoulli variables with
$latex \mathbf{P}(\varepsilon_i=1)=\frac{1}{i}.$
Then, although those are not identically distributed random variables, a general version of the law of large numbers (due to Kolmogorov) suffices to show that
$latex \frac{\mu_N}{\mathbf{E}(\varepsilon_1+\cdots+\varepsilon_N)}$
converges almost surely to 1, and this is the desired statement.
