X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/hdrcouchot.git/blobdiff_plain/01003216d61845263ad195f3ecf7334817d60407..0d1c31c9837325e2dad26554c2cde3a457455158:/14Secrypt.tex?ds=sidebyside

diff --git a/14Secrypt.tex b/14Secrypt.tex
index e36720b..858a8e5 100644
--- a/14Secrypt.tex
+++ b/14Secrypt.tex
@@ -371,7 +371,7 @@ plus,  comme  dans tout  code  de  Gray  cyclique, $\textit{TC}_n(i)$  est  pair
 $\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}
@@ -509,10 +509,17 @@ P=\dfrac{1}{6} \left(
 \]
 \end{xpl}
 
-On remarque que dans cette marche on reste sur place avec une probabilitÃ©
-
-
+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 
@@ -536,73 +543,32 @@ $$d(t)=\max_{X\in\Bool^{\mathsf{N}}}\tv{P^t(X,\cdot)-\pi}$$
 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}.
+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}.
 
 
-\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}
-
-
-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{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)$. 
+\[
+\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
@@ -620,7 +586,7 @@ dans le contexte du $\mathsf{N}$-cube privÃ© d'un chemin hamiltonien.
 
 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 
@@ -1090,7 +1056,7 @@ ComplexitÃ© linaire& 0.005 (0.98)& 0.534 (0.99)& 0.085 (0.97)& 0.996 (1.0)\\ \hl
 
 
 \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. 
