Penpals

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.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?”

The Approach

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

P_s = probability\ of\ success

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:

P_f = 1 - P_s = (1-p)^N

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:

E = \dfrac{1}{N} \sum_{i=1}^{i=N} (1-p)^{i-1} \cdot p \cdot i + (1-p)^N

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:

E = \dfrac {1- (1-p)^N}{N \cdot p}

Substituting our value for 1- Ps above and simplifying:

E =  \dfrac{P_s}{N \cdot p}

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

(1-p)^N = 1 - P_s

N\cdot p \approxeq -ln(1-P_s)

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

E \approxeq  \dfrac{Ps}{ln(1/(1-P_s))}

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

E \approxeq \dfrac{1}{2 \cdot ln(2)}  \approxeq .7213

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:

Penpals

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s