Expected value of the number of substrings 101 or 111 in the string

Question

Let $X_1,X_2,...,X_n, n>6$ are independent, $P(X_i=0)=\frac{3}{4}$ or $P(X_i=1)=\frac{1}{4}$. Let $Y_n$ is the number of substring $101$ or $111$ in the string $(X_1,...,X_n)$.
For example: for $(0,0,1,0,1,0,1,1,1,0,0)$ we have $Y_{11}=3$.
Find $EY_{n}$.

My approach:
I thought about it like about n-2 Bernoulli experiment, where
$p=P(X_{k}=1,X_{k+1}\in\{0,1\},X_{k+2}=1)=\frac{1}{4}*1*\frac{1}{4}=\frac{1}{16}.$

$P(Y_n=k)=\binom{n-2}{k}p^k(1-p)^{(n-2)-k}$.

$EY_n=\sum_{k=0}^{n-2}kP(Y_n=k)=...=\frac{n-2}{16} $

But the experiments are not independent so unfortunately this cannot be solve that way. Maybe you have some hints.

Answer 1

The fact that the experiments are not independent does not impact the result. The linearity of expectation still holds.

Let $Z_n$ be equal 1 if the string starting at position $n$ satisfies the desired criterion, and 0 otherwise.

Then, $$E(Y_n) = E(Z_1 + \ldots + Z_{n-2}) = (n-2)p$$

where $$p=1/16.$$

Here is an alternative solution:

% building transition matrix
n=11
i=1
z=2, o=3, oz=4, oo=5, ozo=6, ooo=7
P(i,z)=pz, P(i,o)=(1-pz)
pz=3/4
P(i,z)=pz, P(i,o)=(1-pz)
P(z,z)=pz, P(z,o) = 1-pz
P(o,oz)=pz, P(o,oo)=1-pz
P(oz,z)=pz, P(oz,ozo)=1-pz
P(oo,oz)=pz, P(oo,ooo)=1-pz
P(ooo,ooo)=1-pz, P(ooo,oz)=pz
P(ozo,oo)=1-pz, P(ozo,oz)=pz

% finding expected value
expectedvalue=0;
for j=1:n
    curmat=P^j;
    expectedvalue=expectedvalue+curmat(i,ozo)+curmat(i,ooo);
end

% the solutions agree
expectedvalue
(n-2)*1/16

P =
               0   0.750000000000000   0.250000000000000                   0                   0                   0                   0
               0   0.750000000000000   0.250000000000000                   0                   0                   0                   0
               0                   0                   0   0.750000000000000   0.250000000000000                   0                   0
               0   0.750000000000000                   0                   0                   0   0.250000000000000                   0
               0                   0                   0   0.750000000000000                   0                   0   0.250000000000000
               0                   0                   0   0.750000000000000   0.250000000000000                   0                   0
               0                   0                   0   0.750000000000000                   0                   0   0.250000000000000


P^2 =

               0   0.562500000000000   0.187500000000000   0.187500000000000   0.062500000000000                   0                   0
               0   0.562500000000000   0.187500000000000   0.187500000000000   0.062500000000000                   0                   0
               0   0.562500000000000                   0   0.187500000000000                   0   0.187500000000000   0.062500000000000
               0   0.562500000000000   0.187500000000000   0.187500000000000   0.062500000000000                   0                   0
               0   0.562500000000000                   0   0.187500000000000                   0   0.187500000000000   0.062500000000000
               0   0.562500000000000                   0   0.187500000000000                   0   0.187500000000000   0.062500000000000
               0   0.562500000000000                   0   0.187500000000000                   0   0.187500000000000   0.062500000000000

and all powers of $P$ greater than or equal to 3 are

               0   0.562500000000000   0.140625000000000   0.187500000000000   0.046875000000000   0.046875000000000   0.015625000000000
               0   0.562500000000000   0.140625000000000   0.187500000000000   0.046875000000000   0.046875000000000   0.015625000000000
               0   0.562500000000000   0.140625000000000   0.187500000000000   0.046875000000000   0.046875000000000   0.015625000000000
               0   0.562500000000000   0.140625000000000   0.187500000000000   0.046875000000000   0.046875000000000   0.015625000000000
               0   0.562500000000000   0.140625000000000   0.187500000000000   0.046875000000000   0.046875000000000   0.015625000000000
               0   0.562500000000000   0.140625000000000   0.187500000000000   0.046875000000000   0.046875000000000   0.015625000000000
               0   0.562500000000000   0.140625000000000   0.187500000000000   0.046875000000000   0.046875000000000   0.015625000000000

where $p=0.046875000000000 + 0.015625000000000=1/16$