The Problem

This week’s Classic asks:

“Graydon is about to depart on a boating expedition that seeks to catch footage of the rare aquatic creature, F. Riddlerius. Every day he is away, he will send a hand-written letter to his new best friend, David Hacker.² But if Graydon still has not spotted the creature after N days (where N is some very, very large number), he will return home.

Knowing the value of N, Graydon confides to David there is only a 50 percent chance of the expedition ending in success before the N days have passed. But as soon as any footage is collected, he will immediately return home (after sending a letter that day, of course).

On average, for what fraction of the N days should David expect to receive a letter?”

The Approach

We will solve the problem in a more general form by setting the 50% value as a parameter:

Solution

Note: Corrected after seeing frompother solutions that part of the probability was left out!

First we observe that given a uniform daily probability p of observing the creature the probability of failure of the expedition after N days is:

The expected fraction of days a letter is sent will be the expected value of the number of days letters are sent divided by N. The probability of i < N letters being sent is the probability of i-1 days of non-discovery times the probability of discovery on the ith day. We then need to add the probability that the creature is not discovered at all:

With some work we can evaluate this sum. One trick to notice is that a sum like this is essentially the derivative of a standard geometric series with an extra term. With a fair bit of algebra and re-arrangements we find:

Substituting our value for 1- Ps above and simplifying:

For large N and small p we can use the following approximation:

And our final expression for the expected fraction of N days that a letter is received is:

For our specific case of Ps = 50% the expectation is:

We graph the expected percentage of days with letters versus probability of expedition success:

We can also look at the case where Ps approaches one and we can see that E will slowly approach zero. In this case we know the unconstrained expected number of letters will be 1/p, the percentage will be 1/N*p and 1/N*p goes as -1/ln(1-Ps) which goes to zero as Ps goes to 1. However it goes to zero very slowly: