2

I have the following Markov chain and my goal is to find the expected convergence time from $A_1$ to any absorbing state $F_1,F_2,\dots$.

My attempt was to transform the chain into a lumped chain with the states $\{A,F,S_1,S_2,\dots\}$ with $A=\{A_1,\dots\}$, $F=\{F_1,\dots\}$,... . Since the initial state now is $A$, I thought I should only find the expected convergence time to $F$.

enter image description here

Now the lumped chain is a symmetric random walk ($p=q=0.5$) with a single absorbing boundary. I know that the chain will converge to the absorbing state, but I cannot find the expected convergence time since the state space is infinity. Is there a way that I can solve this?

Thanks!

Mehran
  • 126
  • 1
    Great start! Take a look at this question for more info on solving the resulting random walk: https://math.stackexchange.com/questions/306467/expected-number-of-steps-for-reaching-k-in-a-random-walk – arturo Aug 15 '22 at 12:41
  • @arturo Thanks for the link. I had also reached to a similar conclusion that it takes infinite steps to reach to $\cal{F}$ (I used the Gambler's ruin with states 0,N being absorbing, so expected convergence time for each state $i$ is $i(N-i)$. I then let $N\to\infty$ to get infinite steps). However, I had a hard time to grasp the solutions. Since I know that with probability one the chain converges to the absorbing state, but when I found the expected time as infinity, I thought my solution was wrong. – Mehran Aug 15 '22 at 12:54
  • 1
    Random variables can be finite with probability 1 yet have infinite expectation. E.g. if $P(T \ge n)$ is asymptotic to $ cn^{-1/2}$, as happens in this case. – Yuval Peres Aug 18 '22 at 16:04

0 Answers0