Consider a Markov chain $X$ on the positive integers where for each $n$: $$n\longrightarrow 1,\;2,\;3\;\dots \;n,\;n+1$$ with equal probability, and $n\longrightarrow m$ with zero probability if $m>n+1$.
I am very confused by something that should be simple and would appreciate some help.
I am asked to find the equilibrium distribution $\pi$ of this chain.
Using $p_{ij}^{(n)}\to \pi_j$ does not feel feasible here, so the only other way I can think of is to find $m_k=\mathbb{E}_k[T_k]$ where $T_k$ is the first passage time to $k$, and then $\pi_k=1/m_k$.
Things I tried:
- $\mathbb{E}_k[T_k]=\sum_i i\cdot p_{kk}^{(i)}$. The problem is $p_{kk}^{(i)}$ gets messy rather fast.
- Conditioning we have $\mathbb{E}_k[T_k]=\frac{1}{k+1}\left(\mathbb{E}_1[T_k]+\mathbb{E}_2[T_k]+\cdots +1+\mathbb{E}_{k+1}[T_k]\right)$ but similarly, this does not seem like a good approach.
Am I missing a trick/standard tool here?
The question then says:
"Now suppose we start at $r$ and stop when we return to $r$; prove that the expected number of jumps is $(r-1)!\cdot e$."
I am confused by this, isn't that number exactly $\mathbb{E}_r[T_r]=1/\pi_r$ which would already have from the previous part? Also, since we return to $r$ in one step with probability $1/(r+1)$ it feels like the expectation should have that fraction somewhere in it, but the expansion of $(r-1)!\cdot e$ doesn't.
Hints for part 1:
it should be clear that $\pi_1=\pi_2$ by considering how to get to states $1$ and $2$
similarly $\pi_3 = \pi_2 - \frac12 \pi_1$ and more generally $\pi_{n+1} = \pi_n - \frac1{n} \pi_{n-1}$
solving this and scaling using $\sum_i \pi_i = 1$ will give you the solution