On considère le  mode
$f_l: \Bool^l \rightarrow \Bool^l$ t.q. le $i^{\textrm{ème}}$ composant 
est défini par 
\begin{equation}
{f_l}(x)_i =
\left\{
\begin{array}{l}
\overline{x_i} \textrm{ si $i$ est impair} \\
x_i \oplus x_{i-1} \textrm{ si $i$ est pair}
\end{array}
\right.
\tag{\eqref{eq:fqq}}
\end{equation}


Prouvons que la matrice de Markov associée est doublement stochastique par induction 
sur la longueur $l$.
Pour $l=1$ et $l=2$ la preuve est évidente.
Considérons que le résulat est établi jusqu'à $l=2k$ avec $k \in \Nats$.

On montre d'abord que la double stochasticité est établie pour $l=2k+1$.
En suivant les notations introduites à la section~\ref{anx:sccg}, soit
$\textsc{giu}(f_{2k+1})^0$ et $\textsc{giu}(f_{2k+1})^1$ les sous-graphes 
de $\textsc{giu}(f_{2k+1})$ induits par les ensembles $\Bool^{2k} \times\{0\}$
et $\Bool^{2k} \times\{1\}$ de $\Bool^{2k+1}$ respectivement.
Les graphes $\textsc{giu}(f_{2k+1})^0$ et $\textsc{giu}(f_{2k+1})^1$ sont isomorphes à $\textsc{giu}(f_{2k})$.
De plus, ils ne sont liés dans $\textsc{giu}(f_{2k+1})$ que par 
des arcs de la forme 
$(x_1,\dots,x_{2k},0) \to (x_1,\dots,x_{2k},1)$ et 
$(x_1,\dots,x_{2k},1) \to (x_1,\dots,x_{2k},0)$.
Dans $\textsc{giu}(f_{2k+1})$, deux sortes d'arcs pointent vers $(x_1,\dots,x_{2k},0)$.
Ceux qui sont de la forme $(y_1,\dots,y_{2k},0)$, où un seul des $y_i$ est différent de $x_i$, 
et leur nombre est celui des arcs qui pointent vers $(x_1,\dots,x_{2k})$ dans $\textsc{giu}(f_{2k})$.
L'arc $(x_1,\dots,x_{2k},0) \to (x_1,\dots,x_{2k},0)$ qui existe d'après la définition de $f_l$
De même pour le nombre d'arcs dont l'extrémité est de la forme $(x_1,\dots,x_{2k},1)$.
Par hypothèse d'induction, la chaîne de Markov associée à $\textsc{giu}(f_{2k})$ 
est doublement stochastique.
Ainsi tous les sommets $(x_1,\dots,x_{2k})$ ont le même nombre d'arcs entrants et la preuve est établie pour $l= 2k+1$.

Montrons à présent la double stochasticité pour $l=2k+2$.
La fonction $f_l$ est définie par $f_l(x)= (\overline{x_1},x_2 \oplus x_{1},\dots,\overline{x_{2k+1}},x_{2k+2} \oplus x_{2k+1})$.  On se concentre sur  
$\textsc{giu}(f_{2k+2})^0$ et   $\textsc{giu}(f_{2k+2})^1$ qui sont isomorphes à  $\textsc{giu}(f_{2k+1})$. 
Parmi les configurations de  $\Bool^{2k+2}$, seuls  quatre suffixes de longueur 2 peuvent appraître:
$00$, $10$, $11$ et $01$.
Puisque 
$f_{2k+2}(\dots,0,0)_{2k+2}=0$, $f_{2k+2}(\dots,1,0)_{2k+2}=1$, 
$f_{2k+2}(\dots,1,1)_{2k+2}=0$ et  $f_{2k+2}(\dots,0,1)_{2k+2}=1$, le nombre d'arcs dont les extrémités est  
\begin{itemize}
\item $(x_1,\dots,x_{2k},0,0)$
est le même que celui dont l'extrémité est de la forme  $(x_1,\dots,x_{2k},0)$ dans $\textsc{giu}(f_{2k+1})$
 auquel on ajoute 1 (une boucle autours des configurations $(x_1,\dots,x_{2k},0,0)$);
\item $(x_1,\dots,x_{2k},1,0)$
est le même que celui dont l'extrémité est de la forme $(x_1,\dots,x_{2k},0)$ in $\textsc{giu}(f_{2k+1})$ 
 auquel on ajoute 1 (l'arc entre les configurations  $(x_1,\dots,x_{2k},1,1)$ et les  configurations 
$(x_1,\dots,x_{2k},1,0)$); 
\item $(x_1,\dots,x_{2k},0,1)$
est le même que celui dont l'extrémité est de la forme $(x_1,\dots,x_{2k},0)$ in $\textsc{giu}(f_{2k+1})$ 
 auquel on ajoute 1 (une boucle autours des configurations $(x_1,\dots,x_{2k},0,1)$);
\item $(x_1,\dots,x_{2k},1,1)$
est le même que celui dont l'extrémité est de la forme $(x_1,\dots,x_{2k},1)$ in $\textsc{giu}(f_{2k+1})$
auquel on ajoute 1 (l'arc entre les configurations  
$(x_1,\dots,x_{2k},1,0)$ et les configurations 
$(x_1,\dots,x_{2k},1,1)$).
\end{itemize}
Chacun des sommets $(x_1,\dots,x_{2k+2})$ a donc le même nombre d'arcs entrants,  
la preuve est donc établie pour $l=2k+2$.
