A fly on a triangle?

Question

A fly is on the vertex of a triangle. It can move left with probability $\frac 12$ and right with probability $\frac 12$.

What is the expected number of moves till it reaches its starting point?

This is my attempted solution.

Let $N$ be the number of moves and let $L$ denote the event the fly moves left on its first turn and $R$ denote the event that it moves right on its first turn. Then

$E[N]=E[N|L]P(L)+E[N|R]P(R)$

$E[N]=E[N|L]\frac{1}{2}+E[N|R]\frac{1}{2}$

Also

$E[N|R]=2\frac{1}{2}+E[N|L]\frac{1}{2}$

since the fly can jump back to its starting point with probability $1/2$ but if it moves right again then this is the same as if it had jumped left on its first go. Similarly

$E[N|L]=2\frac{1}{2}+E[N|R]\frac{1}{2}$

solving this sytem of equations I find $E[N|L]=E[N|R]=2$ and hence $E[N]=2$. But this does not seem right to me. Any ideas where I might have gone wrong?

Answer 1

The easy way is to note that the two non-starting nodes are symmetric, so the expected number of moves to get back to start from $L$ and $R$ are the same. As your move from start is to $L$ or $R$, $E[N]=1+E[R]$ Then $E[R]=\frac 12(1) + \frac 12E[R]$ because you have half chance to go to start and half chance to go to left (which has the same expectation as right). So $E[R]=2, E[N]=3$

For your try, you forgot to add the $1$ move from $N$ to $L$ or $R$. Also writing $2\frac 12$ when you mean the product is confusing. Many (and maybe you later) will read it as $2+\frac 12$

Answer 2

Let $k_n$ be the number of starting moves required to get back to vertex $1$ if you are on vertex $n$ ($n=1,2,3$). Then we have:

\begin{align} k_1&=0\\ k_2&=1+\frac12k_1+\frac12k_3=1+\frac12k_3\\ k_3&=1+\frac12k_1+\frac12k_2=1+\frac12k_2\\ \end{align}

(Since if you are on $k_2$, say, you have to travel $1$ step, and then you land on vertex $1$ with probability $\frac12$, and vertex $3$ with probability $\frac12$, so we have a contribution of $\frac12k_1+\frac12k_3$ to the expected total number of steps.)

Solving these gives:

$$ k_2=1+\frac12k_3=1+\frac12+\frac14k_2\\ \frac34k_2=\frac32\\ k_2=2 $$

Similarly, $k_3=2$.

Now, the expected number of steps given that you start on vertex $1$ (and this does not immediately mean that you've arrived) is given by $1+\frac12k_2+\frac12k_3$, by a similar argument, and this is given by $1+1+1=3$.

Answer 3

After the first step this is the "gambler's ruin" problem for gamblers with $1$ and $2$ dollars respectively (the distances back to the start in the two directions).