Live data from Hacker News

How many draws of a random number [0,1] are needed to sum to 1

bayesianthink.blogspot.com

21–30 of 42 posts

Re: How many draws of a random number [0,1] are needed to sum to 1

#22
Everyone beat me to the punch, but I made a something a little different than you guys, I stored the count of trys to reach 1 and the frequency of the count in a multidimensional array to see what amount of tries got to the sum most frequently. i ran 100,000 tries at a time and ran it about 10 times.

2 was most frequent count every time.

Re: How many draws of a random number [0,1] are needed to sum to 1

#23
post #15

The author is not solving the same problem he states in the title. I'm not even sure what problem he is solving. For one thing, the pdf of uniform distribution on a [0, 1] with regard to Lebesgue measure on R is a function that's 1 on [0, 1] and 0 elsewhere. The pdf he gave is actually a pdf of Poisson distribution with regard to counting measure. Using simple methods from martingale theory we can show that the expec…

You could probably pull out the exact probability mass function with characteristic functions.

To review why these would be useful, let χ[T](s) = ⟨ exp(i ω T) ⟩, then χ[A + B] = χ[A] χ[B] for any A and B which are independent, so the characteristic function for a uniform random variable is going to be χ = (exp(i ω) − 1)/(i ω) and thus the sum of n independent uniform random numbers is just χⁿ. Meanwhile the PDF of a random variable is just the inverse Fourier transform of the characteristic function, so we have

fₙ(t) = ∫ dω/(2π) exp(-i ω t) [χ(ω)]ⁿ

Pr(n samples > 1) = ∫{1 → ∞} dt fₙ(t).

You could then interchange those two integrals, solving the convergence problem of exp(-i ω ∞) by giving ω an infinitesimal negative-imaginary component. This translates to moving the ω contour a little below the real line, and then the normal tricks of complex analysis should give you definite values for all of the integrals as residues about the simple pole at 0.

Re: How many draws of a random number [0,1] are needed to sum to 1

#25
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 to 1

#26
post #15

The author is not solving the same problem he states in the title. I'm not even sure what problem he is solving. For one thing, the pdf of uniform distribution on a [0, 1] with regard to Lebesgue measure on R is a function that's 1 on [0, 1] and 0 elsewhere. The pdf he gave is actually a pdf of Poisson distribution with regard to counting measure. Using simple methods from martingale theory we can show that the expec…

Agree. The relevant concepts from the theory of stochastic processes would be "stopping time" or "expected hitting time".

There are lots of relationships between the jump times of the Poisson process and subdivisions of the real line, so it's possible that the post is doing some version of a valid calculation, but without the right reasoning/understanding.

Re: How many draws of a random number [0,1] are needed to sum to 1

#27

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 v…

Yes, very nice neat elementary solution.

Re: How many draws of a random number [0,1] are needed to sum to 1

#28
post #8

Earlier quoted context omitted.

It's very easy to verify experimentally that e is likely the correct answer.

Doubly confirmed. 2.71832 over 100M trials. import random totalsteps = 0 for i in range(100000000): sum = 0.0 steps = 0 while sum

:) I was too fast for my own good and ddos-ed my box with this loop; it took me 5 minutes to stop it and replace range with xrange

Re: How many draws of a random number [0,1] are needed to sum to 1

#29

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 v…

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 to 1

#30
post #8

Earlier quoted context omitted.

It's very easy to verify experimentally that e is likely the correct answer.

Doubly confirmed. 2.71832 over 100M trials. import random totalsteps = 0 for i in range(100000000): sum = 0.0 steps = 0 while sum

It's funny. I read the problem, estimated that it was "probably 2 or 3" and then wasn't all that surprised to find that the solution was e. The derivation of it is pretty cool, too.
Post reply on HN