Thread: 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

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 , 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 is . Then deduce the probability of being at A at time (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 . Or (this may be easier) you use and note that 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 . (Note that P(T>0)=P(T>1)=1)

You should get

Spoiler:

E[T]=4.5