Random walking and the expected value

Question

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?

Answer 1

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}$

Answer 2

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$.

Answer 3

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$

Answer 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.$

This principle is easy to remember and can be used to solve other interesting problems.