\documentclass[twoside]{article} \usepackage{amsmath} \usepackage{amssymb} \usepackage{epsfig} \usepackage{floatflt} \def\N{{\mathbb N}} % positive integers \def\Q{{\mathbb Q}} % rationals \def\Z{{\mathbb Z}} % integers \def\R{{\mathbb R}} % reals \def\Rn{{\R^{n}}} % product of n copies of reals \def\P{{\mathbb P}} % probability \def\E{{\mathbb E}} % expectation \def\1{{\mathbf 1}} % indicator \def\U{{\mathbb U}} % potential measure \def\var{{\mathop{\mathbf Var}}} % variance \def\borel{{\cal B}} % borel sigmal field \def\G{{\cal G}} % some sigma field \def\F{{\cal F}} % some sigma field \def\H{{\cal H}} % some sigma field \def\L{{\mathbf L}} % L, as in L^2 \def\I{{\mathbf I}} \def\ascv{\stackrel{\scriptscriptstyle a.s.}{\longrightarrow}} % almost sure convergnece \def\pcv{\stackrel{\scriptscriptstyle \P}{\longrightarrow}} % convergnece in P \def\ltcv{\stackrel{\scriptscriptstyle\L^2}{\longrightarrow}} % L2 convergnece \def\lpcv{\stackrel{\scriptscriptstyle\L^p}{\longrightarrow}} % Lp convergnece \def\ci{\perp\!\!\!\perp} % conditional independence % the header/lecture structure\cdotsborrowed from alistair sinclair's cs270 format \newcommand{\lecture}[4]{ \pagestyle{myheadings} \thispagestyle{plain} \newpage \setcounter{page}{1} \setcounter{lecnum}{#4} \noindent \begin{center} \framebox{ \vbox{\vspace{2mm} \hbox to 6.28in { {\bf Stat205A:~Probability~Theory~(Fall 2002) \hfill Lecture: 23-24} } \vspace{6mm} \hbox to 6.28in { {\Large \hfill #1 \hfill} } \vspace{6mm} \hbox to 6.28in { {\it Lecturer: #2 \hfill Scribe: #3} } \vspace{2mm}} } \end{center} \markboth{#1}{#1} \vspace*{4mm} } %\hbox to 5.90in { \hfill {\it Scribe: #3} } % number everything using the lecture number counter % are referring to an example, theorem, exercise, etc. \newcounter{lecnum} \renewcommand{\thepage}{\thelecnum-\arabic{page}} \renewcommand{\thesection}{\thelecnum.\arabic{section}} \renewcommand{\theequation}{\thelecnum.\arabic{equation}} \renewcommand{\thefigure}{\thelecnum.\arabic{figure}} \renewcommand{\thetable}{\thelecnum.\arabic{table}} \newtheorem{theorem}{Theorem}[lecnum] \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{claim}[theorem]{Claim} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{definition}{Definition}[lecnum] \newenvironment{proof}{{\bf Proof:}}{\hfill\rule{2mm}{2mm}} \newenvironment{proofsketch}{{\bf Proof Sketch:}}{\hfill\rule{2mm}{2mm}} \newcommand{\fig}[3]{ \vspace{#2} \begin{center} Figure \thelecnum.#1:~#3 \end{center} } \newtheorem{exercise}{Exercise}[lecnum] \newtheorem{example}{Example}[lecnum] %some things we'll never understand.\cdotsalas \setlength{\oddsidemargin}{0.25 in} \setlength{\evensidemargin}{-0.25 in} \setlength{\topmargin}{-0.6 in} \setlength{\textwidth}{6.0 in} \setlength{\textheight}{8.5 in} \setlength{\headsep}{0.75 in} \setlength{\parindent}{0 in} \setlength{\parskip}{0.1 in} \advance\topmargin by 0.5in %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{document} \lecture{Recurrence and Transience of Random Walks}{James W. Pitman}{Tianbing Chen {\tt ctbing@math.berkeley.edu } }{23} % In this lecture, let $X_1, X_2, \cdots $ be i.i.d. and $S_n=X_1+X_2+\cdots +X_n, \; S_n=0. \; S_n$ is {\bf a random walk}. \begin{theorem} Let $X_1, X_2,\cdots$ be i.i.d. , $\F_n=\sigma(X_1,\cdots, X_n)$, $\tau$ is a stopping time. Conditional on {$\tau < \infty $}, ${S_\tau, S_{\tau+1},\cdots}$ is a R.W.\footnote{random walk} started at $S_\tau$. i.e. ${X_{\tau+1 },X_{\tau+2},\cdots}$ are i.i.d. and independent of $\F_\tau$. \end{theorem} \begin{proofsketch} Conditional on $\tau$ \begin{eqnarray*} &\:&\P(\tau = n,(X_1,\cdots,X_\tau)\in A, (X_{\tau+1},\cdots,X_{\tau+m})\in B)\\ &=& \P(\tau = n, (X_1,\cdots,X_n) \in A, (X_{n+1},\cdots,X_{n+m} \in B) \\ &=& \P(\tau = n, (X_1,\cdots,X_n) \in A)\P((X_1,\cdots,X_m)\in B) \end{eqnarray*} Summing over n gets the desired result. \end{proofsketch} \begin{definition} The number $x \in \R$ is said to be {\bf a recurrent value} for the R.W. $S_n$ if for every $\epsilon > 0$, $\P(S_n \in (x\pm \epsilon)\footnote{$x\pm \epsilon:=[x-\epsilon,x+\epsilon]$}) = 1$. \end{definition} \begin{definition} We say F is {\bf Lattice with period d} if $F(\Z d)=1$ and $d$ is the greatest positive number with this property. Otherwise,\:there is no such $d$,\:and it's called {\bf Non-lattice}. \end{definition} \begin{example} $F=\frac{1}{2}(\delta_e+\delta_1)$ is non-lattice. \end{example} \begin{theorem} If R.W. $S_n$ is lattice with range $\Z d $ as above, then either 1) or 2) \begin{itemize} \item[1)] {each $x\in \Z d $ is recurrent,} \item[2)] {each $x\in \Z d $ is transient.} \end{itemize} \end{theorem} \begin{proofsketch} Just Markov chain theory. \end{proofsketch} \begin{definition} y is said to be {\bf possible} if for every open interval $I$, there exists $k$, s.t. \\$\P(S_k \in I)>0$. \end{definition} \begin{lemma} If x is recurrent and y is possible, then x$-$y is recurrent. \end{lemma} \begin{proofsketch} Take $\epsilon >0$,\;then there exists k, s.t. $\P(|S_k-y|<\epsilon)>0$. % From {\bf Theorem 23.1} \begin{eqnarray*} \P(|S_n-x|<3\epsilon,f.o. \footnotemark ) &\geq & \P(|S_k-y|<\epsilon, |S_(k+n)-S_k-(x-y)|<2\epsilon, f.o.) \\ &=&\P(|S_k-y|<\epsilon)\; \P(S_n-(x-y)|<2\epsilon,f.o.) \end{eqnarray*} If $\P(S_n-(x-y)|<2\epsilon,f.o.) > 0$,\; then $\P(|S_n-x|<3\epsilon,f.o.)> 0$, which is a contradiction! \end{proofsketch} \footnotetext{finitely often} \begin{theorem} If R.W. $S_n$ is non-lattice, then similarly either 1) or 2) \begin{itemize} \item[1)] {each $x\in \R $ is recurrent,} \item[2)] {each $x\in \R $ is transient.} \end{itemize} \end{theorem} \begin{proofsketch} Let G=\{$x \in \R$: x is recurrent\}. Suppose $G\neq \varnothing$, then \begin{itemize} \item It is clear that $G^c$ is open, so G is closed\footnote{topologically closed}. \item From the above lemma, if $x\in G$ and $y \in G$, then $x-y \in G$. Therefore, G is a group. \end{itemize} Since G is a closed subgroup of $\R$ and the R.W. is non-lattice, it follows that G=$\R$. \end{proofsketch} \\ {\bf Note:} If $\E$(X) is defined , finite and not 0, then the R.W. is transient (i.e. \{recurrent points\}=$\varnothing$) by S.L.L.N\footnote{Strong Law of Large Numbers}. \begin{definition} $\U$:\; {\bf potential measure}. For any interval I , \; %\begin{center} $\U$ (I):=$\sum_n\P(S_n \in I)=\E(\sum_n\1_{(S_n \in I)})$. %\end{center} \end{definition} \begin{lemma} $\P(S_n\in(x\pm \epsilon /2) \mbox{ for some n})\; \U(\pm \epsilon /2) \leq \U(x\pm \epsilon)\leq \U(\pm 2\epsilon)$ \end{lemma} \begin{proofsketch} Let $\tau$:=the first hit of $(x \pm \epsilon)$, \; then % %\begin{center} $ S_{\tau +n}\in (x-\epsilon,x+\epsilon) \Rightarrow (S_{\tau +n}-S_\tau )\in (\pm 2\epsilon)$. %\end{center} Therefore from {\bf Theorem 23.1} \begin{eqnarray*} \U(x\pm \epsilon)&=&\E[\mbox{the number of times n that}\; S_n\in (x\pm \epsilon)] \\ &=&\E [\mbox{the number of times n that} (S_{\tau +n}-S_\tau )\in (\pm \epsilon)]\\ &\leq& \E[\mbox{the number of times n that} \; S_n\in (\pm 2\epsilon)] \\ &=& \U(\pm 2\epsilon) \end{eqnarray*} Let $\tau_1$:=the first hit of $(x \pm \epsilon /2)$. Use the same argument % \begin{eqnarray*} \P(S_n\in(x\pm \epsilon /2) \mbox{ for some n})\; \U(\pm \epsilon /2) &=&\E [\mbox{the number of times n that} (S_{\tau_1 +n}-S_{\tau_1} )\in (\pm \epsilon /2)] \\ &\leq& \E[\mbox{the number of times n that} \; S_n\in (x\pm \epsilon)] \\ &=&\U(x\pm \epsilon) \end{eqnarray*} \end{proofsketch} \begin{corollary} $\U (\pm k\epsilon)\leq (2k+1)\: \U(\pm \epsilon),\; \forall \: \:k\in \N$. \end{corollary} \begin{proofsketch} Cover ($-k\epsilon$,\;$k\epsilon$) with (2k+1) intervals of the form $(x\pm \epsilon /2)$.\; Use the fact that $\U$ is a measure. \end{proofsketch} \begin{proposition} Either $\U(I)<\infty$ for all bounded intervals I\;(transient case) or $\U(x\pm \epsilon)=\infty$ for all possible x and all $\epsilon >0$. \end{proposition} \begin{proofsketch} Consider $\U(\pm \delta)$: \begin{itemize} \item[1)]{If $\U(\pm \delta)< \infty$ for some $\delta >0$, then \\ $\U (\pm k\delta)\leq (2k+1)\U (\pm \delta)< \infty, \forall \: \:\;k\in \N$ $\implies \U(I)< \infty$ for all bounded intervals I.} \item[2)]{If $\U(\pm \delta)=\infty$ for all $\delta >0$, then from {\bf Lemma 23.5} \\ $\P(S_n\in(x\pm \delta /2) \mbox{ for some n})\; \U(\pm \delta /2) \leq \U(x\pm \delta) \implies \U(x\pm \delta)=\infty$ for all $\delta> 0$ if x is possible.} \end{itemize} \end{proofsketch} \begin{theorem} Either $\U(\pm 1)<\infty$ and no x is recurrent or $\U(\pm 1)=\infty$ and every possible x is recurrent. \end{theorem} \begin{proofsketch} If $\U(\pm 1)<\infty$, no x is recurrent by {\bf Borel-Cantelli lemma}.\\ The other way: \\ If $S_n$ is in an interval I only finitely often, consider $\tau$:= the {\bf last} time that $S_n\in I$. \\{\bf Careful}: $\tau$ is not a stopping time since $\{\tau=n\}=\{S_n\in I,\; S_{n+1}\in I,\; S_{n+2}\in I, \cdots\}$ \\$\{\tau =0\}=\{S_n\in I,\; \mbox {for all} \; n\} ,\quad \{\tau =\infty\}=\{S_n\in I,\; i.o.\}. $ \\ \\ Since $\U(\pm 1)=\infty$ by assumption, we know that $\U(\pm \epsilon)=\infty ,\; \forall \: \:\epsilon >0$ by estimate:\\ $\U (\pm k\epsilon)\leq (2k+1)\U (\pm \epsilon) \; for \; k\geq \frac{1}{\epsilon}$. \\ Let $\tau$:=last time that the R.W. is in ($\pm \epsilon$), then $\P(S_n \in (\pm \epsilon),\; f.o.)=\sum_n\P(\tau =n)$. \begin{eqnarray*} \{ \tau =n\} &=&\{ S_n\in (\pm \epsilon)\}\cap \{S_{n+k} \not\in (\pm \epsilon),\; \forall \: \:k \geq 1\}\\ &\supset&\{S_n\in (\pm \epsilon)\}\cap\{S_{n+k}-S_n \not\in (\pm 2\epsilon),\; \forall \: \:k \geq 1\}\\ \end{eqnarray*} Therefore $\P(\tau =n) \geq \P (S_n \in (\pm \epsilon)\;\P(|S_k|\in 2\epsilon,\; \forall \: \:k\geq 1)$.\; Sum over n:\\ \begin{center} $1\geq \P(S_n\in \pm \epsilon,\; f.o.)\geq \U(\pm \epsilon)\:\P(|S_k|\geq 2\epsilon,\; \forall \: \:k\geq 1)$ \end{center} But $\U(\pm\epsilon)=\infty$, which forces the term $\P(|S_k|\geq 2\epsilon,\; \forall \: \:k\geq 1)$ to be 0. \\ Rewrite what we have proved: \begin{center} $\U(\pm 1)=\infty \implies \P(|S_n|\geq \delta,\; \forall \: \:n\geq 1)=0$ for all $\delta >0$ \end{center} Finish the argument: \\ \begin{eqnarray*} \P(S_n\in (\pm \epsilon), \;f.o.)&=&\P(\tau < \infty \;\mbox{and}\; S_\tau \in (\pm \epsilon))\\ &=&\lim_{k\rightarrow \infty}\P(\tau < \infty \;\mbox{and}\; S_\tau \in (\pm \epsilon(1-\frac{1}{k})))\\ &=&\lim_{k\rightarrow\infty}\sum_{n=0}^{\infty}\P(S_n\in (\pm \epsilon (1-\frac{1}{k})) \;\mbox{and}\; S_{n+j} \not\in (\pm \epsilon),\; \forall \: \:j\geq 1)\\ &\leq&\lim_{k\rightarrow \infty}\sum_{n=0}^{\infty}\P(S_n\in \pm \epsilon (1-\frac{1}{k}))\;\P(|S_j| \geq \frac{\epsilon}{k},\; \forall \: \:j\geq 1)\\ &=&0 \; \quad since \;\P(|S_n|\geq \delta,\; \forall \: \:n\geq 1)=0 \;for\; all\; \delta >0. \\ \end{eqnarray*} \end{proofsketch} \\ Key idea here: Think about the {\bf last} time in the trip. \begin{theorem}[Chung-Fuchs Theorem] Suppose $\E|X_1|<\infty$. \begin{itemize} \item {If\: $\E X_1\neq 0$, then the R.W. is transient(by S.L.L.N.)} \item {If\: $\E X_1\ = 0$, then all possible points are recurrent.} \end{itemize} \end{theorem} \begin{proofsketch} We'll show $\U(\pm 1)=\infty$ when $\E X_1\ = 0$. We know\\ \begin{eqnarray*} \U(\pm 1)&\geq&(\frac{1}{2k+1})U(\pm k)\\ &=&(\frac{1}{2k+1})\;\sum_{n=0}^{\infty}\P(S_n\in (\pm k)) \end{eqnarray*} Take $\epsilon >0$, and choose k so that\\ \begin{center} $\P(\frac{|S_n|}{n}< \epsilon)\geq \frac{1}{2}$ for all $n\geq k$ (by W.L.L.N. \footnote{Weak Law of Large Numbers}) \end{center} For $k\leq n\leq \frac{k}{\epsilon}$, \;$\P(|S_n|