The 'e' movie

No, this is not an electronic movie, it is literally, a movie about e (or a fantasy on what one would look like).

In a whimsical and interesting article on ABC News (found via topix.net), John Allen Paulos speculates on what a movie about e might look like. He was prompted by the fame achieved by the golden ratio via The Da Vinci Code, and pi via the eponymous movie.

He gives four examples of the 'natural occurrence' of e: for my amusement, I decided to subtitle the examples with the actual mathematical principle. All of these are old friends of of the theoretical computer scientist:

1. Divide up a square portion of the night sky into a very large number, N, of equal smaller squares. That is, imagine a celestial checkerboard. Then search for the N brightest stars in this portion of the sky and count how many of the N smaller squares contain none of these N brightest stars. Call this number U. (We're assuming the stars are distributed randomly so by chance some of the smaller squares will contain one or more of the brightest stars, others none.)

If one knows some probability theory, it's not hard to prove that the ratio of N to U (N divided by U, that is) is very close to e and approaches it more and more closely as N gets large.

Indeed. 1/e is the limit of the expression (1-1/n)ⁿ as n grows unboundedly large.

2. A somewhat unusual appearance of the number involves two decks of cards. Shuffle each deck thoroughly, turn over a card from each, and note if it's the same card (both 7s of diamonds, for example, or both jacks of clubs). Then turn over another card from each deck, and note if it's the same card. Continue doing this until all 52 cards in the decks are turned over. It can be shown that the probability of no matches at all between the two decks during this sequence of turnovers is extremely close to one chance in e; that is, the probability is 1/e or about 37 percent.

This is the classical derangement problem. For many of us, the first introduction to the Principle of Inclusion and Exclusion.

3. ...imagine this year's high school graduates running a quarter-mile race. Runners are randomly selected and sequentially over a period of months each of them runs a quarter-mile and we keep track of the number of record times that they establish. The first runner would surely establish a record time and perhaps the fourth runner would be faster than the first three and establish the second record time.

If the Nth runner sets the Rth record, it can be proved that the Rth root of N will be an approximation to e, and this approximation approaches e more and more closely as N increases without bound.

Another way of saying this is that if we permute a set of numbers randomly and compute the min by the standard procedure, then its value will change roughly ln n times. Timothy Chan made use of this fact in an elegant way to replace parametric search by a cheaper randomized test for many geometric problems.

The fourth example is a variant of the first: however, he alludes (possibly) to another famous homework problem, the secretary problem, in his conclusions. Here, the probability of choosing the best secretary for the job is 1/e, and this is in fact optimal (over all online algorithms that make irrevocable decisions). Considering there is already a movie called 'The Secretary', you'd think this would be a good candidate :)

As an aside, the derangement problem has also been referred to as The Drunken Secretary Problem.