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

  • $\begingroup$ why does $q=1-p$? because it has to reach $0$ or $n$ eventually (because the Markov Chain is recurrent). I do not really understand your question. Your (**) is the correct answer. You mean you want to solve the recurrence relation? $\endgroup$
    – Lost1
    Jun 29, 2014 at 17:15
  • $\begingroup$ yes. here, i wanted a recursion-based solution $\endgroup$ Jun 30, 2014 at 11:46
  • $\begingroup$ I imagine it is probably possible. i will write something when i have more time. (if i figure it out) $\endgroup$
    – Lost1
    Jun 30, 2014 at 11:47
  • $\begingroup$ I am a little puzzled why the book took $1+...$ to be martingale rather than just the ... part to be a martingale. You should find the answer from the martingale approach agrees with my answer. $\endgroup$
    – Lost1
    Jul 2, 2014 at 17:02

1 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


and therefore


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.