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) andC)the 4 corners (2 steps away from 0). PlusD)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 getSpoiler: