2
$\begingroup$

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.

Any advice?

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – Red Five
    Apr 10 at 22:17

1 Answer 1

2
$\begingroup$

$$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$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .