ajout d'intro et de conclusion

[hdrcouchot.git] / 14Secrypt.tex

diff --git a/14Secrypt.tex b/14Secrypt.tex
index 69fb6d8462374bf50a8508cda61e04d087b549c5..858a8e52ac44cb9620f4fb573df55e8991ee7003 100644 (file)
--- 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
 $\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}
 vérifiant $\sum_{i=1}^n\textit{TC}_n(i) = 2^n$.
 
 \begin{xpl}


@@ -477,6 +477,8 @@ particulièrement au chapitre sur les temps d'arrêt.
 
 
 
 
 
 

+
+

 \begin{xpl}
 On considère par exemple le graphe $\textsc{giu}(f)$ donné à la 
 \textsc{Figure~\ref{fig:iteration:f*}.} et la fonction de 
 \begin{xpl}
 On considère par exemple le graphe $\textsc{giu}(f)$ donné à la 
 \textsc{Figure~\ref{fig:iteration:f*}.} et la fonction de 


@@ -484,7 +486,7 @@ probabilités $p$ définie sur l'ensemble des arcs comme suit:
 $$
 p(e) \left\{
 \begin{array}{ll}
 $$
 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.  
 = \frac{1}{6} \textrm{ sinon.}
 \end{array}
 \right.  


@@ -507,7 +509,17 @@ P=\dfrac{1}{6} \left(
 \]
 \end{xpl}
 
 \]
 \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 
 
 
 Tout d'abord, soit $\pi$ et $\mu$ deux distributions sur 


@@ -531,72 +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\}.$$
 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
 
 
 Sans entrer dans les détails de la preuve, on remarque aussi


@@ -614,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
 
 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 
 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 


@@ -1084,7 +1056,7 @@ Complexité linaire& 0.005 (0.98)& 0.534 (0.99)& 0.085 (0.97)& 0.996 (1.0)\\ \hl
 
 
 \section{Conclusion}
 
 
 \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. 
 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.