fin prng

[hdrcouchot.git] / 14Secrypt.tex

diff --git a/14Secrypt.tex b/14Secrypt.tex
index 597acbb2b0f592bf6d4a6adcec05ff0ed2edf5ff..f1fae6f7f3392a12b0598da4748163708d0769a3 100644 (file)
--- a/14Secrypt.tex
+++ b/14Secrypt.tex
@@ -380,43 +380,65 @@ vérifiant $\sum_{i=1}^nNT_n(i) = 2^n$.
 \section{Génération de codes de Gray équilibrés par induction}
 \label{sec:induction}
 
 \section{Génération de codes de Gray équilibrés par induction}
 \label{sec:induction}
 

-Dans  leur  article de  2004~\cite{ZanSup04},  Zanten  et  Suparta proposent  un
-algorithme inductif  pour générer  des codes  de Gray équilibrés  de $n$  bits à
-partir   de  codes   de  $n-2$   bits.   Cependant,   leur  méthode   n'est  pas
-constructive. En effet, elle effectue  des manipulations sur un partitionnement du
-code de Gray  initial de $n-2$ bits pour  obtenir un code de Gray  sur $n$ bits,
-mais le  résultat n'est pas  systématiquement équilibré. Il est  donc nécessaire
-d'évaluer les résultats obtenus à  partir de tous les partitionnements réalisables
-en suivant les  contraintes spécifiées.  Or, le nombre  de possibilités augmente
-exponentiellement (voir~\cite{Mons14} pour  l'évaluation détaillée), ce qui rend
-déraisonnable    tout   parcours    exhaustif.    Une    amélioration   proposée
-dans~\cite{Mons14} permet  de réduire le nombre  de partitionnements considérés,
-mais l'ordre  de grandeur  reste similaire. On  constate donc clairement  ici la
-nécessité de trouver  des algorithmes de génération de  codes de Gray équilibrés
-plus  efficaces.  Ce  problème  représente  une des  voies  que nous  souhaitons
-explorer dans la suite de nos travaux.
-
-Le   tableau~\ref{table:nbFunc}  donne  le   nombre  de   fonctions  différentes
-compatibles avec les codes de  Gray équilibrés générés par l'approche précédente
-selon le nombre  de bits. Il donne  donc la taille de la  classe des générateurs
-pouvant être produits.  Les  cas 7 et 8 ne sont que  des bornes minimales basées
-sur des sous-ensembles des partitionnements possibles.
+De nombreuses approches ont été developpées pour résoudre le problème de construire
+un code de Gray dans un $\mathsf{N}$-cube~\cite{Robinson:1981:CS,DBLP:journals/combinatorics/BhatS96,ZanSup04}, 
+selon les propriétés que doit vérifier ce code.
+
+Dans les travaux~\cite{Robinson:1981:CS}, les auteurs 
+proposent une approche inductive de construction de code de Gray équilibrés 
+(on passe du $\mathsf{N}-2$ à $\mathsf{N}$)
+pour peu que l'utilisateur fournisse une sous-séquence possédant certaines 
+propriétés à chaque pas inductif.
+Ce travail a été renforcé dans ~\cite{DBLP:journals/combinatorics/BhatS96}
+où les auteurs donnent une manière explicite de construire une telle sous-séquence.
+Enfin, les autheurs de~\cite{ZanSup04} présentent une extension de l'algorithme de
+\emph{Robinson-Cohn}. La présentation rigoureuse de cette extension leur permet 
+principalement de prouver que si $\mathsf{N}$ est une puissance de 2, 
+le code de Gray équilibré engendré par l'extension est toujours totalement équilibré et 
+que $S_{\mathsf{N}}$ est la séquence de transition d'un code de Gray de $\mathsf{N}$ bits 
+si  $S_{\mathsf{N}-2}$ l'est aussi.. 
+Cependant les auteurs ne prouvent pas que leur approche fournit systématiquement  
+un code de Gray (totalement) équilibré. 
+Cette section montre que ceci est vrai en rappelant tout d'abord
+l'extension de l'algorithme de \emph{Robinson-Cohn} pour un 
+code de Gray avec $\mathsf{N}-2$ bits.

 
 

-\begin{table}[ht]
-  \begin{center}
-    \begin{tabular}{|l|c|c|c|c|c|}
-      \hline
-      $n$              & 4 & 5 & 6    & 7      & 8      \\
-      \hline
-      nb. de fonctions & 1 & 2 & 1332 & $>$ 2300 & $>$ 4500 \\
-      \hline
-    \end{tabular}
-  \end{center}
-\caption{Nombre de codes de Gray équilibrés selon le nombre de bits.}\label{table:nbFunc}
-\end{table}
+\begin{enumerate}
+\item \label{item:nondet}Soit $l$ un entier positif pair. Trouver des sous-sequences 
+$u_1, u_2, \dots , u_{l-2}, v$ (possiblement vides) de $S_{\mathsf{N}-2}$ 
+telles que $S_{\mathsf{N}-2}$ est la concaténation de  
+$$
+s_{i_1}, u_0, s_{i_2}, u_1, s_{i_3}, u_2, \dots , s_{i_l-1}, u_{l-2}, s_{i_l}, v
+$$
+où $i_1 = 1$, $i_2 = 2$, et $u_0 = \emptyset$ (la séquence vide).
+\item\label{item:u'} Remplacer dans $S_{\mathsf{N}-2}$ les sequences $u_0, u_1, u_2, \ldots, u_{l-2}$ 
+  par 
+  $\mathsf{N} - 1,  u'(u_1,\mathsf{N} - 1, \mathsf{N}) , u'(u_2,\mathsf{N}, \mathsf{N} - 1), u'(u_3,\mathsf{N} - 1,\mathsf{N}), \dots, u'(u_{l-2},\mathsf{N}, \mathsf{N} - 1)$
+  respectivement, où $u'(u,x,y)$ est la séquence $u,x,u^R,y,u$ telle que 
+  $u^R$ est $u$, mais dans l'ordre inverse. La séquence obtenue est ensuite notée $U$.
+\item\label{item:VW} Contruire les séquences $V=v^R,\mathsf{N},v$, $W=\mathsf{N}-1,S_{\mathsf{N}-2},\mathsf{N}$. Soit  alors $W'$ définie commé étant égale à $W$ sauf pour les 
+deux premiers éléments qui ont été intervertis.
+\item La séquence de transition  $S_{\mathsf{N}}$ est la concatenation $U^R, V, W'$.
+\end{enumerate} 
+
+L'étape~(\ref{item:nondet}) n'est pas constructive: il n'est pas précisé
+comment sélectionner des sous-séquences qui assurent que le code obtenu est équilibré.
+La théoreme suivante montre que c'est possible et sa preuve explique comment le faire. 
+
+
+\begin{theorem}\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} 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}

 
 

+La preuve de ce théorème est donnée en annexes~\ref{anx:generateur}.

 
 

-Ces fonctions étant générée, on s'intéresse à étudier à quelle vitesse 
+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.
 C'est l'objectif de la section suivante. 
 
 un générateur les embarquant converge vers la distribution uniforme.
 C'est l'objectif de la section suivante. 
 


@@ -541,19 +563,22 @@ 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}
 
 \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{theorem} \label{prop:stop}
 \begin{theorem} \label{prop:stop}

-If $\ov{h}$ is bijective et telle que if for every $X\in \Bool^{\mathsf{N}}$,
+Si $\ov{h}$ is 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}
 
 $\ov{h}(\ov{h}(X))\neq X$, alors
 $E[\ts]\leq 8{\mathsf{N}}^2+ 4{\mathsf{N}}\ln ({\mathsf{N}}+1)$. 
 \end{theorem}
 

-Sans entrer dans les détails de la preuve, on remarque tout d'abord 
-que le calcul 
-de cette borne n'intègre pas le fait qu'on préfère enlever des 
-chemins hamiltoniens équilibrés. 
-En intégrant cette contrainte, la borne supérieure pourrait être réduite.
-
-On remarque ensuite que la chaîne de Markov proposée ne suit pas exactement
+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}$.
 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}$.


@@ -563,6 +588,67 @@ a été introduite pour simplifier le calcul de la borne sup
 du temps d'arrêt.   
 
 
 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 
+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 effet, le temps de mixage est en $\Theta(N\ln N)$ lors d'une
+marche aléatoire classique paresseuse dans le $\mathsf{N}$-cube.
+On peut ainsi conjecturer que cet ordre de grandeur reste le même 
+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 algorithm~\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 fonctionss ont été générées comme dans 
+ce chapitre. Pour chacune d'elle, le calcul d'une approximation de $E[\ts]$
+est exécuté 10000 fois avec une graine aléatoire.La Figure~\ref{fig:stopping:moy}
+résume ces resultats. Dans celle-ci, un cercle  représente une approximation de 
+$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  cosntate que l'approximation de $E[\ts]$ est largement inférieure 
+à la borne quadratique donnée au thérème~\ref{prop:stop} et que la conjecture 
+donnée au paragraphe précédent est sensée.
+
+
+\begin{algorithm}[ht]
+%\begin{scriptsize}
+\KwIn{a function $f$, an initial configuration $x^0$ ($\mathsf{N}$ bits)}
+\KwOut{a number of iterations $\textit{nbit}$}
+
+$\textit{nbit} \leftarrow 0$\;
+$x\leftarrow x^0$\;
+$\textit{fair}\leftarrow\emptyset$\;
+\While{$\left\vert{\textit{fair}}\right\vert < \mathsf{N} $}
+{
+        $ s \leftarrow \textit{Random}(\mathsf{N})$ \;
+        $\textit{image} \leftarrow f(x) $\;
+        \If{$\textit{Random}(1) \neq 0$ and $x[s] \neq \textit{image}[s]$}{
+            $\textit{fair} \leftarrow \textit{fair} \cup \{s\}$\;
+            $x[s] \leftarrow \textit{image}[s]$\;
+          }
+        $\textit{nbit} \leftarrow \textit{nbit}+1$\;
+}
+\Return{$\textit{nbit}$}\;
+%\end{scriptsize}
+\caption{Pseudo Code of stoping time calculus }
+\label{algo:stop}
+\end{algorithm}
+
+
+\begin{figure}
+\centering
+\includegraphics[width=0.49\textwidth]{images/complexityET}
+\caption{Average Stopping Time Approximation}\label{fig:stopping:moy}
+\end{figure}
+
+

 
 
 \section{Et les itérations généralisées?}
 
 
 \section{Et les itérations généralisées?}