Ant walking in hexagon

Question

There is a hexagon and an ant is performing a random walk on the edges and lines joining center and vertex with equal probability to choose next edge/line. What is the expected number of steps (one edge/line is equal to one step) it needs till it reaches the center again?
There is similar question here but we have a center in this case.

Answer 1

2 approaches:

1) Markov Chains. Your problem can be modelled by a Markov chain where each vertex is a state. Your Transition Matrix looks like (assuming the center is an absorbing state):

$$ TM=\begin{pmatrix} 0& 0& 0& 0& 0& 0& 0\\ 1/3& 0 & 1/3& 0& 0& 0& 1/3\\ 1/3& 1/3& 0& 1/3& 0& 0& 0\\ 1/3& 0 & 1/3& 0& 1/3& 0& 0\\ 1/3& 0 & 0& 1/3& 0& 1/3& 0\\ 1/3& 0 & 0& 0& 1/3& 0& 1/3\\ 1/3& 1/3 & 0& 0& 0& 1/3& 0\\ \end{pmatrix} $$

where i'm labeling the first row/column as the center and the other rows/colums as the rest of the vertices clockwise from the top.

Then to compute the average steps to go back to center from each vertex you can compute:

$$(Id-TM)^{-1}\begin{pmatrix} 0\\ 1\\ 1\\ 1\\ 1\\ 1\\ 1\\ \end{pmatrix}=\begin{pmatrix} 0\\ 3\\ 3\\ 3\\ 3\\ 3\\ 3\\ \end{pmatrix}$$

So you need 3 steps to get from any vertex back to the center plus the step to get out from the center so finaly you need 4 steps total.

2) Series. As commented above and observing the simetry in the problem, Markov chains look like overkill.

You can compute $$1+\sum_{i=1}^{\infty}iP(i)$$ where $$P(i)=\frac{1}{3}\left(\frac{2}{3}\right)^{i-1}$$ since you have 1 out of three possibilities to return at step $i$ after you have to travelled along the exterior vertices for $i-1$ steps.

Using that $$\sum_{i=1}^{\infty}ik^{i-1}=\left(\sum_{i=0}^{\infty}k^{i}\right)'=\frac{1}{(1-k)^2} $$ you get $$1+\sum_{i=1}^{\infty}iP(i)=4$$ as above.

Answer 2

The ant will take 1 step to go outside, and then it can take 1 step to go back in, or it can take 1 step along the outside and then go back in, or ... In other words, it will take 1 step to go out plus 1 or more steps to go back in.

So, let $P(i)$ be the probability of taking $i$ steps to go back in. Then, the expected number of steps to go back in is the number of steps $i$ multiplied by the probability of $P(i)$, for all $i$ ranging from 1 to infinity. Add 1 for the initial step to go out, and you get that the expected number of steps is:

$1+\sum^\infty_{i=1} i*P(i)$ (so this will be a geometric series)

As for $P(i)$ I will leave that up to you, but Pieter gave you a good hint.

Answer 3

Denote by $E_{\rm rim}$ the expected number of additional steps when the ant sits on an outer vertex. Then $$E_{\rm rim}=1+{2\over3}E_{\rm rim}\ ,$$ hence $E_{\rm rim}=3$, and the expected number at the start is $E_0=1+E_{\rm rim}=4$. By the way: The information that the rim is a hexagon is superfluous; it could be any $n$-gon with $n\geq2$.