X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/hdrcouchot.git/blobdiff_plain/020defdbb2ac938563eba1071c78520973093e4b..46fc71ad146f83c82660e358a1a1bc2ccc0f00e6:/14Secrypt.tex?ds=inline

diff --git a/14Secrypt.tex b/14Secrypt.tex
index d4f76f4..e160bc3 100644
--- a/14Secrypt.tex
+++ b/14Secrypt.tex
@@ -23,7 +23,7 @@ results to provide a generation of DSSC matrices with small mixing times.
 
 \section{Programmation logique par contraintes sur des domaines finis}
 Tout d'abord, soit ${\mathsf{N}}$ le nombre d'Ã©lÃ©ments. 
-Pour Ã©viter d'avoir Ã  gÃ©rÃ©r des fractions, on peut considÃ©rer que 
+Pour Ã©viter d'avoir Ã  gÃ©rer des fractions, on peut considÃ©rer que 
 les matrices (d'incidence) Ã  gÃ©nÃ©rer ont des lignes et des colonnes dont les 
 sommes valent ${\mathsf{N}}$ Ã  chaque fois.  
 On cherche ainsi toutes les matrices $M$ de taille  $2^{\mathsf{N}}\times 2^{\mathsf{N}}$ telles que 
@@ -37,16 +37,16 @@ configuration $i$ est infÃ©rieur Ã  ${\mathsf{N}}$;
 
 \item pour $j \neq i$,  $0 \le M_{ij} \le 1$: on construit l'arc de $i$ Ã  $j$ 
 si et seulement si $M_{ij}$ vaut 1 (et 0 sinon)
-\item pour chque indice de ligne  $i$, $1 \le i\le 2^{\mathsf{N}}$, ${\mathsf{N}} = \sum_{1 \le j\le 2^{\mathsf{N}}} M_{ij}$: 
+\item pour chaque indice de ligne  $i$, $1 \le i\le 2^{\mathsf{N}}$, ${\mathsf{N}} = \sum_{1 \le j\le 2^{\mathsf{N}}} M_{ij}$: 
 la matrice est stochastique Ã  droite; 
-\item pour chque indice de colonne $j$, 
+\item pour chaque indice de colonne $j$, 
   $1 \le j\le 2^{\mathsf{N}}$, ${\mathsf{N}} = \sum_{1 \le i\le 2^{\mathsf{N}}} M_{ij}$: 
   la matrice est stochastique Ã  gauche;
 \item Toutes les Ã©lÃ©ments de la somme $\sum_{1\le k\le 2^{\mathsf{N}}}M^k$ sont strictement positif, \textit{i.e.}, le graphe $\textsc{giu}(f)$ est fortement connexe;
 \end{enumerate}
 Ce problÃ¨me s'exprime sur des domaines finis entiers avec des opÃ©rateurs  
-arithmÃ©tiques simples (sommes et poduits). il pourrait thÃ©oriquement Ãªtre 
-traitÃ© par desdÃ©marches de programation logique par contrainte
+arithmÃ©tiques simples (sommes et produits). il pourrait thÃ©oriquement Ãªtre 
+traitÃ© par des dÃ©marches de programmation logique par contrainte
 sur des domaines finis (comme en PROLOG).
 L'algorithme donnÃ© en Figure~\ref{fig:prolog}
 est en effet le c{\oe}ur du programme PROLOG 
@@ -86,7 +86,7 @@ bistoc(X):-
 \caption{Code PROLOG permettant de trouver toutes les matrices DSSC pour $n=2$}\label{fig:prolog}
 \end{figure}
 
-Enfin, on dÃ©finit la relation $\mathcal{R}$, qui est Ã©tablie pourles deux 
+Enfin, on dÃ©finit la relation $\mathcal{R}$, qui est Ã©tablie pour les deux 
 fonctions  $f$ et $g$ si leur graphes 
 respectifs  $\textsf{giu}(f)$ et $\textsf{giu}(g)$ 
 sont isomorphes.
@@ -105,10 +105,10 @@ Cependant, l'approche ne permet pas d'engendrer toutes les solutions
 pour $n=4$.
 Cette approche, basÃ©e sur une dÃ©marche de type \emph{gÃ©nÃ©rer, tester} ne peut 
 pas Ãªtre retenue pour $n$ de grande taille, mÃªme 
-en s'appuyant sur l'Ã©fficience de l'algorithme de backtrack natif de PROLOG.
+en s'appuyant sur l'efficience de l'algorithme de backtrack natif de PROLOG.
 
 Cependant, pour des valeurs de $n$ petites, nous avons 
-comparÃ© les fonctions non Ã©quivalantes selon leur proportion
+comparÃ© les fonctions non Ã©quivalentes selon leur proportion
 Ã  engendrer des temps de mÃ©lange petits (cf. Ã©quation~\ref{eq:mt:ex}).
 
 
@@ -380,18 +380,193 @@ pouvant Ãªtre produits.  Les  cas 7 et 8 ne sont que  des bornes minimales basÃ©
 sur des sous-ensembles des partitionnements possibles.
 
 \begin{table}[ht]
-  %\begin{center}
+  \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 \\
+      nb. de fonctions & 1 & 2 & 1332 & $>$ 2300 & $>$ 4500 \\
       \hline
     \end{tabular}
-  %\end{center}
-\caption{Nombre de gÃ©nÃ©rateurs selon le nombre de bits.}\label{table:nbFunc}
+  \end{center}
+\caption{Nombre de codes de Gray Ã©quilibrÃ©s selon le nombre de bits.}\label{table:nbFunc}
 \end{table}
 
 
+Ces fonctions Ã©tant gÃ©nÃ©rÃ©e, 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. 
+
 \section{Quantifier l'Ã©cart par rapport Ã  la distribution uniforme} 
-%15 Rairo
\ No newline at end of file
+On considÃ¨re ici une fonction construite comme Ã  la section prÃ©cÃ©dente.
+On s'intÃ©resse ici Ã  Ã©tudier de maniÃ¨re thÃ©orique les 
+itÃ©rations dÃ©finies Ã  l'Ã©quation~(\ref{eq:asyn}) pour une 
+stratÃ©gie donnÃ©e.
+Tout d'abord, celles-ci peuvent Ãªtre interprÃ©tÃ©es comme une marche le long d'un 
+graphe d'itÃ©rations $\textsc{giu}(f)$ tel que le choix de tel ou tel arc est donnÃ© par la 
+stratÃ©gie.
+On remarque que ce graphe d'itÃ©ration est toujours un sous graphe 
+du   ${\mathsf{N}}$-cube augmentÃ© des 
+boucles sur chaque sommet, \textit{i.e.}, les arcs
+$(v,v)$ pour chaque $v \in \Bool^{\mathsf{N}}$. 
+Ainsi, le travail ci dessous rÃ©pond Ã  la question de 
+dÃ©finir la longueur du chemin minimum dans ce graphe pour 
+obtenir une distribution uniforme.
+Ceci se base sur la thÃ©orie des chaÃ®nes de Markov.
+Pour une rÃ©fÃ©rence 
+gÃ©nÃ©rale Ã  ce sujet on pourra se rÃ©fÃ©rer 
+au livre~\cite{LevinPeresWilmer2006},
+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 
+probabilitÃ©s $p$ dÃ©finie sur l'ensemble des arcs comme suit:
+$$
+p(e) \left\{
+\begin{array}{ll}
+= \frac{2}{3} \textrm{ si $e=(v,v)$ avec $v \in \Bool^3$,}\\
+= \frac{1}{6} \textrm{ sinon.}
+\end{array}
+\right.  
+$$
+La matrice $P$ de la chaÃ®ne de Markov associÃ©e Ã   $f^*$ 
+est  
+\[
+P=\dfrac{1}{6} \left(
+\begin{array}{llllllll}
+4&1&1&0&0&0&0&0 \\
+1&4&0&0&0&1&0&0 \\
+0&0&4&1&0&0&1&0 \\
+0&1&1&4&0&0&0&0 \\
+1&0&0&0&4&0&1&0 \\
+0&0&0&0&1&4&0&1 \\
+0&0&0&0&1&0&4&1 \\
+0&0&0&1&0&1&0&4 
+\end{array}
+\right)
+\]
+\end{xpl}
+
+
+
+
+Tout d'abord, soit $\pi$ et $\mu$ deux distributions sur 
+$\Bool^{\mathsf{N}}$. 
+La distance de \og totale variation\fg{} entre  $\pi$ et $\mu$ 
+est notÃ©e  $\tv{\pi-\mu}$ et est dÃ©finie par 
+$$\tv{\pi-\mu}=\max_{A\subset \Bool^{\mathsf{N}}} |\pi(A)-\mu(A)|.$$ 
+On sait que 
+$$\tv{\pi-\mu}=\frac{1}{2}\sum_{X\in\Bool^{\mathsf{N}}}|\pi(X)-\mu(X)|.$$
+De plus, si 
+$\nu$ est une distribution on $\Bool^{\mathsf{N}}$, on a 
+$$\tv{\pi-\mu}\leq \tv{\pi-\nu}+\tv{\nu-\mu}.$$
+
+Soit $P$ une matrice d'une chaÃ®ne de Markov sur $\Bool^{\mathsf{N}}$. 
+$P(X,\cdot)$ est la distribution induite par la  $X^{\textrm{Ã¨me}}$ colonne
+de  $P$. 
+Si la chaÃ®ne de  Markov induite par 
+$P$ a une  distribution stationnaire $\pi$, on dÃ©finit alors 
+$$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}.
+
+
+\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}
+
+\begin{theorem} \label{prop:stop}
+If $\ov{h}$ is bijective et telle que if for every $X\in \Bool^{\mathsf{N}}$,
+$\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 que le calcul 
+de cette borne ne tient pas en compte 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.
+
+\section{Et les itÃ©rations gÃ©nÃ©ralisÃ©es?}
+Le chaptire prÃ©cÃ©dent a prÃ©sentÃ© un algorithme de 
+PRNG construit Ã  partir d'itÃ©rations unaires. 
+On pourrait penser que cet algorithme est peu efficace puisqu'il 
+dispose d'une fonction $f$ de $\Bool^n$ dans lui mÃªme mais il ne modifie Ã  
+chaque itÃ©ration qu'un seul Ã©lÃ©ment de $[n]$.
+On pourrait penser Ã  un algorithme basÃ© sur les itÃ©rations gÃ©nÃ©ralisÃ©es, 
+c'est-Ã -dire qui modifierait une partie des Ã©lÃ©ments de $[n]$ Ã  chaque 
+itÃ©ration.
+C'est l'algorithme~\ref{CI Algorithm:prng:g}.
+
+\begin{algorithm}[h]
+%\begin{scriptsize}
+\KwIn{une fonction $f$, un nombre d'itÃ©rations $b$, 
+une configuration initiale $x^0$ ($n$ bits)}
+\KwOut{une configuration $x$ ($n$ bits)}
+$x\leftarrow x^0$\;
+$k\leftarrow b $\;
+\For{$i=1,\dots,k$}
+{
+$s\leftarrow{\textit{Set}(\textit{Random}(2^n))}$\;
+$x\leftarrow{F_{f_g}(s,x)}$\;
+}
+return $x$\;
+%\end{scriptsize}
+\caption{PRNG basÃ© sur les itÃ©rations gÃ©nÃ©ralisÃ©es.}
+\label{CI Algorithm:prng:g}
+\end{algorithm}
+
+Par rapport Ã  l'algorithme~\ref{CI Algorithm} seule 
+la ligne $s\leftarrow{\textit{Set}(\textit{Random}(2^n))}$ est diffÃ©rente.
+Dans celle-ci la fonction  $\textit{Set}   :    \{1,\ldots,2^n\}   \rightarrow
+\mathcal{P}(\{1,\ldots   n\})$   retourne  l'ensemble   dont   la   fonction
+caractÃ©ristique  serait  reprÃ©sentÃ©e par  le  nombre  donnÃ©  en argument.
+Par exemple, pour $n=3$, l'ensemble $\textit{Set}(6)$ vaudraitt $\{3,2\}$.
+On remarque aussi que l'argument de la fonction  $\textit{Random}$
+passe de $n$ Ã  $2^n$.
+
+Dans ce qui suit, on va Ã©tudier cet algorithme comparativement Ã  
+l'algorithme~\ref{CI Algorithm}.
+
