 
Considérons le lemme technique suivant:
\begin{lemma}\label{lem:stoc}
Soit $f: \Bool^{n} \rightarrow \Bool^{n}$, $\textsc{giu}(f)$ son graphe d'itérations, $\check{M}$ la matrice d'adjacence de $\textsc{giu}(f)$, et  $M$  la matrice 
$2^n\times 2^n$  définie par
$M = \frac{1}{n}\check{M}$.
Alors $M$ est une matrice stochastique régulière si et seulement si
$\textsc{giu}(f)$ est fortement connexe.
\end{lemma}

\begin{Proof}  
On remarque tout d'abord que $M$ 
est une matrice stochastique par construction.
Supposons $M$ régulière. 
Il existe donc  $k$ tel que $M_{ij}^k>0$ pour chaque $i,j\in \llbracket
1;  2^n  \rrbracket$. L'inégalité  $\check{M}_{ij}^k>0$  est alors établie.
Puisque $\check{M}_{ij}^k$ est le nombre de chemins de  $i$ à $j$ de longueur $k$
dans $\textsc{giu}(f)$ et puisque ce nombre est positif, alors 
$\textsc{giu}(f)$ est fortement connexe.

Réciproquement si $\textsc{giu}(f)$ 
est fortement connexe, alors pour tous les sommets $i$ et $j$, un chemin peut être construit pour atteindre  $j$  depuis $i$ en au plus $2^n$ étapes.
Il existe donc 
$k_{ij} \in \llbracket 1,  2^n \rrbracket$ tels que $\check{M}_{ij}^{k_{ij}}>0$.  
Comme tous les  multiples $l \times k_{ij}$ de $k_{ij}$ sont tels que 
$\check{M}_{ij}^{l\times  k_{ij}}>0$, 
on peut conclure que, si 
$k$ est le plus petit multiple commun de $\{k_{ij}  \big/ i,j  \in \llbracket 1,  2^n \rrbracket  \}$ alors
$\forall i,j  \in \llbracket  1, 2^n \rrbracket,  \check{M}_{ij}^{k}>0$. 
Ainsi, $\check{M}$ et donc $M$ sont régulières.
\end{Proof}

Ces résultats permettent formuler et de prouver le théorème suivant:

\begin{theorem}
  Soit $f: \Bool^{n} \rightarrow \Bool^{n}$, $\textsc{giu}(f)$ son 
  graphe d'itérations , $\check{M}$ sa matrice d'adjacence
  et $M$ une matrice  $2^n\times 2^n$  définie comme dans le lemme précédent.
  Si $\textsc{giu}(f)$ est fortement connexe, alors 
  la sortie du générateur de nombres pseudo aléatoires détaillé par 
  l'algorithme~\ref{CI Algorithm} suit une loi qui 
  tend vers la distribution uniforme si 
  et seulement si  $M$ est une matrice doublement stochastique.
\end{theorem}

\begin{Proof}
  $M$ est une matrice stochastique régulière (Lemme~\ref{lem:stoc}) 
  qui a un unique vecteur de probabilités stationnaire
  (Théorème \ref{th}).
  Soit $\pi$  défini par 
  $\pi = \left(\frac{1}{2^n}, \hdots, \frac{1}{2^n} \right)$.
  On a  $\pi M = \pi$ si et seulement si
  la somme des valeurs de chaque colonne de $M$  est 1, 
  \textit{i.e.} si et seulement si 
  $M$ est  doublement  stochastique.
\end{Proof}



Montrons que
\begin{lemma}
$d$ est une distance sur $\mathcal{X}_{\mathsf{N},\mathcal{P}}$.
\end{lemma}


\begin{proof}
 $d_{\mathds{B}^\mathsf{N}}$ est la distance de Hamming.
 Prouvons que  
 $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}$ est aussi une distance;
$d$ sera ainsi une distance comme somme de deux distances.
 \begin{itemize}
\item De manière évidente, $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s})\geqslant 0$, et si $s=\check{s}$, alors
$d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s})=0$. 
Réciproquement si $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s})=0$, alors
$\forall k \in \mathds{N}, v^k=\check{v}^k$ d'après la définition de $d$.
Or les éléments entre les positions $p+1$ et  $p+n$ 
sont nules et correspondent à $|u^0-\check{u}^0|$, 
on peut conclure que $u^0=\check{u}^0$.
On peut étendre ce résultat aux $n \times \max{(\mathcal{P})}$ premiers 
bloc engendrant $u^i=\check{u}^i$, $\forall i \leqslant v^0=\check{v}^0$, 
et en vérifiant tous les  $n \times \max{(\mathcal{P})}$ blocs, $u=\check{u}$.
 \item $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}$ est évidemment  symétrique 
($d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s})=d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(\check{s},s)$). 
\item l'inégalité triangulaire est établie puisque la valeur absolue la vérifie
aussi.
 \end{itemize}
\end{proof}
