From 1042ddb8d08dc129da9358b73e723fc5014fb2c8 Mon Sep 17 00:00:00 2001 From: =?utf8?q?Jean-Fran=C3=A7ois=20Couchot?= Date: Wed, 22 Jul 2015 12:45:26 +0200 Subject: [PATCH] stopping time jet 1 --- 11FCT.tex | 4 +- 14Secrypt.tex | 143 ++++++++++++++- 15RairoGen.tex | 2 +- annexePreuveStopping.tex | 381 +++++++++++++++++++++++++++++++++++++++ main.tex | 15 +- modelchecking.tex | 4 +- 6 files changed, 537 insertions(+), 12 deletions(-) create mode 100644 annexePreuveStopping.tex diff --git a/11FCT.tex b/11FCT.tex index 8ab511e..ffa5775 100644 --- a/11FCT.tex +++ b/11FCT.tex @@ -73,7 +73,7 @@ Alors, $\textsc{giu}(f)$ est fortement connexe. La preuve de ce théorème est donnée en annexe~\ref{anx:sccg}. Illustrons ce théorème par un exemple. On considère par le graphe d'interactions -$\Gamma(f)$ donné en figure~\ref{fig:G}. +$\Gamma(f)$ donné en figure~\ref{fig:Adrien:G}. Il vérifie le théorème~\ref{th:Adrien}: toutes les fonctions $f$ possédant un tel graphe d'interactions ont un graphe d'itérations $\textsc{giu}(f)$ fortement connexe. @@ -88,6 +88,6 @@ Deux fonctions sont equivalentes si leurs \textsc{giu} sont isomorphes \begin{center} \includegraphics[scale=0.5]{images/Gi.pdf} \end{center} -\caption{Exemple de graphe d'interactions vérifiant le théorème~\ref{th:Adrien}} \label{fig:G} +\caption{Exemple de graphe d'interactions vérifiant le théorème~\ref{th:Adrien}} \label{fig:Adrien:G} \end{figure} 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. diff --git a/15RairoGen.tex b/15RairoGen.tex index 63eb23b..010beb9 100644 --- a/15RairoGen.tex +++ b/15RairoGen.tex @@ -700,7 +700,7 @@ Il n'est pas difficile de constater que $\textsc{giu}_{\{1\}}(f)$ est $\textsc{g \end{center} \caption{Graphes d'iterations $\textsc{giu}_{\mathcal{P}}(h)$ pour $h(x_1,x_2)=(\overline{x_1},x_1\overline{x_2}+\overline{x_1}x_2)$} - \label{fig:xplgraphIter} + %\label{fig:xplgraphIter} \end{figure} diff --git a/annexePreuveStopping.tex b/annexePreuveStopping.tex new file mode 100644 index 0000000..6bbd41f --- /dev/null +++ b/annexePreuveStopping.tex @@ -0,0 +1,381 @@ +\section{Quantifier l'écart par rapport à la distribution uniforme} +%15 Rairo + + + + + +Let thus be given such kind of map. +This article focuses on studying its iterations according to +the equation~(\ref{eq:asyn}) with a given strategy. +First of all, this can be interpreted as walking into its iteration graph +where the choice of the edge to follow is decided by the strategy. +Notice that the iteration graph is always a subgraph of +${\mathsf{N}}$-cube augmented with all the self-loop, \textit{i.e.}, all the +edges $(v,v)$ for any $v \in \Bool^{\mathsf{N}}$. +Next, if we add probabilities on the transition graph, iterations can be +interpreted as Markov chains. + +\begin{xpl} +Let us consider for instance +the graph $\Gamma(f)$ defined +in \textsc{Figure~\ref{fig:iteration:f*}.} and +the probability function $p$ defined on the set of edges as follows: +$$ +p(e) \left\{ +\begin{array}{ll} += \frac{2}{3} \textrm{ if $e=(v,v)$ with $v \in \Bool^3$,}\\ += \frac{1}{6} \textrm{ otherwise.} +\end{array} +\right. +$$ +The matrix $P$ of the Markov chain associated to the function $f^*$ and to its probability function $p$ is +\[ +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} + + +% % Let us first recall the \emph{Total Variation} distance $\tv{\pi-\mu}$, +% % which is defined for two distributions $\pi$ and $\mu$ on the same set +% % $\Bool^n$ by: +% % $$\tv{\pi-\mu}=\max_{A\subset \Bool^n} |\pi(A)-\mu(A)|.$$ +% % It is known that +% % $$\tv{\pi-\mu}=\frac{1}{2}\sum_{x\in\Bool^n}|\pi(x)-\mu(x)|.$$ + +% % Let then $M(x,\cdot)$ be the +% % distribution induced by the $x$-th row of $M$. If the Markov chain +% % induced by +% % $M$ has a stationary distribution $\pi$, then we define +% % $$d(t)=\max_{x\in\Bool^n}\tv{M^t(x,\cdot)-\pi}.$$ +% Intuitively $d(t)$ is the largest deviation between +% the distribution $\pi$ and $M^t(x,\cdot)$, which +% is the result of iterating $t$ times the function. +% Finally, let $\varepsilon$ be a positive number, the \emph{mixing time} +% with respect to $\varepsilon$ is given by +% $$t_{\rm mix}(\varepsilon)=\min\{t \mid d(t)\leq \varepsilon\}.$$ +% It defines the smallest iteration number +% that is sufficient to obtain a deviation lesser than $\varepsilon$. +% Notice that the upper and lower bounds of mixing times cannot +% directly be computed with eigenvalues formulae as expressed +% in~\cite[Chap. 12]{LevinPeresWilmer2006}. The authors of this latter work +% only consider reversible Markov matrices whereas we do no restrict our +% matrices to such a form. + + + + + + + +This section considers functions $f: \Bool^{\mathsf{N}} \rightarrow \Bool^{\mathsf{N}} $ +issued from an hypercube where an Hamiltonian path has been removed. +A specific random walk in this modified hypercube is first +introduced. We further detail +a theoretical study on the length of the path +which is sufficient to follow to get a uniform distribution. +Notice that for a general references on Markov chains +see~\cite{LevinPeresWilmer2006} +, and particularly Chapter~5 on stopping times. + + + + +First of all, let $\pi$, $\mu$ be two distributions on $\Bool^{\mathsf{N}}$. The total +variation distance between $\pi$ and $\mu$ is denoted $\tv{\pi-\mu}$ and is +defined by +$$\tv{\pi-\mu}=\max_{A\subset \Bool^{\mathsf{N}}} |\pi(A)-\mu(A)|.$$ It is known that +$$\tv{\pi-\mu}=\frac{1}{2}\sum_{X\in\Bool^{\mathsf{N}}}|\pi(X)-\mu(X)|.$$ Moreover, if +$\nu$ is a distribution on $\Bool^{\mathsf{N}}$, one has +$$\tv{\pi-\mu}\leq \tv{\pi-\nu}+\tv{\nu-\mu}$$ + +Let $P$ be the matrix of a Markov chain on $\Bool^{\mathsf{N}}$. $P(X,\cdot)$ is the +distribution induced by the $X$-th row of $P$. If the Markov chain induced by +$P$ has a stationary distribution $\pi$, then we define +$$d(t)=\max_{X\in\Bool^{\mathsf{N}}}\tv{P^t(X,\cdot)-\pi}.$$ + +and + +$$t_{\rm mix}(\varepsilon)=\min\{t \mid d(t)\leq \varepsilon\}.$$ +One can prove that + +$$t_{\rm mix}(\varepsilon)\leq \lceil\log_2(\varepsilon^{-1})\rceil t_{\rm mix}(\frac{1}{4})$$ + + + + +% It is known that $d(t+1)\leq d(t)$. \JFC{references ? Cela a-t-il +% un intérêt dans la preuve ensuite.} + + + +%and +% $$t_{\rm mix}(\varepsilon)=\min\{t \mid d(t)\leq \varepsilon\}.$$ +% One can prove that \JFc{Ou cela a-t-il été fait?} +% $$t_{\rm mix}(\varepsilon)\leq \lceil\log_2(\varepsilon^{-1})\rceil t_{\rm mix}(\frac{1}{4})$$ + + + +Let $(X_t)_{t\in \mathbb{N}}$ be a sequence of $\Bool^{\mathsf{N}}$ valued random +variables. A $\mathbb{N}$-valued random variable $\tau$ is a {\it stopping + time} for the sequence $(X_i)$ if for each $t$ there exists $B_t\subseteq +(\Bool^{\mathsf{N}})^{t+1}$ such that $\{\tau=t\}=\{(X_0,X_1,\ldots,X_t)\in B_t\}$. +In other words, the event $\{\tau = t \}$ only depends on the values of +$(X_0,X_1,\ldots,X_t)$, not on $X_k$ with $k > t$. + + +Let $(X_t)_{t\in \mathbb{N}}$ be a Markov chain and $f(X_{t-1},Z_t)$ a +random mapping representation of the Markov chain. A {\it randomized + stopping time} for the Markov chain is a stopping time for +$(Z_t)_{t\in\mathbb{N}}$. If the Markov chain is irreducible and has $\pi$ +as stationary distribution, then a {\it stationary time} $\tau$ is a +randomized stopping time (possibly depending on the starting position $X$), +such that the distribution of $X_\tau$ is $\pi$: +$$\P_X(X_\tau=Y)=\pi(Y).$$ + +A stopping time $\tau$ is a {\emph strong stationary time} if $X_{\tau}$ is +independent of $\tau$. + + +\begin{theorem} +If $\tau$ is a strong stationary time, then $d(t)\leq \max_{X\in\Bool^{\mathsf{N}}} +\P_X(\tau > t)$. +\end{theorem} + + +%Let $\Bool^n$ be the set of words of length $n$. +Let $E=\{(X,Y)\mid +X\in \Bool^{\mathsf{N}}, Y\in \Bool^{\mathsf{N}},\ X=Y \text{ or } X\oplus Y \in 0^*10^*\}$. +In other words, $E$ is the set of all the edges in the classical +${\mathsf{N}}$-cube. +Let $h$ be a function from $\Bool^{\mathsf{N}}$ into $\llbracket 1, {\mathsf{N}} \rrbracket$. +Intuitively speaking $h$ aims at memorizing for each node +$X \in \Bool^{\mathsf{N}}$ which edge is removed in the Hamiltonian cycle, +\textit{i.e.} which bit in $\llbracket 1, {\mathsf{N}} \rrbracket$ +cannot be switched. + + + +We denote by $E_h$ the set $E\setminus\{(X,Y)\mid X\oplus Y = +0^{{\mathsf{N}}-h(X)}10^{h(X)-1}\}$. This is the set of the modified hypercube, +\textit{i.e.}, the ${\mathsf{N}}$-cube where the Hamiltonian cycle $h$ +has been removed. + +We define the Markov matrix $P_h$ for each line $X$ and +each column $Y$ as follows: +\begin{equation} +\left\{ +\begin{array}{ll} +P_h(X,X)=\frac{1}{2}+\frac{1}{2{\mathsf{N}}} & \\ +P_h(X,Y)=0 & \textrm{if $(X,Y)\notin E_h$}\\ +P_h(X,Y)=\frac{1}{2{\mathsf{N}}} & \textrm{if $X\neq Y$ and $(X,Y) \in E_h$} +\end{array} +\right. +\label{eq:Markov:rairo} +\end{equation} + +We denote by $\ov{h} : \Bool^{\mathsf{N}} \rightarrow \Bool^{\mathsf{N}}$ the function +such that for any $X \in \Bool^{\mathsf{N}} $, +$(X,\ov{h}(X)) \in E$ and $X\oplus\ov{h}(X)=0^{{\mathsf{N}}-h(X)}10^{h(X)-1}$. +The function $\ov{h}$ is said {\it square-free} if for every $X\in \Bool^{\mathsf{N}}$, +$\ov{h}(\ov{h}(X))\neq X$. + +\begin{lemma}\label{lm:h} +If $\ov{h}$ is bijective and square-free, then $h(\ov{h}^{-1}(X))\neq h(X)$. +\end{lemma} + +\begin{proof} +Let $\ov{h}$ be bijective. +Let $k\in \llbracket 1, {\mathsf{N}} \rrbracket$ s.t. $h(\ov{h}^{-1}(X))=k$. +Then $(\ov{h}^{-1}(X),X)$ belongs to $E$ and +$\ov{h}^{-1}(X)\oplus X = 0^{{\mathsf{N}}-k}10^{k-1}$. +Let us suppose $h(X) = h(\ov{h}^{-1}(X))$. In such a case, $h(X) =k$. +By definition of $\ov{h}$, $(X, \ov{h}(X)) \in E $ and +$X\oplus\ov{h}(X)=0^{{\mathsf{N}}-h(X)}10^{h(X)-1} = 0^{{\mathsf{N}}-k}10^{k-1}$. +Thus $\ov{h}(X)= \ov{h}^{-1}(X)$, which leads to $\ov{h}(\ov{h}(X))= X$. +This contradicts the square-freeness of $\ov{h}$. +\end{proof} + +Let $Z$ be a random variable that is uniformly distributed over +$\llbracket 1, {\mathsf{N}} \rrbracket \times \Bool$. +For $X\in \Bool^{\mathsf{N}}$, we +define, with $Z=(i,b)$, +$$ +\left\{ +\begin{array}{ll} +f(X,Z)=X\oplus (0^{{\mathsf{N}}-i}10^{i-1}) & \text{if } b=1 \text{ and } i\neq h(X),\\ +f(X,Z)=X& \text{otherwise.} +\end{array}\right. +$$ + +The Markov chain is thus defined as +$$ +X_t= f(X_{t-1},Z_t) +$$ + + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%ù +%\section{Stopping time} + +An integer $\ell\in \llbracket 1,{\mathsf{N}} \rrbracket$ is said {\it fair} +at time $t$ if there +exists $0\leq j