An ant on a triangle

Label the vertices of the triangle by $a,b,c$ and assume that the ant was at vertex $a$ initially. Let $N(b)$ and $N(c)$ denote the expected number of moves to reach vertex $a$ starting from vertices $b$ and $c$ respectively. Hence we have the following equation : $N(b)=\frac{1}{2}(1) + \frac{1}{2}(1+N(c))$ and $N(c)=\frac{1}{2}(1)+\frac{1}{2}(1+N(b))$ . Solving these two, we have $N(b)=N(c)=2$ . Since after the first move, the ant reaches either vertex $a$ or $b$ (with equal probability), the expected number of moves till it reaches the vertex $a$ again is $1+2=3$ .

This is a textbook example of when to use a Markov chain.

We define three states:

• state 1 refers to the initial state, before the ant has moved from the initial vertex

• state 2 refers to the state when the ant is on either of the two "non-initial" vertices

• state 3 is an absorbing state, when the ant has returned to the initial vertex

The transition matrix, $P$ is as follows:

$P=\begin{bmatrix} 0 & 1 & 0 \\ 0 & { 1 }/{ 2 } & { 1 }/{ 2 } \\ 0 & 0 & 1 \end{bmatrix}$

We define $\mu_{i}$ as the expected number of moves from state $i$ to the absorbing state (state 3). We would like to find $\mu_{1}$ (the expected amount of time it takes to go from state 1 to state 3). Clearly $\mu_{3} = 0$ . For the other states (the "transient" states), $\mu_{i}$ may be described as follows:

${ \mu }_{ i }=1+\sum _{ j=1 }^{ m }{ { P }_{ ij }\cdot { \mu }_{ j } }$

... where $m = 3$ is the total number of states in the Markov chain.

Using the values in the transition matrix, $P$ , we find the following system of equations:

• ${ \mu }_{ 1 }=1+{ \mu }_{ 2 }$

• ${ \mu }_{ 2 }=1+\frac { 1 }{ 2 } { \mu }_{ 2 }+\frac { 1 }{ 2 } { \mu }_{ 3 }$

We know that $\mu_{3} = 0$ , since state 3 is an absorbing state. This gives us two equations with two unknowns:

• ${ \mu }_{ 1 }=1+{ \mu }_{ 2 }$

• ${ \mu }_{ 2 }=1+\frac { 1 }{ 2 } { \mu }_{ 2 }$

We can solve to find $\mu_{2} = 2$ and $\mu_{1} = 3$ .

The answer ( $\mu_{1}$ ) is 3 (a = 3, b = 1, user enters 4).

Let P(E) be the expected number of moves.

P(L) be the expected number of moves after the ant moves left.

P(R) be the expected number of moves after the ant moves right.

P(LR) be the expected number of moves after the ant moves left than right and so on.

Then P(E)=1/2 P(R) + 1/2 P(L)

Note that the expected number of moves after moving right and left is the same.

Then P(E)=P(L)=P(R)

P(L)=1/2 P(LR)+ 1/2 P(LL) => P(LR) means the ant is on the original side.

Since LR means that the ant has made two move, P(E)= 1/2 (2) +1/2 P(LL)

1/2 P(LL) = 1/4 P(LLR) +1/4 P(LLL)=1/4 P(LLR)+ 1/4 (3)

P(E) = 1/2 (2) + 1/4 (3) + 1/4 P(LLR)

Then continuing this, we get a summation tending to infinity.

S= $\frac { 2 }{ 2 } +\frac { 3 }{ 4 } +\frac { 4 }{ 8 } +\frac { 5 }{ 16 } +...$

2S= $\frac { 2 }{ 1 } +\frac { 3 }{ 2 } +\frac { 4 }{ 4 } +\frac { 5 }{ 8 } +...$

S= $2+\frac { 1 }{ 2 } +\frac { 1 }{ 4 } +\frac { 1 }{ 8 } +\frac { 1 }{ 16 } +... = \frac { 3 }{ 1 }$

3 + 1 = $\boxed {4}$

Can someone tell is my approach right?New in here 3 Days

So the probability of the ant to get to the starting point in 2 moves is 2*1/(2^2) and multiply it to number of moves we get a infinite sequence as

Summation (n/2^n )*2 till infinity from n=2

Solving this we get 3

So the answer is 3/1 and hence a+b=4