
\begin{theorem}\label{th:stego}
Soit  $\epsilon$ un nombre positif, 
$l$ un nombre de LSBs, 
$X   \sim \mathbf{U}\left(\mathbb{B}^l\right)$,
un adapteur de stratégie uniformémement distribué indépendant de $X$
$f_l$ un mode tel que  
$\textsc{giu}(f_l)$ est fortement connexe et la 
matrice de Markov associée à  $f_l$ est doublement stochastique.
Il existe un nombre $q$ d'itérations tel que 
$|p(Y|K)- p(X)| < \epsilon$. 
\end{theorem}



\begin{proof}   
Let $\textit{deci}$ be the bijection between $\Bool^{l}$ and 
$\llbracket 0, 2^l-1 \rrbracket$ that associates the decimal value
of any  binary number in $\Bool^{l}$.
The probability $p(X^t) = (p(X^t= e_0),\dots,p(X^t= e_{2^l-1}))$ for $e_j \in \Bool^{l}$ is thus equal to 
$(p(\textit{deci}(X^t)= 0,\dots,p(\textit{deci}(X^t)= 2^l-1))$ further denoted by $\pi^t$.
Let $i \in \llbracket 0, 2^l -1 \rrbracket$, 
the probability $p(\textit{deci}(X^{t+1})= i)$  is 
\[
 \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 
where $ i =_k j $ is true iff the binary representations of 
$i$ and $j$ may only differ for the  $k$-th element,
and where 
$i_k$ abusively denotes, in this proof, the $k$-th element of the binary representation of 
$i$.

Next, due to the proposition's hypotheses on the strategy,
$p(\textit{deci}(X^t) = j , S^t = k , i =_k j, f_k(j) = i_k )$ is equal to  
$\frac{1}{l}.p(\textit{deci}(X^t) = j ,  i =_k j, f_k(j) = i_k)$.
Finally, since $i =_k j$ and $f_k(j) = i_k$ are constant during the 
iterative process  and thus does not depend on $X^t$, we have 
\[
\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 ).
\]

Since 
$\frac{1}{l}  
\sum\limits^{l}_{k=1} 
p(i =_k j, f_k(j) = i_k ) 
$ is equal to $M_{ji}$ where  $M$ is the Markov matrix associated to
 $f_l$ we thus have
\[
\pi^{t+1}_i = \sum\limits^{2^l-1}_{j=0}
\pi^t_j. M_{ji} \textrm{ and thus }
\pi^{t+1} = \pi^{t} M.
\]

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

First of all, 
since the graph $\Gamma(f)$ is strongly connected,
then for all vertices $i$ and $j$, a path can
be  found to  reach $j$  from $i$  in at  most $2^l$  steps.  
There  exists thus $k_{ij} \in \llbracket 1,  2^l \rrbracket$ s.t.
${M}_{ij}^{k_{ij}}>0$.  
As all the multiples $l \times k_{ij}$ of $k_{ij}$ are such that 
${M}_{ij}^{l\times  k_{ij}}>0$, 
we can  conclude that, if
$k$ is the least common multiple of $\{k_{ij}  \big/ i,j  \in \llbracket 1,  2^l \rrbracket  \}$ thus 
$\forall i,j  \in \llbracket  1, 2^l \rrbracket,  {M}_{ij}^{k}>0$ and thus 
$M$ is a regular stochastic matrix.


Let us now recall the following stochastic matrix theorem:
\begin{theorem}[Stochastic Matrix]
  If $M$ is a regular stochastic matrix, then $M$ 
  has an unique stationary  probability vector $\pi$. Moreover, 
  if $\pi^0$ is any initial probability vector and 
  $\pi^{t+1} = \pi^t.M $ for $t = 0, 1,\dots$ then the Markov chain $\pi^t$
  converges to $\pi$ as $t$ tends to infinity.
\end{theorem}

Thanks to this theorem, $M$ 
has an unique stationary  probability vector $\pi$. 
By hypothesis, since $M$ is doubly stochastic we have 
$(\frac{1}{2^l},\dots,\frac{1}{2^l}) = (\frac{1}{2^l},\dots,\frac{1}{2^l})M$
and thus $\pi =  (\frac{1}{2^l},\dots,\frac{1}{2^l})$.
Due to the matrix theorem, there exists some 
$q$ s.t. 
$|\pi^q- \pi| < \epsilon$
and the proof is established.
Since $p(Y| K)$ is $p(X^q)$ the method is then $\epsilon$-stego-secure
provided the strategy-adapter is uniformly distributed.
 \end{proof}
