Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
Do you want a proof that this works or do you only want an explanation of why your intuition is wrong? –  Qiaochu Yuan Aug 10 '10 at 17:06
    
@Qiaochu Yuan: I would like to know why my intuition is wrong. I don't need a formal proof. –  StackedCrooked Aug 10 '10 at 17:27
    
The expected sum is e/2. –  starblue Aug 10 '10 at 18:32
    
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...) –  Digital Gal Aug 10 '10 at 20:24
add comment

5 Answers 5

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

share|improve this answer
add comment

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

share|improve this answer
    
Whcih is great, but this is not what the OP asked for. –  Qiaochu Yuan Aug 10 '10 at 19:33
    
@Qiao: You're right. Reworded a little. –  KennyTM Aug 10 '10 at 19:36
    
This is nice. Thanks for the explanation. –  user977 Aug 10 '10 at 19:38
add comment

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
share|improve this answer
    
It'll be off by a little bit since it is generating random numbers in the range [0,1) instead of (0,1). –  Dennis Williamson Aug 10 '10 at 18:33
    
Will it really matter that 0 is included? –  KennyTM Aug 10 '10 at 19:03
2  
It does not matter :-) –  botismarius Aug 10 '10 at 19:58
    
@KennyTM: It doesn't matter for the sum, but it makes a very slight difference whether zeros are counted when the average is calculated. –  Dennis Williamson Aug 11 '10 at 1:27
add comment

"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.

share|improve this answer
add comment

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.

share|improve this answer
1  
That's not an argument that the expected number is at most 3; it can take an arbitrary finite number of numbers. –  Qiaochu Yuan Aug 10 '10 at 17:49
    
@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. –  stevenvh Aug 11 '10 at 5:51
    
Your argument is still not enough to show that the expected number is at most 3; at best, it's a heuristic. –  Qiaochu Yuan Aug 11 '10 at 8:10
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.