-\end{xpl}
-
-
-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
-$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.
-
-\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{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^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 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).$$
-
-
-\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
-% only consider reversible Markov matrices whereas we do no restrict our
-% matrices to such a form.
-
