section~\ref{sec:mixing}.
L'extension du travail aux itérations généralisées est présentée à la
section~\ref{sec:prng:gray:general}.
-Finalement, des instances de PRNGS engendrés selon les méthodes détaillées dans
-ce chapitre sont présentés en section~\ref{sec:prng;gray:tests}.
-Les sections~\ref{sec:plc} à~\ref{sub:gray} ont été publiées
+Finalement, des instances de PRNGs engendrés selon les méthodes détaillées dans
+ce chapitre sont présentées en section~\ref{sec:prng;gray:tests}.
+Les sections~\ref{sec:plc} à~\ref{sub:gray} ont été publiées
à~\cite{chgw+14:oip}.
+La section~\ref{sec:mixing} est publiée dans~\cite{ccgh16}.
% This aim of this section is to show
configuration $i$ est inférieur à ${\mathsf{N}}$;
\item pour $j \neq i$, $0 \le M_{ij} \le 1$: on construit l'arc de $i$ à $j$
-si et seulement si $M_{ij}$ vaut 1 (et 0 sinon)
+si et seulement si $M_{ij}$ vaut 1 (et 0 sinon);
\item pour chaque indice de ligne $i$, $1 \le i\le 2^{\mathsf{N}}$, ${\mathsf{N}} = \sum_{1 \le j\le 2^{\mathsf{N}}} M_{ij}$:
la matrice est stochastique à droite;
\item pour chaque indice de colonne $j$,
principalement de prouver que si $\mathsf{N}$ est une puissance de 2,
le code de Gray équilibré engendré par l'extension est toujours totalement équilibré et
que $S_{\mathsf{N}}$ est la séquence de transition d'un code de Gray de $\mathsf{N}$ bits
-si $S_{\mathsf{N}-2}$ l'est aussi..
+si $S_{\mathsf{N}-2}$ l'est aussi.
Cependant les auteurs ne prouvent pas que leur approche fournit systématiquement
un code de Gray (totalement) équilibré.
Cette section montre que ceci est vrai en rappelant tout d'abord
La chaîne de Markov associée converge vers la distribution uniforme et
\[
-\forall \varepsilon >0,\, t_{\rm mix}(\varepsilon) \le 32 {\mathsf{N}}^2+ 16{\mathsf{N}}\ln ({\mathsf{N}}+1) = O(N^2).
+\forall \varepsilon >0,\, t_{\rm mix}(\varepsilon) \le
+x
+\leq \lceil\log_2(\varepsilon^{-1})
+(32 {\mathsf{N}}^2+ 16{\mathsf{N}}\ln ({\mathsf{N}}+1))
\]
\end{restatable}
}
\Return{$\textit{nbit}$}\;
%\end{scriptsize}
-\caption{Pseudo Code pour évaluer le temps d'arrêt}
+\caption{Pseudo-code pour évaluer le temps d'arrêt}
\label{algo:stop}
\end{algorithm}
définie par
$M = \dfrac{1}{2^n} \check{M}$.
Si $\textsc{gig}(f)$ est fortement connexe, alors
- la sortie du générateur de nombres pseudo aléatoires détaillé par
+ la sortie du générateur de nombres pseudo-aléatoires détaillé par
l'algorithme~\ref{CI Algorithm:prng:g} suit une loi qui
tend vers la distribution uniforme si
et seulement si $M$ est une matrice doublement stochastique.
Cela s'explique assez simplement. Depuis une configuration initiale, le nombre
de configurations qu'on ne peut pas atteindre en une itération est de:
\begin{itemize}
-\item $2^n-n$ en unaire. Ceci représente un rapport de
- $\dfrac{2^n-n}{2^n} = 1-\dfrac{n}{2^n}$
+\item $2^n-n-1$ en unaire. Ceci représente un rapport de
+ $\dfrac{2^n-n-1}{2^n} = 1-\dfrac{n-1}{2^n}$
de toutes les configurations; plus $n$ est grand,
plus ce nombre est proche de $1$, et plus grand devient le nombre
d'itérations nécessaires pour atteinte une déviation faible;
