
Prouvons le théorème suivant.
\theoremstegoscureepsilon*



\begin{proof}   
Soit $\textit{deci}$ la bijection
entre $\Bool^{l}$ et
$\llbracket 0, 2^l-1 \rrbracket$ qui associe la valeur décimale 
à chaque nombre binaire dans $\Bool^{l} $.
La probabilité $p(X^t) = (p(X^t= e_0),\dots,p(X^t= e_{2^l-1}))$ pour $e_j \in \Bool^{l}$ est égale à 
$(p(\textit{deci}(X^t)= 0,\dots,p(\textit{deci}(X^t)= 2^l-1))$, notée par la suite $\pi^t$.
Pour $i \in \llbracket 0, 2^l -1 \rrbracket$, 
la probabilité  $p(\textit{deci}(X^{t+1})= i)$  est 
\[
 \sum\limits^{2^l-1}_{j=0}  
\sum\limits^{l}_{k=1} 
p(\textit{deci}(X^{t}) = j , S^t = k , i =_k j , f_k(j) = i_k ) 
\]
\noindent 
où  $ i =_k j $ est vraie si et seulement si les représentations binaires de 
$i$ et de  $j$ ne diffèrent que le $k^{\textrm{ème}}$ élément et 
où 
$i_k$ représente dans cette preuve  le $k^{\textrm{ème}}$ élément dans la représentation binaire 
du nombre
$i$.

En raison des hypothèses sur la stratégie, la probabilité 
$p(\textit{deci}(X^t) = j , S^t = k , i =_k j, f_k(j) = i_k )$ est égale à
$\frac{1}{l}.p(\textit{deci}(X^t) = j ,  i =_k j, f_k(j) = i_k)$.
Enfin, puisque $i =_k j$ et  $f_k(j) = i_k$ sont constant 
et sont donc indépendants de  $X^t$, on a 
\[
\pi^{t+1}_i = \sum\limits^{2^l-1}_{j=0}
\pi^t_j.\frac{1}{l}  
\sum\limits^{l}_{k=1} 
p(i =_k j, f_k(j) = i_k ).
\]

Puisque 
$\frac{1}{l}  
\sum\limits^{l}_{k=1} 
p(i =_k j, f_k(j) = i_k ) 
$ est égal à  $M_{ji}$ où  $M$ est la matrice de Markov associée à 
 $f_l$, on a ainsi
\[
\pi^{t+1}_i = \sum\limits^{2^l-1}_{j=0}
\pi^t_j. M_{ji} \textrm{ et donc }
\pi^{t+1} = \pi^{t} M.
\]

% The calculus of $p(X^{t+1} = e)$ is thus equal to 
% $\pi^{t+1}_i$. 

Maintenant, puisque le graphe  $\Gamma(f)$ est fortement connexe,
pour chaque couple de sommets $(i,j)$, un chemin peut être trouvé de $i$ jusqu'à $j$ 
de longueur au plus égale à $2^l$.
Il existe donc  $k_{ij} \in \llbracket 1,  2^l \rrbracket$ t.q.
${M}_{ij}^{k_{ij}}>0$.  

Comme tous les multiples $l \times k_{ij}$ de $k_{ij}$ sont tels que 
${M}_{ij}^{l\times  k_{ij}}>0$, on peut conclure que si 
$k$ est le PPCM de $\left\{k_{ij}  \big/ i,j  \in \llbracket 1,  2^l \rrbracket  \right\}$ alors
$\forall i,j  \in \llbracket  1, 2^l \rrbracket,  {M}_{ij}^{k}>0$ et donc 
$M$ est une matrice stochastique régulière. 



\begin{theorem}
  Si $M$ est une matrice stochastique régulière, alors $M$ 
  possède un unique vecteur stationnaire de probabilités  $\pi$
  ($\pi.M = \pi$).
  De plus, si $\pi^0$ est un vecteur de probabilité
 et si on définit 
  la suite $(\pi^{k})^{k \in  \Nats}$ par 
  $\pi^{k+1} = \pi^k.M $ pour $k = 0, 1,\dots$ 
  alors la chaîne de Markov $\pi^k$
  converge vers $\pi$ lorsque $k$ tend vers l'infini.
\end{theorem}

Grâce à ce théorème,  $M$ admet un unique vecteur stationnaire de probabilité $\pi$. 
Par hypothèses, puisque $M$ est doublement stochastique, on a 
$(\frac{1}{2^l},\dots,\frac{1}{2^l}) = (\frac{1}{2^l},\dots,\frac{1}{2^l})M$
et donc $\pi =  (\frac{1}{2^l},\dots,\frac{1}{2^l})$.
Il existe donc $q$ t.q.
$|\pi^q- \pi| < \epsilon$.
Puisque $p(Y| K)$ est $p(X^q)$, la méthode est donc $\epsilon$-stego-secure
pour peu que l'adapteur de stratégie soit uniformément distribué.
 \end{proof}
