Math 6010 • Linear Models

Consider a one-dimensional simple symmetric random walk:
\(S_n=x+\sum_{k=1}^{n}X_k\), where \(x\) is where the walk starts and
\(\{X_n:n\geq1\}\) are i.i.d. with
\[
  \Prob(X_n=1)=\Prob(X_n=-1)=1/2.
\]
\begin{enumerate}
\item[(a)] Compute the probability that starting at \(x=0\) the random walk will
hit \(-1\) before it hits \(b\in\mathbb{N}\). Deduce from this that the random walk
is recurrent, i.e. starting at 0 the random walk will return to 0 with
probability 1.
\item[(b)] Compute the mean time it takes the random walk to go from \(x=0\) to
\(-1\). Deduce from this that the random walk is null recurrent, i.e. starting at
0, the mean time it takes to return to 0 is infinite.
\end{enumerate}
(Hint: Prove first that when \(x=0\) both \(S_n\) and \(S_n^2-n\) are martingales.)

\newpage