Summing random powers up to a threshold

Pick random numbers uniformly between 0 and 1, adding them as you go, and stop when you get a result bigger than 1. How many numbers would you expect to add together on average?

You need at least two samples, and often two are enough, but you might get any number, and those larger numbers will pull the expected value up.

Here's a simulation program in Python.

 from random import random from collections import Counter N = 1000000 c = Counter() for _ in range(N): x = 0 steps = 0 while x < 1: x += random() steps += 1 c[steps] += 1 print( sum([ k*c[k] for k in c.keys() ])/N )

When I ran it I got 2.718921. There's a theoretical result first proved by W. Weissblum that the expected value is e = 2.71828" Our error was on the order of 1/aN, which is what we'd expect from the central limit theorem.

Now we can explore further in a couple directions. We could take a look at a the distribution of the number steps, not just its expected value. Printing c shows us the raw data.

 Counter({ 2: 499786, 3: 333175, 4: 125300, 5: 33466, 6: 6856, 7: 1213, 8: 172, 9: 29, 10: 3 })

And here's a plot.

We could also generalize the problem by taking powers of the random numbers. Here's what we get when we use exponents 1 through 20.

There's a theoretical result that the expected number of steps is asymptotically equal to cn where

I computed c = 1.2494. The plot above shows that the dependence on the exponent n does look linear. The simulation results appear to be higher than the asymptotic prediction by a constant, but that's consistent with the asymptotic prediction since relative to n, a constant goes away as n increases.

Reference for theoretical results: D. J. Newman and M. S. Klamkin. Expectations for Sums of Powers. The American Mathematical Monthly, Vol. 66, No. 1 (Jan., 1959), pp. 50-51