Compute a probability in Random Walk by Martingales

Question

Let $X_n$ be the state at time $n$ of a Markov chain with these transition probabilities : $$p_{i,i+1}=p_i\qquad,\qquad p_{i,i-1}=q_i=1-p_i$$ $(a)$ Show that $Z_n=g(X_n)\,;\,n\geq0$, is a martingale with respect to $X_n\,;\,n\geq0$, when $g(1)=1$, and $$g(j)=1+\sum_{i=1}^{j-1}\frac{q_1\cdots q_i}{p_1\cdots p_i}\,;\,j\geq 2$$ $(b)$ Find the probability, starting in state $i$, that the chain reaches $n$ before $0$, where $0<i<n$.

**#** from Ross, Probability Models for Computer Science

I've proved part $(a)$ easily, and wrote it for upcoming needed information.

For part $(b)$, despite Martingale approach, I think it's a good idea to find a recursive relation to find the desired probability, like we do for Gambler's Ruin Problem, as follows :

Let $a_k$ be the such probability, starting from state $1\leq k\leq n-1$. Now we can write : $$(p_k+q_k)a_k=a_k=p_k.a_{k+1}+q_k.a_{k-1}\Longrightarrow \frac{p_k}{q_k}=\frac{a_{k+1}-a_k}{a_k-a_{k-1}}\tag{*}$$ We can also manually define $a_0=0,a_n=1$. But from now I don't know there's any way to extract a formula for $a_k$. Please help me HERE !

---

Coming back to Martingales, if we define $N=\min\{t\geq 0|X_t=n\vee X_t=0\}$, then $N$ is a Stopping-Time for $Z_i$ and :

$Z_N=\left\{ \begin{array}{lc} g(n)&\text{with probability $p$}\\ g(0)&\text{with probability $q$} \end{array} \right.$.

where $p$ is the probability chain reaches $n$ before $0$ and $q$ is the probability chain reaches $0$ before $n$. Hence by Stopping Time Theorem, $$p.g(n)+q.g(0)=\mathbb{E}[Z_N]=\mathbb{E}[Z_0]=\mathbb{E}[g(i)]=g(i)\tag{**}$$ But $q=1-p$(why?), intuitively because of positively recurrence of the subchain $\{0,1,\cdots,n\}$. Therefore, $\:p$ will be derived from $(**)$

Answer 1

By the way, there is a typo in the post. The recurrence relationship is meant to say

$$a_{k+1}-a_k = \frac{p_k}{q_k}(a_k-a_{k-1})$$

Let's take $u_k= a_k-a_{k-1}$, $$u_{k+1}= \frac{p_k}{q_k}u_k\tag 1$$

using the fact $a_0=0$ and $a_1=1$, we have

$$u_1+u_2+\cdots+u_n=1\tag 2$$

Repeated applying the recurrence relation (1), we see that for $2\leq i\leq n$

$$u_i = \frac{\prod_{j=1}^{i-1}p_i}{\prod_{j=1}^{i-1}q_i}u_1= c_i u_1\tag 3.$$

From (2), we have

$$u_1(1+c_2+c_3+\cdots+c_n)=1$$

and therefore

$$a_1=u_1=\frac{1}{1+c_2+c_3+\cdots+c_n}$$

This then allows you find other value of $u_i$ (and therefore $a_i$) by (3)