3
$\begingroup$

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?

  • 2
    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.2012-09-05

4 Answers 4

7

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

5

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.

4

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

1

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$