Ant on a Cube
Goldman Sachs, Wincent
You start in one of the corners of the cube. Then you randomly pick one nearby edge and move to its end. You then repeat this process indefinitely. What is the expected number of moves you will make before you reach the opposite corner of the cube?
Answer
This is a markov chain problem. You can tell because they ask for an expected number of steps until a result, and if you tried to evaluate all possibilities manually there are infinite paths you can take. You solve it by drawing a diagram and recognising when familiar states appear again.
Looking at the image above, we start off at state $S_0$, which is 3 edges away from the finish $S_3$. Next step invariably leads us to one of the three vertices which are 2 edges away from the finish (call it $S_1$). The key is to recognise that all these three states are equivalent - 1 step away from the start and 2 steps away from the end. In turn, expected number of steps from $S_0$ is $E_0 = 1 + E_1$ where $E_1$ is the expected number of states once we are in state $S_1$.
From there, we have $\frac{1}{3}$ chance of moving back to $S_1$ and $\frac{2}{3}$ chance of moving to state $S_2$ - which is two edges away from $S_0$ and one edge away from $S_3$. Finally, we have $\frac{1}{3}$ chance of moving to $S_3$ and $\frac{2}{3}$ chance of moving back to $S_2$.
Setting up the equations, we have: $$E_0 = 1+E_1$$ $$E_1 = \frac{1}{3} \cdot E_0 + \frac{2}{3} \cdot E_2 + 1$$ $$E_2 = \frac{1}{3} \cdot E_3 + \frac{2}{3} \cdot E_1 + 1$$ $$E_3=0$$ Solving the system, we find $E_0=10$