\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|<k)\geq \frac{1}{2}$. Hence \\
\begin{eqnarray*}
\sum_{n=0}^{\infty}\P(S_n\in (\pm 1))&\geq&(\frac{1}{2k+1})\;\sum_{n=0}^{\infty}\P(S_n\in (\pm k))\\
&\geq& (\frac{1}{2k+1})\;\sum_{k\leq n\leq \frac{k}{\epsilon}}\P(S_n\in (\pm k))\\
&\geq& (\frac{1}{2k+1})\;\sum_{k\leq n\leq \frac{k}{\epsilon}}\;\frac{1}{2}\\
&\geq& \frac{1}{2}\;(\frac{1}{2k+1})\;(\frac{k}{\epsilon}-k)\\
&\geq& \frac{1}{2}\;(\frac{1}{3k})\;(\frac{k}{\epsilon}-k)\\
&\geq& \frac{1}{6}(\frac{1}{\epsilon}-1) \\
&\rightarrow& \infty \; \quad as \; \epsilon \rightarrow 0.
\end{eqnarray*}
\end{proofsketch}
\end{document}
