\section{Lien avec les codes de Gray cycliques (totalement) équilibrés}
\label{sub:gray}
-La borne inférieure du nombre de codes de Gray ($\left(\frac{n*\log2}{e \log
+Un minorant du nombre de codes de Gray ($\left(\frac{n*\log2}{e \log
\log n}\times(1 - o(1))\right)^{2^n}$), donnée dans~\cite{Feder2009NTB},
indique une explosion combinatoire pour notre recherche. Afin de contourner
cette difficulté, nous nous restreignons aux codes induisant un graphe
La théorème suivante montre que c'est possible et sa preuve,
donnée en annexes~\ref{anx:generateur}, explique comment le faire.
-
-\begin{theorem}\label{prop:balanced}
+\begin{restatable}[Existence d'un code de Gray équilibré]{theorem}{theograyequilibre}
+\label{prop:balanced}
Soit $\mathsf{N}$ dans $\Nats^*$, et $a_{\mathsf{N}}$ défini par
$a_{\mathsf{N}}= 2 \left\lfloor \dfrac{2^{\mathsf{N}}}{2\mathsf{N}} \right\rfloor$.
il existe une séquence $l$ dans l'étape~(\ref{item:nondet}) de l'extension
-de l'algorithme de \emph{Robinson-Cohn} telle que
+de l'algorithme de \emph{Robinson-Cohn} extension telle que
le nombres de transitions $\textit{TC}_{\mathsf{N}}(i)$
sont tous $a_{\mathsf{N}}$ ou $a_{\mathsf{N}}+2$
pour chaque $i$, $1 \le i \le \mathsf{N}$.
-\end{theorem}
+\end{restatable}
Ces fonctions étant générées, on s'intéresse à étudier à quelle vitesse
un générateur les embarquant converge vers la distribution uniforme.
+
+
\begin{xpl}
On considère par exemple le graphe $\textsc{giu}(f)$ donné à la
\textsc{Figure~\ref{fig:iteration:f*}.} et la fonction de
$$
p(e) \left\{
\begin{array}{ll}
-= \frac{2}{3} \textrm{ si $e=(v,v)$ avec $v \in \Bool^3$,}\\
+= \frac{1}{2} + \frac{1}{6} \textrm{ si $e=(v,v)$ avec $v \in \Bool^3$,}\\
= \frac{1}{6} \textrm{ sinon.}
\end{array}
\right.
\]
\end{xpl}
+On remarque que dans cette marche on reste sur place avec une probabilité
+
+
Soit $(X_t)_{t\in \mathbb{N}}$ une suite de variables aléatoires de
$\Bool^{\mathsf{N}}$.
-une variable aléatoire $\tau$ dans $\mathbb{N}$ est un
+Une variable aléatoire $\tau$ dans $\mathbb{N}$ est un
\emph{temps d'arrêt} pour la suite
$(X_i)$ si pour chaque $t$ il existe $B_t\subseteq
(\Bool^{\mathsf{N}})^{t+1}$ tel que
$\ov{h}(\ov{h}(X))\neq X$.
-\begin{theorem} \label{prop:stop}
+\begin{restatable}[Majoration du temps d'arrêt]{theorem}{theostopmajorant}
+\label{prop:stop}
Si $\ov{h}$ est bijective et anti involutive
$\ov{h}(\ov{h}(X))\neq X$, alors
$E[\ts]\leq 8{\mathsf{N}}^2+ 4{\mathsf{N}}\ln ({\mathsf{N}}+1)$.
-\end{theorem}
+\end{restatable}
Les détails de la preuve sont donnés en annexes~\ref{anx:generateur}.
On remarque tout d'abord que la chaîne de Markov proposée ne suit pas exactement
est fixée à $\frac{1}{2}+\frac{1}{2n}$.
Dans l'algorithme initial, celle-ci est de $\frac{1}{n}$.
Cette version, qui reste davantage sur place que l'algorithme original,
-a été introduite pour simplifier le calcul de la borne sup
+a été introduite pour simplifier le calcul d'un majorant
du temps d'arrêt.
Sans entrer dans les détails de la preuve, on remarque aussi
-que le calcul de cette borne impose uniquement que
+que le calcul de ce majorant impose uniquement que
pour chaque n{\oe}ud du $\mathsf{N}$-cube
un arc entrant et un arc sortant sont supprimés.
Le fait qu'on enlève un cycle hamiltonien et que ce dernier
soit équilibré n'est pas pris en compte.
-En intégrant cette contrainte, la borne supérieure pourrait être réduite.
+En intégrant cette contrainte, ce majorant pourrait être réduite.
En effet, le temps de mixage est en $\Theta(N\ln N)$ lors d'une
marche aléatoire classique paresseuse dans le $\mathsf{N}$-cube.
$E[\ts]$ pour un $\mathsf{N}$ donné tandis que la courbe est une représentation de
la fonction $x \mapsto 2x\ln(2x+8)$.
On constate que l'approximation de $E[\ts]$ est largement inférieure
-à la borne quadratique donnée au théorème~\ref{prop:stop} et que la conjecture
+à le majorant quadratique donné au théorème~\ref{prop:stop} et que la conjecture
donnée au paragraphe précédent est sensée.
existantes.
Dans le cas des itérations unaires,
l'algorithme qui en découle a un temps de mélange qui a
-une borne sup quadratique de convergence vers la distribution uniforme.
+un majorant quadratique de convergence vers la distribution uniforme.
Pratiquement, ce temps de mélange se rapproche de $N\ln N$.
Les expérimentations au travers de la batterie de test de NIST ont montré
que toutes les propriétés statistiques sont obtenues pour
