ajout de la partie chaos

[rairo15.git] / preliminaries.tex

diff --git a/preliminaries.tex b/preliminaries.tex
index 628cd446996d1436e2bfb6923e5fc3f3c9ffe6b6..9441aab3a586ced9fb98b0b7d799c13e24d4ffed 100644 (file)
--- a/preliminaries.tex
+++ b/preliminaries.tex
@@ -53,12 +53,12 @@ Figure~\ref{fig:iteration:f*}.
 
 
 Let thus be given such kind of map.
 
 
 Let thus be given such kind of map.

-This article focusses on studying its iterations according to
+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 
 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 
+$n$-cube augmented 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.
 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.


@@ -94,57 +94,6 @@ P=\dfrac{1}{6} \left(
 \end{xpl}
 
 
 \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:
 % % 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:


@@ -173,53 +122,4 @@ If $\tau$ is a strong stationary time, then $d(t)\leq \max_{x\in\Bool^n}
 
 
 
 
 
 

-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 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.
-The final configuration is thus outputted.
-This PRNG is formalized in Algorithm~\ref{CI Algorithm}.
-
-
-
-\begin{algorithm}[ht]
-%\begin{scriptsize}
-\KwIn{a function $f$, an iteration number $b$, an initial configuration $x^0$ ($n$ bits)}
-\KwOut{a configuration $x$ ($n$ bits)}
-$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{15Rairo}}$ PRNG}
-\label{CI Algorithm}
-\end{algorithm}
-
-
-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 
-if its iteration graph is strongly connected, then 
-the output of $\chi_{\textit{14Secrypt}}$ follows 
-a law that tends to the uniform distribution 
-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.