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?