Finding EV and variance of the number of times a word occurs Consider an iid sequence $X_1, X_2, \dots, X_{n+1}$ taking values 0 or 1 with probability distribution
$$P\{X_i=1\} = 1-P\{X_i=0\} = p.$$
Uniformly choose $M$ fragments $F_1, F_2, \dots, F_M$ of length 2 starting in the interval $[1,n]$, that is, $F_i = \left(X_{j_i}, X_{j_i+1}\right)$ for some $1 \leq j_i \leq n$. Let $W=(1,1)$.
Let $N_W$ be the number of times the word $W$ occurs among the $M$ fragments. Calculate $\mathbb{E}(N_W)$.
Calculate the probability $P(F_1=W, F_2=W)$.
Calculate $\text{Var}(N_W)$.
In the problem, it says we can ignore boundary effect due to time constraints.
Clearly, $P\left( \left(X_i,X_{i+1}\right) = W\right) = P(X_i=1)P(X_{i+1}=1) = p^2$ for any $i$. For the first part, I think (but am not sure) I can say
$$\mathbb{E}(N_W) = \sum_{i=1}^M \mathbb{E}1_{\{F_i=W\}} = Mp^2.$$
As for the second part, we write $P(F_1=W, F_2=W) = P\left( \left(X_{j_1}, X_{j_1+1}\right) = (1,1), \left(X_{j_2}, X_{j_2+1}\right) = (1,1) \right)$, and so, there are three cases:


*

*There is no overlap, i.e. $j_2 \neq j_1-1, j_1, j_1+1$ happens with probability $(n-3)/n$.
$$P(F_1=W,F_2=W) = p^4$$

*There is one overlap, i.e. $j_2 = j_1-1, j_1+1$ happens with probability $2/n$.
$$P(F_1=W,F_2=W) = p^3$$

*Complete overlap, i.e. $j_2=j_1$ happens with probability $1/n$.
$$P(F_1=W, F_2=W) = p^2$$
Thus,
$$P(F_1=W, F_2=W) = \frac{n-3}{n}p^4 + \frac{2}{n}p^3 + \frac{1}{n}p^2.$$
Is this correct? And I don't even know how to approach the third part.
Any hint would be appreciated!
 A: This is just a straightforward computation. Let $Y_i = 1_{\{X_i=1\}}$
\begin{align*}
\text{Var}(N_W) &= \text{Var}\left( \sum_{i=1}^M Y_{j_i}Y_{j_i+1} \right) \\
&= \sum_{i=1}^M \text{Var}(Y_{j_1}Y_{j_1+1}) + \sum_{i \neq k} \text{Cov}(Y_{j_i}Y_{j_i+1}, Y_{j_k}Y_{j_k+1}) \\
&= M\text{Var}(Y_{j_1}Y_{j_1+1}) + 2\sum_{i=1}^{M-1} \text{Cov}(Y_{j_i}Y_{j_i+1}, Y_{j_i+1}Y_{j_i+2}) \\
&= M\text{Var}(Y_{j_1}Y_{j_1+1}) + 2(M-1)\text{Cov}(Y_{j_1}Y_{j_1+1}, Y_{j_1+1}Y_{j_1+2}) \\
&= M\left(\mathbb{E}Y_{j_1}Y_{j_1+1} - \left(\mathbb{E}Y_{j_1}Y_{j_1+1}\right)^2 \right) \\ &\quad + 2(M-1) \left(\mathbb{E}Y_{j_1}Y_{j_1+1}Y_{j_1+2} - \left(\mathbb{E}Y_{j_1}Y_{j_1+1}\right)\left(\mathbb{E}Y_{j_1+1}Y_{j_1+2}\right)\right) \\
&= M(p^2 - p^4) + 2(M-1)(p^3-p^4)
\end{align*}
A: I got a different answer. May be I made mistake somewhere.
OK we randomly choose $M$ pair. The way how you choose the fragments is equivalent to $M$ independent drawing of two numbers from the set of $n$ (and putting them back). 
So always the probability the pair be equal $(1,1)$ is $p^2$ like you wrote. 
Now lets denote $N_w(M)$ as a function of  $M$ drawning:
Now we can easily built the following recurrent  relation:
$$ 
E(N_w(M))=p^2(E(N_w(M-1))+1)+(1-p^2)E(N_w(M-1))=E(N_w(M-1))+p^2=Mp^2\\
E(N_w(M)^2)=p^2((E[N_w(M-1)+1)^2]+(1-p^2)(E[N_w(M-1)^2]=E[N_w(M-1)^2]+2p^2E[N_w(M-1)]+p^2=E[N_w(M-1)^2]+2p^4(M-1)+p^2
$$
So 
$$
Var(N_w(M))=E(N_w(M)^2)-(E(N_w(M)))^2=Var(N_w(M-1))+2p^4(M-1)+p^2-p^4-2p^4(M-1)=
Var(N_w(M-1))+p^2-p^4=M(p^2-p^4)
$$
