What is the expected number of times that the phrase will appear in the sentence?

Question

You create a random sentence of length n by repeatedly picking words at random from the vocabulary {a, is, not,rose}, with each word being equally likely to be picked. What is the expected number of times that the phrase “a rose is a rose” will appear in the sentence?

Answer 1

Suppose the sentence is $S = w_1w_2\cdots w_n$. Define random variables $X_i$ for $1 \leq i \leq n - 4$ as $$ X_i = \begin{cases} 1 & \text{ if }\ w_iw_{i+1}\cdots w_{i+4} = \text{"a rose is a rose"} \\ 0 & \text { otherwise } \end{cases} $$ The number of "a rose is a rose" in $S$ is therefore $$ X = \sum_{i=1}^{n-4} X_i $$ Thus $$ \mathbb{E}[X] = \sum_{i=1}^{n-4} \mathbb{E}[X_i] = (n-4)\cdot \frac{1}{4^5} $$