3 ms·
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 wher
by Sniffnoy 14y ago
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.
- tome 14y agoYes, very nice neat elementary solution.
- dgreensp 14y agoThat's right, this is the simplest way to show it.
- mturmon 14y agoHey, nice answer. If you are comfortable with the formula (http://en.wikipedia.org/wiki/Expected_value#Discrete_distribution_taking_only_non-negative_integer_values 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
- Sniffnoy 14y agoYeah, I guess that neatly encapsulates the bit about subtracting off to make it exact before multiplying by n...
- sbi 14y agoThis 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 ...