# Random walking and the expected value

I was asked this question at an interview, and I didn't know how to solve it. Was curious if anyone could help me.

Lets say we have a square, with vertex's 1234. I can randomly walk to each neighbouring vertex with equal probability. My goal is to start at '1', and get back to '1'. How many average walks will I take before I return back to 1?

-
What are the neighboring vertices? For 1 just 2? For 2 1 and 3? for 3 2 and 4? for 4 just 3? If this is the case what are the transistion probabilities? Must you go from 1 to 2 and from 4 to 3 and for 2 and 3 are the probabilities 1/2 each for going to 1 or 3 for 2 and 2 or 4 for 3? If I can make all these assumptions then I can solve the problem. Without knowing this I can't. – Michael Chernick Sep 5 '12 at 16:39

After an even number of steps, you are either at 1 or at 3; after an odd number of steps, you are either at 2 or at 4. Hence you cannot return home after an odd number of steps. To return home for the first time after $2n$ steps, you must have had "bad luck" add all odd steps (i.e. have gone to 3 instead of 1) and the choice in even steps (when you are at 4 - except at the beginning) does not matter. Therefore $P(X=2n) = 2^{-n}$ and $E(X) = \sum_{n=1}^\infty 2n P(X=n) = \sum_{n=1}^\infty n 2^{-n}$. In case you dont recognize that series in an interview situation, observe that $E(X) = 2E(X)-E(X)= \sum_{n=0}^\infty (n+1) 2^{1-n}-\sum_{n=1}^\infty n 2^{1-n}=\sum_{n=0}^\infty 2^{1-n}=4$. Note: 2E(X)=2 $\sum_{n=1}^\infty n 2^{-n}$$=\sum_{n=1}^\infty n 2^{1-n} - Since we are not feeling clever, we use a general procedure. We work directly with expectations. Let e be the expected length of the walk. Let a be the expected length of a walk, if we start at 2 and stop when we first end up at 1. By symmetry, this is the same as the expected length of a walk if we start at 4 and stop when we end up at 1. Let b be the expected length of a walk starting from 3, and stopping when we return to 1. Note that b=1+\frac{1}{2}a+\frac{1}{2}a=a+1. This is because if we are at 3, it takes us a step to go to 2 or 4, and in each case our expectation when we get there is a. Note also that e=1+\frac{1}{2}a+\frac{1}{2}a=a+1. This is because we take a step, and end up at a place that has expectation a. Finally,$$a=1+\frac{1}{2}b=1+\frac{1}{2}(a+1)=\frac{3}{2}+\frac{1}{2}a.\tag{$1$}$$This is because if we are at say$2$, we take a step, and with probability$\frac{1}{2}$it's over. With probability$\frac{1}{2}$we end up at$3$, from where the expectation is$a+1$. From$(1)$, we conclude that$a=3$and therefore$e=4$. - If your numbers run around the square, positions$2$and$4$are equivalent. Let$x$be the average number of steps to return to$1$,$y$be the average number of steps to get to$1$from$2$, and$z$to be the average number of steps to get to$1$from$3$. If you are at$3$, you must go to$2$, so$z=y+1$. If you are at$2$, you go to$1$with chance$\frac 12$, so$y=\frac 12+\frac12(1+z)$. Similarly,$x=1+y$. So$y=\frac 12 + \frac 12 (y+2)3$, or$y=3$and$x=4$- By symmetry, the unique invariant probability measure$\pi$for this Markov chain is uniform on the four states. The expected return time is therefore$\mathbb{E}_1(T_1)=1/\pi(1)=4.\$