The search for PI

Probability Level 4

A string of letters is formed by selecting one letter at a time (uniformly at random among the 26 letters of the alphabet) and concatenating it to the end of the string. The string ends when the letters $\text{PI}$ are placed at the end (in that order, with no other letters between them).

$\ldots \text{KJDMNQHTYANQDV}{\color{#D61F06}\text{PI}}$

What is the expected value of the number of characters in this string?

The answer is 676.

1 solution

Andy Hayes
May 17, 2017

Let $X_\text{PI}$ be the length of the string until the first $\text{PI}$ is concatenated, and let $P$ be the event that the most recent letter was a $\text{P}.$ For the sake of readability, let

$\begin{aligned} x &= \text{E}\left[X_\text{PI}\right] \\ y &= \text{E}\left[X_\text{PI} \mid P \right] \end{aligned}$

Applying linearity of expectation :

$\begin{aligned} x &= \frac{1}{26}(1+y)+\frac{25}{26}(1+x) \\ y &= \frac{1}{26}(1)+\frac{1}{26}(1+y)+\frac{24}{26}(1+x) \end{aligned}$

Solving this system yields $x=676,$ and so the expected value of the length of the string is $\boxed{676}.$

The search for PI

The answer is 676.

1 solution

0 pending reports