From: couchot Date: Tue, 17 Feb 2015 15:44:00 +0000 (+0100) Subject: tw X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/rairo15.git/commitdiff_plain/49ca2ad778013ab14ba1e6f9ab70697a97557e26 tw --- diff --git a/main.tex b/main.tex index 6dbf3ef..4bbcc0e 100644 --- a/main.tex +++ b/main.tex @@ -61,16 +61,16 @@ % \theoremsymbol{\ensuremath{\diamondsuit}} % \theoremprework{\bigskip} % \theoremseparator{.} -\newtheorem{Def}{\underline{Définition}} -\newtheorem{Lemma}{\underline{Lemme}} -\newtheorem{Theo}{\underline{Théorème}} +\newtheorem{Def}{\underline{Definition}} +\newtheorem{Lemma}{\underline{Lemma}} +\newtheorem{Theo}{\underline{Theorem}} % \theoremheaderfont{\sc} % \theorembodyfont{\upshape} % \theoremstyle{nonumberplain} % \theoremseparator{} % \theoremsymbol{\rule{1ex}{1ex}} -\newtheorem{Proof}{Preuve :} -\newtheorem{xpl}{Exemple illustratif :} +\newtheorem{Proof}{Proof} +\newtheorem{xpl}{Running Example} \newcommand{\vectornorm}[1]{\ensuremath{\left|\left|#1\right|\right|_2}} %\newcommand{\ie}{\textit{i.e.}} diff --git a/preliminaries.tex b/preliminaries.tex index 8f7774a..3b559b1 100644 --- a/preliminaries.tex +++ b/preliminaries.tex @@ -9,8 +9,9 @@ to itself such that $x=(x_1,\dots,x_n)$ maps to $f(x)=(f_1(x),\dots,f_n(x))$. Functions are iterated as follows. -At the $t^{th}$ iteration, only the $s_{t}-$th component is -``iterated'', where $s = \left(s_t\right)_{t \in \mathds{N}}$ is a sequence of indices taken in $\llbracket 1;n \rrbracket$ called ``strategy''. Formally, +At the $t^{th}$ iteration, only the $s_{t}-$th component is said to be +``iterated'', where $s = \left(s_t\right)_{t \in \mathds{N}}$ is a sequence of indices taken in $\llbracket 1;n \rrbracket$ called ``strategy''. +Formally, let $F_f: \llbracket1;n\rrbracket\times \Bool^{n}$ to $\Bool^n$ be defined by \[ F_f(i,x)=(x_1,\dots,x_{i-1},f_i(x),x_{i+1},\dots,x_n). @@ -75,22 +76,76 @@ Figure~\ref{fig:iteration:f*}. % \] %\end{xpl} +Let thus be given such kind of map. +This article focusses 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 +$n$-cube augemented with all the self-loop, \textit{i.e.}, all the +edges $(v,v)$ for any $v \in \Bool^n$. +Next, if we add probabilities on the transition graph, iterations can be +interpreted as Markov chains. -It is usual to check whether rows of such kind of matrices -converge to a specific -distribution. -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 -$\Omega$ by: -$$\tv{\pi-\mu}=\max_{A\subset \Omega} |\pi(A)-\mu(A)|.$$ + + + +Let $\pi$, $\mu$ be two distribution on a same set $\Omega$. The total +variation distance between $\pi$ and $\mu$ is denoted $\tv{\pi-\mu}$ and is +defined by +$$\tv{\pi-\mu}=\max_{A\subset \Omega} |\pi(A)-\mu(A)|.$$ It is known that +$$\tv{\pi-\mu}=\frac{1}{2}\sum_{x\in\Omega}|\pi(x)-\mu(x)|.$$ Moreover, if +$\nu$ is a distribution on $\Omega$, one has +$$\tv{\pi-\mu}\leq \tv{\pi-\nu}+\tv{\nu-\mu}$$ + +Let $P$ be the matrix of a markov chain on $\Omega$. $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\Omega}\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)$. + + + +Let $(X_t)_{t\in \mathbb{N}}$ be a sequence of $\Omega$ 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\}$. + +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}}$. It he markov chain is irreductible and has $\pi$ +as stationary distribution, then a {\it stationay time} $\tau$ is a +randomized stopping time (possibily 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\Omega} +\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 +% $\Omega$ by: +% $$\tv{\pi-\mu}=\max_{A\subset \Omega} |\pi(A)-\mu(A)|.$$ % It is known that % $$\tv{\pi-\mu}=\frac{1}{2}\sum_{x\in\Omega}|\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\Omega}\tv{M^t(x,\cdot)-\pi}.$$ +% 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\Omega}\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. diff --git a/stopping.tex b/stopping.tex index 5bf7425..0a1dbe2 100644 --- a/stopping.tex +++ b/stopping.tex @@ -1,103 +1,3 @@ -\documentclass{article} -%\usepackage{prentcsmacro} -%\sloppy -\usepackage[a4paper]{geometry} -\geometry{hmargin=3cm, vmargin=3cm } - -\usepackage[latin1]{inputenc} -\usepackage[T1]{fontenc} -\usepackage[english]{babel} -\usepackage{amsmath,amssymb,latexsym,eufrak,euscript} -\usepackage{subfigure,pstricks,pst-node,pst-coil} - - -\usepackage{url,tikz} -\usepackage{pgflibrarysnakes} - -\usepackage{multicol} - -\usetikzlibrary{arrows} -\usetikzlibrary{automata} -\usetikzlibrary{snakes} -\usetikzlibrary{shapes} - -%% \setlength{\oddsidemargin}{15mm} -%% \setlength{\evensidemargin}{15mm} \setlength{\textwidth}{140mm} -%% \setlength{\textheight}{219mm} \setlength{\topmargin}{5mm} -\newtheorem{theorem}{Theorem} -%\newtheorem{definition}[theorem]{Definition} -% %\newtheorem{defis}[thm]{D\'efinitions} - \newtheorem{example}[theorem]{Example} -% %\newtheorem{Exes}[thm]{Exemples} -\newtheorem{lemma}[theorem]{Lemma} -\newtheorem{proposition}[theorem]{Proposition} -\newtheorem{construction}[theorem]{Construction} -\newtheorem{corollary}[theorem]{Corollary} -% \newtheorem{algor}[thm]{Algorithm} -%\newtheorem{propdef}[thm]{Proposition-D\'efinition} -\newcommand{\mlabel}[1]{\label{#1}\marginpar{\fbox{#1}}} -\newcommand{\flsup}[1]{\stackrel{#1}{\longrightarrow}} - -\newcommand{\stirlingtwo}[2]{\genfrac{\lbrace}{\rbrace}{0pt}{}{#1}{#2}} -\newcommand{\stirlingone}[2]{\genfrac{\lbrack}{\rbrack}{0pt}{}{#1}{#2}} - -\newenvironment{algo} -{ \vspace{1em} -\begin{algor}\mbox -\newline \vspace{-0.1em} -\begin{quote}\begin{rm}} -{\end{rm}\end{quote}\end{algor}\vspace{-1.5em}\vspace{2em}} -%\null \hfill $\diamondsuit$ \par\medskip \vspace{1em}} - -\newenvironment{exe} -{\begin{example}\rm } -{\end{example} -%\vspace*{-1.5em} -%\null \hfill $\triangledown$ \par\medskip} -%\null \hfill $\triangledown$ \par\medskip \vspace{1em}} -} - - -\newenvironment{proof} -{ \noindent {\sc Proof.\/} } -{\null \hfill $\Box$ \par\medskip \vspace{1em}} - - - -\newcommand {\tv}[1] {\lVert #1 \rVert_{\rm TV}} -\def \top {1.8} -\def \topt {2.3} -\def \P {\mathbb{P}} -\def \ov {\overline} -\def \ts {\tau_{\rm stop}} -\begin{document} -\label{firstpage} - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\section{Mathematical Backgroung} - - - -Let $\pi$, $\mu$ be two distribution on a same set $\Omega$. The total -variation distance between $\pi$ and $\mu$ is denoted $\tv{\pi-\mu}$ and is -defined by -$$\tv{\pi-\mu}=\max_{A\subset \Omega} |\pi(A)-\mu(A)|.$$ It is known that -$$\tv{\pi-\mu}=\frac{1}{2}\sum_{x\in\Omega}|\pi(x)-\mu(x)|.$$ Moreover, if -$\nu$ is a distribution on $\Omega$, one has -$$\tv{\pi-\mu}\leq \tv{\pi-\nu}+\tv{\nu-\mu}$$ - -Let $P$ be the matrix of a markov chain on $\Omega$. $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\Omega}\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)$. %% A {\it coupling} with transition matrix $P$ is a process $(X_t,Y_t)_{t\geq 0}$ @@ -108,24 +8,6 @@ It is known that $d(t+1)\leq d(t)$. %% with $\tau_{\rm couple}=\min_t\{X_t=Y_t\}$. -Let $(X_t)_{t\in \mathbb{N}}$ be a sequence of $\Omega$ 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\}$. - -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}}$. It he markov chain is irreductible and has $\pi$ -as stationary distribution, then a {\it stationay time} $\tau$ is a -randomized stopping time (possibily depending on the starting position $x$), -such that the distribution of $X_\tau$ is $\pi$: -$$\P_x(X_\tau=y)=\pi(y).$$ - -\begin{proposition} -If $\tau$ is a strong stationary time, then $d(t)\leq \max_{x\in\Omega} -\P_x(\tau > t)$. -\end{proposition} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Random walk on the modified Hypercube} @@ -151,13 +33,13 @@ 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$, $\ov{h}(\ov{h}(x))\neq x$. -\begin{lemma}\label{lm:h} +\begin{Lemma}\label{lm:h} If $\ov{h}$ is bijective and square-free, then $h(\ov{h}^{-1}(x))\neq h(x)$. -\end{lemma} +\end{Lemma} -\begin{proof} +\begin{Proof} -\end{proof} +\end{Proof} Let $Z$ be a random variable over $\{1,\ldots,N\}\times\{0,1\}$ uniformaly distributed. For $X\in \Omega$, we @@ -187,9 +69,9 @@ are fair. The integer $\ts$ is a randomized stopping time for the markov chain $(X_t)$. -\begin{lemma} +\begin{Lemma} The integer $\ts$ is a strong stationnary time. -\end{lemma} +\end{Lemma} \begin{proof} Let $\tau_\ell$ be the first time that $\ell$ is fair. The random variable @@ -201,10 +83,10 @@ $\ell$-th bit of $X_t$ is $0$ or $1$ with the same probability, proving the lemma. \end{proof} -\begin{proposition} \label{prop:stop} +\begin{Theo} \label{prop:stop} If $\ov{h}$ is bijective and square-free, then $E[\ts]\leq 8N^2+ N\ln (N+1)$. -\end{proposition} +\end{Theo} For each $x\in \Omega$ 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 @@ -215,9 +97,9 @@ $$S_{x,\ell}=\min \{m \geq 1\mid h(X_m)\neq \ell\text{ and }Z_m=\ell\text{ and } $$\lambda_h=\max_{x,\ell} S_{x,\ell}.$$ -\begin{lemma}\label{prop:lambda} +\begin{Lemma}\label{prop:lambda} If $\ov{h}$ is a square-free bijective function, then one has $E[\lambda_h]\leq 8N^2.$ -\end{lemma} +\end{Lemma} \begin{proof} For evey $x$, every $\ell$, one has $\P(S_{x,\ell})\leq 2)\geq @@ -248,9 +130,9 @@ which concludes the proof. Let $\ts^\prime$ be the first time that there are exactly $N-1$ fair elements. -\begin{lemma}\label{lm:stopprime} +\begin{Lemma}\label{lm:stopprime} One has $E[\ts^\prime]\leq N \ln (N+1).$ -\end{lemma} +\end{Lemma} \begin{proof} This is a classical Coupon Collector's like problem. Let $W_i$ be the @@ -269,11 +151,11 @@ Consequently, $E[\ts^\prime]\leq N (-\frac{1}{2}+\ln(N+1))\leq N\ln(N+1)$. \end{proof} -One can now prove Proposition~\ref{prop:stop}. +One can now prove Theo~\ref{prop:stop}. \begin{proof} One has $\ts\leq \ts^\prime+\lambda_h$. Therefore, -Proposition~\ref{prop:stop} is a direct application of +Theorem~\ref{prop:stop} is a direct application of lemma~\ref{prop:lambda} and~\ref{lm:stopprime}. \end{proof}