tw

diff --git a/main.tex b/main.tex
index 6dbf3ef2fedcfb5c4dbf19faf3a116e06ac241a9..4bbcc0e0396483d8cd6e7a1592cf12d3cd8a02e0 100644 (file)
--- a/main.tex
+++ b/main.tex
@@ -61,16 +61,16 @@
 % \theoremsymbol{\ensuremath{\diamondsuit}}
 % \theoremprework{\bigskip}
 % \theoremseparator{.}
 % \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}}
 % \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.}}
 
 \newcommand{\vectornorm}[1]{\ensuremath{\left|\left|#1\right|\right|_2}}
 %\newcommand{\ie}{\textit{i.e.}}

diff --git a/preliminaries.tex b/preliminaries.tex
index 8f7774a4e441b117c5afed1b81b32cf2fe26fa90..3b559b11ba0f7867ff7876da30b226e7f1d8e458 100644 (file)
--- 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. 
 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).
 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}
 
 % \]
 %\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)|.$$
 
 % 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.
 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 5bf7425f83811b6a57006f31db11f02e118ac3d4..0a1dbe2dde19eaed5bab16445498ff21313703da 100644 (file)
--- 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}$
 
 
 %% 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\}$.
 
 
 %% 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}
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \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$. 
 
 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)$.
 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
 
 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)$.
 
 
 the markov chain $(X_t)$.
 
 

-\begin{lemma}
+\begin{Lemma}

 The integer $\ts$ is a strong stationnary time.
 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
 
 \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}
 
 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)$. 
 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
 
 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}.$$
 
 
 $$\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.$
 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
 
 \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. 
 
 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).$
 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
 
 \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}
 
 $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,
 
 \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}
 
 lemma~\ref{prop:lambda} and~\ref{lm:stopprime}.
 \end{proof}