Estimate e by summing uniforms past 1

Question

Draw U(0,1) numbers one at a time and add them up. Stop the moment the running sum exceeds 1, and record how many draws that took. A remarkable fact is that the expected number of draws is exactly e \approx 2.71828. Write the estimator, and say roughly how many trials you need for 3 correct decimals of e.

Accepted Answer

Let N = \min\{k : U1 + \dots + Uk 1\}. Then P(N k) = P(U1 + \dots + Uk \le 1) = 	frac{1}{k!} (the volume of the k-dimensional simplex), so E[N] = \sum{k \ge 0} P(N k) = \sum{k \ge 0} 	frac{1}{k!} = e. Average N over many trials: Convergence. Using P(Nk)=1/k! again, E[N^2] = \sum{k\ge 0}(2k+1)P(Nk) = 3e, so \operatorname{Var}(N) = 3e - e^2 \approx 0.766. The estimator's standard error is \sqrt{0.766/n} \approx 0.875/\sqrt n. For error near 10^{-3} you need n \approx (0.875/0.001)^2 \approx 7.7 	imes 10^{5} trials. Takeaway. This is Monte Carlo for an expectation rather than an area: simulat…

Estimate e by summing uniforms past 1

Your answer

More Coding questions