March 26, 2016

# 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 $\frac{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.