I plan to continue my discussion of Boij–Söderberg theory from last time, but I’d like to make a quick detour first. This came up today in the office when I was talking with yanzhang.
Question: If I randomly pick numbers (with a uniform distribution) from the unit interval [0,1], what is the expected number of numbers that I need to pick before their sum is at least 1?
The answer for some strange reason is the number e, and I’ll illustrate this with two approaches. Both give different expressions of e, so this problem will show an equivalence between two definitions of e.
The first approach is to use calculus. For , let f(r) be the expected number of randomly selected numbers in [0,1] so that their sum is at least r, and define f(r) = 0 if r is negative. Then we have the following integral equation
To see this, pick a number t randomly in [0,1], and then add f(r-t). Since we need to account for all such t, we just integrate over [0,r] (I could integrate over [0,1], but remember that f(r-t) = 0 if t>r), and divide this integral by the length of [0,1], which is 1. The second inequality follows from a change of variables s=r-t. Taking derivatives of both sides, we get by the fundamental theorem of calculus, so for some constant c. Of course, f(0) = 1, so c=1. Our original question was for r=1, in which case f(1) = e, as we promised.
The second approach is the same, except we discretize everything. Let’s ask an analogous question. First fix k. If I randomly pick integers uniformly from [0,k], what is the expected number that I need before their sum is at least n, where ? Let g(n) be this expected value. Then again, we have
by the same reasoning as before. Let be the first difference operator, i.e., . Now apply to the above equation to get
Of course, g(-1) = 0, and rewriting this last equation gives
assuming that n>0. Since g(0) = 1, this means that . Now set k=n: If we rephrase this question, we also see that g(n) is the expected number of random selections of rational numbers with denominator n from [0,1] such that their sum is at least 1. Letting n go to infinity, we should get the answer from the previous method since the rationals form a dense subset of the reals.
So these two approaches show the equivalence of two definitions of e: one as the unique number such that , and the other as the limit .
Do you know of any other solutions to the original question?