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

diff --git a/14Secrypt.tex b/14Secrypt.tex
index d4f76f4..9de2b0d 100644
--- a/14Secrypt.tex
+++ b/14Secrypt.tex
@@ -380,18 +380,151 @@ 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'objeftif 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'equation~(\ref{eq:asyn}) pour une 
+stratégie donnée.
+Tout d'abord, celles-ci peuvent être inerpré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 remaque 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èrementau 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 chaine 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 Markovs 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 irreductible 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 pourraît être réduite.