X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/rairo15.git/blobdiff_plain/f18e5003b9da99d6565d366a1a9d56f8d893e5d9..17bd6f6df9a94a46128919486c226ae8b1124740:/preliminaries.tex

diff --git a/preliminaries.tex b/preliminaries.tex
index 8f7774a..628cd44 100644
--- a/preliminaries.tex
+++ b/preliminaries.tex
@@ -9,8 +9,9 @@ to itself
 such that 
 $x=(x_1,\dots,x_n)$ maps to $f(x)=(f_1(x),\dots,f_n(x))$.
 Functions are iterated as follows. 
-At the $t^{th}$ iteration, only the $s_{t}-$th component is
-``iterated'', where $s = \left(s_t\right)_{t \in \mathds{N}}$ is a sequence of indices taken in $\llbracket 1;n \rrbracket$ called ``strategy''. Formally,
+At the $t^{th}$ iteration, only the $s_{t}-$th component is said to be
+``iterated'', where $s = \left(s_t\right)_{t \in \mathds{N}}$ is a sequence of indices taken in $\llbracket 1;n \rrbracket$ called ``strategy''. 
+Formally,
 let $F_f: \llbracket1;n\rrbracket\times \Bool^{n}$ to $\Bool^n$ be defined by
 \[
 F_f(i,x)=(x_1,\dots,x_{i-1},f_i(x),x_{i+1},\dots,x_n).
@@ -50,55 +51,120 @@ Figure~\ref{fig:iteration:f*}.
 \end{figure}
 \end{xpl}
 
-% \vspace{-0.5em}
-% It is easy to associate a Markov Matrix $M$ to such a graph $G(f)$
-% as follows:
-
-% $M_{ij} = \frac{1}{n}$ if there is an edge from $i$ to $j$ in $\Gamma(f)$ and $i \neq j$;  $M_{ii} = 1 - \sum\limits_{j=1, j\neq i}^n M_{ij}$; and $M_{ij} = 0$ otherwise.
-
-% \begin{xpl}
-% The Markov matrix associated to the function $f^*$ is 
-
-% \[
-% M=\dfrac{1}{3} \left(
-% \begin{array}{llllllll}
-% 1&1&1&0&0&0&0&0 \\
-% 1&1&0&0&0&1&0&0 \\
-% 0&0&1&1&0&0&1&0 \\
-% 0&1&1&1&0&0&0&0 \\
-% 1&0&0&0&1&0&1&0 \\
-% 0&0&0&0&1&1&0&1 \\
-% 0&0&0&0&1&0&1&1 \\
-% 0&0&0&1&0&1&0&1 
-% \end{array}
-% \right)
-% \]
-%\end{xpl}
-
-
-It is usual to check whether rows of such kind of matrices
-converge to a specific 
-distribution. 
-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 
-$\Omega$  by:
-$$\tv{\pi-\mu}=\max_{A\subset \Omega} |\pi(A)-\mu(A)|.$$ 
-% It is known that
-% $$\tv{\pi-\mu}=\frac{1}{2}\sum_{x\in\Omega}|\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\Omega}\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$.
+
+Let thus be given such kind of map.
+This article focusses 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 
+$n$-cube augemented with all the self-loop, \textit{i.e.}, all the 
+edges $(v,v)$ for any $v \in \Bool^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}
+
+
+
+More generally, let $\pi$, $\mu$ be two distribution on $\Bool^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^n} |\pi(A)-\mu(A)|.$$ It is known that
+$$\tv{\pi-\mu}=\frac{1}{2}\sum_{x\in\Bool^n}|\pi(x)-\mu(x)|.$$ Moreover, if
+$\nu$ is a distribution on $\Bool^n$, one has
+$$\tv{\pi-\mu}\leq \tv{\pi-\nu}+\tv{\nu-\mu}$$
+
+Let $P$ be the matrix of a markov chain on $\Bool^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^n}\tv{P^t(x,\cdot)-\pi}.$$
+It is known that $d(t+1)\leq d(t)$. \JFC{rÃ©fÃ©rence ? 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^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
+\Omega^{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$. 
+ 
+
+\JFC{Je ne comprends pas la definition de randomized stopping time, Peut-on enrichir ?}
+
+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 irreductible and has $\pi$
+as stationary distribution, then a {\it stationary time} $\tau$ is a
+randomized stopping time (possibily depending on the starting position $x$),
+such that  the distribution of $X_\tau$ is $\pi$:
+$$\P_x(X_\tau=y)=\pi(y).$$
+
+
+\JFC{Ou ceci a-t-il ete prouvÃ©}
+\begin{Theo}
+If $\tau$ is a strong stationary time, then $d(t)\leq \max_{x\in\Bool^n}
+\P_x(\tau > t)$.
+\end{Theo}
+
+% % 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  
@@ -107,11 +173,11 @@ that is sufficient to obtain a deviation lesser than $\varepsilon$.
 
 
 
-Let us finally present the pseudorandom number generator $\chi_{\textit{14Secrypt}}$
+Let us finally present the pseudorandom number generator $\chi_{\textit{15Rairo}}$
 which is based on random walks in $\Gamma(f)$. 
 More precisely, let be given a Boolean map $f:\Bool^n \rightarrow \Bool^n$,
 a PRNG \textit{Random},
-an integer $b$ that corresponds to an awaited mixing time, and 
+an integer $b$ that corresponds an iteration number (\textit{i.e.}, the lenght of the walk), and 
 an initial configuration $x^0$. 
 Starting from $x^0$, the algorithm repeats $b$ times 
 a random choice of which edge to follow and traverses this edge.
@@ -120,7 +186,6 @@ This PRNG is formalized in Algorithm~\ref{CI Algorithm}.
 
 
 
-\vspace{-1em}
 \begin{algorithm}[ht]
 %\begin{scriptsize}
 \KwIn{a function $f$, an iteration number $b$, an initial configuration $x^0$ ($n$ bits)}
@@ -128,21 +193,23 @@ This PRNG is formalized in Algorithm~\ref{CI Algorithm}.
 $x\leftarrow x^0$\;
 \For{$i=0,\dots,b-1$}
 {
+\If{$\textit{Random}(1) \neq 0$}{
 $s\leftarrow{\textit{Random}(n)}$\;
 $x\leftarrow{F_f(s,x)}$\;
 }
+}
 return $x$\;
 %\end{scriptsize}
-\caption{Pseudo Code of the $\chi_{\textit{14Secrypt}}$ PRNG}
+\caption{Pseudo Code of the $\chi_{\textit{15Rairo}}$ PRNG}
 \label{CI Algorithm}
 \end{algorithm}
-\vspace{-0.5em}
-This PRNG is a particularized version of Algorithm given in~\cite{BCGR11}.
-Compared to this latter, the length of the random 
-walk of our algorithm is always constant (and is equal to $b$) whereas it 
-was given by a second PRNG in this latter.
-However, all the theoretical results that are given in~\cite{BCGR11} remain
-true since the proofs do not rely on this fact. 
+
+
+This PRNG is a particularized version of Algorithm given in~\cite{DBLP:conf/secrypt/CouchotHGWB14}.
+As this latter, the length of the random 
+walk of our algorithm is always constant (and is equal to $b$). 
+However, in the current version, we add the constraint that   
+
 
 Let $f: \Bool^{n} \rightarrow \Bool^{n}$.
 It has been shown~\cite[Th. 4, p. 135]{BCGR11}} that 
@@ -154,5 +221,5 @@ if and only if its Markov matrix is a doubly stochastic matrix.
 Let us now present  a method to
 generate  functions
 with Doubly Stochastic matrix and Strongly Connected iteration graph,
- denoted as DSSC matrix.   
+denoted as DSSC matrix.   
 
