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 $(**)$