A particle moves on 12 points situated on a circle. At each step it is
equally likely to move one step in the clockwise or in the
counterclockwise direction. Find the mean number of steps for the
particle to return to its starting position.
Here is what I have tried:
Let $X_i$ be the event that the particle returns to its starting position given that it starts at $i$, then we have
$E[X_i]=\frac12E[X_{i-1}]+\frac12[X_{i+1}]=\frac12(\frac12(2)+\frac12E[X_{i+2}])+\frac12(\frac12(2)+\frac12E[X_{i-2}]$
which yields $E[X_i]=1+\frac12E[X_{i+2}]+\frac12E[X_{i-2}]$.
I am now stuck. How should I proceed?
Thanks in advance.
Here is my second attempt. Please feel free to comment on it:
Note that the above Markov chain is doubly stochastic, i.e. the sum of all entries in the same column sum up to $1$. Thus, the limiting probability $\pi_i$ for all $i$ should be $\frac1{12}$.
Now, $\pi_i$ being the limiting probability, we know that it is equal to $\frac1{m_{jj}}$, where $m_{jj}$ equals to the expected number of transitions required for state $j$ to return to state $j$. It now follows that the mean number of steps for particle to return to its starting position is $1/ (\frac1{12})=12$.
Best Answer
Denote with $1$ it's starting position. Let $h(i)$ be the expected number of steps to return to the position $1$ starting from position $i$ for $i=1,2,\ldots 12$. To avoid confusion it can be helpful to denote state $1$ (the initial state) as state $13$ when you visit it the second time. With this notation you have that $$h(1)=1+\frac{1}{2}h(2)+\frac{1}{2}h(12)$$ but $$h(13)=0$$ (since starting from $1$ you have first to move away (so $h(1)\neq0$) and then visit this state again in order to satisfy your target of returning (so $h(13)$ or $h(1')$ is equal to $0$). This gives you the set of equations $$\begin{cases}h(1)=1+\frac{1}{2}h(2)+\frac{1}{2}h(12)\\h(2)=1+\frac{1}{2}h(13)+\frac{1}{2}h(3)=1+\frac{1}{2}h(3)\\h(3)=1+\frac{1}{2}h(2)+\frac{1}{2}h(4)\\\ldots\\h(11)=1+\frac{1}{2}h(10)+\frac{1}{2}h(12)\\h(12)=1+\frac{1}{2}h(13)+\frac{1}{2}h(11)=1+\frac{1}{2}h(11)\\\end{cases}$$ which you can solve recursively to determine $h(1)$.