An Ant is on a vertex of a triangle. Each second, it moves randomly to an adjacent vertex. What is the expected number of seconds before it arrives back at the original vertex?
My solution: I dont know how to use markov chains yet, but Im guessing that could be a way to do this. I was wondering if there was an intuitive way to solve this problem. I would have guessed 3 seconds as an answer.
I'm assuming that if it is at Vertex A, there is a 1/2 chance of going to Vertex B or C. So minimum number of seconds is 2 seconds. Max number could be infinite if it keeps bouncing back between B and C without returning to A.
I'm still not sure how to do this puzzle.
Best Answer
The ant moves $1$ time, then moves another $N$ times to return to the original vertex. After the first move, the ant either takes one more move back to the original vertex, or it moves to the other non-original vertex, then continues trying from there. Recursively then:
$$\mathsf E(N) ~=~ \tfrac 12+\tfrac 12(1+\mathsf E(N)) \\ ~ \\ \therefore \quad \mathsf E(N)+1=3$$
The expected time the ant takes to move and return to the origin is $3$seconds.