{"id":179,"date":"2008-12-26T06:04:00","date_gmt":"2008-12-26T05:04:00","guid":{"rendered":"https:\/\/wpethzprd.ethz.ch\/kowalski\/?p=179"},"modified":"2024-02-20T13:40:57","modified_gmt":"2024-02-20T11:40:57","slug":"a-buffon-needle-for-e","status":"publish","type":"post","link":"https:\/\/blogs.ethz.ch\/kowalski\/2008\/12\/26\/a-buffon-needle-for-e\/","title":{"rendered":"A “Buffon needle” for e"},"content":{"rendered":"

Suppose we want to compute the constant e<\/em> (the basis of the natural exponential) in a probabilistic way, similar to the Buffon needle<\/a> experiment that leads to a probability directly related to \u00a4\u00c7<\/em>; 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<\/em>; otherwise, picking a real number between, say 0 and 3, uniformly and independently and checking whether it is at most e<\/em> will lead to an uninteresting solution).<\/p>\n

There’s at least two ways that I know of, one of which I learnt only recently from looking at a paper of R\u00e9nyi<\/a> in the journal Annales Scientifiques de l’Universit\u00e9 Clermont-Ferrand 2<\/em>, the archives of which were recently added to the outstanding Numdam<\/a> collection.<\/p>\n

But first, the one I already knew: it is based on the probability that a random (uniformly chosen) permutation \u00a4\u00e2<\/em> in Sn<\/sub><\/em> has at least one fixed point. Indeed, using the inclusion-exclusion formula, one gets that this probability is exactly<\/p>\n

$latex p_n=1-\\frac{1}{2!}+\\frac{1}{3!}-\\cdots +(-1)^{n-1}\\frac{1}{n!}$<\/p>\n

and so<\/p>\n

$latex \\lim_{n\\rightarrow +\\infty}{p_n}=1-\\frac{1}{e}.$<\/p>\n

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<\/em>, and repeating the experiment of drawing independently and uniformly at random a permutation of n<\/em> letters, and calculating the proportion of those that have a fixed point. However<\/em>, 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<\/em> — otherwise, the convergence may fail to hold.<\/p>\n

Another objection from the point of view of the analogy with Buffon’s needle, is that we are not repeating the same<\/em> experiment here: we need to change the size of the permutations to reach the limit.<\/p>\n

Here’s then R\u00e9nyi’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<\/p>\n

$latex X_1,\\ X_2,\\ldots, X_n,\\ $<\/p>\n

Then, among the sequence of values observed in such a sample, say that an index k<\/em> corresponds to a rising<\/em> point (\u00e9l\u00e9ment saillant<\/em> is the terminology used by R\u00e9nyi, in French) if<\/p>\n

$latex X_k=\\max_{1\\leq j\\leq k}{X_j}.$<\/p>\n

Almost surely, there will be infinitely many rising points and corresponding indices, denoted<\/p>\n

$latex 1=\\nu_1<\\nu_2<\\cdots <\\nu_n<\\cdots$<\/p>\n

which are clearly themselves random variables. Here is R\u00e9nyi’s theorem:<\/p>\n

We have almost surely
\n$latex \\lim_{k\\rightarrow +\\infty}{\\sqrt[k]{\\nu_k}}=e.$<\/p><\/blockquote>\n

(R\u00e9nyi 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…).<\/p>\n

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<\/em> is the distribution function, then<\/p>\n

$latex Y_n=F(X_n)$<\/p>\n

are independent random variables now uniformly distributed<\/em> on [0,1], and the rising points for this new sequence are the same as those for the original one (since F<\/em> is increasing).<\/p>\n

R\u00e9nyi’s proof is quite short, after the following re-interpretation: instead of studying \u256c\u00a2k<\/sub><\/em>, consider the “dual” random variables<\/p>\n

$latex \\mu_N=|\\{n\\leq N\\,\\mid\\, X_n \\text{ is a rising point}\\}|$<\/p>\n

which is at most k<\/em> if and only if \u256c\u00a2k<\/sub><\/em> is strictly larger than N<\/em>. Then the result is equivalent with<\/p>\n

$latex \\lim_{N\\rightarrow +\\infty}{\\frac{\\mu_N}{\\log N}}=1$<\/p>\n

almost surely. But R\u00e9nyi observes that if we write<\/p>\n

$latex \\mu_N=\\varepsilon_1+\\cdots+\\varepsilon_N$<\/p>\n

where the i<\/em>-th summand is the characteristic function of the event “Xi<\/sub><\/em> is a rising point”, then (somewhat surprisingly) those summands are independent<\/em> Bernoulli variables with<\/p>\n

$latex \\mathbf{P}(\\varepsilon_i=1)=\\frac{1}{i}.$<\/p>\n

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<\/p>\n

$latex \\frac{\\mu_N}{\\mathbf{E}(\\varepsilon_1+\\cdots+\\varepsilon_N)}$<\/p>\n

converges almost surely to 1, and this is the desired statement.<\/p>\n","protected":false},"excerpt":{"rendered":"

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 \u00a4\u00c7; how should we proceed? (Of course, the game is only valid if we restrict in some way to solutions where the experiment … Continue reading A “Buffon needle” for e<\/span><\/a><\/p>\n","protected":false},"author":625,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[2],"tags":[],"class_list":["post-179","post","type-post","status-publish","format-standard","hentry","category-blogroll"],"_links":{"self":[{"href":"https:\/\/blogs.ethz.ch\/kowalski\/wp-json\/wp\/v2\/posts\/179","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blogs.ethz.ch\/kowalski\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.ethz.ch\/kowalski\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.ethz.ch\/kowalski\/wp-json\/wp\/v2\/users\/625"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.ethz.ch\/kowalski\/wp-json\/wp\/v2\/comments?post=179"}],"version-history":[{"count":0,"href":"https:\/\/blogs.ethz.ch\/kowalski\/wp-json\/wp\/v2\/posts\/179\/revisions"}],"wp:attachment":[{"href":"https:\/\/blogs.ethz.ch\/kowalski\/wp-json\/wp\/v2\/media?parent=179"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.ethz.ch\/kowalski\/wp-json\/wp\/v2\/categories?post=179"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.ethz.ch\/kowalski\/wp-json\/wp\/v2\/tags?post=179"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}