$$
p(e) \left\{
\begin{array}{ll}
-= \frac{1}{3} \textrm{ if $e=(v,v)$ with $v \in \Bool^3$,}\\
-= \frac{1}{3} \textrm{ otherwise.}
+= \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}{3} \left(
+P=\dfrac{1}{6} \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
+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)
\]
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.
and
$$t_{\rm mix}(\varepsilon)=\min\{t \mid d(t)\leq \varepsilon\}.$$
-% One can prove that
+One can prove that
-% $$t_{\rm mix}(\varepsilon)\leq \lceil\log_2(\varepsilon^{-1})\rceil t_{\rm mix}(\frac{1}{4})$$
+$$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.}
+% 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?}
+% 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})$$
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{Theo}
+\begin{thrm}
If $\tau$ is a strong stationary time, then $d(t)\leq \max_{X\in\Bool^{\mathsf{N}}}
\P_X(\tau > t)$.
-\end{Theo}
+\end{thrm}
%Let $\Bool^n$ be the set of words of length $n$.
We define the Markov matrix $P_h$ for each line $X$ and
each column $Y$ as follows:
-$$\left\{
+\begin{equation}
+\left\{
\begin{array}{ll}
-P_h(X,X)=\frac{1}{{\mathsf{N}}} & \\
+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}{{\mathsf{N}}} & \textrm{if $X\neq Y$ and $(X,Y) \in 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}} $,
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}
+\begin{lmm}\label{lm:h}
If $\ov{h}$ is bijective and square-free, then $h(\ov{h}^{-1}(X))\neq h(X)$.
-\end{Lemma}
+\end{lmm}
\begin{proof}
Let $\ov{h}$ be bijective.
\end{proof}
Let $Z$ be a random variable that is uniformly distributed over
-$\llbracket 1, {\mathsf{N}}$.
+$\llbracket 1, {\mathsf{N}} \rrbracket \times \Bool$.
For $X\in \Bool^{\mathsf{N}}$, we
-define, with $Z=i$,
+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\oplus (0^{{\mathsf{N}}-i}10^{i-1}) & \text{if $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.
$$
-%%%%%%%%%%%%%%%%%%%%%%%%%%%ù
+%%%%%%%%%%%%%%%%%%%%%%%%%%%ù
%\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$ and $h(X_j)\neq \ell$.
-In other words, there exist a date $j$ before $t$ where
-the random variable $Z$ is $l$
+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$.
the Markov chain $(X_t)$.
-\begin{Lemma}
+\begin{lmm}
The integer $\ts$ is a strong stationary time.
-\end{Lemma}
+\end{lmm}
\begin{proof}
Let $\tau_\ell$ be the first time that $\ell$ is fair. The random variable
-$Z_{\tau_\ell}$ is of the form $\ell$ %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
+$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}$).
$\ell$-th bit of $X_t$ is $0$ or $1$ with the same probability, proving the
lemma.\end{proof}
-\begin{Theo} \label{prop:stop}
+\begin{thrm} \label{prop:stop}
If $\ov{h}$ is bijective and square-free, then
-$E[\ts]\leq {\mathsf{N}}^2+ (\mathsf{N}+2)(\ln(\mathsf{N})+2)$.
-\end{Theo}
+$E[\ts]\leq 8{\mathsf{N}}^2+ 4{\mathsf{N}}\ln ({\mathsf{N}}+1)$.
+\end{thrm}
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}.$$
+$$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}
-If $\ov{h}$ is a square-free bijective function, then the inequality
-$E[\lambda_h]\leq 2{\mathsf{N}}^2$ is established.
-\end{Lemma}
+\begin{lmm}\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{lmm}
\begin{proof}
-For every $X$, every $\ell$, one has $\P(S_{X,\ell}\leq 2)\geq
-\frac{1}{{\mathsf{N}}^2}$.
+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}{{\mathsf{N}}}\geq \frac{1}{{\mathsf{N}}^2}$.
+$\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}{N}$). And in
+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}{{\mathsf{N}}}$. Now, by Lemma~\ref{lm:h},
+$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}{{\mathsf{N}}}$, proving that $\P(S_{x,\ell}\leq 2)\geq
-\frac{1}{{\mathsf{N}}^2}$.
+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}{{\mathsf{N}}^2}$. By induction, one
+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}{{\mathsf{N}}^2}\right)^i$.
+\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).$$
\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}{{\mathsf{N}}^2}\right)^i=2+2({\mathsf{N}}^2-1)=2{\mathsf{N}}^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 ${\mathsf{N}}-1$ fair
-elements.
+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 (\mathsf{N}+2)(\ln(\mathsf{N})+2)$.
-\end{Lemma}
+\begin{lmm}\label{lm:stopprime}
+One has $E[\ts^\prime]\leq 4{\mathsf{N}} \ln ({\mathsf{N}}+1).$
+\end{lmm}
\begin{proof}
-This is a classical Coupon Collector's like problem. Let $W_i$
-be the time to obtain the $i$-th fair bit
-after $i-1$ fair bits have been obtained.
-One has $\ts^\prime=\sum_{i=1}^{{\mathsf{N}}}W_i$.
-
-At position $X$ with $i-1$ fair bits,
-we do not obtain a new fair if $Z$ is one of the $i-1$ already fair bits
-or if $Z$ is a new fair bit but $h(X)$ is $Z$.
-This occures with probability
-$p
-= \frac{i-1}{{\mathsf{N}}} + \frac{n-i+1}{\mathsf{N}}.\frac{1}{\mathsf{N}}
-=\frac{i(\mathsf{N}-1) +1}{\mathsf{N^2}}
-$.
-The random variable $W_i$ has a geometric distribution
-\textit{i.e.}, $P(W_i = k) = p^{k-1}.(1-p)$ and
-$E(W_i) = \frac{\mathsf{N^2}}{i(\mathsf{N}-1) +1}$.
-Therefore
-$$E[\ts^\prime]=\sum_{i=1}^{{\mathsf{N}}}E[W_i]
-=\frac{\mathsf{N^2}}{\mathsf{N}(\mathsf{N}-1) +1} + \sum_{i=1}^{{\mathsf{N}}-1}E[W_i].$$
-
-A simple study of the function $\mathsf{N} \mapsto \frac{\mathsf{N^2}}{\mathsf{N}(\mathsf{N}-1) +1}$ shows that it is bounded by $\frac{4}{3} \leq 2$.
-For the second term, we successively have
-$$
-\sum_{i=1}^{{\mathsf{N}}-1}E[W_i]
-= \mathsf{N}^2\sum_{i=1}^{{\mathsf{N}}-1} \frac{1}{i(\mathsf{N}-1) +1}
-\leq \mathsf{N}^2\sum_{i=1}^{{\mathsf{N}}-1} \frac{1}{i(\mathsf{N}-1)}
-\leq \frac{\mathsf{N}^2}{\mathsf{N}-1}\sum_{i=1}^{{\mathsf{N}}-1} \frac{1}{i}
-\leq (\mathsf{N}+2)\sum_{i=1}^{{\mathsf{N}}-1} \frac{1}{i}
-$$
+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 is well known that
-$\sum_{i=1}^{{\mathsf{N}}-1}\frac{1}{i}\leq 1+\ln({\mathsf{N}}-1)$.
-It follows that
-$2+(\mathsf{N}+2)\sum_{i=1}^{{\mathsf{N}}-1}\frac{1}{i}
-\leq
-2+(\mathsf{N}+2)(\ln(\mathsf{N}-1)+1)
-\leq
-(\mathsf{N}+2)(\ln(\mathsf{N})+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}
-One has $\ts\leq \ts^\prime+\lambda_h$. Therefore,
+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
+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.
