--- /dev/null
+
+
+
+In what follows, we consider the Boolean algebra on the set
+$\Bool=\{0,1\}$ with the classical operators of conjunction '.',
+of disjunction '+', of negation '$\overline{~}$', and of
+disjunctive union $\oplus$.
+
+Let $n$ be a positive integer. A {\emph{Boolean map} $f$ is
+a function from the Boolean domain
+ 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,
+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).
+\]
+Then, let $x^0\in\Bool^n$ be an initial configuration
+and $s\in
+\llbracket1;n\rrbracket^\Nats$ be a strategy,
+the dynamics are described by the recurrence
+\begin{equation}\label{eq:asyn}
+x^{t+1}=F_f(s_t,x^t).
+\end{equation}
+
+
+Let be given a Boolean map $f$. Its associated
+{\emph{iteration graph}} $\Gamma(f)$ is the
+directed graph such that the set of vertices is
+$\Bool^n$, and for all $x\in\Bool^n$ and $i\in \llbracket1;n\rrbracket$,
+the graph $\Gamma(f)$ contains an arc from $x$ to $F_f(i,x)$.
+
+\begin{xpl}
+Let us consider for instance $n=3$.
+Let
+$f^*: \Bool^3 \rightarrow \Bool^3$ be defined by
+
+$f^*(x_1,x_2,x_3) =
+(x_2 \oplus x_3, \overline{x_1}\overline{x_3} + x_1\overline{x_2},
+\overline{x_1}\overline{x_3} + x_1x_2)$
+The iteration graph $\Gamma(f^*)$ of this function is given in
+Figure~\ref{fig:iteration:f*}.
+
+\vspace{-1em}
+\begin{figure}[ht]
+\begin{center}
+\includegraphics[scale=0.5]{images/iter_f0b}
+\end{center}
+\vspace{-0.5em}
+\caption{Iteration Graph $\Gamma(f^*)$ of the function $f^*$}\label{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$.
+% 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.
+
+
+
+Let us finally present the pseudorandom number generator $\chi_{\textit{14Secrypt}}$
+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 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}.
+
+
+
+\vspace{-1em}
+\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$}
+{
+$s\leftarrow{\textit{Random}(n)}$\;
+$x\leftarrow{F_f(s,x)}$\;
+}
+return $x$\;
+%\end{scriptsize}
+\caption{Pseudo Code of the $\chi_{\textit{14Secrypt}}$ 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.
+
+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.
+
--- /dev/null
+\documentclass{article}
+%\usepackage{prentcsmacro}
+%\sloppy
+\usepackage[a4paper]{geometry}
+\geometry{hmargin=3cm, vmargin=3cm }
+
+\usepackage[latin1]{inputenc}
+\usepackage[T1]{fontenc}
+\usepackage[english]{babel}
+\usepackage{amsmath,amssymb,latexsym,eufrak,euscript}
+\usepackage{subfigure,pstricks,pst-node,pst-coil}
+
+
+\usepackage{url,tikz}
+\usepackage{pgflibrarysnakes}
+
+\usepackage{multicol}
+
+\usetikzlibrary{arrows}
+\usetikzlibrary{automata}
+\usetikzlibrary{snakes}
+\usetikzlibrary{shapes}
+
+%% \setlength{\oddsidemargin}{15mm}
+%% \setlength{\evensidemargin}{15mm} \setlength{\textwidth}{140mm}
+%% \setlength{\textheight}{219mm} \setlength{\topmargin}{5mm}
+\newtheorem{theorem}{Theorem}
+%\newtheorem{definition}[theorem]{Definition}
+% %\newtheorem{defis}[thm]{D\'efinitions}
+ \newtheorem{example}[theorem]{Example}
+% %\newtheorem{Exes}[thm]{Exemples}
+\newtheorem{lemma}[theorem]{Lemma}
+\newtheorem{proposition}[theorem]{Proposition}
+\newtheorem{construction}[theorem]{Construction}
+\newtheorem{corollary}[theorem]{Corollary}
+% \newtheorem{algor}[thm]{Algorithm}
+%\newtheorem{propdef}[thm]{Proposition-D\'efinition}
+\newcommand{\mlabel}[1]{\label{#1}\marginpar{\fbox{#1}}}
+\newcommand{\flsup}[1]{\stackrel{#1}{\longrightarrow}}
+
+\newcommand{\stirlingtwo}[2]{\genfrac{\lbrace}{\rbrace}{0pt}{}{#1}{#2}}
+\newcommand{\stirlingone}[2]{\genfrac{\lbrack}{\rbrack}{0pt}{}{#1}{#2}}
+
+\newenvironment{algo}
+{ \vspace{1em}
+\begin{algor}\mbox
+\newline \vspace{-0.1em}
+\begin{quote}\begin{rm}}
+{\end{rm}\end{quote}\end{algor}\vspace{-1.5em}\vspace{2em}}
+%\null \hfill $\diamondsuit$ \par\medskip \vspace{1em}}
+
+\newenvironment{exe}
+{\begin{example}\rm }
+{\end{example}
+%\vspace*{-1.5em}
+%\null \hfill $\triangledown$ \par\medskip}
+%\null \hfill $\triangledown$ \par\medskip \vspace{1em}}
+}
+
+
+\newenvironment{proof}
+{ \noindent {\sc Proof.\/} }
+{\null \hfill $\Box$ \par\medskip \vspace{1em}}
+
+
+
+\newcommand {\tv}[1] {\lVert #1 \rVert_{\rm TV}}
+\def \top {1.8}
+\def \topt {2.3}
+\def \P {\mathbb{P}}
+\def \ov {\overline}
+\def \ts {\tau_{\rm stop}}
+\begin{document}
+\label{firstpage}
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\section{Mathematical Backgroung}
+
+
+
+Let $\pi$, $\mu$ be two distribution on a same set $\Omega$. The total
+variation distance between $\pi$ and $\mu$ is denoted $\tv{\pi-\mu}$ and is
+defined 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)|.$$ Moreover, if
+$\nu$ is a distribution on $\Omega$, one has
+$$\tv{\pi-\mu}\leq \tv{\pi-\nu}+\tv{\nu-\mu}$$
+
+Let $P$ be the matrix of a markov chain on $\Omega$. $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\Omega}\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)$.
+
+
+%% A {\it coupling} with transition matrix $P$ is a process $(X_t,Y_t)_{t\geq 0}$
+%% such that both $(X_t)$ and $(Y_t)$ are markov chains of matric $P$; moreover
+%% it is required that if $X_s=Y_s$, then for any $t\geq s$, $X_t=Y_t$.
+%% A results provides that if $(X_t,Y_t)_{t\geq 0}$ is a coupling, then
+%% $$d(t)\leq \max_{x,y} P_{x,y}(\{\tau_{\rm couple} \geq t\}),$$
+%% with $\tau_{\rm couple}=\min_t\{X_t=Y_t\}$.
+
+
+Let $(X_t)_{t\in \mathbb{N}}$ be a sequence of $\Omega$ 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\}$.
+
+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}}$. It he markov chain is irreductible and has $\pi$
+as stationary distribution, then a {\it stationay 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).$$
+
+\begin{proposition}
+If $\tau$ is a strong stationary time, then $d(t)\leq \max_{x\in\Omega}
+\P_x(\tau > t)$.
+\end{proposition}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\section{Random walk on the modified Hypercube}
+
+
+Let $\Omega=\{0,1\}^N$ be the set of words of length $N$. Let $E=\{(x,y)\mid
+x\in \Omega, y\in \Omega,\ x=y \text{ or } x\oplus y \in 0^*10^*\}$. Let $h$
+be a function from $\Omega$ into $\{1,\ldots,N\}$.
+
+We denote by $E_h$ the set $E\setminus\{(x,y)\mid x\oplus y =
+0^{N-h(x)}10^{h(x)-1}\}$. We define the matrix $P_h$ has follows:
+$$\left\{
+\begin{array}{ll}
+P_h(x,y)=0 & \text{ if } (x,y)\notin E_h\\
+P_h(x,x)=\frac{1}{2}+\frac{1}{2N} & \\
+P_h(x,x)=\frac{1}{2N} & \text{otherwise}\\
+
+\end{array}
+\right.
+$$
+
+We denote by $\ov{h}$ the function from $\Omega$ into $\omega$ defined
+by $x\oplus\ov{h}(x)=0^{N-h(x)}10^{h(x)-1}.$
+The function $\ov{h}$ is said {\it square-free} if for every $x\in E$,
+$\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}
+
+\end{proof}
+
+Let $Z$ be a random variable over
+$\{1,\ldots,N\}\times\{0,1\}$ uniformaly distributed. For $X\in \Omega$, we
+define, with $Z=(i,x)$,
+$$
+\left\{
+\begin{array}{ll}
+f(X,Z)=X\oplus (0^{N-i}10^{i-1}) & \text{if } x=1 \text{ and } i\neq h(X),\\
+f(X,Z)=X& \text{otherwise.}
+\end{array}\right.
+$$
+
+The pair $f,Z$ is a random mapping representation of $P_h$.
+
+
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%ù
+\section{Stopping time}
+
+An integer $\ell\in\{1,\ldots,N\}$ is said {\it fair} at time $t$ if there
+exists $0\leq j <t$ such that $Z_j=(\ell,\cdot)$ and $h(X_j)\neq \ell$.
+
+
+Let $\ts$ be the first time all the elements of $\{1,\ldots,N\}$
+are fair. The integer $\ts$ is a randomized stopping time for
+the markov chain $(X_t)$.
+
+
+\begin{lemma}
+The integer $\ts$ is a strong stationnary time.
+\end{lemma}
+
+\begin{proof}
+Let $\tau_\ell$ be the first time that $\ell$ is fair. The random variable
+$Z_{\tau_\ell-1}$ is of the form $(\ell,\delta)$ with $\delta\in\{0,1\}$ and
+$\delta=1$ with probability $\frac{1}{2}$ and $\delta=0$ with probability
+$\frac{1}{2}$. Since $h(X_{\tau_\ell-1})\neq\ell$ the value of the $\ell$-th
+bit of $X_{\tau_\ell}$ is $\delta$. By symetry, for $t\geq \tau_\ell$, the
+$\ell$-th bit of $X_t$ is $0$ or $1$ with the same probability, proving the
+lemma.
+\end{proof}
+
+\begin{proposition} \label{prop:stop}
+If $\ov{h}$ is bijective and square-free, then
+$E[\ts]\leq 8N^2+ N\ln (N+1)$.
+\end{proposition}
+
+For each $x\in \Omega$ and $\ell\in\{1,\ldots,N\}$, let $S_{x,\ell}$ be the
+random variable counting the number of steps done until reaching from $x$ a state where
+$\ell$ is fair. More formaly
+$$S_{x,\ell}=\min \{m \geq 1\mid h(X_m)\neq \ell\text{ and }Z_m=\ell\text{ and } X_0=x\}.$$
+
+ We denote by
+$$\lambda_h=\max_{x,\ell} S_{x,\ell}.$$
+
+
+\begin{lemma}\label{prop:lambda}
+If $\ov{h}$ is a square-free bijective function, then one has $E[\lambda_h]\leq 8N^2.$
+\end{lemma}
+
+\begin{proof}
+For evey $x$, every $\ell$, one has $\P(S_{x,\ell})\leq 2)\geq
+\frac{1}{4N^2}$. Indeed, if $h(x)\neq \ell$, then
+$\P(S_{x,\ell}=1)=\frac{1}{2N}\geq \frac{1}{4N^2}$. If $h(x)=\ell$, then
+$\P(S_{x,\ell}=1)=0$. Let $X_0=x$. Since $\ov{h}$ is square-free,
+$\ov{h}(\ov{h}^{-1}(x))\neq x$. It follows that $(x,\ov{h}^{-1}(x))\in E_h$.
+Thefore $P(X_1=\ov{h}^{-1}(x))=\frac{1}{2N}$. Now,
+by Lemma~\ref{lm:h}, $h(\ov{h}^{-1}(x))\neq h(x)$. Therefore
+$\P(S_{x,\ell}=2\mid X_1=\ov{h}^{-1}(x))=\frac{1}{2N}$, proving that
+$\P(S_{x,\ell}\leq 2)\geq \frac{1}{4N^2}$.
+
+Therefore, $\P(S_{x,\ell}\geq 2)\leq 1-\frac{1}{4N^2}$. By induction, one
+has, for every $i$, $\P(S_{x,\ell}\geq 2i)\leq
+\left(1-\frac{1}{4N^2}\right)^i$.
+ Moreover,
+since $S_{x,\ell}$ is positive, it is known~\cite[lemma 2.9]{}, that
+$$E[S_{x,\ell}]=\sum_{i=1}^{+\infty}\P(S_{x,\ell}\geq i).$$
+Since $\P(S_{x,\ell}\geq i)\geq \P(S_{x,\ell}\geq i+1)$, one has
+$$E[S_{x,\ell}]=\sum_{i=1}^{+\infty}\P(S_{x,\ell}\geq i)\leq
+\P(S_{x,\ell}\geq 1)+2 \sum_{i=1}^{+\infty}\P(S_{x,\ell}\geq 2i).$$
+Consequently,
+$$E[S_{x,\ell}]\leq 1+2
+\sum_{i=1}^{+\infty}\left(1-\frac{1}{4N^2}\right)^i=1+2(4N^2-1)=8N^2-2,$$
+which concludes the proof.
+\end{proof}
+
+Let $\ts^\prime$ be the first time that there are exactly $N-1$ fair
+elements.
+
+\begin{lemma}\label{lm:stopprime}
+One has $E[\ts^\prime]\leq N \ln (N+1).$
+\end{lemma}
+
+\begin{proof}
+This is a classical Coupon Collector's like problem. Let $W_i$ be the
+random variable counting the number of moves done in the markov chain while
+we had exactly $i-1$ fair bits. One has $\ts^\prime=\sum_{i=1}^{N-1}W_i$.
+ But when we are at position $x$ with $i-1$ fair bits, the probability of
+ obtaining a new fair bit is either $1-\frac{i-1}{N}$ if $h(x)$ is fair,
+ or $1-\frac{i-2}{N}$ if $h(x)$ is not fair. It follows that
+$E[W_i]\leq \frac{N}{N-i+2}$. Therefore
+$$E[\ts^\prime]=\sum_{i=1}^{N-1}E[W_i]\leq N\sum_{i=1}^{N-1}
+ \frac{1}{N-i+2}=N\sum_{i=3}^{N+1}\frac{1}{i}.$$
+
+But $\sum_{i=1}^{N+1}\frac{1}{i}\leq 1+\ln(N+1)$. It follows that
+$1+\frac{1}{2}+\sum_{i=3}^{N+1}\frac{1}{i}\leq 1+\ln(N+1).$
+Consequently,
+$E[\ts^\prime]\leq N (-\frac{1}{2}+\ln(N+1))\leq N\ln(N+1)$.
+\end{proof}
+
+One can now prove Proposition~\ref{prop:stop}.
+
+\begin{proof}
+One has $\ts\leq \ts^\prime+\lambda_h$. Therefore,
+Proposition~\ref{prop:stop} is a direct application of
+lemma~\ref{prop:lambda} and~\ref{lm:stopprime}.
+\end{proof}
+
+\end{document}
