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?
 A: 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$. 
A: 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.$ 
This principle is easy to remember and can be used to solve other interesting problems.
A: 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}$
A: 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$
