Ant is on a vertex of a triangle. What is the expected number of seconds to get back to the original vertex?

Question

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.

Answer 1

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.

Answer 2

I assume the ant starts at vertex $A.$ We want to find the expected of value the random variable $X$ which is the number of vertex-to-vertex steps (i.e. the number of seconds) the ant takes. Now $$X=X_{A,B}+X_{B,A}+X_{B,C}+X_{C,B}+X_{C,A}+X_{A,C}$$ where $X_{A,B}$ is the number of times the ant walks from $A$ to $B,\ $ $X_{B,A}$ the number of times it walks from $B$ to $A,\ $ $X_{B,C}$ the number of times it walks from $B$ to $C,$ and so on. By the linearity of expectation, $$E(X)=E(X_{A,B})+E(X_{B,A})+E(X_{B,C})+E(X_{C,B})+E(X_{C,A})+E(X_{A,C}).$$ By symmetry we have $$E(X_{A,B})=E(X_{A,C})\text{ and }E(X_{B,A})=E(X_{B,C})=E(X_{C,B})=E(X_{C,A}).$$ Also $$X_{A,B}+X_{A,C}=1\text{ and }X_{B,A}+X_{C,A}=1$$ because the vertex leaves the vertex $A$ exactly once and enters it exactly once. It follows that $$E(X_{A,B})=E(X_{B,A})=E(X_{B,C})=E(X_{C,B})=E(X_{C,A})=E(X_{A,C})=\frac12$$ and so $$E(X)=6\cdot\frac12=\boxed3.$$ This is a special case of a general theorem about random walks on finite graphs. Namely, if an ant goes on a random walk on a finite connected undirected graph, which ends the first time it returns to the starting vertex, then the expected length of the walk is $\frac{2e}d,$ where $e$ is the number of edges in the graph and $d$ is the degree of the starting vertex. In your case the graph is $K_3,$ the complete graph on three vertices, so $e=3$ and $d=2.$

Answer 3

Let the 3 vertices be A, B, and C. Without loss of generality, assume that the ant starts at A.

Let $E_{A}$, $E_{B}$, and $E_{C}$ be the expected number of seconds to get back to vertex A when it's at A, B and C respectively.

We can write the following relation:

$$E_{A} = 1 + \frac{1}{2}E_{B} + \frac{1}{2}E_{C}$$

$$E_{B} = 1 + \frac{1}{2}(0) + \frac{1}{2}E_{C}$$

$$E_{C} = 1 + \frac{1}{2}(0) + \frac{1}{2}E_{B}$$

Solving the set of equations above, we have

$$E_{B} = 2 $$ $$E_{C} = 2 $$ $$E_{A} = 3 $$

$E_{A} = 3$ is the answer to the question