From 3820ec6286eab552baad3b3d7c0451e1bbc42482 Mon Sep 17 00:00:00 2001
From: couchot <jf.couchot@gmail.com>
Date: Fri, 20 Feb 2015 10:11:30 +0100
Subject: [PATCH 1/1] modif Sxl
---
stopping.tex | 152 +++++++++++++++++++++++++++++----------------------
1 file changed, 87 insertions(+), 65 deletions(-)
diff --git a/stopping.tex b/stopping.tex
index 9309221..567ab01 100644
--- a/stopping.tex
+++ b/stopping.tex
@@ -13,14 +13,14 @@ First of all, let $\pi$, $\mu$ be two distributions 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
+$$\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}.$$
+$$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.}
@@ -48,86 +48,103 @@ 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$),
+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).$$
-\JFC{Ou ceci a-t-il ete prouvé}
+\JFC{Ou ceci a-t-il ete prouvé. On ne définit pas ce qu'est un strong stationary time.}
\begin{Theo}
-If $\tau$ is a strong stationary time, then $d(t)\leq \max_{x\in\Bool^n}
-\P_x(\tau > t)$.
+If $\tau$ is a strong stationary time, then $d(t)\leq \max_{X\in\Bool^n}
+\P_X(\tau > t)$.
\end{Theo}
%Let $\Bool^n$ be the set of words of length $n$.
-Let $E=\{(x,y)\mid
-x\in \Bool^n, y\in \Bool^n,\ x=y \text{ or } x\oplus y \in 0^*10^*\}$.
+Let $E=\{(X,Y)\mid
+X\in \Bool^n, Y\in \Bool^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
$n$-cube.
Let $h$ be a function from $\Bool^n$ into $\llbracket 1, n \rrbracket$.
Intuitively speaking $h$ aims at memorizing for each node
-$x \in \Bool^n$ which edge is removed in the Hamiltonian cycle,
+$X \in \Bool^n$ which edge is removed in the Hamiltonian cycle,
\textit{i.e.} which bit in $\llbracket 1, n \rrbracket$
cannot be switched.
-We denote by $E_h$ the set $E\setminus\{(x,y)\mid x\oplus y =
-0^{n-h(x)}10^{h(x)-1}\}$. This is the set of the modified hypercube,
+We denote by $E_h$ the set $E\setminus\{(X,Y)\mid X\oplus Y =
+0^{n-h(X)}10^{h(X)-1}\}$. This is the set of the modified hypercube,
\textit{i.e.}, the $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:
+We define the Markov matrix $P_h$ for each line $X$ and
+each column $Y$ as follows:
$$\left\{
\begin{array}{ll}
-P_h(x,x)=\frac{1}{2}+\frac{1}{2n} & \\
-P_h(x,y)=0 & \textrm{if $(x,y)\notin E_h$}\\
-P_h(x,y)=\frac{1}{2n} & \textrm{if $x\neq y$ and $(x,y) \in E_h$}
+P_h(X,X)=\frac{1}{2}+\frac{1}{2n} & \\
+P_h(X,Y)=0 & \textrm{if $(X,Y)\notin E_h$}\\
+P_h(X,Y)=\frac{1}{2n} & \textrm{if $X\neq Y$ and $(X,Y) \in E_h$}
\end{array}
\right.
$$
We denote by $\ov{h} : \Bool^n \rightarrow \Bool^n$ the function
-such that for any $x \in \Bool^n $,
-$(x,\ov{h}(x)) \in E$ and $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 \Bool^n$,
-$\ov{h}(\ov{h}(x))\neq x$.
+such that for any $X \in \Bool^n $,
+$(X,\ov{h}(X)) \in E$ and $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 \Bool^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)$.
+If $\ov{h}$ is bijective and square-free, then $h(\ov{h}^{-1}(X))\neq h(X)$.
\end{Lemma}
-\begin{Proof}
-\JFC{ecrire la preuve}
-\end{Proof}
+\begin{proof}
+Let $\ov{h}$ be bijective.
+Let $k\in \llbracket 1, 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^{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^{n-h(X)}10^{h(X)-1} = 0^{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
-$\llbracket 1, n \rrbracket \times\{0,1\}$ uniformly distributed.
- For $X\in \Bool^n$, we
-define, with $Z=(i,x)$,
+Let $Z$ be a random variable that is uniformly distributed over
+$\llbracket 1, n \rrbracket \times \Bool$.
+For $X\in \Bool^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^{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)
+$$
+The pair $(f,Z)$ is a random mapping representation of $P_h$.
+\JFC{interet de la phrase precedente}
%%%%%%%%%%%%%%%%%%%%%%%%%%%ù
-\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,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, n \rrbracket$
are fair. The integer $\ts$ is a randomized stopping time for
the Markov chain $(X_t)$.
@@ -138,10 +155,13 @@ The integer $\ts$ is a strong stationary time.
\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 symmetry, for $t\geq \tau_\ell$, the
+bit of $X_{\tau_\ell}$
+is $0$ or $1$ with the same probability ($\frac{1}{2}$).
+By symmetry, \JFC{Je ne comprends pas ce by symetry} 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}
@@ -151,13 +171,15 @@ If $\ov{h}$ is bijective and square-free, then
$E[\ts]\leq 8n^2+ n\ln (n+1)$.
\end{Theo}
-For each $x\in \Bool^n$ 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
+For each $X\in \Bool^n$ and $\ell\in\llbracket 1,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 \{m \geq 1\mid h(X_m)\neq \ell\text{ and }Z_m=\ell\text{ and } X_0=x\}.$$
+$$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}
@@ -165,27 +187,27 @@ If $\ov{h}$ is a square-free bijective function, then one has $E[\lambda_h]\leq
\end{Lemma}
\begin{proof}
-For every $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$.
-Therefore $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
+For every $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$.
+Therefore $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$.
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]{}, 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).$$
Consequently,
-$$E[S_{x,\ell}]\leq 1+2
+$$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,$$
which concludes the proof.
\end{proof}
@@ -201,9 +223,9 @@ One has $E[\ts^\prime]\leq n \ln (n+1).$
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
+ 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}.$$
--
2.39.5