an express riddle

A quick puzzle on The Riddler this week that enjoys a quick solution once one writes it out. The core of the puzzle is about finding the average number of draws one need to empty a population of size T if each draw is uniform over the remaining number of individuals between one and the number that remain. It is indeed easy to see that this average satisfies

$\epsilon^T=1+\frac{1}{T}\sum_{i=1}^{T-1} \epsilon^i$

since all draws but one require an extra draw. A recursion then leads by elimination to deduce that

$\epsilon^T=\frac{1}{T}+\frac{1}{T-1}+\ldots+\frac{1}{2}+1$

which is the beginning of the (divergent) harmonic series. In the case T=30, the solution is (almost) equal to 4.

> sum(1/(1:30))*1e10
[1] 39949871309

A second riddle the same week reminded me of a result in Devroye’s Non-Uniform Random Variate Generation, namely to find the average number of draws from a Uniform until the sequence goes down. Actually, the real riddle operates with a finite support Uniform, but I find the solution with the continuous Uniform more elegant. And it only took a few metro stops to solve. The solution goes as follows: the probability to stop after two Uniform draws is 1/2, after n uniform draws, it is (n-1)/n!, which does sum up to 1:

$\sum_{n=2}^\infty \frac{n-1}{n!} = \sum_{n=2}^\infty \frac{n}{n!} - \sum_{n=2}^\infty \frac{1}{n!} = \sum_{n=1}^\infty \frac{1}{n!} - \sum_{n=2}^\infty \frac{1}{n!}=1$

and the expectation of this distribution is e-1 by a very similar argument, as can be checked by a rudimentary Monte Carlo experiment

> over(1e7) #my implementation of the puzzle
[1] 1.7185152

This entry was posted on January 20, 2017 at 12:17 am and is filed under Books, Kids, R with tags FiveThirtyEight, harmonic series, The Riddler. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

Xi'an's Og