A “Buffon needle” for e

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

p_n=1-\frac{1}{2!}+\frac{1}{3!}-\cdots +(-1)^{n-1}\frac{1}{n!}

and so

\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

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

X_k=\max_{1\leq j\leq k}{X_j}.

Almost surely, there will be infinitely many rising points and corresponding indices, denoted

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
\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

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

\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

\lim_{N\rightarrow +\infty}{\frac{\mu_N}{\log N}}=1

almost surely. But Rényi observes that if we write

\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

\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

\frac{\mu_N}{\mathbf{E}(\varepsilon_1+\cdots+\varepsilon_N)}

converges almost surely to 1, and this is the desired statement.

Published by

Kowalski

I am a professor of mathematics at ETH Zürich since 2008.

6 thoughts on “A “Buffon needle” for e”

  1. Emmanuel, here’s one more methodology for you. Sample random numbers uniformly from [0,1] until the sum first exceeds 1; the expected number of draws is then e. The proof is not difficult, and one approach is to solve the general problem of the expected number of draws for the sum to exceed x, with 0 <= x <= 1. You get an integro-differential equation, the solution of which is e^x. I don’t know the rate of convergence.

  2. I think the accepted term for permutation without fixed point is “derangement”:

    http://en.wikipedia.org/wiki/Derangement

    Renyi’s calculation sounds closely related to the Sultan’s Daughter problem:

    http://mathworld.wolfram.com/SultansDowryProblem.html

    which also involves e asymptotically.

    Using the prime number theorem and testing a random n-digit number for primality, one gets an (asymptotic) Buffon needle for $\log 10$.

    The next challenge, of course, is Euler’s constant $\gamma$. Presumably one can use Mertens’ theorem to obtain some sort of Buffon needle for $e^\gamma$?

  3. Thanks for the interesting post! I have two questions, the first is about the journal Annales Scientifiques de l’Université Clermont-Ferrand 2. I find it very interesting that there is a “Discussion” part after some papers. Do you know if this was part of the referee report or there was some kind of public questions answers session?
    My second question/remark is about Renyi’s paper. It seems to me that Renyi’s result is closely related to the so called marriage, secretary, or beauty contest problem, however there is no reference to Renyi’s work among statisticians working on that problems.

    “Beauty contest: Suppose a boy is to have a date with his choice of one of n unseen and unknown girls, and suppose he wishes to choose the prettiest. The girls are presented for him to see one at a time in a random order, and he must choose or reject a girl when she appears. Once he chooses, he sees the rest, and he is disappointed if his date is not the prettiest. How can he maximize his probability of choosing the prettiest of the lot?”
    From: Recognizing the Maximum of a Sequence, by
    John P. Gilbert and Frederick Mosteller.
    Another reference:
    Who Solved the Secretary Problem?
    Thomas S. Ferguson Statistical Science, Vol.4, No.3 (1989), 282-289

  4. Thanks for the comments! (And sorry for the slow moderation as I was traveling for holidays…) I’ll try to follow up on the questions when I have a bit more time.

    (And Happy Holidays to every reader, by the way)

  5. Thanks for the pointer to the Rényi paper. It reminds me of some combinatorial work on random permutations — for example, “rising points” in permutations are considered in the first chapter of Stanley’s Enumerative Combinatorics, under the name of “records” or “left-to-right maxima”. (I don’t have the book at hand.) It’s interesting to see a probabilistic perspective on this.

    (Of course, Rényi’s paper predates Stanley’s book, even though I read them in the opposite order.)

  6. Back from vacation, here are more remarks on some of the previous comments:

    * #1: Rényi also does not discuss the speed of convergence of his limit, though it is probably possible to get some estimates by using what is known about the law of large numbers that he uses.

    * #2: I’ve read and heard the proper terminology “derangement”, but somehow it doesn’t come naturally (which is a shame since it’s a very good choice of word… hopefully I will now remember to use it).
    It would also be fun to have a nice procedure for Euler’s constant…

    * #3: as for the discussions at the end of the papers, I think they are here because this issue of the journal is actually a Conference Proceedings, and they correspond to the discussion at the end of each lecture.

    * #4: Rényi mentions a link with random permutations at the end of his paper (the random variable \mu_N is distributed like the number of cycles of a random permutation of size N).

Leave a Reply to Kowalski Cancel reply

Your email address will not be published.