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{ if $i$ is odd} \\
x_i \oplus x_{i-1} \textrm{ if $i$ is even}
\end{array}
\right.
\end{equation}\label{eq:fqq}

Prouvons que la matrice de Markov associée est doublement stochastique.

the Markov chain is stochastic by construction. 

Let us prove that its Markov chain is doubly stochastic by induction on the 
length $l$.
For $l=1$ and $l=2$ the proof is obvious. Let us consider that the 
result is established until $l=2k$ for some $k \in \Nats$.

Let us then firstly prove the doubly stochasticity for $l=2k+1$.
Following notations introduced in~\cite{bcgr11:ip}, 
Let  $\textsc{giu}(f_{2k+1})^0$ and $\textsc{giu}(f_{2k+1})^1$ denote
the subgraphs of $\textsc{giu}(f_{2k+1})$ induced by the subset $\Bool^{2k} \times\{0\}$
and $\Bool^{2k} \times\{1\}$ of $\Bool^{2k+1}$ respectively.
$\textsc{giu}(f_{2k+1})^0$ and   $\textsc{giu}(f_{2k+1})^1$ are isomorphic to $\textsc{giu}(f_{2k})$.
Furthermore, these two graphs are linked together only with arcs of the form
$(x_1,\dots,x_{2k},0) \to (x_1,\dots,x_{2k},1)$ and 
$(x_1,\dots,x_{2k},1) \to (x_1,\dots,x_{2k},0)$.
In $\textsc{giu}(f_{2k+1})$ the number of arcs whose extremity is $(x_1,\dots,x_{2k},0)$
is  the same than the number of arcs whose extremity is $(x_1,\dots,x_{2k})$ 
augmented with 1, and similarly for $(x_1,\dots,x_{2k},1)$.
By induction hypothesis, the Markov chain associated to $\textsc{giu}(f_{2k})$ is doubly stochastic. All the vertices $(x_1,\dots,x_{2k})$ have thus the same number of 
ingoing arcs and the proof is established for $l$ is $2k+1$.

Let us then  prove the doubly stochasticity for $l=2k+2$.
The map $f_l$ is defined by 
$f_l(x)= (\overline{x_1},x_2 \oplus x_{1},\dots,\overline{x_{2k+1}},x_{2k+2} \oplus x_{2k+1})$.
With previously defined  notations, let us focus on 
$\textsc{giu}(f_{2k+2})^0$ and   $\textsc{giu}(f_{2k+2})^1$ which are isomorphic to $\textsc{giu}(f_{2k+1})$. 
Among configurations of $\Bool^{2k+2}$, only four suffixes of length 2 can be
obviously observed, namely, $00$, $10$, $11$ and $01$.
Since 
$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$ and $f_{2k+2}(\dots,0,1)_{2k+2}=1$, the number of 
arcs whose extremity is 
\begin{itemize}
\item $(x_1,\dots,x_{2k},0,0)$
 is the same than the one whose extremity is $(x_1,\dots,x_{2k},0)$ in $\textsc{giu}(f_{2k+1})$ augmented with 1 (loop over configurations $(x_1,\dots,x_{2k},0,0)$).
\item $(x_1,\dots,x_{2k},1,0)$
 is the same than the one whose extremity is $(x_1,\dots,x_{2k},0)$ in $\textsc{giu}(f_{2k+1})$ augmented with 1 (arc from configurations 
$(x_1,\dots,x_{2k},1,1)$ to configurations 
$(x_1,\dots,x_{2k},1,0)$) 
\item $(x_1,\dots,x_{2k},0,1)$
 is the same than the one whose extremity is $(x_1,\dots,x_{2k},0)$ in $\textsc{giu}(f_{2k+1})$ augmented with 1 (loop over configurations $(x_1,\dots,x_{2k},0,1)$).
\item $(x_1,\dots,x_{2k},1,1)$
 is the same than the one whose extremity is $(x_1,\dots,x_{2k},1)$ in $\textsc{giu}(f_{2k+1})$ augmented with 1 (arc from configurations 
$(x_1,\dots,x_{2k},1,0)$ to configurations 
$(x_1,\dots,x_{2k},1,1)$).
\end{itemize}
Thus all the vertices $(x_1,\dots,x_{2k})$ have  the same number of 
ingoing arcs and the proof is established for $l=2k+2$.
