News for hackers. Stuff that matters.
Re:How many draws of a random number [0,1] are needed to sum... by dmvaldman on Sunday February 24, 2013 @01:35PM (#5275285)
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?
Re:How many draws of a random number [0,1] are needed to sum... by jamii on Sunday February 24, 2013 @02:37PM (#5275564)
> Am I missing something?

No, I was confused too. The maths doesn't make sense to me and the whole blog seems to exist just to push amazon affiliate links.

If you are actually interested in probability theory, I highly recommend this (non-affiliate-link) book:

http://www.amazon.co.uk/Probability-Computing-Randomized-Alg...

It does a good job of motivating the subject by applying the new theory in each chapter to the study of useful randomized algorithms.

Re:How many draws of a random number [0,1] are needed to sum... by DanWaterworth on Sunday February 24, 2013 @01:50PM (#5275342)
It's very easy to verify experimentally that e is likely the correct answer.
Re:How many draws of a random number [0,1] are needed to sum... by psyklic on Sunday February 24, 2013 @02:08PM (#5275432)
Doubly confirmed. 2.71832 over 100M trials.

  import random

  totalsteps = 0
  for i in range(100000000):
  	sum = 0.0
  	steps = 0
  	while sum < 1.0:
  		sum += random.random()
  		steps += 1
  	totalsteps += steps
  
  print('AVG STEPS: ' + str(totalsteps / i))
Re:How many draws of a random number [0,1] are needed to sum... by DanWaterworth on Sunday February 24, 2013 @02:17PM (#5275473)
This is almost exactly what I wrote, I've done more than 4 billion trails and I have: 2.7182718267 (pypy speeds it up a lot).
Re:How many draws of a random number [0,1] are needed to sum... by Natsu on Sunday February 24, 2013 @03:01PM (#5275667)
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.
Re:How many draws of a random number [0,1] are needed to sum... by crististm on Sunday February 24, 2013 @02:54PM (#5275651)
:) 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... by zwegner on Sunday February 24, 2013 @03:03PM (#5275676)
That's because you're using an obsolete Python :)
Re:How many draws of a random number [0,1] are needed to sum... by eCa on Sunday February 24, 2013 @02:23PM (#5275499)
Confirmed again:

    perl -e 'my $testcount = 10_000_000; my $total = 0; foreach my $i (0 .. $testcount) { my $sum = 0; while($sum < 1) { $sum += rand(); ++$total } } print $total / $testcount'

    2.7186292
Re:How many draws of a random number [0,1] are needed to sum... by ced on Sunday February 24, 2013 @02:07PM (#5275424)
I confirmed it for fun. Got 2.746 over 10000 trials. Close enough.

  (average (map-n (fn ()
		    (1+ (position-if (let1 x 0
				       (fni (< 1.0 (incf x (random 1.0)))))
				     (range 100))))
		  10000))
Re:How many draws of a random number [0,1] are needed to sum... by prezjordan on Sunday February 24, 2013 @02:11PM (#5275444)
Yep: http://codepad.org/gIaWdVY9

EDIT: Beaten to it :)

Re:How many draws of a random number [0,1] are needed to sum... by tome on Sunday February 24, 2013 @02:33PM (#5275541)
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[N] = e.

Re:How many draws of a random number [0,1] are needed to sum... by huhsamovar on Sunday February 24, 2013 @06:43PM (#5276490)
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... by huhsamovar on Sunday February 24, 2013 @01:56PM (#5275375)
You are correct.