X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/hdrcouchot.git/blobdiff_plain/01003216d61845263ad195f3ecf7334817d60407..HEAD:/annexePreuveStopping.tex

diff --git a/annexePreuveStopping.tex b/annexePreuveStopping.tex
index 510dcef..75d05e4 100644
--- a/annexePreuveStopping.tex
+++ b/annexePreuveStopping.tex
@@ -1,378 +1,293 @@
-\section{Quantifier l'écart par rapport à la distribution uniforme} 
-%15 Rairo
+L'objectif principal de cette section est de démontrer le théorème~\ref{theo:tmps:mix} rappelé en fin de section.
 
 
-
-
-
-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
+Un résultat classique est
 
 $$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$. 
+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$. 
  
 
-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$:
+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 irréductible 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$.  
 
-A stopping time $\tau$ is a {\emph strong stationary time} if $X_{\tau}$ is
-independent of $\tau$. 
-
+On rappelle le théorème suivant~\cite[Proposition 6.10]{LevinPeresWilmer2006}.
 
-\begin{theorem}
-If $\tau$ is a strong stationary time, then $d(t)\leq \max_{X\in\Bool^{\mathsf{N}}}
+\begin{theorem}\label{thm-sst}
+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}
 
 
-%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 
+Soit $E=\{(X,Y)\mid
+X\in \Bool^{\mathsf{N}}, Y\in \Bool^{\mathsf{N}},\ X=Y \text{ ou } X\oplus Y \in 0^*10^*\}$.
+En d'autres mots, $E$ est l'ensemble des tous les arcs du   
 ${\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.
+Soit $h: \Bool^{\mathsf{N}} \to [{\mathsf{N}}]$ 
+qui mémorise pour chaque n{\oe}ud $X \in \Bool^{\mathsf{N}}$ quel
+arc est supprimé à partir du cycle hamiltonien,
+\textit{i.e.} quel bit dans  $[{\mathsf{N}} ]$ 
+ne peut pas être inversé.
 
 
 
-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.
+On définit ensuite  l'ensemble $E_h = E\setminus\{(X,Y)\mid X\oplus Y =
+0^{{\mathsf{N}}-h(X)}10^{h(X)-1}\}$. C'est l'ensemble de tous les arcs 
+appartenant à l'hypercube modifié, 
+\textit{i.e.}, le ${\mathsf{N}}$-cube où le cycle hamiltonien $h$ 
+a été enlevé.
 
-We define the Markov matrix $P_h$ for each line $X$ and 
-each column $Y$  as follows:
+On définit la matrice de Markov $P_h$ pour chaque ligne $X$ et  
+chaque colonne $Y$  comme suit:
 \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$}
+P_h(X,Y)=0 & \textrm{si  $(X,Y)\notin E_h$}\\
+P_h(X,Y)=\frac{1}{2{\mathsf{N}}} & \textrm{si $X\neq Y$ et $(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}}$,
+
+
+
+
+Soit alors $\ov{h} : \Bool^{\mathsf{N}} \rightarrow \Bool^{\mathsf{N}}$ la fonction 
+telle que pour $X \in \Bool^{\mathsf{N}} $, 
+$(X,\ov{h}(X)) \in E$ et $X\oplus\ov{h}(X)=0^{{\mathsf{N}}-h(X)}10^{h(X)-1}$. 
+La fonction $\ov{h}$ est dite  {\it anti-involutive} si pour tout $X\in \Bool^{\mathsf{N}}$,
 $\ov{h}(\ov{h}(X))\neq X$. 
 
+
+%Let $\Bool^n$ be the set of words of length $n$. 
+
 \begin{lemma}\label{lm:h}
-If $\ov{h}$ is bijective and square-free, then $h(\ov{h}^{-1}(X))\neq h(X)$.
+Si $\ov{h}$ est bijective et anti-involutive, alors
+$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 
+Soit $\ov{h}$  bijective. 
+Soit $k\in \llbracket 1, {\mathsf{N}} \rrbracket$ t.q. $h(\ov{h}^{-1}(X))=k$.
+Alors $(\ov{h}^{-1}(X),X)$ appartient à  $E$ et
 $\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 
+Supposons $h(X) = h(\ov{h}^{-1}(X))$. Dans un tel cas, $h(X) =k$.
+Par définition  $\ov{h}$, $(X, \ov{h}(X)) \in E $ et
 $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}$.
+Ainsi $\ov{h}(X)= \ov{h}^{-1}(X)$, ce qui entraîne $\ov{h}(\ov{h}(X))= X$ et 
+qui contredit le fait que $\ov{h}$ est anti-involutive.
 \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)$,  
-$$
+Soit $Z$ une variable aléatoire suivant une distribution uniforme sur 
+$[ {\mathsf{N}}] \times \Bool$.
+Pour $X\in \Bool^{\mathsf{N}}$, on définit avec  $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.} 
+f(X,Z)=X\oplus (0^{{\mathsf{N}}-i}10^{i-1}) & \text{ si } b=1 \text{ et } i\neq h(X),\\
+f(X,Z)=X& \text{sinon.} 
 \end{array}\right.
-$$
+\]
 
-The Markov chain is thus defined as 
-$$
-X_t= f(X_{t-1},Z_t)
-$$
+La chaîne de Markov est ainsi définie par 
+\[
+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 <t$ such that $Z_{j+1}=(\ell,\cdot)$ and $h(X_j)\neq \ell$.
-In other words, there exist a date $j$ before $t$ where 
-the first element of the random variable $Z$ is exactly $l$ 
-(\textit{i.e.}, $l$ is the strategy at date $j$) 
-and where the configuration $X_j$ allows to traverse the edge $l$.  
+Un entier $\ell\in \llbracket 1,{\mathsf{N}} \rrbracket$ est  \emph{équitable} 
+ au temps $t$ s'il existe  $0\leq j <t$ tel que $Z_{j+1}=(\ell,\cdot)$ et $h(X_j)\neq \ell$. En d'autres mots, il existe une date $j$ antérieure à  $t$ 
+où le premier élément de la variable aléatoire  $Z$ est $l$ 
+(\textit{i.e.}, la stratégie vaut $l$ à la date $j$) 
+et où le n{\oe}ud $X_j$ permet de traverser l'arc  $l$.  
  
-Let $\ts$ be the first time all the elements of $\llbracket 1, {\mathsf{N}} \rrbracket$
-are fair. The integer $\ts$ is a randomized stopping time for
-the Markov chain $(X_t)$.
+Soit $\ts$ le premier temps où tous les éléments de $\llbracket 1, {\mathsf{N}} \rrbracket$ 
+sont  équitables.  On a le lemme suivant:%L'entier $\ts$ est un temps d'arrêt pour la chaîne de Markov $(X_t)$.
 
 
 \begin{lemma}
-The integer $\ts$ is a strong stationary time.
+L'entier $\ts$ est un temps stationnaire fort.
 \end{lemma}
 
 \begin{proof}
-Let $\tau_\ell$ be the first time that $\ell$ is fair. The random variable
-$Z_{\tau_\ell}$ is of the form $(\ell,b)$ %with $\delta\in\{0,1\}$ and
-such that 
-$b=1$ with probability $\frac{1}{2}$ and $b=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 $0$ or $1$ with the same probability ($\frac{1}{2}$).
+Soit $\tau_\ell$ la première date où $\ell$ est équitable.
+La variable aléatoire $Z_{\tau_\ell}$ est de la forme  $(\ell,b)$ %with $\delta\in\{0,1\}$ and
+et telle que 
+$b=1$ avec la probabilité $\frac{1}{2}$ et $b=0$ avec la probabilité 
+$\frac{1}{2}$. Comme $h(X_{\tau_\ell-1})\neq\ell$,
+la valeur du $\ell^{\textrm{ème}}$
+bit de $X_{\tau_\ell}$ 
+est $0$ ou $1$ avec la même probabilité  ($\frac{1}{2}$).
+
+A chaque étape, le $l^{\textrm{ème}}$ bit  est inversé de $0$ à $1$ ou de $1$ à $0$, chaque fois avec la même 
+probabilité. Ainsi,  pour $t\geq \tau_\ell$, le
+$\ell^{\textrm{ème}}$ bit de $X_t$ est $0$ ou $1$ avec la même probabilité,
+et ce indépendamment de la valeur des autres bits.
+\end{proof}
 
- Moving next in the chain, at each step,
-the $l$-th bit  is switched from $0$ to $1$ or from $1$ to $0$ each time with
-the same probability. Therefore,  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}
 
-\theostopmajorant*
 
-For each $X\in \Bool^{\mathsf{N}}$ and $\ell\in\llbracket 1,{\mathsf{N}}\rrbracket$, 
-let $S_{X,\ell}$ be the
-random variable that counts the number of steps 
-from $X$ until we reach a configuration where
-$\ell$ is fair. More formally
-$$S_{X,\ell}=\min \{t \geq 1\mid h(X_{t-1})\neq \ell\text{ and }Z_t=(\ell,.)\text{ and } X_0=X\}.$$
 
-%  We denote by
-% $$\lambda_h=\max_{X,\ell} S_{X,\ell}.$$
+
+
+
+Pour chaque $X\in \Bool^{\mathsf{N}}$ et $\ell\in [{\mathsf{N}}]$, 
+soit $S_{X,\ell}$ une variable aléatoire qui compte le nombre d'itérations
+tel qu'en démarrant de la configuration  $X$ on en atteigne une où 
+$\ell$  est équitable. Plus formellement, 
+$$S_{X,\ell}=\min \{t \geq 1\mid h(X_{t-1})\neq \ell\text{ et }Z_t=(\ell,.)\text{ et } X_0=X\}.$$
+On peut majorer l'espérance de cette variable aléatoire comme suit.
 
 
 \begin{lemma}\label{prop:lambda}
-Let $\ov{h}$ is a square-free bijective function. Then
-for all $X$ and 
-all $\ell$, 
-the inequality 
-$E[S_{X,\ell}]\leq 8{\mathsf{N}}^2$ is established.
+Soit $\ov{h}$ un fonction bijective et anti-involutive. Alors pour tout 
+ $X\in \Bool^{\mathsf{N}}$ et $\ell\in [{\mathsf{N}}]$, 
+l'inégalité $E[S_{X,\ell}]\leq 8{\mathsf{N}}^2$ est établie.
 \end{lemma}
 
 \begin{proof}
-For every $X$, every $\ell$, one has $\P(S_{X,\ell})\leq 2)\geq
-\frac{1}{4{\mathsf{N}}^2}$. 
-Let $X_0= X$.
-Indeed, 
+Montrons tout d'abord que pour chaque $X$ et chaque  $\ell$, on a  $\P(S_{X,\ell})\leq 2)\geq
+\frac{1}{4{\mathsf{N}}^2}$. Soit  $X_0= X$.
+
 \begin{itemize}
-\item if $h(X)\neq \ell$, then
+\item Si $h(X)\neq \ell$, alors
 $\P(S_{X,\ell}=1)=\frac{1}{2{\mathsf{N}}}\geq \frac{1}{4{\mathsf{N}}^2}$. 
-\item otherwise, $h(X)=\ell$, then
-$\P(S_{X,\ell}=1)=0$.
-But in this case, intuitively, it is possible to move
-from $X$ to $\ov{h}^{-1}(X)$ (with probability $\frac{1}{2N}$). And in
-$\ov{h}^{-1}(X)$ the $l$-th bit can be switched. 
-More formally,
-since $\ov{h}$ is square-free,
-$\ov{h}(X)=\ov{h}(\ov{h}(\ov{h}^{-1}(X)))\neq \ov{h}^{-1}(X)$. It follows
-that $(X,\ov{h}^{-1}(X))\in E_h$. We thus have
-$P(X_1=\ov{h}^{-1}(X))=\frac{1}{2{\mathsf{N}}}$. 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}{2{\mathsf{N}}}$, proving that $\P(S_{x,\ell}\leq 2)\geq
+\item Sinon, $h(X)=\ell$, alors
+$\P(S_{X,\ell}=1)=0$. Dans ce cas, intuitivement, il est possible de passer de $X$ à $\ov{h}^{-1}(X)$ 
+(avec la probabilité $\frac{1}{2N}$). De plus, dans la configuration
+$\ov{h}^{-1}(X)$, le $l^{\textrm{ème}}$ bit peut être inversé.
+Plus formellement, puisque $\ov{h}$ est anti-involutive,
+$\ov{h}(X)=\ov{h}(\ov{h}(\ov{h}^{-1}(X)))\neq \ov{h}^{-1}(X)$. On en déduit
+que $(X,\ov{h}^{-1}(X))\in E_h$. On a ainsi
+$P(X_1=\ov{h}^{-1}(X))=\frac{1}{2{\mathsf{N}}}$. 
+D'après le  lemme~\ref{lm:h},
+$h(\ov{h}^{-1}(X))$ est différent de $h(X)$. 
+Ainsi, $\P(S_{x,\ell}=2\mid X_1=\ov{h}^{-1}(X))=\frac{1}{2{\mathsf{N}}}$, 
+prouvant ainsi que  $\P(S_{x,\ell}\leq 2)\geq
 \frac{1}{4{\mathsf{N}}^2}$.
 \end{itemize}
 
 
 
 
-Therefore, $\P(S_{X,\ell}\geq 3)\leq 1-\frac{1}{4{\mathsf{N}}^2}$. By induction, one
-has, for every $i$, $\P(S_{X,\ell}\geq 2i)\leq
+Ainsi, $\P(S_{X,\ell}\geq 3)\leq 1-\frac{1}{4{\mathsf{N}}^2}$. Par induction, on a,
+pour chaque $i$, $\P(S_{X,\ell}\geq 2i)\leq
 \left(1-\frac{1}{4{\mathsf{N}}^2}\right)^i$.
- Moreover,
-since $S_{X,\ell}$ is positive, it is known~\cite[lemma 2.9]{proba}, 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)+\P(S_{X,\ell}\geq 2)+2 \sum_{i=1}^{+\infty}\P(S_{X,\ell}\geq 2i).$$
-Consequently,
+De plus,
+puisque $S_{X,\ell}$ est positive, on sait~\cite[lemme 2.9]{proba} que
+\[
+E[S_{X,\ell}]=\sum_{i=1}^{+\infty}\P(S_{X,\ell}\geq i).
+\]
+Puisque $\P(S_{X,\ell}\geq i)\geq \P(S_{X,\ell}\geq i+1)$, on a 
+\[
+E[S_{X,\ell}]=\sum_{i=1}^{+\infty}\P(S_{X,\ell}\geq i)\leq
+\P(S_{X,\ell}\geq 1)+\P(S_{X,\ell}\geq 2)+2 \sum_{i=1}^{+\infty}\P(S_{X,\ell}\geq 2i).\]
+Ainsi,
 $$E[S_{X,\ell}]\leq 1+1+2
 \sum_{i=1}^{+\infty}\left(1-\frac{1}{4{\mathsf{N}}^2}\right)^i=2+2(4{\mathsf{N}}^2-1)=8{\mathsf{N}}^2,$$
-which concludes the proof.
+ce qui conclut la preuve du lemme.
 \end{proof}
 
-Let $\ts^\prime$ be the time used to get all the bits but one fair.
+Soit $\ts^\prime$ la variable aléatoire comptant le nombre d'itérations pour avoir exactement
+$\mathsf{N}-1$ bits équitables. On peut majorer son espérance.
 
 \begin{lemma}\label{lm:stopprime}
-One has $E[\ts^\prime]\leq 4{\mathsf{N}} \ln ({\mathsf{N}}+1).$
+On a  $E[\ts^\prime]\leq 4{\mathsf{N}} \ln ({\mathsf{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}^{{\mathsf{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}{{\mathsf{N}}}$ if $h(X)$ is fair,
- or  $1-\frac{i-2}{{\mathsf{N}}}$ if $h(X)$ is not fair. 
-
-Therefore,
+C'est un problème classique de collectionneur de vignettes. Soit $W_i$ la variable aléatoire 
+comptant le nombre de déplacements dans la chaîne de Markov pour avoir exactement
+$i-1$ bits équitables. On a $\ts^\prime=\sum_{i=1}^{{\mathsf{N}}-1}W_i$.
+Dans la configuration $X$ avec $i-1$ bits équitables,
+la probabilité d'obtenir un nouveau bit équitable est soit
+$1-\frac{i-1}{{\mathsf{N}}}$ si $h(X)$ est équitable,
+soit $1-\frac{i-2}{{\mathsf{N}}}$ si $h(X)$ ne l'est pas. 
+
+Ainsi, 
 $\P (W_i=k)\leq \left(\frac{i-1}{{\mathsf{N}}}\right)^{k-1} \frac{{\mathsf{N}}-i+2}{{\mathsf{N}}}.$
-Consequently, we have $\P(W_i\geq k)\leq \left(\frac{i-1}{{\mathsf{N}}}\right)^{k-1} \frac{{\mathsf{N}}-i+2}{{\mathsf{N}}-i+1}.$
-It follows that $E[W_i]=\sum_{k=1}^{+\infty} \P (W_i\geq k)\leq {\mathsf{N}} \frac{{\mathsf{N}}-i+2}{({\mathsf{N}}-i+1)^2}\leq \frac{4{\mathsf{N}}}{{\mathsf{N}}-i+2}$.
-
-
+On a par conséquent $\P(W_i\geq k)\leq \left(\frac{i-1}{{\mathsf{N}}}\right)^{k-1} \frac{{\mathsf{N}}-i+2}{{\mathsf{N}}-i+1}.$
+On en déduit que 
+\[
+E[W_i]=\sum_{k=1}^{+\infty} \P (W_i\geq k)\leq {\mathsf{N}} \frac{{\mathsf{N}}-i+2}{({\mathsf{N}}-i+1)^2}\leq \frac{4{\mathsf{N}}}{{\mathsf{N}}-i+2},
+\]
+et donc que 
 
-It follows that 
-$E[W_i]\leq \frac{4{\mathsf{N}}}{{\mathsf{N}}-i+2}$. Therefore
-$$E[\ts^\prime]=\sum_{i=1}^{{\mathsf{N}}-1}E[W_i]\leq 
+\[
+E[\ts^\prime]=\sum_{i=1}^{{\mathsf{N}}-1}E[W_i]\leq 
 4{\mathsf{N}}\sum_{i=1}^{{\mathsf{N}}-1} \frac{1}{{\mathsf{N}}-i+2}=
-4{\mathsf{N}}\sum_{i=3}^{{\mathsf{N}}+1}\frac{1}{i}.$$
+4{\mathsf{N}}\sum_{i=3}^{{\mathsf{N}}+1}\frac{1}{i}.\]
 
-But $\sum_{i=1}^{{\mathsf{N}}+1}\frac{1}{i}\leq 1+\ln({\mathsf{N}}+1)$. It follows that
+Or $\sum_{i=1}^{{\mathsf{N}}+1}\frac{1}{i}\leq 1+\ln({\mathsf{N}}+1)$. On en déduit que 
 $1+\frac{1}{2}+\sum_{i=3}^{{\mathsf{N}}+1}\frac{1}{i}\leq 1+\ln({\mathsf{N}}+1).$
-Consequently,
-$E[\ts^\prime]\leq 
+Ainsi, on a la majoration suivante
+\[
+E[\ts^\prime]\leq 
 4{\mathsf{N}} (-\frac{1}{2}+\ln({\mathsf{N}}+1))\leq 
-4{\mathsf{N}}\ln({\mathsf{N}}+1)$.
+4{\mathsf{N}}\ln({\mathsf{N}}+1),
+\]
+ce qui termine la preuve du lemme.
 \end{proof}
 
-One can now prove Theorem~\ref{prop:stop}.
-
+Tous les éléments sont en place pour majorer l'espérance de $\ts$. 
+\begin{theorem}
+\label{prop:stop}
+Si $\ov{h}$ est bijective et anti- involutive 
+$\ov{h}(\ov{h}(X))\neq X$, alors
+$E[\ts]\leq 8{\mathsf{N}}^2+ 4{\mathsf{N}}\ln ({\mathsf{N}}+1)$. 
+\end{theorem}
 \begin{proof}
-Since $\ts^\prime$ is the time used to obtain $\mathsf{N}-1$ fair bits.
-Assume that the last unfair bit is $\ell$. One has
-$\ts=\ts^\prime+S_{X_\tau,\ell}$, and therefore
-$E[\ts] = E[\ts^\prime]+E[S_{X_\tau,\ell}]$. Therefore,
-Theorem~\ref{prop:stop} is a direct application of
-lemma~\ref{prop:lambda} and~\ref{lm:stopprime}.
+Sans perte de généralité, considérons que le dernier bit 
+non équitable est $\ell$. On a 
+$\ts=\ts^\prime+S_{X_\tau,\ell}$ et donc
+$E[\ts] = E[\ts^\prime]+E[S_{X_\tau,\ell}]$. Ainsi, le théorème 
+est une application directe des lemmes~\ref{prop:lambda} et~\ref{lm:stopprime}.
 \end{proof}
 
-Notice that the calculus of the stationary time upper bound is obtained
-under the following constraint: for each vertex in the $\mathsf{N}$-cube 
-there are one ongoing arc and one outgoing arc that are removed. 
-The calculus does not consider (balanced) Hamiltonian cycles, which 
-are more regular and more binding than this constraint.
-In this later context, we claim that the upper bound for the stopping time 
-should be reduced.
+Montrons alors le théorème~\ref{theo:tmps:mix} rappelé ci-dessous
+
+\theotpsmix*
+
+\begin{proof}
+Comme $\tau$ est positive, on peut appliquer l'inégalité de Markov:
+\[
+\P_X(\tau > t)\leq \frac{E[\tau]}{t}.
+\]
+
+En posant $t_n=32N^2+16N\ln (N+1)$, on obtient:  
+\[
+\P_X(\tau > t_n)\leq \frac{1}{4}.
+\] 
+
+
+D'après la définition de $t_{\rm mix}$ et d'après le théorème~\ref{thm-sst},
+on en déduit
+\[
+t_{\rm mix}\leq 32N^2+16N\ln (N+1)=O(N^2)
+\].
+\end{proof}