X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/rairo15.git/blobdiff_plain/07a05f881830e54c344db7060dfbfd74220d0eec..935ffe48008761ee21d78930849f51e32c62fcec:/stopping.tex?ds=sidebyside diff --git a/stopping.tex b/stopping.tex index 96fd41b..faab606 100644 --- a/stopping.tex +++ b/stopping.tex @@ -20,23 +20,23 @@ 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.} += \frac{1}{3} \textrm{ if $e=(v,v)$ with $v \in \Bool^3$,}\\ += \frac{1}{3} \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( +P=\dfrac{1}{3} \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 +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 \end{array} \right) \] @@ -75,7 +75,7 @@ P=\dfrac{1}{6} \left( -This section considers functions $f: \Bool^n \rightarrow \Bool^n $ +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 @@ -86,45 +86,45 @@ which is sufficient to follow to get a uniform distribution. -First of all, let $\pi$, $\mu$ be two distributions on $\Bool^n$. The total +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^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}=\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^n$. $P(X,\cdot)$ is the +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^n}\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\}.$$ -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})$$ -Let $(X_t)_{t\in \mathbb{N}}$ be a sequence of $\Bool^n$ 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 -(\Bool^n)^{t+1}$ such that $\{\tau=t\}=\{(X_0,X_1,\ldots,X_t)\in B_t\}$. +(\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$. @@ -140,44 +140,44 @@ $$\P_X(X_\tau=Y)=\pi(Y).$$ \begin{Theo} -If $\tau$ is a strong stationary time, then $d(t)\leq \max_{X\in\Bool^n} +If $\tau$ is a strong stationary time, then $d(t)\leq \max_{X\in\Bool^{\mathsf{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^*\}$. +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 -$n$-cube. -Let $h$ be a function from $\Bool^n$ into $\llbracket 1, n \rrbracket$. +${\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^n$ which edge is removed in the Hamiltonian cycle, -\textit{i.e.} which bit in $\llbracket 1, n \rrbracket$ +$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^{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$ +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: $$\left\{ \begin{array}{ll} -P_h(X,X)=\frac{1}{2}+\frac{1}{2n} & \\ +P_h(X,X)=\frac{1}{{\mathsf{N}}} & \\ 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,Y)=\frac{1}{{\mathsf{N}}} & \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$, +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} @@ -186,24 +186,25 @@ If $\ov{h}$ is bijective and square-free, then $h(\ov{h}^{-1}(X))\neq h(X)$. \begin{proof} Let $\ov{h}$ be bijective. -Let $k\in \llbracket 1, n \rrbracket$ s.t. $h(\ov{h}^{-1}(X))=k$. +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^{n-k}10^{k-1}$. +$\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^{n-h(X)}10^{h(X)-1} = 0^{n-k}10^{k-1}$. +$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, n \rrbracket \times \Bool$. -For $X\in \Bool^n$, we -define, with $Z=(i,b)$, +$\llbracket 1, {\mathsf{N}}$. +For $X\in \Bool^{\mathsf{N}}$, we +define, with $Z=i$, $$ \left\{ \begin{array}{ll} -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\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& \text{otherwise.} \end{array}\right. $$ @@ -215,18 +216,18 @@ $$ -%%%%%%%%%%%%%%%%%%%%%%%%%%%ù +%%%%%%%%%%%%%%%%%%%%%%%%%%%ù %\section{Stopping time} -An integer $\ell\in \llbracket 1,n \rrbracket$ is said {\it fair} +An integer $\ell\in \llbracket 1,{\mathsf{N}} \rrbracket$ is said {\it fair} at time $t$ if there -exists $0\leq j