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.2 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?”
We will solve the problem in a more general form by setting the 50% value as a parameter:
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: