X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/rairo15.git/blobdiff_plain/8845f0ad0e1fda56b399e8c451712a1cd6b3afe4..e4f6e60e4d2af88e0e16f2d680cf4fe3725ea1fc:/stopping.tex diff --git a/stopping.tex b/stopping.tex index 19f1feb..25e458d 100644 --- a/stopping.tex +++ b/stopping.tex @@ -1,4 +1,81 @@ -This section considers functions $f: \Bool^n \rightarrow \Bool^n $ + + + +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{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}{3} \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 +\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 @@ -9,40 +86,49 @@ 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 -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\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.} +$$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 + +% $$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.} %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$. -\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 @@ -53,46 +139,45 @@ such that the distribution of $X_\tau$ is $\pi$: $$\P_X(X_\tau=Y)=\pi(Y).$$ -\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} +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} @@ -101,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. $$ @@ -128,23 +214,20 @@ $$ 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 \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