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