Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
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. –  Michael Chernick Sep 5 '12 at 16:39

4 Answers 4

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

share|improve this answer

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.

share|improve this answer

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

share|improve this answer

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$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.