Markov chain problem to write a recursive equation

Question

write a recursive equation for $a_N(i)$ by considering what happens on the first transition out of state $i$.

Please help me on this problem. I don't know how to start. Thanks!

Answer 1

Denoting with $\tau_i$ the first time we visit a state $i$, we have: \begin{align*} a_N(i) &= \mathbb{P}(\tau_N < \tau_0 | X_t = i). \end{align*} If we are now in $i$ the next step we are either in $i-1, i+1$ or again in $i$ itself, which gives: \begin{align*} a_N(i) &= p_1 \mathbb{P}(\tau_N < \tau_0 | X_t = i, X_{t+1} = i+1) + q_1 \mathbb{P}(\tau_N < \tau_0 | X_t = i, X_{t+1} = i-1) + r_1 \mathbb{P}(\tau_N < \tau_0 | X_t = i, X_{t+1} = i) \\ &= p_1 \mathbb{P}(\tau_N < \tau_0 | X_{t+1} = i+1) + q_1 \mathbb{P}(\tau_N < \tau_0 | X_{t+1} = i-1) + r_1 \mathbb{P}(\tau_N < \tau_0 | X_{t+1} = i) \\ &= p_1 a_N(i+1) + q_1 a_N(i-1) + r_1 a_N(i), \end{align*} where the second step follows from the properties of a Markov Chain. Rewriting now gives the recursion: \begin{align*} a_N(i+1) &= \frac{-q_1}{p_1}a_N(i-1) + \frac{1-r_1}{p_1}a_N(i) \end{align*}

Answer 2

There are two cases coming out of state $i$. You either go to state $i-1$ or state $i+1$. What are the probabilities of both cases? What are the probabilities of going to $0$ or $N$ first coming from those states?