6
$\begingroup$

Recently I found this post on Reddit. It describes the following algorithm to find e:

Here is an example of e turning up unexpectedly. Select a random number between 0 and 1. Now select another and add it to the first. Keep doing this, piling on random numbers. How many random numbers, on average, do you need to make the total greater than 1? The answer is e.

This means that you need on average ~2.7 random real numbers to make the sum greater than 1.

However, a random number between 0 and 1 would on average be equal to 0.5. So intuitively I would think that, on average, only 2 random numbers would be required to have a sum > 1.

So where did I go wrong in my thinking?

Update

I just figured it out myself: You need at least two numbers to have a sum > 1, but often you'll need three, sometimes you'll need four, sometimes five, etc... So it only natural that the average required numbers is above 2.

Thanks for the replies!

  • 0
    Do you want a proof that this works or do you only want an explanation of why your intuition is wrong?2010-08-10
  • 0
    @Qiaochu Yuan: I would like to know why my intuition is wrong. I don't need a formal proof.2010-08-10
  • 0
    The expected sum is e/2.2010-08-10
  • 0
    Of course there are some sequences which will never sum up to be greater than 1 (i.e. 1/4,1/8,1/16, etc...)2010-08-10

5 Answers 5

4

It is never possible to get greater than 1 on the first try, so the average must be strictly greater than 2.

3

The other answers should have resolved why the number is >2, but for the exact reason why it is e:

For having N random numbers whose sum is <1, the probability is exactly the same as the volume of a unit standard N-simplex, i.e. 1/N!.

Therefore, the probability that it takes exactly N random numbers for a sum of ≥1, the probability is

$$ \frac1{(N-1)!} - \frac1{N!} = \frac1{N(N-2)!} $$

Therefore the expected number is

$$ \sum_{N=1}^\infty \frac N{N(N-2)!} = e $$

  • 0
    Whcih is great, but this is not what the OP asked for.2010-08-10
  • 0
    @Qiao: You're right. Reworded a little.2010-08-10
  • 0
    This is nice. Thanks for the explanation.2010-08-10
1

I believe the answer is related to this:

$e = \sum_{n = 0}^\infty \frac{1}{n!} = \frac{1}{0!} + \frac{1}{1!} + \frac{1}{2!} + \frac{1}{3!} + \frac{1}{4!} + \cdots$

In that, by choosing random numbers, you're approximating a sampling from that series.

For your amusement, here's a little Python program that does a brute force calculation:

#!/usr/bin/env python
import random
iterations = 100000000
count = 0.0
for i in range(iterations):
    sum = 0
    while sum < 1:
            sum += random.random()
            count += 1
print count / iterations
  • 0
    It'll be off by a little bit since it is generating random numbers in the range `[0,1)` instead of `(0,1)`.2010-08-10
  • 0
    Will it really matter that 0 is included?2010-08-10
  • 2
    It does not matter :-)2010-08-10
  • 0
    @KennyTM: It doesn't matter for the sum, but it makes a very slight difference whether zeros are counted when the average is calculated.2010-08-11
0

"How many..., on average, ..." means the expected number of random numbers. That is, the sum of each possible number of random numbers multiplied by its probability. As Qiaochu Yuan's answer says, it is impossible to be greater than 1 on the first try, so the expected number is $$2\cdot P(\mathrm{it\ takes\ exactly\ 2\ numbers})+3\cdot P(\mathrm{it\ takes\ exactly\ 3\ numbers})$$ $$+\;4\cdot P(\mathrm{it\ takes\ exactly\ 4\ numbers})+\cdots$$ Since each of those probabilities is nonzero, but the sum of those probabilities is 1, the expected number must be strictly greater than 2.

-1

Sorry, can't explain it either. It's obvious you need at least two random numbers to go greater than 1. And if the random numbers are on average .5 you'll need (edit) on average (/edit) maximum three numbers. So we end up in the range [2..3], but that's as close as I can get to e.

While the method sure looks curious, it must be about the least efficient way ever to calculate e digits. A quick-and-dirty test program I wrote only gave 4 correct significant digits after a billion iterations. Or maybe Delphi's PRNG isn't perfect.

  • 1
    That's not an argument that the expected number is at most 3; it can take an arbitrary finite number of numbers.2010-08-10
  • 0
    @Qiaochu Yuan: I didn't say you'll never need more than 3. We're talking about averaging. I've edited my post to reflect this.2010-08-11
  • 0
    Your argument is still not enough to show that the expected number is at most 3; at best, it's a heuristic.2010-08-11