
\documentclass{article}

\usepackage{amssymb,amsmath, amsthm, cite}
\newtheorem{Theorem}{Theorem}
\theoremstyle{definition}
\newtheorem{Definition}[Theorem]{Definition}
\theoremstyle{theorem}
       \newtheorem{Lemma}[Theorem]{Lemma}
       \theoremstyle{theorem}
            \newtheorem{Corollary}[Theorem]{Corollary}
                 \newtheorem{Exercise}[Theorem]{Exercise}
\author{\sc{Arpit Gupta}}
\title{\sc{Recursion and Random Walks}}

\begin{document}
\maketitle

\begin{abstract}
This paper examines conditions for recurrence and transience for
random walks on discrete surfaces, such as $\mathbb{Z}^d$, trees,
and random environments.
\end{abstract}

\section{\sc{Random Walks on Non-Random Environments}}

\subsection{\sc{Definitions}}

 %We are interested in describing a walker traveling
%randomly on an integer lattice.  First, a few definitions:
\begin{Definition}
A class of subsets $\mathcal{F}$ of a set $\Omega$ is an
\emph{algebra} if the following hold:
\begin{enumerate}
\item $\emptyset \in \mathcal{F}$ and $\Omega \in \mathcal{F}$.
\item $A_1, A_2, \ldots, A_n \in \mathcal{F} \Longrightarrow \bigcup_{i = 1}^n A_i \in \mathcal{F}$.
\item $A \in \mathcal{F} \Longrightarrow A^c \in \mathcal{F}$.
\end{enumerate}
If additionally  $A_1, A_2, \ldots \in \mathcal{F} \Longrightarrow
\bigcup_{i = 1}^\infty A_i \in \mathcal{F}$, then $\mathcal{F}$ is
called a \emph{$\sigma$-algebra}.
\end{Definition}

\begin{Definition}
A \emph{Probability Measure} is a function $\mathbb{P}: \mathcal{F} \to [0,1]$, where $\mathcal{F}$ is a $\sigma$-algebra, satisfying:
\begin{enumerate}
\item $ \mathbb{P}\{ \emptyset\} = 0$
\item If $A_1, A_2, \ldots$ is a collection of disjoint members of $\mathcal{F}$, so that $A_i \cap A_j = \emptyset \ \forall i \not = j$, then
\[ \mathbb{P} \Big \{ \bigcup_{i = 1}^\infty A_i \Big \} = \sum_{i = 1}^\infty \mathbb{P} \{ A_i \}. \]
\end{enumerate}


\end{Definition}


\begin{Definition}
A \emph{Probability Space} is represented by the triple $(\Omega,
\mathcal{F}, \mathbb{P})$, where $\Omega$ is a set, called a
\emph{Sample Space}, containing all possible outcomes, $\mathcal{F}$
is a $\sigma$-algebra of subsets of $\Omega$ containing events, and
$\mathbb{P}$ is a probability
measure that assigns a measure of 1 to the whole space.  $\mathcal{F}$ will be a $\sigma$-algebra on $\Omega$ throughout the paper.%The triple
%$(\Omega, \mathcal{F}, \mathbb{P})$ comprising a sample space
%$\Omega$, containing all possible outcomes, a $\sigma $- algebra
%$\mathcal{F}$ containing interesting subsets of $\Omega$ (events),
%and a probability measure $\mathbb{P}$ on $(\Omega, \mathcal{F})$ is
%called a \emph{Probability Space}.
\end{Definition}


\begin{Definition}
A \emph{Random Variable} is a function $X: \Omega \to \mathbb{R}$
with the property that \[\{ \omega \in \Omega: X(\omega) \leq x \}
\in \mathcal{F} \ \forall x \in \mathbb{R}.\] Two events $ A = \{
X_i \leq x_i \}, B = \{ X_j \leq x_j \}$ are \emph{independent} when
$\mathbb{P}\{ A  \cap  B \} = \mathbb{P}\{A \} \mathbb{P} \{B\} $.
More generally, random variables $X_1, X_2, \ldots$ are independent
if $\forall k \in \mathbb{N}, x_1, x_2, \ldots \in \mathbb{R}$,
\[ \mathbb{P} \{ X_1 \leq x_1, X_2 \leq x_2, \ldots X_k \leq x_k \} = \prod_{i=1}^k \mathbb{P} \{ X_i \leq x_i \}.\]


 If $X$ is a
random variable, then for every Borel subset $B$ of $\mathbb{R}$,
$X^{-1} (B) \in \mathcal{F}$.  We define a measure $\mu_X$, called
the \emph{distribution} of the random variable, on Borel sets by
\[ \mu_{X} (B) := \mathbb{P} \{ X \in B \} = \mathbb{} \{ X^{-1} (B) \}. \]

If $\mu_{X}$ takes values only for countable subsets of the real
numbers, $X$ is a \emph{discrete} random variable; these are the
only random variables we consider in this paper.  If random
variables $X_1, X_2, \ldots$ are all independent and have the same
distribution, we say they are \emph{ independent and identically
distributed} (i.i.d.).


\end{Definition}


%\begin{Definition}
%A \emph{discrete system} is characterized by a state space V, %and
%transitions between the states.
%\end{Definition}

\begin{Definition}
 Intuitively, a \emph{discrete stochastic process} is characterized by a state space $V$, and transitions between states which occur randomly according to some
probability distribution.  The process is \emph{memoryless} if the
probability of a transition $i \to j$ does not depend on the history
of the process, i.e. $\forall i, j, u_o, \ldots, u_{t - 1} \in V,$
 \[  \quad \mathbb{P}\{X_{t + 1} = j |
 X_t = i, X_{t-1} = u_{t - 1}, \ldots, X_0 = u_0 \} = \mathbb{P}\{X_{t + 1} = j
 | X_t = i\}. \]

If additionally $p_{ij} = \mathbb{P}\{X_{t + 1} = j | X_t
 = i\} = \mathbb{P} \{ X_{t} = j | X_{t - 1} = i \}$, so the transition probability does not depend on time, then the process is \emph{homogenous}.
\end{Definition}

\begin{Definition}
A \emph{Markov chain} is a memoryless homogeneous discrete
stochastic process.
\end{Definition}

Roughly, this means that, conditional upon knowing the state of the process up to the $n^{\textrm{th}}$ step, the values after $n$ steps do not depend on the values before the $n^{\textrm{th}}$ step.
 \subsection{\sc{Simple Random Walks on Integer Lattices}}

First we consider a simple random walk on $\mathbb{Z}$ where a
walker starts at some $z \in \mathbb{Z}$ and always moves to either
adjacent point with probability 1/2.  Let $S_n$ denote the position
of the walker after $n$ steps.  The model immediately implies that
the random walk is a Markov Chain, i.e.
%%\[ \mathbb{P} \{ S_{n + 1} = i_{n + 1} | S_n = i_n, S_{n - 1} = i_{n - 1},  \ldots , S_1 = i_1, S_0 = i_0 = 0 \}
%%= \mathbb{P} \{S_{n + 1}  = i_{n + 1} | S_n = i_n \} = \frac{1}{2} \]
{\setlength\arraycolsep{-50pt
\begin{eqnarray}
\mathbb{P} \{ S_{n + 1} = i_{n + 1} | S_n = i_n, S_{n - 1} = i_{n - 1},  \ldots , S_1 = i_1, S_0 = i_0 = z \} \nonumber\\
&&= \mathbb{P} \{S_{n + 1}  = i_{n + 1} | S_n = i_n \} = \frac{1}{2},\end{eqnarray}}
where $i_0 = z, i_1, i_2, \ldots, i_{n + 1}$ is a sequence of integers with $| i_1 - i_0| = |i_2 - i_1| = \cdots = |i_{n +1} - i_n | = 1$.\\

Alternatively, work on the probability space $[0, 1]$ with Lebesgue
measure.  Let $X_1, X_2, \ldots$ be a sequence of i.i.d. random
variables with $\mathbb{P} \{ X_1 = 1 \} = \mathbb{P} \{ X_1 = -1 \}
=1/2$, where $X_i$ corresponds to the value of the $i^\textrm{th}$
coin flip (that $X_1, X_2, \ldots$ exist with these properties is
beyond the scope of this paper). Then the position of the random
walk after $n$ steps is given by:
\[ S_n = z + X_1 + X_2 + \cdots + X_n \qquad n = 1, 2, \ldots. \]





\begin{Lemma}
Let $S_n$ denote the position of a random walker at time n. Let
\[ p_n = \mathbb{P}\{S_{n} = S_0 \} \]
Then \[ p_n  \sim \frac{1}{\sqrt{2\pi n}}.\]
\end{Lemma}

\begin{proof}
When $n$ is odd, $p_n = 0$, so we only consider the case where the
walker takes an even number of steps $2n$.  To return to the
starting point in that number of steps, the walk must consist of
exactly $n$ steps to the right and $n $ to the left, and there are
$\binom{2n}{n} $ways to choose such a move. Each particular choice
of $2n$ steps occurs with probability $2^{-2n}$.  Using Stirling's
formula, given by
\[ n! \sim \sqrt{2 \pi n} \ e^{-n} n^{n }  \]

%\[ \frac{p_{n + 1}}{p_n} = \frac{ \binom{2n + 2}{n + 1} / 2^{2(n +
%1)}}{\binom{2n}{n} / 2^{2n}} = \frac{(2n + 2)(2n+1)}{4(n + 1)^2} = \frac{2n + 1}{2n + 2}. \] Which gives:


%\[ p_n = \frac{1 \cdot 3 \cdot 5 \cdots (2n - 1)}{2 \cdot 4 \cdot 6 \cdots 2n} .\]

We have
\[ p_{2n} = \binom{2n}{n} \frac{1}{2^{2n}} = \frac{(2n)!}{n!n!} \frac{1}{2^{2n}} \sim \frac{\sqrt{4 \pi n } \ e^{-2n}(2n)^{2n}}{(\sqrt{2\pi n} \ e^{-n}n^n)^2 2^{2n}} = \frac{1}{\sqrt{2\pi n}} .\]

\end{proof}

We can form an analogous construction for simple random walks on
$\mathbb{Z}^d$.  The random walk $S_n$ now has $2d$ choices of moves
for each $n$.  The probability of moving in any one direction at
time $n$  $( \frac{1}{2d} )$ is equal to the probability of moving
in any other direction, and is independent of the particular path
the walker followed to arrive at $n$.\\


     Another way to to think of
the simple random walk in $\mathbb{Z}^d$ is to think of $d$
different simple random walks in each of the $d$ directions.  To
choose each step, one of the one-dimensional random walks is picked
at random to make a move, and the walker moves in the direction
indicated by that move, keeping the position in other directions
constant.

\begin{Lemma}\cite{Snell}
Let $S_n$ denote the position of a two-dimensional walker after $n$
steps, and $p_n = \mathbb{P} \{ S_n = S_o \}$.  Then,
\[ p_n \sim \frac{1}{2 \pi n }.\]
\end{Lemma}


\begin{proof}
To return to the starting point in 2 dimensions, the walk must again
comprise an even number of steps $2n$, and there are $4^{2n}$ ways
to choose such walks of length $2n$ returning to the starting point.
All the walks returning to the starting point consist of $k$ steps
to the north and south, and $n - k$ to the east and west.  So we
have

\[ p_{2n} = 2^{-2n} \sum_{k = 0}^n \binom{2n}{k \ k \ n - k \ n - k
} = 2^{-2n} \sum_{k = 0}^n \frac{(2n)!}{k!k!(n - k)!(n - k)!}\]
\[ = 2^{-2n} \sum_{k = 0}^n \frac{(2n)!}{n!n!}
\frac{n!n!}{k!k!(n-k)!(n-k)!} = 2^{-2n} \binom{2n}{n} \sum_{k = 0}^n \binom{n}{k}^2.\]

However, $\sum_{k = 0}^n \binom{n}{k}^2 = \binom{2n}{n}$, so
\[ p_{2n} = \Bigg (\binom{2n}{n} \frac{1}{2^{2n}}\Bigg )^2,\]
which is the square of the one-dimensional result.  Therefore we
have
\[ p_{2n} \sim \Big (\frac{1}{\sqrt{2 \pi n}} \Big )^2 = \frac{1}{2
\pi n}. \]
\end{proof}

\begin{Lemma}\cite{Snell}
Let $S_n$ denote the position of a three-dimensional random walk,
and $p_n$ as before.  Then,
\[ p_{2n} \leq \frac{C}{n^{3/2}}. \]
\end{Lemma}
\begin{proof}
As before, the three-dimensional random walk must make an equal
number of steps in each direction in order to return to its starting
point.  There are now $6^{2n}$ ways to choose walks of length $2n$
returning to the origin.  If we let $n_1$ denote the number of steps
in the $x$ direction, $n_2$ the steps in the $y$ direction, and
$n_3$ the steps in the $z$ direction, we have
\[ p_{2n} = 6^{-2n} \sum_{n_1 + n_2 + n_3 = 2n} \binom{2n}{n_1 \ n_1
\ n_2 \ n_2 \ n_3 \ n_3 }\]
 \[ = 6^{-2n} \sum_{n_1 + n_2 + n_3 = 2n}
\frac{n!}{n_1! n_2! n_3!} = \frac{1}{3^{2n}} \binom{n}{n_1 \ n_2 \
n_3}\]  $\frac{1}{3^{2n}}\binom{n}{n_1 \ n_2 \ n_3}$ represents the
probability that when 3 balls are able to fall into 3 separate bins,
$n_1$ of them fall into the first, $n_2$ into the second, and $n_3$
into the third.  Informally, we see that if the balls fall randomly,
this probability is maximized by letting $n_1$, $n_2$, $n_3$ be as
close as possible to $n/3$.  Replacing one of the terms by this
fact, we have
\[ p_{2n} \leq 2^{-2n} \binom{2n}{n} \frac{1}{3^n} \frac{n!}{\lfloor
\frac{n}{3} \rfloor ! \ \lfloor \frac{n}{3} \rfloor ! \ \lfloor
\frac{n}{3} \rfloor ! } \sum_{n_1 + n_2 + n_3 = 2n} \frac{1}{3^n}
\frac{n!}{n_1!n_2!n_3!}. \] Here $\lfloor \frac{n}{3} \rfloor$ denotes the largest integer less than or equal to $\frac{n}{3}$. The last sum represents the sum of all probabilities for the outcome that $n$ balls fit into three bins, and so is just one.  Therefore, we have
\[ p_{2n} \leq \frac{1}{2^{2n}} \binom{2n}{n}
\frac{1}{3^n}\frac{n!}{\lfloor \frac{n}{3} \rfloor !^3} .\] Applying Stirling's formula, we have
\[ p_{2n} \leq \frac{C}{n^{3/2}}. \]

\end{proof}




%\begin{Lemma}(\cite{Pal}, p.193)
%Let $S_n$ be a random walk on $\mathbb{Z}^d$, and let $n_1$ denote
%the number of steps taken in the $+x$ direction, $n_2$ the steps in
%the $+y$ direction, and so on.  For any $n = 1, 2, \ldots, d= 1, 2,
%\ldots$ \[ p_{2n} = \mathbb{P} \{S_{2n} = S_0 \} =   (2d)^{-2n}
%\binom{2n}{n} \sum_{n_1 + n_2 + \cdots + n_d = n}
%\Big(\frac{n!}{n_1!n_2!\ldots n_d!} \Big )^2.\]
%\end{Lemma}
%\begin{proof}
%To return to the starting point in $d$ dimensions, the random walk
%must make the same number of steps in each of the $d$ directions.
%The walk must again comprise an even number of steps $2n$ to return
%to origin, and ere are $(2d)^{2n}$ ways to choose such walks of
%length $2n$ returning to the origin.  So we have
%\[ p_{2n} = \mathbb{P}\{S_{2n} = S_0 \} = (2d)^{-2n} \sum_{n_1 + n_2 + \ldots + n_d = 2n} \binom{2n}{n_1 \ n_1 \ n_2 \ n_2 \ \cdots \ n_d \ n_d}\]
%\[ = (2d)^{-2n}  \sum_{n_1 + n_2 + \ldots + n_d = 2n} \frac{(2n)!}{(n_1!n_2!\ldots n_d!(n - n_1)!(n - n_2)!\cdots(n - n_d)!)^2} \]
%\[ = (2d)^{-2n} \sum_{n_1 + n_2 + \ldots + n_d = 2n}  \frac{(2n)!}{n!n!} \Big(\frac{n!}{n_1!n_2!\ldots n_d!} \Big )^2 \]
%\[ =(2d)^{-2n} \binom{2n}{n} \sum_{n_1 + n_2 + \cdots + n_d = 2n} \Big(\frac{n!}{n_1!n_2!\ldots n_d!} \Big )^2.\]


%\end{proof}

%\begin{Lemma} (*)
%Let $S_n$ be a random walk in $\mathbb{Z}^d$.  For any $d = 1, 2,
%\ldots$, we have
%\[ p_{2n} = \mathbb{P} \{ S_{2n} = S_0 \} \sim 2 \Big ( \frac{d}{4n\pi} \Big)^{d/2}.\] (~\cite{Pal} p.193)
%\end{Lemma}
%\begin{proof}
%Using the previous Lemma and Stirling's formula, we conclude
%\[ (2d)^{-2n} \binom{2n}{n} \sum_{n_1 + n_2 + \cdots + n_d = n} \Big(\frac{n!}{n_1!n_2!\ldots n_d!} \Big )^2  \]
%\[ \sim  \frac{2^{2n}}{(2d)^{2n} \sqrt{2 \pi n}} \sum_{n_1 + n_2 + \ldots + n_d = n} \bigg ( \frac{\sqrt{2 \pi n } \ e^{-n} n^n }{(\sqrt{2 \pi n_1} \ e^{-n_1} n_1^{n_1} ) \cdots (\sqrt{2 \pi n_d} \ e^{-n_d} n_d^{n_d} ) } \bigg )^2\]
%\[ = \frac{1}{d^{2n} \sqrt{2 \pi n}} \sum_{n_1 + n_2 + \ldots + n_d = n} \frac{1}{(2 \pi)^{d -1}}\bigg (  \frac{n^{n}}{n_1^{n_1} \cdots n_d^{n_d}}  \bigg )^2 = 2 \Big ( \frac{d}{4n\pi} \Big)^{d/2} .\]

%Where the last equality follows from the fact that $\sum_{n_1 + n_2 + \ldots + n_d = n} ( \frac{n^{n}}{n_1^{n_1} \cdots n_d^{n_d}})^2 = 2^{1-d/2} d^{nd} n^{(1 - d)/2} .$



%\end{proof}



%\begin{Theorem}
%Let $S_n$ denote a d-dimensional simple random walk and let $R_n^1,
%\ldots, R_n^d $ denote the number of steps taken in each of the
%d-directions.  Then $\forall n > 0$ the probability that $R_{2n}^1
%\ldots, R_{2n}^d$ are all even is $2^{-(d-1)}$.
%\end{Theorem}

%\begin{proof} We proceed by induction on d.  When $d = 1$, the probability that the moves are
%even is 1/2, since it is equally likely that the moves are odd. Suppose the
%Theorem holds for $d = k$.  Consider $k + 1$ dimensions.  The probability that any
%$k$ of the directions are all even is $2^{-(d-1)}$.  Once we have fixed those moves,
%the moves in the $k + 1$ direction are independent, and the probability is the
%same as in the one dimensional case.  So the probability is $2 * 2^{-(d-1)} = 2^{-(d}$,
%which is what we expect.
%\end{proof}

In addition to the probability of the random walk returning to its starting point, we are also interested in the frequency of return.

\begin{Definition}
Let $A_n$ be the event that a random walk returns to its starting
point on the $n^{\textrm{th}}$, $\{S_n = S_0  \}$.  Then the event
that the random walk returns to its starting point infinitely often
is given by:
\[ \{ A_n \ \textrm{infinitely often (i.o.)} \}  :=  \limsup_{n \to \infty} A_n = \bigcap_{n = 1}^\infty \bigcup_{m = n}^\infty A_m .\]
If $\mathbb{P} \{ A_n \ \textrm{i.o.} \} = 1$, the walk is called \emph{recurrent}.  If $\mathbb{P} \{A_n \ \textrm{i.o.} \} = 0$, the walk is called \emph{transient}.
\end{Definition}








\begin{Theorem}[Recurrence Theorem] \cite{Lawler}
A random walk $S_n$ on $\mathbb{Z}^d$ is recurrent if $d \leq 2$.
If $d \geq 3$, then the walk is transient, and \[\mathbb{P} \{ S_n
\not = S_0 \ \forall n > 0 \}
> 0 .
\]
\end{Theorem}

\begin{proof}
Let $J_n = 1\{ A_n \} $ be an indicator variable for the event
that the random walk returns to its starting point.  %Note that we do not
%assume that the walker starts at the origin.
The total number of
visits to the origin is given by:
\[ V = \sum_{n = 0}^\infty J_{2n}.\]
Using the linearity of the expected value,
\[ \mathbb{E}[V] = \sum_{n = 0}^\infty \mathbb{E} [J_{2n} ] =
\sum_{n = 0}^\infty \mathbb{P} \{ S_{2n} = S_0 \}. \]

We know $\sum n ^{-a} $ converges only when $a > 1$. So when $d = 1,
2$, by Lemmas 7 and 8, the sum is divergent.  When $d = 3$, by Lemma
9, the sum is convergent.  For $d > 3$, we see that to return, the
random walk in four dimensions must at least return in three
dimensions. Since the sum of returning probabilities converges in
three dimensions, it must also converge in any greater number of
dimensions.  Therefore, we have

\[
\mathbb{E}[V]  = \left\{ \begin{array}{ll }
\qquad \qquad \quad  \infty & \qquad \qquad \qquad \qquad \qquad \qquad d = 1, 2\\
 \qquad \qquad \quad  < \infty & \qquad \qquad \qquad \qquad \qquad \qquad d \geq 3
\end{array} \right.\]

Let $q$ be the probability that the random walker ever returns to
its starting point.  Assuming $q < 1$, its distribution is given by:
%%NOTENOTENOTENOTENNOTENOTENOTE why assume q < 1?
\[\mathbb{P} \{ V = k \} = q^{k -1} (1 - q), \qquad k = 1, 2, \ldots\]

Again assuming $q < 1$, we find:
\[ \mathbb{E}[V] = \sum_{k = 1}^\infty k \mathbb{P} \{ V = k \} = \sum_{k = 1}^\infty k q^k (1-q) = \frac{1}{1 - q} <  \infty. \]

For $d = 1, 2$ we know $\mathbb{E}[V] = \infty$, so by contradiction
$q = 1$, and the walk returns to the origin for some $n$ with
probability 1. When $d \geq 3$, $\frac{1}{1 - q} < \infty$, so $q <
1$, and with non-zero probability the random walk may not return to
the starting point at all.

Now from the distribution of $q$,
\[ \mathbb{P} \{ A_n \ \textrm{finitely often} \} \geq \mathbb{P} \{ V = k \} = 1 - q^k \] So if $d = 1,2 $, as $k \to \infty$, $\mathbb{P}
\{ A_n \ \textrm{finitely often} \} \to 0$, so $\mathbb{P} \{ A_n \
\textrm{i.o.} \} = 1$.  When $d \geq 3$, as $k \to \infty$,
$\mathbb{P} \{ A_n \} \to 1$, so $\mathbb{P} \{ A_n \ \textrm{i.o.}
\} = 0$.

%So the walk is certain to return to the origin, and once there,
%faces a probability of return for one; and so returns infinitely
%often. (Alternatively, suppose the walk returns finitely often.  But
%one) return once more--contradicting the assumption that the walk
%returns finitely often.)











\end{proof}

%This is not the original formulation of the question, as posed by Polya.  Polya defined a walk a recurrent if
%with probability 1 it returned to the starting point.  But the two formulations are equivalent. (not true, below is true)


%since if the walk is recurrent in our sense, then it must return to the starting point again and again.
%But each time the walk makes an excursion away from the starting point, it has a non-zero probability of hitting any target
%point before returning.  So eventually a recurrent walk, in our sense, will hit every lattice point and be recurrent in
%the sense of Polya.



%\begin{Corollary}\cite{Lawler}
%Suppose $S_n$ is a simple random walk in $\mathbb{Z}^d$.  If $d = 1, 2$ then the walk returns to the origin with probability one.  If $d \geq 3$, then \[\mathbb{P} \{ S_n
%\not = S_0 \ \forall n > 0 \}
%> 0 .
%\]
%\end{Corollary}

%\begin{proof}
%Let
%$q$ be the probability that the random walker ever %returns to its starting point.
%\[ \mathbb{P} \{ V = k \} = q^{k -1} (1 - q), \qquad %k = 1, 2, \ldots \]
%Suppose $d \geq 3$.  Then,
%\[ \mathbb{E}[V] = \sum_{k = 1}^\infty k \mathbb{P} %\{ V = k \} = \sum_{k = 1}^\infty k q^k (1-q) = %\frac{1}{1 - q} < \infty. \]
%Where the last inequality follows from the fact that a random walk on $d \geq 3$ is transient.
%Therefore, $1 - q > 0$, so the random walk may not return to its starting point at all.  When $ d = 1, 2$, however, $\frac{1}{1 - q} = \infty$ so $q = 1$, and the walk returns to the origin with probability 1.\cite{Lawler}

%\end{proof}






%We are interested in the probability that random walk of length $n + j$, where $0 \leq j \leq n$, contains a run of length $n$ in either direction.

%\begin{Lemma}
%Let \[I_1 (n, a) = \max_{\substack{0 \leq k \leq n - a} } (S_{k + a} - S_k).\]
%Then,
%\[p(n + j, n) := \mathbb{P}\{I_1(n + j, n) = n) = \frac{j + 2}{2^{n + 1}} \quad j = 0, 1, \ldots, n \]
%\end{Lemma}

%\begin{proof}
%Let $A  = \{ I_1 (n + j, n) = n \} $; the event that the random walk has a sequence in one direction of length $n$.  Let $A_k = \{S_{k + n} - S_k = n %\}$; the event that the $k^{th}$ position of the random walk begins a sequence in one direction of length $n$.
%If the event A happens at all, then the sequence of length $n$ must begin at one of the points $1, 2, \ldots , j$.  If we let $\overline{A}_k = \{ %S_{k + n} - S_k \not = n \} $, then:
%\[ A = A_0 + \overline{A}_0 A_1 + \overline{A}_0 \overline{A}_1 A_2 + \cdots + \overline{A}_0 \overline{A}_1 \cdots \overline{A}_{j - 1} A_j
%= A_0 + \overline{A}_0  A_1 + \overline{A}_1 A_2 + \cdots + \overline{A}_{j - 1} A_j . \]
%Since $\mathbb{P} \{A_0\} = 2^{-n} $ and $\mathbb{P} \{ \overline{A}_0 \overline {A}_1 \cdots \overline{A}_i A_{i + 1} \} = 2^{-n - 1} $ for any $i = %1, 2, \ldots$, the Lemma follows immediately.
%\end{proof}

\subsection{\sc{The Zero-One Law}}

The proof of the Recurrence Theorem is based on the fact that \[
\mathbb{P}\{S_n = S_0 \ \textrm{at least for one n} \} = 1
\Longrightarrow \mathbb{P}\{ S_n = S_0 \  \textrm{infinitely often
(i.o.)} \} = 1\]  And \[\mathbb{P}\{S_n=S_0 \ \textrm{at least for
one n} \} < 1 \Longrightarrow \mathbb{P}\{ S_n = S_0 \ \textrm{i.o.}
\} = 0.\] That is, if the random walk returns once to the origin
with probability 1, it will return again and again with probability
1. Similarly, if the random walk stays away from the origin with
non-zero probability for every $n$, then it cannot possibly return
infinitely often. With infinite sequences of independent random
variables, the probabilities of certain events can only be 0 or 1.
This observation is formalized in Kolmogorov's Zero-One Law, which
can be used to provide another proof of the Recurrence Theorem.
%\begin{Definition}

%Let $X_1, X_2, \ldots$ be a collection of random variables on the probability space $(\Omega, \mathcal{F}, \mathbb{P})$. For any subcollection $X_n, X_{n + 1}, \ldots$,  the \emph{tail $\sigma-$ field} of the $X_1, X_2, \ldots$ refers to $\sigma( X_n, X_{n + 1}, \ldots)$; the smallest $\sigma-$ field with respect to which each of the variables $X_n, X_{n + 1}, \ldots$ measurable. This $\sigma -$ field exists due to the fact that if $\{ \mathcal{F}_1, \mathcal{F}_2, \ldots \}$ is a family of $\sigma-$ fields of subsets of $\Omega$, then $\mathcal{I} = \cap_{i} \mathcal{F}_i$ is also a $\sigma -$ field.  If
 %\[ \mathcal{H} = \sigma(X_n, X_{n + 1}, \ldots ), \]
%Then the tail $\sigma-$ field is given by
%\[ \mathcal{H}_\infty = \bigcap_i \mathcal{H}_i. \]
%\end{Definition}
\begin{Definition}
Let $(\Omega, \mathbb{P})$ be a probability space.  Two
$\sigma$-algebras $\mathcal{A}$, $\mathcal{B}$ are independent if
for all $A \in \mathcal{A}$, $B \in \mathcal{B}$,
\[ \mathbb{P} \{A \cap B \} = \mathbb{P} \{A \} \mathbb{P} \{ B \}.\]
\end{Definition}


\begin{Definition}
Assume $X_1, X_2, \ldots$ are independent random variables on
$(\Omega,\mathcal{F})$.  Then the $\sigma$-algebra \emph{generated}
by $X_1, X_2, \ldots$ is the smallest $\sigma$-algebra on which all
the $X_i$ are measurable.
%The $\sigma$-algebra \emph{generated} by
%any subcollection $X_i, \ldots$ is given by the intersection of all
%$\sigma$-algebras over $X_1, \ldots$ containing $X_i, \ldots$, and
%is denoted by $\sigma(X_i, \ldots)$. This $\sigma$-algebra is the
%smallest $\sigma$-algebra over $X_1, X_2, \ldots$ containing $X_i,
%\ldots$.
\end{Definition}

\begin{Definition} Let $\mathcal{F}_n$ be the $\sigma$-algebra generated by $X_1,
\ldots, X_n$, and let $\mathcal{G}_n$ be the $\sigma$-algebra
generated by $X_{n + 1}, X_{n + 2}, \ldots$ with $\mathcal{F}_1
\subset \mathcal{F}_2 \subset\cdots$, and $\mathcal{G}_1 \supset
\mathcal{G}_2 \supset \cdots$.  Let $\mathcal{F}$ be the
$\sigma$-algebra generated by $X_1, X_2, \ldots$, the smallest
$\sigma$-algebra containing the algebra $\mathcal{F}^0 = \cup_{n =
1}^\infty \mathcal{F}_n$, and $\mathcal{G}$ defined similarly.  The
\emph{tail $\sigma$-algebra} $\mathcal{T}$ is defined by
\[ \mathcal{T} = \bigcap_{n = 1}^\infty \mathcal{G}_n.\]
\end{Definition}


\begin{Lemma} \cite{Lawler}
Suppose $\mathcal{F} $ and $\mathcal{G}$ are two algebras of events
that are independent.  Then $\mathcal{F}^1 = \sigma(\mathcal{F})$
and $\mathcal{G}^1 = \sigma(\mathcal{G})$ are independent
$\sigma$-algebras.
\end{Lemma}
\begin{proof}
Let $B \in \mathcal{G}$ and define the measure
\[ \nu_B (A) := \mathbb{P} \{ A \cap B \}, \quad \overline{\nu}_B (A):= \mathbb{P} \{A \} \mathbb{P} \{B \} \]
Since $\nu_B, \overline{\nu}_B$ are finite measures, they agree on
$\mathcal{F}$.  Using the Carath\'eodory extension (which states
that $\mathbb{P}$ can be extended uniquely to a measure space
$(\Omega, \overline{\mathcal{F}}, \mathbb{P})$ where $\mathcal{F}
\subset \overline{\mathcal{F}}$), they must agree on $\mathcal{F}$.
So $\mathbb{P} \{A \cap B \} = \mathbb{P} \{A \} \mathbb{P} \{ B \}
.$  Supposing $A \in \mathcal{F}^1$, $B \in \mathcal{G}^1$, we take
the measures
\[ \nu_{A} (B) := \mathbb{P} \{A \cap B \}, \quad \overline{\nu}_A (B) := \mathbb{P} \{A \} \mathbb{P} \{B \},  \]
completing the proof.




\end{proof}






\begin{Theorem}[Zero-One Law] (\cite{Grimmett}, p. 290) Let $X_1, X_2, \ldots $ be independent random variables on  $(\Omega, \mathcal{F}, \mathbb{P})$.  If $A \in
\mathcal{T}$,
\[ \mathbb{P} \{A\} = 0 \qquad \textrm{or} \qquad \mathbb{P} \{ A \} = 1 .\]
\end{Theorem}

\begin{proof}
By Lemma 14, any event in $\sigma(X_n, X_{n + 1}, \ldots)$ is
independent of any event in $\sigma(X_1, \ldots, X_n)$.  Defining
$\mathcal{F}^0$ and $\mathcal{T}$ as above, any event in
$\mathcal{F}^0$ is independent of any event in $\cup_{n = 1}^\infty
\mathcal{H}_n$. So any event in $\mathcal{H}_\infty $ is independent
of any event in $\sigma( \cup_{n = 1}^\infty \mathcal{H}_n )$.
However, $\mathcal{H}_\infty \subset \sigma (X_1, \ldots) = \sigma
(\cup_{n = 1}^\infty \mathcal{H}_n)$,
 so any tail event is independent of itself.  That is, $\mathbb{P} \{ A \} = \mathbb{P} \{ A \cap A \} = \mathbb{P} \{A \} \mathbb{P} \{ A \}$,
 so $\mathbb{P} \{A \} = 0, 1$.
%Monotone class Theorem
\end{proof}
%\begin{proof}
%(proof 2 - ~\cite{Lawler})
%Let $A \in \mathcal{T}$ and $\epsilon > 0$.  Find a set $A_0 \in \mathcal{F}^0$ such that $\mathbb{P} \{ A \triangle A_0 \} < \epsilon$, where $\triangle$ denotes symmetric difference. Then $mathcal{A}_0 \in \mathcal{F}_n$ for some $n$.  $\mathcal{T} \subset \mathcal{G}_n$ and $\mathcal{F}_n$ is independent of $\mathcal{G}_n$, so $A$ and $A_0$ are independent.  So $mathbb{P} \{ A \cap A_0 \} = \mathbb{P} \{A\}\mathbb{P} \{A_0 \}$.  Also, $\mathbb{P} \{A \cap A_0 \} \geq \mathbb{P} \{A \} - \mathbb{P} \{A \triangle A_0 \} \geq \mathbb{P} \{ A \} - \epsilon$. As $\epsilon \to 0$, $\mathbb{P} \{ A \} = \mathbb{P} \{A\} \mathbb{P} \{A \} \mathbb{P} \{A \}$, which implies $\mathbb{P} \{A\} = 0, 1$.

%\end{proof}

\begin{Lemma}[Borel-Cantelli 1] (\cite{Pal}, p. 27)

Let $A_1, A_2, \ldots$ be a sequence of events for which $\sum_{n = 1}^\infty \mathbb{P} \{A_n \} < \infty$.  Then
\[ \mathbb{P} \{ \limsup_{n \to \infty} A_n \}  = \mathbb{P} \{ A_n \ \textrm{i.o.} \ \} = 0. \]
\end{Lemma}

So with probability 1, only a finite number of the events $A_n$
occur.

\begin{proof}

Supposing that $ \sum_{n = 1}^\infty \mathbb{P} \{A_n \} = 0$ and
using Definition 9, one has
\[ \mathbb{P} \{ \limsup_{n \to \infty} A_n \} = \mathbb{P} \{  \bigcap_{n = 1}^\infty \bigcup_{m = n}^\infty A_m \} = \lim_{n \to \infty} \mathbb{P} \{ \bigcup_{m = n}^\infty A_n \} \leq \lim_{n \to \infty} \sum_{m = n}^\infty \mathbb{P} \{ A_m \} = 0, \]

where the second equality follows from the fact that if $\nu$ is a
measure, $A_1, \ldots$ are measurable set, $A_{n + 1} \subset A_n, n
= 1,, \ldots$, and $\nu\{A_n\} < \infty$, then $\nu \{ \cap_{n
=1}^\infty \}= \lim_{n \to \infty} \nu \{ A_n \}.$  The third
inequality comes from the fact that the $A_n$ are not necessarily
disjoint.

\end{proof}

\begin{Lemma}[Borel-Cantelli 2](\cite{Spitzer}, p. 319)
Let $A_1, A_2, \ldots$ be a sequence of events for which
\[ \sum_{n = 1}^\infty \mathbb{P} \{A_n \} = \infty \quad \textrm{and} \quad \liminf_{n \to \infty} \frac{\sum_{k = 1}^n \sum_{i = 1}^n \mathbb{P} \{A_k A_i \}}{(\sum_{k = 1}^n \mathbb{P} \{A_k \} )^2 } \leq C \quad C \geq 1 \].  Then,
\[ \mathbb{P} \{ \limsup_{n \to \infty} A_n  \} \geq C^{-1}. \]
\end{Lemma}
\begin{proof}
Let $J_n = 1\{A_n\}$ and $N_k = \sum_{n = 1}^k J_n$. $\forall
\epsilon
> 0$, let $B_{n, \epsilon}$ denote the measurable set defined by
\[ N_k \geq \epsilon \mathbb{E} [ N_k] \quad \textrm{for some} \ k \geq n. \]
We pick the measurable functions given by $\mathbf{f}(t) =
\mathbb{E} [ e^{itX} ]$, the characteristic function of the set
$B_{n, \epsilon}$ and $\mathbf{g} = \mathbf{f} ( N_n)$. By the
Cauchy-Schwartz Inequality, given by $\mathbb{E} [ \mathbf{f g } ]^2
\leq \mathbb{E} [ \mathbf{f}^2] \mathbb{E} [\mathbf{g}^2 ] $, we
have
\[ \mathbb{P} \{ B_{n, \epsilon} \}= \mathbb{E} [ \mathbf{f}^2 ] \geq \frac{\mathbb{E}[\mathbf{fg}]^2}{\mathbb{E}[\mathbf{g}^2]} \geq \frac{\mathbb{E}[\mathbf{fg}]^2}{\mathbb{E}[\mathbf{N_n}^2]}
\geq \frac{(\mathbb{E}[N_n] - \mathbb{E}[N_n(1 -
\mathbf{f})])^2}{\mathbb{E}[N_n^2]. }\] But $\mathbb{E}[N_n (1 -
\mathbf{f})] \leq \epsilon \mathbb{E}[N_n]$, so \[ \mathbb{P}\{B_{n,
\epsilon} \geq (1 - \epsilon)^2
\frac{\mathbb{E}[N_n]^2}{\mathbb{E}[N_n^2]} \qquad n = 1, 2,
\ldots.\] Since $\mathbb{E}[N_n] \to \infty $ as $n \to \infty$,
\[ \mathbb{P} \{ \bigcap_{n = 1}^\infty \bigcup_{n = m}^\infty A_m \} \geq \lim_{n \to \infty} \mathbb{P} \{ B_{n, \epsilon}\}.\]
Since this is true for every $\epsilon > 0$,
\[ \mathbb{E} \{ \bigcap_{n = 1}^\infty \bigcup_{m = n}^\infty A_m \} \geq \limsup_{n \to \infty} \frac{\mathbb{E}[N_n]^2}{\mathbb{E}[N_n^2]} = \limsup_{n \to \infty} \frac{\sum_{k = 1}^n \sum_{i = 1}^n \mathbb{P} \{A_k A_i \}}{(\sum_{k = 1}^n \mathbb{P} \{A_k \} )^2 } \leq C. \]






\end{proof}




\begin{Lemma}(\cite{Pal}, p. 25)
For any $- \infty < a \leq b < + \infty$ we have
\[ \mathbb{P} \{ \liminf_{n \to \infty} S_n = a \}  = \mathbb{P} \{ \limsup_{n \to \infty} S_n = b \} = 0 \]
\end{Lemma}

\begin{proof}

\[\limsup_{n \to \infty} S_n = \lim_{n \to \infty} \big ( \sup_{m \geq n} S_m \big ) = \lim_{n \to \infty} n = \infty \]
So $\mathbb{P} \{ \liminf_{n \to \infty} S_n = a \} = 0$ and similarly for the lim inf.




\end{proof}

\begin{Lemma} (\cite{Pal}, p. 196)
When $d = 2$,
\[ \lim_{n \to \infty} \frac{\sum_{j = 1}^n \sum_{k = 1}^n \mathbb{P} \{ S_{2j} = S_0, S_{2k} = S_0 \}}{(\sum_{k = 1}^n \mathbb{P}\{S_{2k} = S_0 \})^2} = 2 \]
\end{Lemma}

\begin{proof}
\[ \sum_{j = 1}^n \sum_{k = 1}^n \mathbb{P} \{S_{2j} = S_0, S_{2k} = S_0 \}\]
\[ = 2 \sum_{j = 1}^n \sum_{k = 1}^{n - j} \mathbb{P} \{ S_{2j} = S_0, S_{2j + 2k} = S_0 \} + \sum_{j = 1}^n \mathbb{P} \{ S_{2j} = S_0 \} \]
\[ = 2 \sum_{j = 1}^n \sum_{k = 1}^{n - j} \mathbb{P} \{ S_{2j} = S_0\} \mathbb{P} \{ S_{2k} = S_0 \} + \sum_{j = 1}^n \mathbb{P} \{ S_{2j} = S_0 \}\]
\[ \sim \frac{2}{\pi^2} \sum_{j = 1}^n \sum_{k = 1}^{n - j} j^{-1} k^{-1} \sim 2 \Big (\frac{\log n }{\pi} \Big )^2 \sim 2 \Big ( \sum_{k = 1}^n \mathbb{P} \{ S_{2k } =  S_0 \} \Big )^2. \]

\end{proof}

We use the above facts to provide another proof of Theorem 11.

\paragraph{Proof of Recurrence Theorem for $d = 1$.}
\begin{proof}

Contained in the tail $\sigma$-algebra generated by random variables
$X_1, X_2, \ldots$ are events such as
\[ \{A_n > 0 \ \textrm{i.o.} \}, \quad \{ \limsup_{n \to \infty } A_n = 0\} \]
which do not refer to finite subcollections such as $X_1, \ldots
X_n$.  Our random walk $S_n$, by the Markov Property, has a value
after $n$ steps which depend on the $n^\textrm{th}$ step, but not
previous steps. The symmetric nature of the random walk implies that
$ \mathbb{P} \{ \liminf_{n \to \infty} S_n = - \infty \} =
\mathbb{P} \{ \limsup_{n \to \infty } S_n = + \infty \} = C$, while
Lemma 18 guarantees that $C
> 0$.  Since the Zero-One Law guarantees that $C$ can be only zero or one, $C = 1$.


\end{proof}

\paragraph{Proof of Recurrence Theorem for $d = 2$.} (\cite{Pal}, p. 197)
Lemma 15  shows that the random walk on two dimensions satisfies the hypotheses of the second Borel-Cantelli Lemma, which in turn asserts that
\[ \mathbb{P} \{ S_n = S_0 \ \textrm{i.o.} \} \geq 1/2 .\]
By the Zero-One law, since this probability is not zero, it must be one.



\paragraph{Proof of the Recurrence Theorem for $d \geq 3$.} (\cite{Pal}, p. 197)

Lemma 7 asserts that the probability of return when $d \geq 3$ converges in sum.  This satisfies the hypothesis of the first Borel-Cantelli lemma, which immediately shows that the probability of return is zero.



\subsection{\sc{Time}}
Let $\rho_1 (k)= \min \{ n : S_n = k \} \quad k = 1, 2, \ldots $.

\begin{Lemma}(\cite{Pal}, p. 97)
Let $\rho_0 = 0$ and $\rho_k = \min \{ j : j > \rho_{k - 1}, S_j = 0 \} \ k = 1, 2, \ldots$.  Then,
\[ \mathbb{P} \{ \rho_1 = 2k \} = 2^{-2k + 1} k^{-1} \binom{2k - 2}{k - 1} \quad k = 1, 2, \ldots \]
and
\[ \mathbb{P} \{\rho_1 > 2n \} = 2^{-2n} \binom{2n}{n} = \mathbb{P} \{ S_{2n} = 0 \}.\]
\end{Lemma}

\begin{proof}
\[ \mathbb{P} \{ \rho = 2k \} = \frac{1}{2} \mathbb{P} \{ \rho_1 = 2k | X_1 = + 1 \} + \frac{1}{2} \mathbb{P} \{\rho_1 = 2k | X_1 = -1 \} \]
Clearly,
\[ \mathbb{P} \{ \rho_1 = 2k | X_1 = + 1 \} = \mathbb{P} \{ \rho_1 = 2k | X_1 = -1 \} = \mathbb{P} \{ \rho_1 (1) = 2k - 1 \}. \]
\end{proof}

\paragraph{Remark}
\[ \mathbb{P} \{ \rho_1 < \infty \} = \sum_{k = 1}^\infty \mathbb{P} \{ \rho_1 = 2k \} = \sum_{k = 1}^\infty 2^{2k + 1} k^{-1} \binom{2k - 2}{k -1} = 1\]
So the particle returns to the origin with probability one, i.e. we
have a new proof of the Recurrence Theorem for $d = 1$.



While it is guaranteed that a random walker will return to the origin, the mean waiting time of the recurrence is infinite.

\begin{Theorem}
The expected time to hit the origin is infinite.
\end{Theorem}

\begin{proof}
\[ \mathbb{E}[\rho_1] = \sum_{k =1}^\infty 2^{-2k + 2} \binom{2k - 2}{k - 1} = \infty. \]
\end{proof}


%\begin{proof}
%Let $T_0$ be the first $n$ such that $S_n = 0$.  If $S_0 = 1$ we know that $T_0 < \infty$
%with probability one.  However, the amount of time to reach $0$ is at least as large
%as the amount of time to reach $0$ or $N$.  Therefore $\mathbb{E}[T_0] \geq N.$  Since
%this is true for every $N$, $\mathbb{E}[T_0] = \infty.$
%\end{proof}

%\begin{Theorem}
%Suppose that $S_n$ is a simple random walk and $S_0 %= 0$.  The probability
%that the last visit to $0$ up to time $2m$ occurred %at time $2k$ is
%\[ \mathbb{P}\{ S_{2k} = 0\}\mathbb{P}\{S_{2n - 2k} %= 0 \}. \]
%\end{Theorem}

%\begin{proof}
%If $T_{2n}$ is the time of the last visit to $0$ up %to time $2n$, then
%\[ \mathbb{P} \{ T_{2n} \leq 2xn \} \sim \sum_{k %\leq xn} \frac{1}{\pi[k(n-k)]^{1/2}}
%\sim \int_{u = 0}^{xn} \frac{1}{\pi[u(n - u)]^{1/2}} %du = \frac{2}{\pi} \sin^{-1} x^{\frac{1}{2}}. \]
%\end{proof}


\subsection{\sc{Biased Random Walk}}

A biased random walk is a random walk which tends to move in some
directions with greater probability than others.  More formally, let
$S_n$ denote the position after $n$ steps of a a \emph{biased}
one-dimensional random walker. Let $p
> 1/2$ and $S_n = X_1 + \ldots X_n$ , where $X_1, \ldots, X_n $ are
independent with
\[ \mathbb{P} \{x_j\} = 1 - \mathbb{P}\{x_j = -1\} = p
\]

\begin{Theorem}~\cite{Lawler}
Let $S_n$ denote the position of a biased one-dimensional random
walker.  Then there is a $\rho < 1$ such that as $n \to \infty $
\[ \mathbb{P} \{S_{2n} = 0\} \sim \rho^n \frac{1}{\sqrt{\pi n}}, \]
and the random walk is transient.
\end{Theorem}

\begin{proof}
%Let $j$ represent the starting location of the walker (note that we do
%not assume that $j = 0$).  The probability of visiting the origin is $0$
%unless $n - j = 2m, m \in \mathbb{Z}$.  For the random walk to be at the origin
%after $n$ steps, the walk must both go to the origin and also remain there.
%%if $j$ is non-negative and probability $p^{-j}$ if $j$ is negative.  To remain at the
%origin, the walk must use the $2m$ remaining moves by going $m$ steps in one direction and
%$m$ in the other.  There are $\binom{2m}{m}$ ways to do such a move, and each event has
%probability $p^m (1-p)^m$.  To sum things up,
%\[ \mathbb{P}\{ S_{2n} = 0 \} = (1-p)^j \binom{2m}{m} p^m (1-p)^m. \]

%Alternate method:
%Suppose the walker makes $2n$ steps.  In order for the walker to
%move from $j$ to the origin, the walk must consist of $n + j$ steps
%in the direction of the origin and $n - j$ steps in the other
%direction.  There are $\binom{2n}{n + j}$ ways to choose which $n +
%j$ steps are in the direction of the origin.  If $j$ is
%non-negative, then the probability of any particular choice is $p^{n
%+ j} \cdot (1-p)^{n - j}$; if $j$ is negative, then the probability
%is $(1-p)^{n + j} \cdot p^{m - j}$.
The number of choices available for a random walk to return to its
starting point remains the same as in the case of the simple random
walk.  The probability of such paths, however, is now given by $p^n
(1 - p)^n$, since out of $2n$ steps, $n$ must be taken in either
direction, and the probability of moves is $p$ in one direction and
$1-p$ in the other.
\[ \mathbb{P}\{S_{2n} = 0 | P_0 = 0 \} = \binom{2n}{n } p^{n } (1-p)^{n}
= \frac{(2n)!}{(n )!(n )!} p^{n } (1-p)^{n }. \]
Using Stirling's formula, we find that
\[ \frac{(2n)!}{n!n!} p^n (1-p)^n \sim  \frac{\sqrt{4 \pi n }e^{-2n}(2n)^{2n}}{(\sqrt{2\pi n}e^{-n}n^n)^2 } = \frac{2^{2n}}{\sqrt{2 \pi n}} (p(1 - p))^n = \rho^n \frac{1}{\sqrt{\pi n}}.            \]
  This sum converges, so by
the first Borel-Cantelli lemma we have transience.

\end{proof}

%\paragraph{Remark}

%Now we consider a \emph{phased} random walk, in which a random
%walker may move to either side or stay put.

%\begin{Theorem}
%Let $S_n$ be a phased random walk in $\mathbb{Z}^d$ starting at the
%origin, where at each step the walker moves in any of $2d$ positions
%with probability $n \mod d$.  Then the probability of return to the
%origin in $n$ steps is $O(n - d/2)$.
%\end{Theorem}

%\begin{proof}
%Needs proof.


%\end{proof}





%%\subsection{\sc{Electric Potentials}}

%%There is a curious similarity between potential theory and random walks.
%We think of $\mathbb{Z}^d$ as an electrical network in which each pair
%of neighboring points is joined by a conducting wire with resistance $1$ ohm.

%Let G, H be disjoint sets of points in $\mathbb{Z}^d$. Connect a battery into
%the network such that the points in H are joined to earth and the points
%in G are raised to the potential $1$ volt.  This potential difference induces a
%potential $V(w), w \in \mathbb{Z}^d$, together with a current along each wire.
%These potentials and currents satisfy Kirchhoff's laws and Ohm's law.  We use
%this result to provide an alternate proof for the following Theorem:

%\begin{Theorem}
%The simple random walk on $\mathbb{Z}^2$ is persistent.
%\end{Theorem}
%\begin{proof}
%We let G be the origin and $H_n$ the set of points on the edge of the square with
%side length $2n$ and center at 0.  Then,
%\[ p_n (w) = \mathbb{P}\{0 \ \textrm{before} H_n | S_0 = w \} \]
%satisfies the requirements:
%\[ p(w) = 1/4 [(p((w_1 + 1, w_2)) + p((w_1 - 1, w_2)) + p((w_1, w_2 + 1)) + p((w_1, w_2 - 1)))]  \\
%w = (w_1, w_2) \textrm{is subject to the boundary conditions} \\
%p(w) = 0 1 \]

%If $S_0 = 0$, then the probability.
%\end{proof}





\subsection{\sc{Random Walks on Graphs}}

We construct a tree $\mathcal{T}_1$ as follows.  The vertices of
$\mathcal{T}_1$ are the empty word, denoted by $o$, and all finite
sequences of the letters $a, b$, i.e. words $x_1 \ldots x_n $ where
$x_1, x_2, \ldots x_n \in \{a , b \} $.  Both words of one letter
are adjacent to $o$. We say that a word of length $n - 1$ and of
length $n$ are adjacent if they have the exact same letters, in
order, in the first $n - 1$ positions.  Note that each word of
positive length is adjacent to three words and the root is adjacent
to only two words. We construct another tree $\mathcal{T}_2$
similarly, calling the root $\overline{o}$ and using the letters
$\overline{a}, \overline{b}$. Finally we make a tree $\mathcal{T}$
by taking the union of $\mathcal{T}_1$ and $\mathcal{T}_2$ and
adding one more connection: we say that o and $\overline{o}$ are
adjacent.\\


\setlength{\unitlength}{0.75mm}
\begin{picture}(70,50)
\put(65, 25){\vector(1,0){15}} \put(80, 25){\vector(-1,0){15}}
 \put(80,25){\vector(2,1){20}}
\put(80,25){\vector(2, -1){20}} \put(77,28){$o$} \put(96,37){$a$}
\put(96,11){$b$}
\put(100,35){\vector(2,1){20}}\put(100,35){\vector(3, -1){20}}
\put(100,15){\vector(3,1){20}} \put(100,15){\vector(2, -1){20}}
\put(122, 45) {$aa$} \put(122, 29) {$ab$} \put(122, 21){$aa$}
\put(122, 3) {$bb$}% \put(70,15){\vector(2, -1){20}}


\put(65,25){\vector(-2,1){20}} \put(65,25){\vector(-2, -1){20}}
\put(65,28){$\overline{o}$} \put(47,37){$\overline{a}$}
\put(47,9){$\overline{b}$}
\put(45,35){\vector(-2,1){20}}\put(45,35){\vector(-3, -1){20}}
\put(45,15){\vector(-3,1){20}} \put(45,15){\vector(-2, -1){20}}
\put(18, 45) {$\overline{aa}$} \put(18, 29) {$\overline{ab}$}
\put(18, 21){$\overline{aa}$} \put(18,3) {$\overline{bb}$}
\end{picture}


\begin{Lemma}~\cite{Lawler}
$\mathcal{T}$ is a connected tree
\end{Lemma}

\begin{proof} Suppose $x, y \in \mathcal{T}_1$.  We construct a unique path between
them as follows: If $x \sim y $ we are done.  If not, consider the
\emph{common word} consisting of the first k letters in which $x$
and $y$ agree (this may be the empty word).  Any word of length $n$
in this tree is adjacent to only one word of length $n - 1$. Call
the edge between them a \emph{reduction}. Using reductions, we can
find a unique path from $x$ to the common word, and similarly for
$y$. Uniting the path from $x$ to the common word, and from $y$ to
the common word provides the path from $x$ to $y$.

If $x \in \mathcal{T}_1$ and $y \in \mathcal{T}_2$, then we use
reductions to find a unique path from $x$ to $o$ and from $y$ to
$\overline{o}$.  Then we use the fact that $o \sim \overline{o}$ to
find a unique path between $x$ and $y$.
\end{proof}


\begin{Theorem}~\cite{Lawler}
Let $S_n$ denote simple random walk on the tree, where the walker
goes to one of the three neighbors each with probability 1/3, and
each choice is independent of the previous choices.  Then $S_n$ is
transient.
\end{Theorem}

\begin{proof}

Let $p_n = \mathbb{P}\{S_n = S_0\}$.  For the random walk to return to
the starting point, the walk must still make $n$ steps to the left,
and $n$ steps in the other direction.  Steps to the left are made with
probability $\frac{1}{3}$ while steps to the right occur with probability
$\frac{2}{3}$.  The total probability is given by:
\[ p_{2n} = \binom{2n}{n} \Big(\frac{1}{3}\Big)^n \Big(\frac{2}{3}\Big)^n = \frac{(2n)!}{n! n!}\Big(\frac{2}{9}\Big)^n \]
Using Stirling's formula, we arrive at:


\[ p_{2n} = \frac{(2n)!}{n! n!}\Big(\frac{2}{3}\Big)^n \sim \frac{\sqrt{4 \pi n }e^{-2n}(2n)^{2n}}{(\sqrt{2\pi n}e^{-n}n^n)^2 2^{2n}} \Big( \frac{2}{9} \Big )^n=\frac{2^{2n}}{\sqrt{2 \pi n}} \Big ( \frac{2}{9} \Big )^n = \frac{1}{\sqrt{2 \pi n}} \Big (\frac{8}{9} \Big )^n \]
Since the sum
\[ \sum_{n = 1}^\infty \frac{1}{\sqrt{2 \pi n}} \Big (\frac{8}{9} \Big )^n \]
converges, the first Borel-Cantelli lemma guarantees that the walk
is transient.



\end{proof}

\begin{Theorem}~\cite{Lawler}
With probability 1 the random walk does one of the two things:
either the random walk visits $\mathcal{T}_1$ only finitely often,
or it visits $\mathcal{T}_2$ finitely often.
\end{Theorem}

\begin{proof}

In order for a random walk on $\mathcal{T}$ to visit either
$\mathcal{T}_1$ or $\mathcal{T}_2$ finitely often, it must at least
visit the points $o, \overline{o}$ (the 'bridge' points) finitely
often.  Then we have:
\[ \mathbb{P} \{ \textrm{The random walk visits $\mathcal{T}_1$ or
$\mathcal{T}_2$ only finitely often} \} \geq \]
\[\mathbb{P} \{
\textrm{the random walk visits the bridge points finitely often}
\}\] However, transience establishes that the probability of visiting any point finitely often is one, so the random walk must visit either $\mathcal{T}_1$ or $\mathcal{T}_2$ only finitely often.







\end{proof}








%\begin{Definition}
%A \emph{Random Graph on n vertices} is defined by fixing a set of $n$ vertices,
%say $V = [n]$, and flipping a fair coin $\binom{n}{2}$ times to decide adjacency
%of the $\binom{n}{2}$ pairs of vertices.  Let $\mathcal{G}_n$ denote a random graph
%on the vertex set $[n]$.
%\end{Definition}

%\begin{Theorem}
%Let $p_n$ denote the probability that a graph on $n$ vertices has diameter $2$.
%Then $\lim_{n \to \infty} p_n = 1$.
%\end{Theorem}

%\begin{Theorem}
%$\omega(G)$ denotes the size of the largest clique (complete subgraph) in the graph G;
%$\alpha(G)$ denotes the size of the largest independent set (anticlique) in G, and $\chi(G)$
%denotes the chromatic number of G.  Note that $\alpha(G) = \omega(\overline{G})$, where $\overline{G}$
%denotes the complement of $G$.  Also, $\chi(G) \geq \omega (G)$.
%Then, $\chi(G)\geq n/\alpha(G)$.
%Also, there exists $c > 0$ such that for all sufficiently large $n$ there exists a graph $G_n$ with $n$
%vertices such that
%\[ \frac{\chi(G_n)}{\omega(G_n)} \geq \frac{cn}{(log n )^2} \]
%Also, for almost all graphs, $\chi(G) = \theta (n / \log n ) $
%\end{Theorem}


\section{\sc{Random Walks on Random Environments}}

\subsection{\sc{The Creation of the Universe}}
The random walk considered in the first section is a mathematical
model of linear Brownian motion in a homogenous, or non-random,
environment.  We now consider a random environment (in one
dimension) encountered, for instance, in a magnetic field. Instead
of always moving to the right or left with equal probability (as in
the simple random walk) or always moving to the right with one
probability and the left with another (as in the biased random
walk), the chance of moving to the right or left now vary randomly
depending on where the walker is on a one-dimensional integer
lattice. Our model is given in two steps:

\paragraph{God creates the Universe}
With a sequence of i.i.d. random variables $\mathcal{E} = \{ \ldots
E_{-2}, E_{-1}, E_0, E_1, E_2, \ldots \}$ with distribution
$\mathbb{P}_1 \{ E_0 < x \} = \mu_\mathcal{E} (x),  \mu_\mathcal{E}
(0)  = 0, \mu_\mathcal{E} (1) = 1$, God visits the integers and to
$i \in \mathbb{Z}$ randomly assigns a value $E_i$ (this is a random
number between zero and one).


\paragraph{Life in the Universe}
Into a random environment $\mathcal{E}$, a particle is born on the
origin and begins a random walk.  The particle moves a step to the
right with probability $E_0$, and left with probability $1 - E_0$.
If after $n$ steps the particle is at point $i$, then the
probability of a step to the right is $E_i$, while the probability
of a step to the left is $1 - E_i$.  We have defined a random walk
$R_n$ with $R_0 = 0$ and

\begin{eqnarray}
\mathbb{P}_\mathcal{E} \{ R_{n + 1} = i + 1 | R_n = i, R_{n - 1} , R_{n - 2}, \ldots , R_1 \} \nonumber\\
&& = 1 - \mathbb{P}_\mathcal{E} \{ R_{n + 1} = i - 1 | R_n = i, R_{n -1 } , R_{n - 2}, \ldots, R_1 \} = E_i. \end{eqnarray}}


%\[ \mathbb{P}_\mathcal{E} \{ R_{n + 1} = i + 1 | R_n = i, R_{n - 1} , R_{n - 2}, \ldots , R_1 \} = 1 - \mathbb{P}_\mathcal{E} \{ R_{n + 1} = i - 1 | R_n = i, R_{n -1 } , R_{n - 2}, \ldots, R_1 \} = E_i \]

Note that when $\mathbb{P}_1 \{ E_0 = 1/2 \} = \mu_X(1/2 + 0) -
\mu_X(1/2) = 1$, we have our usual simple random walk.

Formally, let $\{ \Omega_1, \mathcal{F}_1, \mathbb{P}_1 \}$ be a
probability space and let $(\omega_1 \in \Omega_1)$ be a sequence of
i.i.d. random variables with $\mathbb{P}_1 \{E_1 < x \} = F(x), F(0)
= 1 - F(1) = 0$ and
\[ \mathcal{E} = \mathcal{E} (\omega_1) = \{ \ldots  E_{-1} = E_{-1}
(\omega_1), E_0 = E_0 (\omega_1), E_1 = E_1(\omega_1), \ldots \} \]
Let $\{ \Omega_2, \mathcal{F}_2 \}$ be the measurable space of the
sequences $\omega_2 = \{ \epsilon_1, \epsilon_2, \ldots \}$ where
$\epsilon_i = 1$ or $-1$ for $i = 1, 2, \ldots$ and $\mathcal{F}_2$
is the natural $\sigma$-algebra (the $\sigma$-algebra generated by
collections of all product sets). Define the random variable $Y_1,
Y_2, \ldots $ on $\Omega_2$ by $Y_i(\omega_2) = \epsilon_i$ for $i =
1, 2, \ldots$ and let $R_0 = 0, R_n = Y_1 + Y_2 + \cdots + Y_n, n =
1, 2, \ldots$. Then we construct a probability measure $\mathbb{P}$
on the measurable space $\{ \Omega = \Omega_1 \times \Omega_2 ,
\mathcal{F} = \mathcal{F}_1 \times \mathcal{F}_2 \}$ as follows: for
any given $\omega_1 \in \Omega_1$ we define a measure
$\mathbb{P}_{\omega1} = \mathbb{P}_{\mathcal{E}(\omega1)} =
\mathbb{P}_\mathcal{E}$ on $\mathcal{F}_2 $ satisfying (2).  \\
Note the difference between $\mathbb{P}_1$ and
$\mathbb{P}_\mathcal{E}$: the former is a probability measure used
when determining the probability that any $i \in \mathbb{Z}$ takes
on some value $E_i$. With the creation of the random environment,
the probability measure $\mathbb{P}_\mathcal{E}$ refers to the
probability applicable for the random walk, referring to the
probability of moving to the right
or left.  %$\mathbb{P}$ is a probability measure that incorporates
%both measures which allows us to talk about the probability of a
%random walk attaining a value.
%on some $\mathcal{F}_1$ with the
%property that the probability ($\mathbb{P}_1$) of $E_i \in
%\mathcal{F}$ taking on some value follows a distribution $\mu_X$

Let $U_k = (1 - E_k)/E_k$, $V_j = \log U_j$, and $F(x)$ as above.
We assume the following conditions:

\begin{eqnarray} \label{conditions}
\exists \ 0 < \beta < 1/2 \ \textrm{s.t.} \ \mathbb{P}\{ \beta < E_0 < 1 - \beta \} = 1 \\
 \mathbb{E}_1 [V_0] = \int_\infty^\infty x d\mathbb{P}_1 \{ V_0 < x \} = \int_{\beta}^{1 - \beta} \log \frac{1 - x}{x} dF(x) = 0\\
0 < \sigma^2= \mathbb{E}_1[ V_0^2] = \int_{\beta}^{1 - \beta} \big( \log \frac{1 - x}{x} \big )^2 dF(x) < \infty.
\end{eqnarray}

Note that for the simple random walk, $\mathbb{P} \{U_0 = 1 \} =
\mathbb{P}_1 \{V_0 = 0 \} = 1$, so (3) and (4) are satisfied.
However, (5) is not satisfied since $\mathbb{E}_1 [V_0^2] = \sigma^2
= 0$ (that is, we expect the simple random walk to be at its
starting point).
\subsection{\sc{Recursion in a Random Environment}} We
can state a theorem of recurrence in random environments analogous
to the result in non-random environment.  With probability one, God
creates an environment in which the random walk is recurrent. First,
two Lemmas:


\begin{Lemma}(\cite{Pal}, p. 311)
Let
\[ p(a, b, c) = \mathbb{P}_\mathcal{E} \{ \min \{ j :j > m , R_j =
a \} < \min \{j : j > m, R_j = c \} S_m = b \} \quad a \leq b \leq c
\] Where $p(a, b, c) = p(a, b, c, \mathcal{E})$ is the probability that a
particle starting from $b$ hits $a$ before $c$ given the environment
$\mathcal{E}$. Then \[ p(a, b, c) = 1 - \frac{D(a, b )}{D(a, c)} \]
where

\[D(a, b) = \left\{ \begin{array}{lll }
\quad   0  & \qquad \qquad \qquad  b = a\\
 \quad   1 & \qquad \qquad \qquad  b = a + 1\\
  \quad   1 + \sum_{j = 1}^{b - a - 1} \prod_{i = 1}^j U_{a + i} & \qquad \qquad \qquad  b \geq a + 2
\end{array} \right.\]

%\[ D(a, b) = \big \{ 0 \quad \textrm{if} \quad b = a \\ 1 \quad \textrm{if} \quad b = a + 1 \\ 1 + \sum_{j = 1}^{b - a - 1} \prod_{i = 1}^j U_{a + i} \quad \textrm{if} \quad b \geq a + 2 \]
and in particular,
\[ p(0, 1, ) = 1 - \frac{1}{D(n)}  \]
where $D(b) = D(0, b) + 1 + U_1 + U_1 U_2 + \cdots + U_1 U_2 \ldots
U_{b - 1}  $
\end{Lemma}

\begin{proof}
Obviously $p(a, a, c) = 1, \ p(a, c, c) = 0,$ and $p(a, b, c) = E_b
p(a, b + 1, c) + (1 - E_b) p(a, b - 1, c)$. Therefore, $p(a, b + 1,
c) - p(a, b, ) = \frac{1 - E_b}{E_b} (p(a, b, c) - p(a, b -1, c)$.
By iteration, we have
\begin{eqnarray}
 p(a, b + 1, ) - p(a, b, c) = U_b U_{b - 1} \cdots U_{a + 1} p(a, a + 1, c) - p(a, a, c)) \nonumber\\
  = U_b U_{b - 1} \cdots U_{a + 1} (p(a, a + 1, c) - 1)
\end{eqnarray}

Adding the above equations for $b = a, a + 1, \ldots , c - 1$ we
have
\[ -1 = p(a, c, c) - p(a, a, c) = D(a, c)(p(a, a +1 , c) - 1) \] or
\[p(a, a + 1, c) = 1 - \frac{1}{D(a, c)} \]
Two equations above imply
\[ p(a, b + 1, c) - p(a, b, c) = -\frac{1}{D(a, c)} U_b U_{b - 1} \cdots U_{a + 1} \]
Adding these equations gives
\[ p(a, b _ 1, c) - 1 = p(a, b + 1, c) - p(a, a, c)\]
\[ = \frac{-1}{D(a, c)} (1 + U_{a + 1} + U_{a + 1} U_{a + 2} + \cdots + U_{a + 1} U_{a + 2} \cdots U_b ) = \frac{-D(a, b + 1)}{D(a, c)}. \]
So we have the lemma
\end{proof}

\paragraph{Consequence}
\begin{eqnarray}\mathbb{P} \{ \lim_{n \to \infty} p(0, 1, n; \mathcal{E}) = \lim_{n \to \infty} ( 1 - \frac{1}{D(n)} ) = 1 \} = 1 \end{eqnarray}
The consequence follows from the previous Lemma and a claim, left
unproven, that $\lim_{n \to \infty} D(n) = \infty$ in probability
(with respect to $\mathbb{P}_1$.)



\begin{Lemma}
For any $-\infty < a \leq b < \infty$ we have
\[ \mathbb{P} \{ \limsup_{n \to \infty} R_n = a \} = \mathbb{P} \{
\limsup_{n \to \infty} R_n = b \} = 0.\]
\end{Lemma}
\begin{proof}
Analogue of Lemma 19.
\end{proof}




\begin{Theorem} (\cite{Pal}, p.311)
Assuming conditions 4, 5, 6 we have
\[ \mathbb{P} \{ R_n = 0 \ i.o. \} = \mathbb{P}_1 \{ \mathbb{P}_{\mathcal{E}} \{ R_n = 0 \ i.o. \} = 1 \} = 1 \]
Assuming 4, 6, and $\mathbb{E}_1V_0 \not = 0$ we have
\[ \mathbb{P}_1 \{ \mathbb{P}_\mathcal{E} \{ R_n = 0 \
\textrm{i.o.} \} > 0 \} = 0 .\]
\end{Theorem}
\begin{proof}
Assume that the walk begins with a move to the right.  Then Lemma 28
implies that the walker either returns to 0 or else goes to
$+\infty$ before it returns.  But by (7), for any $\epsilon > 0$
there is a $n_0 = n_0(\epsilon, \mathcal{E})$ such that $p(0, 1, n)
= 1 - 1/D(n) \geq 1 -\epsilon$ when $n \geq n_0$  Therefore the
probability that the walker returns to zero is greater than $1 -
\epsilon$ for any $\epsilon >0$, and so is one.





\end{proof}




%\begin{Lemma}
%\[ \limsup_{n \to \infty} T_n = \limsup_{n \to \infty} T_{-n} = -\limsup_{n \to \infty} T_n = - \liminf_{n \to \infty} T_{-n} = \infty \textrm{almost surely(a.s.)} \ \mathbb{P}_1 \]
%Assuming the conditions mentioned above.
%\end{Lemma} (~\cite{Pal}, p. 307)

%\begin{proof}

%The claim is consequence of the LIL of Hartmann and Wintner, Lemma 27.
%(sec 4.4).

%\end{proof}


%\begin{Lemma}
%\[ \lim_{n \to \infty} D(n) = \infty \quad \textrm{almost surely} (\mathbb{P}_1) \]
%\end{Lemma} (~\cite{Pal}, p. 308)

%\begin{proof}
%Since
%\[ D(n) = 1 + U_1 + U_1 U_2 + \cdots + U_1 U_2 \ldots U_{n - 1} = e^0 + E^{T_1} + e^{T_2} + \cdots + e^{T_n - 1} \]
%The claim follows from the previous Lemma:
%\end{proof}






%One consequence is:

%\[ \mathbb{P} \{ \lim_{n \to \infty} p(0, 1, n; \mathcal{E}) = \lim_{n \to \infty} ( 1 - \frac{1}{D(n)} ) = 1 \} = 1 \]
%which follows from the previous two lemmas.

%\begin{Lemma}
%For any $- \infty < a \leq b < \infty$ we have
%\[ \mathbb{P} \{ \liminf_{n \to \infty} R_n = a \} = \mathbb{P} \{ \limsup_{n \to \infty} R_n = b \} = 0 \]
%\end{Lemma} (~\cite{Pal}, p. 313)

%\begin{Lemma}[LIL of Hartman-Wintner] (~\cite{Pal}, p. 32)
%Let $Y_1, Y_2,\ldots$ be a sequence of i.i.d. random variables with
%$\mathbb{E}[Y_1] = 0$ and $\mathbb{E}[Y_1^2] = 1$.  Then,
%\[ \limsup_{n \to \infty} b_n (Y_1 + Y_2 + \cdots + Y_n ) = 1 \quad \textrm{a.s.} \]
%\end{Lemma}

%\begin{Theorem}
%Assuming conditions 4, 5, 6 we have
%\[ \mathbb{P} \{ R_n = 0 \ i.o. \} = \mathbb{P}_1 \{ \mathbb{P}_{\mathcal{E}} \{ R_n = 0 \ i.o. \} = 1 \} = 1 \]
%Assuming 4, 6, and $\mathbb{E}_1V_0 \not = 0$ we have
%\[ \mathbb{P}_1 \{ \mathbb{P}_\mathcal{E} \{ R_n = 0 \ \textrm{i.o.} \} > 0 \} = 0 \]
%\end{Theorem} (~\cite{Pal}, p.311)

%The Theorem states that with probability one $(\mathbb{P}_1)$ God creates an environment in which the Recurrence Theorem is true, i.e. the particle returns to the origin with probability 1 $(\mathbb{P}_\mathcal{E})$.
%\begin{proof}
%Assume that $R_1 = 1$.  Then by the previous Lemma, the particle returns to 0 or it is going to $+ \infty$ before returning.  However, by Lemma 25, for any $\epsilon > 0$ there exists an $n_0 = n_0 (\epsilon, \mathcal{E})$ such that $p(0, 1, n) = 1 - 1/D(n) \geq 1 - \epsilon $ if $n \geq n_0$.  So the probability that the particle returns to 0 is large than $1 - \epsilon$ for any $\epsilon > 0$, which proves the Theorem.
%\end{proof}


%\subsection{\sc{Random Walk in Random $\mathbb{Z}^d$}}
%The model presented can be easily extended to several dimensions.  We only consider $d = 2$.  Let
%$U_{ij} = (U_{ij}^{(1)}, U_{ij}^{2}, U_{ij}^{(3)}, U_{ij}^{(4)}) (i, j = 0, 1, -1, 2, -2, \ldots)$ be an aay of i.i.d.r.v.'s with $U_{ij}^{(k)} \geq 0 , U_{ij}^{(1)} + U_{ij}^{(2)} + U_{ij}^{(3)} + U_{ij}^{(4)} = 1$.  The array $\mathcal{E} = \{ U_{ij} , i, j = 0, 1, -1, 2, -2, \ldots \}$ is called a two dimensional random environment.  Having an environment $\mathcal{E}$ a random walk $\{ R_n , n = 0, 1, 2, \ldots \} $ can be defined by $R_0 = 0$ and
%\begin{eqnarray}
% \mathbb{P} \{ R_{n + 1} = (i + 1, j) | R_n = (i, j), R_{n -1 }, \ldots, R_0 \} = U_{ij}^{(1)} \nonumber\\
%\mathbb{P} \{ R_{n + 1} = (i, j + 1) | R_n = (i, j), R_{n - 1}, \ldots, R_0 \} = U_{ij}^{(2)} \nonumber \\
%\mathbb{P} \{ R_{n + 1} = (i -1, j) | R_n = (i, j), R_{n - 1}, \ldots, R_0 \} = U_{ij}^{(3)} \nonumber\\
%\mathbb{P} \{ R_{n + 1} = (i, j -1) | R_n = (i, j), R_{n - 1}, \ldots, R_0 \} = U_{ij}^{(4)}
%\end{eqnarray}

%It is an open question whether a non-trivial, sufficient condition is known for
%\[ \mathbb{P} \{ R_n = 0 \ \textrm{i.o.} \} = 1 \]

%But in the case of $d \geq 2$ we can provide necessary conditions. ~\cite{Kalikow}










\begin{thebibliography}{99}
\bibitem{Grimmett} Grimmett, Stirzaker.  \emph{Probability and Random Process}.  Oxford: Clarendon Press, 1992.

\bibitem{Pal} R\'ev\'esz, P\'al.  \emph{Random Walk in Random and Non-Random Environments}.  New Jersey: World Scientific, 2005.

\bibitem{Lawler} Professor Gregory Lawler's Lecture Notes.
\texttt{http://www.math.uchicago.edu/\%7Elawler/probnotes.pdf}

\bibitem{Spitzer} Spitzer, Frank.  \emph{Principles of Random Walk}.  Princeton: Springer, 1964.

\bibitem{Kalikow} Kalikow S.A. \emph{Generalized Random Walk in a Random Environment}.  The Annals of Probability, 9, 753-768.

\bibitem{Snell} Doyle, Peter and Snell, J.  \emph{Random Walks and
Electrical Networks}.  \texttt{http://arxiv.org/abs/math/0001057}

\end{thebibliography}

\end{document}
