This is a question I found online
A monkey types at a 26-letter keyboard with one key corresponding to each of the lowercase English letters. Each keystroke is chosen independently and uniformly at random
from the 26 possibilities. If the monkey types 1 million letters, what is the expected
number of times the sequence “book” appears?
And this is the solution
There are 1,000,000 − 4 + 1 = 999,997 places where “book” can appear, each with a
(non-independent) probability of $1/26^4$ of happening. If A is the random variable that tells
how many times “book” appears, and Ai
is the indicator variable that is 1 if “book”
appears starting at the ith letter, then
$E[A] = E[A_1 +···+A_{999,997}]
= E[A_1] +···+E[A_{999,997}]
=
999,997/
264
≈ 2.19$
I don't understand why it works because i and i+1-th letter cannot be "BOOK" at the same time. How can we sum up $ E[A_{i}]$ and $E[A_{i+1}]$?
Best Answer
Expectation is additive even if the random variables involved are not independent. If some fixed substring $s$ occurs with probability $p(s)$ in first place and probability $p(s)$ in second place, then the expected number of times that this string occurs in first or second place is $2p(s)$, even though the probability that the string appears in both places at once depends on the string in question.