X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/hdrcouchot.git/blobdiff_plain/01003216d61845263ad195f3ecf7334817d60407..d4e1bfa4290a182013268daf63d78c1f4fce5b55:/14Secrypt.tex 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.