From: Jean-François Couchot <couchot@couchot.iut-bm.univ-fcomte.fr>
Date: Wed, 22 Jul 2015 10:45:26 +0000 (+0200)
Subject: stopping time jet 1
X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/hdrcouchot.git/commitdiff_plain/1042ddb8d08dc129da9358b73e723fc5014fb2c8

stopping time jet 1
---

diff --git a/11FCT.tex b/11FCT.tex
index 8ab511e..ffa5775 100644
--- a/11FCT.tex
+++ b/11FCT.tex
@@ -73,7 +73,7 @@ Alors, $\textsc{giu}(f)$ est fortement connexe.
 La preuve de ce théorème est donnée en annexe~\ref{anx:sccg}.
 
 Illustrons ce théorème par un exemple. On considère par le graphe d'interactions 
-$\Gamma(f)$ donné en figure~\ref{fig:G}. 
+$\Gamma(f)$ donné en figure~\ref{fig:Adrien:G}. 
 Il vérifie le théorème~\ref{th:Adrien}: 
 toutes les fonctions $f$ possédant un tel graphe d'interactions
 ont un graphe d'itérations  $\textsc{giu}(f)$ fortement connexe.
@@ -88,6 +88,6 @@ Deux fonctions sont equivalentes si leurs \textsc{giu} sont isomorphes
   \begin{center}
     \includegraphics[scale=0.5]{images/Gi.pdf}
   \end{center}
-\caption{Exemple de graphe d'interactions vérifiant le théorème~\ref{th:Adrien}} \label{fig:G}
+\caption{Exemple de graphe d'interactions vérifiant le théorème~\ref{th:Adrien}} \label{fig:Adrien:G}
 \end{figure}
 
diff --git a/14Secrypt.tex b/14Secrypt.tex
index d4f76f4..9de2b0d 100644
--- a/14Secrypt.tex
+++ b/14Secrypt.tex
@@ -380,18 +380,151 @@ pouvant être produits.  Les  cas 7 et 8 ne sont que  des bornes minimales basé
 sur des sous-ensembles des partitionnements possibles.
 
 \begin{table}[ht]
-  %\begin{center}
+  \begin{center}
     \begin{tabular}{|l|c|c|c|c|c|}
       \hline
       $n$              & 4 & 5 & 6    & 7      & 8      \\
       \hline
-      nb. de fonctions & 1 & 2 & 1332 & > 2300 & > 4500 \\
+      nb. de fonctions & 1 & 2 & 1332 & $>$ 2300 & $>$ 4500 \\
       \hline
     \end{tabular}
-  %\end{center}
-\caption{Nombre de générateurs selon le nombre de bits.}\label{table:nbFunc}
+  \end{center}
+\caption{Nombre de codes de Gray équilibrés selon le nombre de bits.}\label{table:nbFunc}
 \end{table}
 
 
+Ces fonctions étant générée, on s'intéresse à étudier à quelle vitesse 
+un générateur les embarquant converge vers la distribution uniforme.
+C'est l'objeftif de la section suivante. 
+
 \section{Quantifier l'écart par rapport à la distribution uniforme} 
-%15 Rairo
\ No newline at end of file
+On considère ici une fonction construite comme à la section précédente.
+On s'intéresse ici à étudier de manière théorique les 
+itérations définies à l'equation~(\ref{eq:asyn}) pour une 
+stratégie donnée.
+Tout d'abord, celles-ci peuvent être inerprétées comme une marche le long d'un 
+graphe d'itérations $\textsc{giu}(f)$ tel que le choix de tel ou tel arc est donné par la 
+stratégie.
+On remaque que ce graphe d'itération est toujours un sous graphe 
+du   ${\mathsf{N}}$-cube augmenté des 
+boucles sur chaque sommet, \textit{i.e.}, les arcs
+$(v,v)$ pour chaque $v \in \Bool^{\mathsf{N}}$. 
+Ainsi, le travail ci dessous répond à la question de 
+définir la longueur du chemin minimum dans ce graphe pour 
+obtenir une distribution uniforme.
+Ceci se base sur la théorie des chaînes de Markov.
+Pour une référence 
+générale à ce sujet on pourra se référer 
+au livre~\cite{LevinPeresWilmer2006},
+particulièrementau chapitre sur les temps d'arrêt.
+
+
+
+
+\begin{xpl}
+On considère par exemple le graphe $\textsc{giu}(f)$ donné à la 
+\textsc{Figure~\ref{fig:iteration:f*}.} et la fonction de 
+probabilités $p$ définie sur l'ensemble des arcs comme suit:
+$$
+p(e) \left\{
+\begin{array}{ll}
+= \frac{2}{3} \textrm{ si $e=(v,v)$ avec $v \in \Bool^3$,}\\
+= \frac{1}{6} \textrm{ sinon.}
+\end{array}
+\right.  
+$$
+La matrice $P$ de la chaine de Markov associée à  $f^*$ 
+est  
+\[
+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}
+
+
+
+
+Tout d'abord, soit $\pi$ et $\mu$ deux distributions sur 
+$\Bool^{\mathsf{N}}$. 
+La distance de \og totale variation\fg{} entre  $\pi$ et $\mu$ 
+est notée  $\tv{\pi-\mu}$ et est définie par 
+$$\tv{\pi-\mu}=\max_{A\subset \Bool^{\mathsf{N}}} |\pi(A)-\mu(A)|.$$ 
+On sait que 
+$$\tv{\pi-\mu}=\frac{1}{2}\sum_{X\in\Bool^{\mathsf{N}}}|\pi(X)-\mu(X)|.$$
+De plus, si 
+$\nu$ est une distribution on $\Bool^{\mathsf{N}}$, on a 
+$$\tv{\pi-\mu}\leq \tv{\pi-\nu}+\tv{\nu-\mu}.$$
+
+Soit $P$ une matrice d'une chaîne de Markovs sur $\Bool^{\mathsf{N}}$. 
+$P(X,\cdot)$ est la distribution induite par la  $X^{\textrm{ème}}$ colonne
+de  $P$. 
+Si la chaîne de  Markov induite par 
+$P$ a une  distribution stationnaire $\pi$, on définit alors 
+$$d(t)=\max_{X\in\Bool^{\mathsf{N}}}\tv{P^t(X,\cdot)-\pi}$$
+
+et
+
+$$t_{\rm mix}(\varepsilon)=\min\{t \mid d(t)\leq \varepsilon\}.$$
+
+Un résultat classique est
+
+$$t_{\rm mix}(\varepsilon)\leq \lceil\log_2(\varepsilon^{-1})\rceil t_{\rm mix}(\frac{1}{4})$$
+
+
+
+
+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$. 
+ 
+
+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 irreductible 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$.  On a les deux théorèmes suivants, dont les 
+démonstrations sont données en annexes~\ref{anx:generateur}.
+
+
+\begin{theorem}
+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}
+
+\begin{theorem} \label{prop:stop}
+If $\ov{h}$ is bijective et telle que if for every $X\in \Bool^{\mathsf{N}}$,
+$\ov{h}(\ov{h}(X))\neq X$, alors
+$E[\ts]\leq 8{\mathsf{N}}^2+ 4{\mathsf{N}}\ln ({\mathsf{N}}+1)$. 
+\end{theorem}
+
+Sans entrer dans les détails de la preuve, on remarque que le calcul 
+de cette borne ne tient pas en compte le fait qu'on préfère enlever des 
+chemins hamiltoniens équilibrés. 
+En intégrant cette contrainte, la borne supérieure pourraît être réduite.
diff --git a/15RairoGen.tex b/15RairoGen.tex
index 63eb23b..010beb9 100644
--- a/15RairoGen.tex
+++ b/15RairoGen.tex
@@ -700,7 +700,7 @@ Il n'est pas difficile de constater que $\textsc{giu}_{\{1\}}(f)$ est $\textsc{g
 
     \end{center}
     \caption{Graphes d'iterations $\textsc{giu}_{\mathcal{P}}(h)$ pour $h(x_1,x_2)=(\overline{x_1},x_1\overline{x_2}+\overline{x_1}x_2)$}
-    \label{fig:xplgraphIter}
+    %\label{fig:xplgraphIter}
   \end{figure}
 
 
diff --git a/annexePreuveStopping.tex b/annexePreuveStopping.tex
new file mode 100644
index 0000000..6bbd41f
--- /dev/null
+++ b/annexePreuveStopping.tex
@@ -0,0 +1,381 @@
+\section{Quantifier l'écart par rapport à la distribution uniforme} 
+%15 Rairo
+
+
+
+
+
+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
+
+$$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$. 
+ 
+
+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).$$
+
+A stopping time $\tau$ is a {\emph strong stationary time} if $X_{\tau}$ is
+independent of $\tau$. 
+
+
+\begin{theorem}
+If $\tau$ is a strong stationary time, then $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 
+${\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.
+
+
+
+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.
+
+We define the Markov matrix $P_h$ for each line $X$ and 
+each column $Y$  as follows:
+\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$}
+\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}}$,
+$\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}
+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 
+$\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 
+$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}$.
+\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)$,  
+$$
+\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.} 
+\end{array}\right.
+$$
+
+The Markov chain is thus defined as 
+$$
+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$.  
+ 
+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)$.
+
+
+\begin{lemma}
+The integer $\ts$ is a strong stationary time.
+\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}$).
+
+ 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}
+
+\begin{theorem} \label{prop:stop}
+If $\ov{h}$ is bijective and square-free, then
+$E[\ts]\leq 8{\mathsf{N}}^2+ 4{\mathsf{N}}\ln ({\mathsf{N}}+1)$. 
+\end{theorem}
+
+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}.$$
+
+
+\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.
+\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, 
+\begin{itemize}
+\item if $h(X)\neq \ell$, then
+$\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
+\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
+\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,
+$$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.
+\end{proof}
+
+Let $\ts^\prime$ be the time used to get all the bits but one fair.
+
+\begin{lemma}\label{lm:stopprime}
+One has $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,
+$\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}$.
+
+
+
+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 
+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}.$$
+
+But $\sum_{i=1}^{{\mathsf{N}}+1}\frac{1}{i}\leq 1+\ln({\mathsf{N}}+1)$. It follows that
+$1+\frac{1}{2}+\sum_{i=3}^{{\mathsf{N}}+1}\frac{1}{i}\leq 1+\ln({\mathsf{N}}+1).$
+Consequently,
+$E[\ts^\prime]\leq 
+4{\mathsf{N}} (-\frac{1}{2}+\ln({\mathsf{N}}+1))\leq 
+4{\mathsf{N}}\ln({\mathsf{N}}+1)$.
+\end{proof}
+
+One can now prove Theorem~\ref{prop:stop}.
+
+\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}.
+\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.
diff --git a/main.tex b/main.tex
index 658149c..071ab50 100644
--- a/main.tex
+++ b/main.tex
@@ -34,7 +34,8 @@
  
 %%--------------------
 %% Set the author of the HDR
-\addauthor[first.name@utbm.fr]{First}{Name}
+\addauthor[couchot@femto-st.fr]{Jean-François}{Couchot}
+
  
 %%--------------------
 %% Add a member of the jury
@@ -123,6 +124,15 @@
 \newcommand{\dom}[0]{\ensuremath{\textit{dom}}}
  \newcommand{\eqNode}[0]{\ensuremath{{\mathcal{R}}}}
 
+
+\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}}
+
+
 \newtheorem{theorem}{Théorème}
 \newtheorem{lemma}{Lemme}
 \newtheorem{corollary}{Corollaire}
@@ -215,7 +225,7 @@ On montre qu'on a des résultats similaires.
 \input{14Secrypt}
 
 
-
+\chapter{Quelques expérimentations}
 
 
 
@@ -301,6 +311,7 @@ pourrait étendre, ce que l'on a déjà, ce qu'il reste à faire.
 
 \chapter{Preuves sur les générateurs de nombres pseudo-aléatoires}\label{anx:generateur}
 \input{annexePreuveDistribution}
+\input{annexePreuveStopping}
 
 \backmatter
 
diff --git a/modelchecking.tex b/modelchecking.tex
index 6f968bb..0ee325e 100644
--- a/modelchecking.tex
+++ b/modelchecking.tex
@@ -69,7 +69,7 @@ sont ensuite fournies (\Sec{sec:spin:practical}).
     \hfill
     \subfigure[Graphe d'intéraction]{
       \includegraphics[width=4cm]{images/xplCnxMc.eps}
-      \label{fig:xplgraph}
+      \label{fig:xplgraph:inter:mc}
     }
   \end{center}
   \caption{Exemple pour SDD $\approx$ SPIN.}
@@ -82,7 +82,7 @@ sont ensuite fournies (\Sec{sec:spin:practical}).
   Chaque configuration est ainsi un élement de $\Bool^3$, \textit{i.e.}, 
   un nombre entre 0 et 7. 
   La \Fig{fig:map} précise la fonction $f$ considérée et 
-  la \Fig{fig:xplgraph} donne son graphe d'intéraction.
+  la \Fig{fig:xplgraph:inter:mc} donne son graphe d'intéraction.