Squared recurrence relation in Markov chain situation A roulette-like game uses a wheel with three angular regions, colored
black, red and white (which we will denote by $B,R$ and $W$). The black
and red regions have equal length $a$, and the white region has much smaller
length $\varepsilon$. We rescale so that $a+2\varepsilon=1$. Spinning the wheel
$n$ times yields an uple $(X_1,\ldots,X_n)\in \lbrace B,R,W\rbrace^n$. Denote by
$T_n$ the number of times when the same (non-white) color is obtained three
times in a row, formally 
$$T_n=\Big|\Big\lbrace i\in[1..(n-3)] \ \Big| \ (X_i,X_{i+1},X_{i+2})
\in \lbrace (B,B,B),(R,R,R)\rbrace
\Big\rbrace\Big|$$
Now let $a_n=P(T_n=0)$. A simple argument (see below) shows that $(a_n)$
satisfies the recurrence relation 
$a_{n+3}=(a+\varepsilon)a_{n+2}+a(a+\varepsilon)a_{n+1}+\varepsilon a^2 a_n$,
in other words $(a_n)$ is annihilated by 
$Q=X^3-(a+\varepsilon)X^2-a(a+\varepsilon)X-\varepsilon a^2$.
Next, let $b_n=P(T_n=1)$. With some painstaking and ugly computation,
I was able to show that $(b_n)$ is annihilated by $Q^2$. I wonder if there
is a more simple way to derive this fact ? More generally, is
$(P(T_n=k))_{n\geq 1}$ annihilated by $Q^k$ ?
Proof of the recurrence relation for $(a_n)$. For
$(p_1,p_2)\in \lbrace B,R,W\rbrace^n$, let $f_n(p_1,p_2)=p((T_n=0)\cap(X_1,X_2)=(p_1,p_2))$. Then, using
the interchangeable roles of $B$ and $R$ and other natural invariants
of the problem, we have :


*

*$f_n(W,D)=f_n(W,R)=f_n(R,B)=f_n(B,R)$ (denote this common value by $v_1(n)$).

*$f_n(R,W)=f_n(B,W)=f_n(W,W)$ (denote this common value by $v_2(n)$).

*$f_n(R,R)=f_n(B,B)$ (denote this common value by $v_3(n)$).
It follows that $v_n=(v_1(n),v_2(n),v_3(n))$ satisfies the relation
$v_{n+1}=Mv_n$, where $M$ is the matrix
$$
M=\left(\begin{array}{ccc}
a & \varepsilon & a \\
2a & \varepsilon & 0 \\
a & \varepsilon & a \\
\end{array}\right)
$$
The characteristic polynomial of $M$ is $Q$, concluding the proof.
 A: We first re-explain carefully the computations in the post, leading to the case $k=0$, then we generalize these to solve the case $k=1$, and finally we explain briefly how the method actually solves the question for every $k\geqslant0$.
1. The case $k=0$ 
For every $n$, consider the vector $u_n=(u_n^i)_{0\leqslant i\leqslant2}$, where $u_n^i$ denotes the probability that $T_n=0$ and that the sequence $(X_1,X_2,\ldots,X_n)$ ends by a prefix of $BBB$ or $RRR$ of length $i$ but not larger. 
If $n\geqslant3$, $u_n^0$ corresponds to sequences ending by $W$, $u^1_n$ corresponds to sequences ending by $WB$ or $WR$, and $u^2_n$ corresponds to sequences ending by $WBB$, $RBB$, $WRR$ and $BRR$.
One-step decompositions similar to those explained in the question lead to the recursion $$u_{n+1}=Au_n$$ where $$A=\begin{pmatrix}1-2a&1-2a&1-2a\\2a&a&a\\0&a&0\end{pmatrix}$$ The behaviour of each sequence $u^i=(u^i_n)_n$ is ruled by the eigenvalues of $A$, that are the roots of the characteristic polynomial $\chi_A$ of $A$, in the sense that 
$$\chi_A(\vartheta)(u)=0$$ where $u=(u_n)_u$ and the shift $\vartheta$ is defined, for every sequence $a=(a_n)$, by the identity $$(\vartheta a)_n=a_{n+1}$$  Note that
$$\chi_A(x)=x^3-(1-a)x^2-a(1-a)x-a^2(1-2a)$$ hence, since $a_n=P(T_n=0)$ is also $a_n=\mathbf 1^Tu_n$, all this indeed leads to the identities
$$a_{n+3}-(1-a)a_{n+2}-a(1-a)a_{n+1}-a^2(1-2a)a_n=0$$
2. The case $k=1$
Consider the vector $v_n=(v_n^i)_{0\leqslant i\leqslant3}$, where $v_n^i$ denotes the probability that $T_n=1$ and that the sequence $(X_1,X_2,\ldots,X_n)$ ends by a prefix $BBB$ or $RRR$ of length $i$ but not larger. Note that the case $i=3$ becomes relevant since sequences ending by $BBB$ or $RRR$ can occur when $T_n\geqslant1$. Using similar notations as before, one gets $$v_{n+1}=Cv_n+Bu_n$$ where $$C=\begin{pmatrix}1-2a&1-2a&1-2a&1-2a\\2a&a&a&a\\0&a&0&0\\0&0&0&0\end{pmatrix}\qquad B=\begin{pmatrix}0&0&0\\0&0&0\\0&0&0\\0&0&a\end{pmatrix}$$
Now, 
$$\chi_A(\vartheta)(\vartheta v-Cv)=\chi_A(\vartheta)(Bu)=B\chi_A(\vartheta)(u)=0$$
hence $$\vartheta\chi_A(\vartheta)(v)=\chi_A(\vartheta)(Cv)=C\chi_A(\vartheta)(v)$$ Thus, the sequence $$w=\chi_A(\vartheta)(v)$$ solves $$w_{n+1}=Cw_n$$ and, as such, $$\chi_C(\vartheta)(w)=0$$
By inspection, $$\chi_C(x)=x\cdot\chi_{A}(x)$$ hence $$\vartheta\chi_{A}(\vartheta)(\chi_A(\vartheta)(v))=0$$ that is, to use the language in the question, the polynomial $Q_1(x)=x\chi_A(x)^2$ annihilates each $(v_n^i)$ hence, since $b_n=P(T_n=1)$ is also $b_n=\mathbf 1^Tv_n$, the polynomial $Q_1(x)$ annihilates the sequence $(b_n)$.
3. The general case
For every $k\geqslant1$, using notations that are hopefully self-explanatory, one can show that $$v^{(k+1)}_{n+1}=Cv_n^{(k+1)}+Bv_n^{(k)}$$ hence, if $Q_k(x)$ annihilates the sequence $P(T_n=k)$ then $Q_{k+1}(x)=x\chi_A(x)Q_k(x)$ annihilates the sequence $P(T_n=k+1)$. Finally, all this proves the following result.

Let  $\chi_A(x)=x^3-(1-a)x^2-a(1-a)x-a^2(1-2a)$. Then, for every $k\geqslant0$, the polynomial $Q_k(x)=x^k\chi_A(x)^{k+1}$ annihilates the sequence $(P(T_n=k))_{n\geqslant1}$. Equivalently, the polynomial $\chi_A(x)^{k+1}$ annihilates the sequence $(P(T_n=k))_{n\geqslant k+1}$.

