# Expected Number of Steps To Reach 0 in Circle

You are in a circle with 100 points labelled 0 - 99 clockwise. You start at 1 and can move left or right with equal probability. What is the expected time to reach $$0$$?

I attempted this by setting up a Markov chain recursive formula for the expectation at each point. For example: $$E_i$$ designates the expected number of steps to reach $$0$$ from point $$i$$. Hence, the first couple equations are:

$$E_1 = \frac{1}{2} \times (1) + \frac{1}{2} \times (E_2 + 1)$$

$$E_2 = \frac{1}{2} \times (E_1 + 1) + \frac{1}{2} \times (E_3 + 1)$$

You can expand this so on until point 99. However, I am having a hard time evaluating this.

• What happens if you start with only three states: $0,1,2$ or only four states: $0,1,2,3$? A pattern should emerge pretty quickly but may differ if the total number of states is odd/even. Apr 10 at 22:17
$$E_1-E_2/2=1$$ $$-E_1/2+E_2-E_3/2=1$$ $$-E_2/2+E_3-E_4/2=1$$ $$\dots$$ $$-E_{97}/2+E_{98}-E_{99}/2=1$$ $$-E_{98}/2+E_{99}=1$$ Adding the $$99$$ equations together gives $$E_1/2+E_{99}/2=99$$. By symmetry $$E_1=E_{99}$$, and so $$E_1=99$$.