$\forall i\in\{1,...,n\}$, alors les systèmes ayant un nombre d'éléments
différent de $2^k$, ne peuvent avoir que des codes de Gray équilibrés avec
$\textit{TC}_n(i)=\lfloor\frac{2^n}{n}\rfloor$ ou
-$\textit{NT}_n(i)=\lceil\frac{2^n}{n}\rceil, \forall i\in\{1,...,n\}$ et
+$\textit{TC}_n(i)=\lceil\frac{2^n}{n}\rceil, \forall i\in\{1,...,n\}$ et
vérifiant $\sum_{i=1}^n\textit{TC}_n(i) = 2^n$.
\begin{xpl}
+
+
\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é égale
+à $\frac{1}{2}+\frac{1}{2\mathsf{N}}$ et l'on passe d'un sommet à son voisin
+lorsque c'est possible avec une probabilité $\frac{1}{2\mathsf{N}}$.
+Les probabilités usuelles que l'on appliquerait aux transitions de
+l'algorithme~\ref{CI Algorithm} serait quant à elles uniformément égales
+à $\frac{1}{\mathsf{N}}$.
+Cette manière paresseuse d'itérer (puisqu'on reste plus souvent sur place) n'est donc pas équivalente à celle issue de l'algorithme.
+Cependant, l'étude théorique de référence~\cite{LevinPeresWilmer2006}
+considère cette marche comme cadre. S'inspirant de
+celle-ci, le travail suivant se replace donc dans ce cadre théorique.
Tout d'abord, soit $\pi$ et $\mu$ deux distributions sur
et
$$t_{\rm mix}(\varepsilon)=\min\{t \mid d(t)\leq \varepsilon\}.$$
-
-Un résultat classique est
-
-$$t_{\rm mix}(\varepsilon)\leq \lceil\log_2(\varepsilon^{-1})\rceil t_{\rm mix}(\frac{1}{4})$$
-
-
-
-
-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
-\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
-$\{\tau=t\}=\{(X_0,X_1,\ldots,X_t)\in B_t\}$.
-En d'autres termes, l'événement $\{\tau = t \}$ dépend uniquement des valeurs
-de
-$(X_0,X_1,\ldots,X_t)$, et non de celles de $X_k$ pour $k > t$.
-
-Soit $(X_t)_{t\in \mathbb{N}}$ une chaîne de Markov et
-$f(X_{t-1},Z_t)$ une représentation fonctionnelle de celle-ci.
-Un \emph{temps d'arrêt aléatoire} pour la chaîne de
-Markov est un temps d'arrêt pour
-$(Z_t)_{t\in\mathbb{N}}$.
-Si la chaîne de Markov est irréductible et a $\pi$
-comme distribution stationnaire, alors un
-\emph{temps stationnaire} $\tau$ est temps d'arrêt aléatoire
-(qui peut dépendre de la configuration initiale $X$),
-tel que la distribution de $X_\tau$ est $\pi$:
-$$\P_X(X_\tau=Y)=\pi(Y).$$
-
-
-Un temps d'arrêt $\tau$ est qualifié de \emph{fort} si $X_{\tau}$
-est indépendant de $\tau$. On a les deux théorèmes suivants, dont les
-démonstrations sont données en annexes~\ref{anx:generateur}.
-
-
-\begin{theorem}
-Si $\tau$ est un temps d'arrêt fort, alors $d(t)\leq \max_{X\in\Bool^{\mathsf{N}}}
-\P_X(\tau > t)$.
-\end{theorem}
+Intuitivement, $t_{\rm mix}(\varepsilon)$ est le nombre d'itérations nécessaire
+pour être proche de la distribution stationnaire à $\varepsilon$ prêt,
+peut importe la configuration de départ. On a le théorème suivant démontré en annexes~\ref{anx:generateur}.
-Soit alors $\ov{h} : \Bool^{\mathsf{N}} \rightarrow \Bool^{\mathsf{N}}$ la fonction
-telle que pour $X \in \Bool^{\mathsf{N}} $,
-$(X,\ov{h}(X)) \in E$ et $X\oplus\ov{h}(X)=0^{{\mathsf{N}}-h(X)}10^{h(X)-1}$.
-La fonction $\ov{h}$ est dite {\it anti-involutive} si pour tout $X\in \Bool^{\mathsf{N}}$,
-$\ov{h}(\ov{h}(X))\neq X$.
+\begin{restatable}[Temps de mixage sans chemin hamiltonien]{theorem}{theotpsmix}
+\label{theo:tmps:mix}
+On considère un $\mathsf{N}$-cube dans lequel un chemin hamiltonien a été supprimé et la fonction de
+probabilités $p$ définie sur l'ensemble des arcs comme suit:
+\[
+p(e) \left\{
+\begin{array}{ll}
+= \frac{1}{2} + \frac{1}{2\mathsf{N}} \textrm{ si $e=(v,v)$ avec $v \in \Bool^{\mathsf{N}}$,}\\
+= \frac{1}{2\mathsf{N}} \textrm{ sinon.}
+\end{array}
+\right.
+\]
+La chaîne de Markov associée converge vers la distribution uniforme et
-\begin{theorem} \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}
+\[
+\forall \varepsilon >0,\, t_{\rm mix}(\varepsilon) \le 32 {\mathsf{N}}^2+ 16{\mathsf{N}}\ln ({\mathsf{N}}+1) = O(N^2).
+\]
+\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
-l'algorithme~\ref{CI Algorithm}. En effet dans la section présente,
-la probabilité de rester dans une configuration donnée
-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 d'un majorant
-du temps d'arrêt.
Sans entrer dans les détails de la preuve, on remarque aussi
On peut évaluer ceci pratiquement: pour une fonction
$f: \Bool^{\mathsf{N}} \rightarrow \Bool^{\mathsf{N}}$ et une graine initiale
-$x^0$, le code donné à l'algorithme ~\ref{algo:stop} retourne le
+$x^0$, le code donné à l'algorithme~\ref{algo:stop} retourne le
nombre d'itérations suffisant tel que tous les éléments $\ell\in \llbracket 1,{\mathsf{N}} \rrbracket$ sont équitables. Il permet de déduire une approximation de $E[\ts]$
en l'instanciant un grand nombre de fois: pour chaque nombre $\mathsf{N}$,
$ 3 \le \mathsf{N} \le 16$, 10 fonctions ont été générées comme dans
\section{Conclusion}
-Ce chaptitre a montré comment construire un PRNG chaotique, notamment à partir
+Ce chapitre a montré comment construire un PRNG chaotique, notamment à partir
de codes de Gray équilibrés. Une méthode complètement automatique de
construction de ce type de codes a été présentée étendant les méthodes
existantes.
