\documentclass[a4paper,12pt]{article}
\newcommand{\ds}{\displaystyle}
\newcommand{\pl}{\partial}
\parindent=0pt
\begin{document}


{\bf Question}

Starting from an origin a particle moves in a plane in
two-dimensional simple random walk.  At each step it can move one
unit north or south (each with probability $\frac{1}{2}$) and,
independently, one unit east or west (each with probability
$\frac{1}{2}$).  After the step is taken, the move is repeated
from the new position and so on indefinitely.  Sketch one
realisation of this process.  By regarding the process as the
product of two independent simple random walks, calculate the
probability that the particle is at the origin after $k$ steps.
Hence show that with probability 1 the particle returns infinitely
often to the origin.



\vspace{.25in}

{\bf Answer}


\begin{center}
\setlength{\unitlength}{.4in}
\begin{picture}(8,9)
\put(4,0){\line(0,1){8}}

\put(0,4){\line(1,0){8}}

\multiput(0,0)(1,0){9}{\circle*{.05}}

\multiput(0,1)(1,0){9}{\circle*{.05}}

\multiput(0,2)(1,0){9}{\circle*{.05}}

\multiput(0,3)(1,0){9}{\circle*{.05}}

\multiput(0,4)(1,0){9}{\circle*{.05}}

\multiput(0,5)(1,0){9}{\circle*{.05}}

\multiput(0,6)(1,0){9}{\circle*{.05}}

\multiput(0,7)(1,0){9}{\circle*{.05}}

\multiput(0,8)(1,0){9}{\circle*{.05}}

\put(4,4){\line(1,1){1}}

\put(4,4){\vector(1,1){0.5}}

\put(5,5){\line(1,-1){1}}

\put(5,5){\vector(1,-1){0.5}}

\put(6,4){\line(1,1){1}}

\put(6,4){\vector(1,1){0.5}}

\put(7,5){\line(-1,1){2}}

\put(7,5){\vector(-1,1){0.5}}

\put(6,6){\vector(-1,1){0.5}}

\put(5,7){\line(-1,-1){3}}

\put(5,7){\vector(-1,-1){0.5}}

\put(4,6){\vector(-1,-1){0.5}}

\put(3,5){\vector(-1,-1){0.5}}

\put(2,4){\line(1,-1){1}}

\put(2,4){\vector(1,-1){0.5}}

\put(3,3){\line(-1,-1){1}}

\put(3,3){\vector(-1,-1){0.5}}


\end{picture}
\end{center}

The reasoning is very similar to the 1-dimensional case. To return
to 0 the particle must do so as a result of a simultaneous return
in in respect of movement both east/west and north/south.

$\ds P({\rm Particle\ is\ at\ 0\ after\ } k\ {\rm steps}) =
\left\{
\begin{array}{ll} 0 & {\rm if\ } k{\rm\ is\ odd} \\ \left[ \left(
\begin{array}{c} 2n \\ n \end{array} \right) \left( \ds\frac{1}{2}
\right)^{2n} \right]^2 & {\rm if\ }k = 2n \end{array} \right.$

\medskip

The expected number of returns to the origin is \begin{eqnarray*}
E & = & \sum_{k = 1}^\infty E(R_k) \cdot R_k =
\left\{\begin{array}{ll}  1 & {\rm if\ particle\ at\ 0\ after\ }
k\ {\rm steps} \\ 0 & {\rm otherwise} \end{array} \right. \\ & = &
\sum_{k=1} ^\infty P(R_k = 1) \\ & = & \sum_{n=1}^\infty  \left[
\left( \begin{array}{c} 2n \\ n \end{array} \right) \left(
\frac{1}{2} \right)^{2n} \right]^2   \\ & \approx &
\sum_{n=1}^\infty \frac{1}{\pi n} \end{eqnarray*}

using Stirling's approximation. The series diverges, so $E=
\infty$.  Standard theory gives $\ds P = 1 - \frac{1}{1+E}$ so $P
= 1$



\end{document}