From: Jean-François Couchot Date: Wed, 18 Feb 2015 16:29:58 +0000 (+0100) Subject: relecture preuve PCH X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/rairo15.git/commitdiff_plain/28e2670bed58d41eddd7820a3c86f9eef9870c33 relecture preuve PCH --- diff --git a/main.tex b/main.tex index e10eba4..bc8bb20 100644 --- a/main.tex +++ b/main.tex @@ -126,7 +126,7 @@ may be updated at each iteration. At the theoretical level, we show that -\section{Stopping Time} +\section{Random walk on the modified Hypercube} \input{stopping} % Donner la borne du stopping time quand on marche dedans (nouveau). diff --git a/preliminaries.tex b/preliminaries.tex index de77e12..9441aab 100644 --- a/preliminaries.tex +++ b/preliminaries.tex @@ -94,57 +94,6 @@ P=\dfrac{1}{6} \left( \end{xpl} - -More generally, let $\pi$, $\mu$ be two distribution 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 -$\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}.$$ -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^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\}$. -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$. - - -\JFC{Je ne comprends pas la definition de randomized stopping time, Peut-on enrichir ?} - -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).$$ - - -\JFC{Ou ceci a-t-il ete prouvé} -\begin{Theo} -If $\tau$ is a strong stationary time, then $d(t)\leq \max_{x\in\Bool^n} -\P_x(\tau > t)$. -\end{Theo} - % % 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: diff --git a/stopping.tex b/stopping.tex index 0a1dbe2..9309221 100644 --- a/stopping.tex +++ b/stopping.tex @@ -1,36 +1,98 @@ +This section considers functions $f: \Bool^n \rightarrow \Bool^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^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 +$\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}.$$ +It is known that $d(t+1)\leq d(t)$. \JFC{references ? Cela a-t-il +un intérêt dans la preuve ensuite.} -%% 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\}$. -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\section{Random walk on the modified Hypercube} +%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^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^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$. + + +\JFC{Je ne comprends pas la definition de randomized stopping time, Peut-on enrichir ?} + +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).$$ + + +\JFC{Ou ceci a-t-il ete prouvé} +\begin{Theo} +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^*\}$. +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, +\textit{i.e.} which bit in $\llbracket 1, n \rrbracket$ +cannot be switched. -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: +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: $$\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}\\ - +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}$ 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$, +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$. \begin{Lemma}\label{lm:h} @@ -38,16 +100,17 @@ 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} Let $Z$ be a random variable over -$\{1,\ldots,N\}\times\{0,1\}$ uniformaly distributed. For $X\in \Omega$, we +$\llbracket 1, n \rrbracket \times\{0,1\}$ uniformly distributed. + For $X\in \Bool^n$, we define, with $Z=(i,x)$, $$ \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 } x=1 \text{ and } i\neq h(X),\\ f(X,Z)=X& \text{otherwise.} \end{array}\right. $$ @@ -60,17 +123,17 @@ The pair $f,Z$ is a random mapping representation of $P_h$. %%%%%%%%%%%%%%%%%%%%%%%%%%%ù \section{Stopping time} -An integer $\ell\in\{1,\ldots,N\}$ is said {\it fair} at time $t$ if there +An integer $\ell\in\{1,\ldots,n\}$ is said {\it fair} at time $t$ if there exists $0\leq j