News for hackers. Stuff that matters.
Re:How many draws of a random number [0,1] are needed to sum... by Sniffnoy on Sunday February 24, 2013 @02:45PM (#5275611)
Here's a more elementary solution.

Let's say we draw n times. What's the probability that we get a number at least 1? Well, we want to exclude the cases where we get a number less than 1, so we want the volume of the unit cube (n-tuples of numbers from 0 to 1) minus the volume of the region below the standard simplex (standard simplex is stuff that sums to 1, we're excluding stuff that sums to less than 1.)

Now the volume of the region below the standard simplex in n dimensions is 1/n!. (Brief proof, if you're not familiar: True in 1 dimension. Assume true in n dimensions. Then for n+1 dimensions, have integral over volume in n dimensions, as "sum of first n variables" parameter varies from 0 to 1. But volume varies as length^n in n dimensions, so this is integral from 0 to 1 of x^n/n!, i.e. 1/(n+1)!.)

So after n draws, the probability that we've exceeded 1 is 1-1/n!. So the probability that it requires exactly n draws is 1/(n-1)! - 1/n! (assuming n>1; for n=0 the probability is 0).

So the expected number of draws, then, is the sum over n>=1 of n/(n-1)! - n/n!, but this latter is (assuming n>=2) equal to n/(n-1)! - 1/(n-1)! = (n-1)/(n-1)! = 1/(n-2)!. (For n=1, we get 0.)

I.e. it's the sum over n>=2 of 1/(n-2)!, i.e. the sum over n>=0 of 1/n!, or in other words it's e.

Re:How many draws of a random number [0,1] are needed to sum... by mturmon on Sunday February 24, 2013 @03:02PM (#5275674)
Hey, nice answer. If you are comfortable with the formula (http://en.wikipedia.org/wiki/Expected_value#Discrete_distrib...):

  E[N] = Sum_{i >= 0} P(N >= i)
then you can reduce some of your calculations and edge considerations.

Because the chance that (N >= i) is the volume below the standard simplex, which, as you note, is just 1/i!. Plug in to the above and you get

  E[N] = Sum_{i >= 0} 1/i! = 1/e
Re:How many draws of a random number [0,1] are needed to sum... by Sniffnoy on Sunday February 24, 2013 @03:45PM (#5275821)
Yeah, I guess that neatly encapsulates the bit about subtracting off to make it exact before multiplying by n...
Re:How many draws of a random number [0,1] are needed to sum... by sbi on Sunday February 24, 2013 @04:58PM (#5276088)
This is a pretty solution, and it gives you the probability generating function for free: by some power series manipulation, the pgf of the number of draws needed is g(z) = 1 + (z-1)*exp(z). So you can show fairly easily that Var(draws needed) = 3e - e^2, for example ...
Re:How many draws of a random number [0,1] are needed to sum... by tome on Sunday February 24, 2013 @02:53PM (#5275648)
Yes, very nice neat elementary solution.
Re:How many draws of a random number [0,1] are needed to sum... by dgreensp on Sunday February 24, 2013 @02:56PM (#5275656)
That's right, this is the simplest way to show it.
Re:How many draws of a random number [0,1] are needed to sum... by coutud on Tuesday February 26, 2013 @05:09AM (#5284806)
Nope, there's an even simpler way.

Say f(x) is the expected value of the number of draws to get to value x. Then f(x) = 1 + integral_0^x f(x)

Hence f'(x) = f(x), so f(x) = c exp(x) The constant is of course 1, and f(1) = exp(1).

Re:How many draws of a random number [0,1] are needed to sum... by jderick on Tuesday February 26, 2013 @06:53PM (#5289508)
Why is f(x) = 1 + integral_0^x f(x)?