# Thread: 2d random walk on Z^2

1. ## 2d random walk on Z^2

Hi,
I'm stuck with this question about 2d random walks on Z^2

Let S_n = (X_n, Y_n) be a simple symmetric random walk in Z^2, starting from (0, 0), and set T = inf {n >= 0: max{|X_n|, |Y_n|} = 2}. Calculate E(T) (Expectation of T).

How would I proceed? would i just use the standard definition of expectation? if so, i would need to work out P[T=n] for natural numbers n yes? but how would i work this out, there are too many possibilities!!!! Is there a formula for this?

Thanks

2. Originally Posted by ramdayal9
if so, i would need to work out P[T=n] for natural numbers n yes? but how would i work this out, there are too many possibilities!!!!
Hi,

this is a nice problem; at first, there indeed seems to be extremely many possibilities, but symmetry simplifies the situation a lot.

So you want the expected time needed to exit the 3x3 square centered at 0. There are in fact only 3 kinds of vertices: A) the middle vertex 0, B) the four "medians" (1 step away from 0) and C) the 4 corners (2 steps away from 0). Plus D) the outside vertices.

You can sketch a much simpler equivalent Markov chain with the only states A,B,C,D; for instance $\displaystyle p_{A,B}=1, p_{B,A}=\frac{1}{4}=p_{B,D}, p_{B,C}=\frac{1}{2}$, etc.

Starting from 0, i.e. from A, you see that the walk can only be at B (or D) at odd times. Using induction, prove that the probability of being at B at time $\displaystyle 2k+1$ is $\displaystyle \frac{1}{2^k}$. Then deduce the probability of being at A at time $\displaystyle 2k$ (hint: the walk is at B right before) and similarly for C.

From there, you have several possibilities to conclude. Either you compute the probability to be at D at time n (this means being at B at time n-1 if n is even, or at C at time n-1 if n is odd) and sum $\displaystyle E[T]=\sum_n n P(T=n)$. Or (this may be easier) you use $\displaystyle E[T]=\sum_{n=0}^\infty P(T> n)$ and note that $\displaystyle P(T> n)$ is the probability that the walk at time n is either at A, B or C (thus at B if n is odd, or at A or C if n is even) and you just have to sum the probabilities to get $\displaystyle P(T>n)$. (Note that P(T>0)=P(T>1)=1)

You should get
Spoiler:
E[T]=4.5