Casino Game

The solution for this weeks FiveThirtyEight riddler is pretty nutty.

The riddle is essentially:

If you drew random numbers from a uniform distribution from [0,1], what is the expected number of draws 
you would perform until their sum exceeds 1?

So let us define $$S_{n}$$ as the sum of the nth number drawn. Then the probability of the first sum $$S_{1}$$ being less than some value x is:

$$P(S_{1}\leq x) = x$$

Then probability of the second sum $$S_{2}$$ being less than x can be calculated by taking $$P(S_{1}\leq x)$$ as a conditional distribution on $$P(S_{2}\leq x)$$ and calculating the marginal prob.:

$$P(S_{2}\leq x) =\int_0^1{P(S_{1}\leq x)}\cdot 1\ dx$$
$$ =\int_0^1 x\ dx$$
$$ =\frac{x^2}{2}$$

Probability of the 3rd is:

$$P(S_{3}\leq x) =\int_0^1{P(S_{2}\leq x)}\cdot 1\ dx$$
$$ =\int_0^1 \frac{x^2}{2}\ dx$$
$$ =\frac{x^3}{6}$$

Extending to n:

$$P(S_{n}\leq x) =\frac{x^n}{n!}$$

Since we're concerned with the sum exceeding $x=1$:

$$P(S_{n}\leq 1) =\frac{1}{n!}$$

To find the probability of exactly $n$ draws summing greater than 1, we have to find the probability of $n-1$'s sum exceeding one and subtract that off the probability of $n$'s sum exceeding.

$$P(N\ge n) = \frac{1}{n-1!} - \frac{1}{n!}$$

Then we can calculate the expectation on that distribution:

$$E[P(N\ge n)] = \sum_{n=2}^\infty n \cdot (\frac{1}{n-1!} - \frac{1}{n!})$$
$$ = \sum_{n=2}^\infty (\frac{n}{n-1!} - \frac{1}{n-1!})$$
$$ = \sum_{n=2}^\infty \frac{1}{n-2!}$$
$$ = \sum_{n=0}^\infty \frac{1}{n!}$$
$$ = e$$

The expected number of draws you need to exceed 1 is e!

The convergence to e does make some intuitive sense. You'll almost assuredly never bust on the first draw, so the minimum # of draws you'll have to make is at least two. Since we're drawing from a uniform distribution from [0,1], we have a mean of 1/2. 2x the mean gets us to 1, and 3x the mean moves us to 1.5, so a value in between 2-3 fits the bill.