Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

bayesianthink.blogspot.com

Post reply on HN
Print view View original

31–40 of 42 posts

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

#31

Post by mturmon »

Sniffnoy wrote: post #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 v…

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

#32

Post by zwegner »

crististm wrote: post #28
psyklic wrote: post #8

Earlier quoted context omitted.

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

That's because you're using an obsolete Python :)

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

#33

Post by Sniffnoy »

mturmon wrote: post #31
Sniffnoy wrote: post #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 v…

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

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

#34

Post by sbi »

Sniffnoy wrote: post #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 v…

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

#35

Post by dxbydt »

Some motivation for the non-math folks out here - twitter shows an ad on your timeline. Assume the chances of twitter getting a callback on that ad is uniform ( very unlikely, but play along ). That means roughly 50% of folks will ignore the ad or dismiss the ad, the rest will actually engage with the ad impression. Lets say twitter makes a dollar per engagement. How many ads need to be shown to make the first dollar ? Two dollars ? How about five, ten, hundred, or a million ?

That's what this problem gets at.And in case you are curious about the solution to all that money -

     ----
     scala> def uniform = util.Random.nextDouble
     def sumsTo(n:Int) = {
         var (times, sum) = (0.0d,0.0d);
         while(sum sumsTo(n)).sum/1000000.0d

     List(1,2,5,10,100,500,1000).map(x=> (x,meanSumsTo(x))

     scala> res1: List[(Int, Double)] = List((1,2.718594), (2,4.672438), (5,10.665755), (10,20.668308), (100,200.65537), (500,1000.669558), (1000,2000.669246))
     ----

    So you need to show 3 ads to make a buck, 5 ads to make $2 etc.

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

#36

Post by ivansavz »

The calculation given by the OP does not solve the stated problem, as remarked by xyzzyz.

Sniffnoy already gave the correct solution in elementary terms, but since I spent the last two hour learning about the convolution formula, I want to give my solution here.

Define: U[0,1] to the the uniform distr. on [0,1] and S_n to be the sum of n copies of the uniform distribution. We can compute the probability density function f_{S_n}(x) using the convolution formula:

    f_{S_n}(x) = 1/(n-1)! * \sum_{0≤j≤x} (-1)^j (n choose j) (x - j)^{n-1}.
see http://www.dartmouth.edu/~chance/teaching_aids/books_article...

In particular we are interested in the event that the sum goes over 1:

    Pr{ S_n
In the range [0,1] the function pdf f_{S_n}(x) takes on the simple form 1/(n-1)!x^{n-1} because j=0 is the only term we keep in the summation, so we can evaluate the above integral:

    Pr{ S_n
OK, now for the problem statement ;)

Let N be the random variable which describes the number of draws from U[0,1] we will make to reach a sum of 1. We need to find the probability density of N (call it p(n)) and then calculate its expected value

    E{N} = \sum_n=0^\infty n*p(n)
As pointed out by Sniffnoy, the formula for p(n), the probability that it will take //exactly// n draws to go over 1 is given by:

  p(1) = 0,
  p(2) =  1                  - Pr{ S_{2}
Note that [1 - p(n-1) - p(n-2) - ... - p(2)] is the prob of not going over 1 in the first n-1 trials, from which we subtract 1/n! -- the probability of not going over in the n'th trial.

The final steps are:

     E{N} = \sum_n=2^\infty n*p(n) 
          = \sum_n=2^\infty n*[1/(n-1)! - 1/n! ] 
          = \sum_n=2^\infty [n/(n-1)! - n/n! ] 
          = \sum_n=2^\infty [n/(n-1)! - 1/(n-1)! ] 
          = \sum_n=2^\infty [(n-1)/(n-1)!] 
          = \sum_n=2^\infty 1/(n-2)!
          = \sum_m=0^\infty 1/m!        (change of var m = n-2) 
          = e
Very nice problem.

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

#38

Post by huhsamovar »

tome wrote: post #16
dmvaldman wrote: post #2

Isn't the pdf of a uniform distribution just f(x) = 1. What he gave was an exponential distribution with rate parameter lambda. The rest of the math seems correct. But the dependence on e is not surprising as it is relevant to the initial pdf. Am I missing something?

You're right. I think the article's reasoning is fallacious. At least, I don't see what the Poission distribution has to do with this at all. One way to arrive at the answer correctly is to write the number of samples needed before they first sum to 1 as N and observe that the probability that P[N > k] = 1/k!. You can get this from a k-dimensional integral. A general formula for E[N] is Sum_k=0^infty P[N > k] thus E[…

Yes, you're right; the Poisson distribution is completely superfluous to the argument.

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

#39

Post by Bryan22 »

Bryan22 wrote: post #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.

Considering [0-1] inclusive, these are the percentages after a million runs;

1- 1%

2- 49%

3- 33%

4- 12%

5- 3%

6- .7%

7- .1%

8- .02%

it doesn't add up to 100% because of rounding, but you get the picture.

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

#40

Post by Bryan22 »

The simplest answer is: you have a 50% chance of the number being > .5 and a 50% chance of getting a number > num1 +num2 >=1 so the answer is 2 draws. people are trying to show these grand equations to figure it out, but it's really a simple solution; Most of the time it take 2 draws.

Use your mind, which is enormously greater at making common sense solutions than a computer, and figure it out with common sense, then test it with an algorithm.

Post reply on HN