X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/rairo15.git/blobdiff_plain/586298b57c6e1cec5566bbe692ac21c4c701fd51..7dd748e9a068c99c61fefdcbde3c24e4c9b74bf9:/stopping.tex
diff --git a/stopping.tex b/stopping.tex
index 5bf7425..d3b4f4d 100644
--- a/stopping.tex
+++ b/stopping.tex
@@ -1,95 +1,104 @@
-\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
+
+
+
+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.
+
+
+
+
+
+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 \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}=\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 $\Omega$. $P(x,\cdot)$ is the
-distribution induced by the $x$-th row of $P$. If the markov chain induced by
+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\Omega}\tv{P^t(x,\cdot)-\pi},$$
+$$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\}.$$
@@ -97,184 +106,251 @@ 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\}$.
+
+% 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 $\Omega$ valued random
+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
-\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$),
+(\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).$$
+$$\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}
+\begin{Theo}
+If $\tau$ is a strong stationary time, then $d(t)\leq \max_{X\in\Bool^{\mathsf{N}}}
+\P_X(\tau > t)$.
+\end{Theo}
-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}\\
+%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}$ 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$.
+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{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 over
-$\{1,\ldots,N\}\times\{0,1\}$ uniformaly distributed. For $X\in \Omega$, we
-define, with $Z=(i,x)$,
+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^{N-i}10^{i-1}) & \text{if } x=1 \text{ and } i\neq h(X),\\
+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 pair $f,Z$ is a random mapping representation of $P_h$.
-
+The Markov chain is thus defined as
+$$
+X_t= f(X_{t-1},Z_t)
+$$
%%%%%%%%%%%%%%%%%%%%%%%%%%%ù
-\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$.
-
+%\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 $\{1,\ldots,N\}$
+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)$.
+the Markov chain $(X_t)$.
-\begin{lemma}
-The integer $\ts$ is a strong stationnary time.
-\end{lemma}
+\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-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
+$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 $\delta$. By symetry, for $t\geq \tau_\ell$, the
+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}
+lemma.\end{proof}
-\begin{proposition} \label{prop:stop}
+\begin{Theo} \label{prop:stop}
If $\ov{h}$ is bijective and square-free, then
-$E[\ts]\leq 8N^2+ N\ln (N+1)$.
-\end{proposition}
+$E[\ts]\leq 8{\mathsf{N}}^2+ {\mathsf{N}}\ln ({\mathsf{N}}+1)$.
+\end{Theo}
-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\}.$$
+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}.$$
+$$\lambda_h=\max_{X,\ell} S_{X,\ell}.$$
+
+\begin{Lemma}\label{prop:lambda}
+If $\ov{h}$ is a square-free bijective function, then the inequality
+$E[\lambda_h]\leq 8{\mathsf{N}}^2$ is established.
-\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}
+\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$.
+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, intutively, 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]{}, 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).$$
+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+2
-\sum_{i=1}^{+\infty}\left(1-\frac{1}{4N^2}\right)^i=1+2(4N^2-1)=8N^2-2,$$
+$$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 first time that there are exactly $N-1$ fair
+Let $\ts^\prime$ be the first time that there are exactly ${\mathsf{N}}-1$ fair
elements.
-\begin{lemma}\label{lm:stopprime}
-One has $E[\ts^\prime]\leq N \ln (N+1).$
-\end{lemma}
+\begin{Lemma}\label{lm:stopprime}
+One has $E[\ts^\prime]\leq {\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}^{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).$
+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. It follows that
+$E[W_i]\leq \frac{{\mathsf{N}}}{{\mathsf{N}}-i+2}$. Therefore
+$$E[\ts^\prime]=\sum_{i=1}^{{\mathsf{N}}-1}E[W_i]\leq {\mathsf{N}}\sum_{i=1}^{{\mathsf{N}}-1}
+ \frac{1}{{\mathsf{N}}-i+2}={\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 N (-\frac{1}{2}+\ln(N+1))\leq N\ln(N+1)$.
+$E[\ts^\prime]\leq {\mathsf{N}} (-\frac{1}{2}+\ln({\mathsf{N}}+1))\leq {\mathsf{N}}\ln({\mathsf{N}}+1)$.
\end{proof}
-One can now prove Proposition~\ref{prop:stop}.
+One can now prove Theorem~\ref{prop:stop}.
\begin{proof}
One has $\ts\leq \ts^\prime+\lambda_h$. Therefore,
-Proposition~\ref{prop:stop} is a direct application of
+Theorem~\ref{prop:stop} is a direct application of
lemma~\ref{prop:lambda} and~\ref{lm:stopprime}.
\end{proof}
-\end{document}
+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.