Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

enter image description here

Im meant to produce the transition matrix which I've already done (in the picture) and list the communication classes. But Im not sure how to find the probability regarding the hitting times (see question). Any suggestions?


share|cite|improve this question
This will be helpful:… – Byron Schmuland Nov 7 '11 at 21:59


Let $\pi_i = \mathbb{P}\left(\tau_N < \tau_0 \vert X_0 = i \right)$, then $\pi_0 = 0$, and $\pi_N = 1$. Conditioning on the first transition we get $\pi_i = \pi_{i-1} (1-p) + \pi_{i+1} p$. Now solve this recurrence equation.

share|cite|improve this answer
Thanks, apprecaite it! – John Southall Nov 8 '11 at 19:37

Keyword: martingale.

Fix $a\ne0$ and consider $M_n=a^{X_n}$ for every $n\geqslant0$. Then, as long as $1\leqslant M_n\leqslant N-1$, $M_{n+1}=M_n\cdot a$ with probability $p$ and $M_{n+1}=M_n\cdot a^{-1}$ with probability $q=1-p$. Assume that $pa+qa^{-1}=1$, then $(M_n)_{n\geqslant0}$ is a bounded martingale (called de Moivre's martingale) hence $\mathrm E(M_T)=\mathrm E(M_0)$ for every stopping time $T$. If $T=\inf\{\tau_0,\tau_N\}$, $M_T=a^N$ on $[\tau_N<\tau_0]$ and $M_T=1$ on $[\tau_0<\tau_N]$, hence $$ \mathrm E(M_T)=\mathrm P(\tau_N<\tau_0)\cdot a^N+1-\mathrm P(\tau_N<\tau_0). $$ Since $M_0=a^i$, this yields $\mathrm P(\tau_N<\tau_0)=\dfrac{1-a^i}{1-a^N}$ if $a\ne1$. It remains to compute $a$. Since $pa^2-a+q=0$, $a=q/p$ will do for every $p\ne1/2$, in which case one gets $$ \mathrm P(\tau_N<\tau_0\mid X_0=i)=\dfrac{1-(q/p)^i}{1-(q/p)^N}. $$ If $p=1/2$, either one takes the limit when $p\to1/2$ of the formula above or one notes that, in this case, $M_n=X_n$ defines a martingale, to which one can apply the stopping time theorem. Both methods yield $$ \mathrm P(\tau_N<\tau_0\mid X_0=i)=\frac{i}N. $$

share|cite|improve this answer
The other, more general, method is to solve the linear system described by @Sasha. – Did Nov 8 '11 at 6:34
Thanks, I've tried learning both yours and sasha's method, it was helpful. Most appreciated! – John Southall Nov 8 '11 at 19:37
@DidierPiau Thanks for the new technique! (+1) – Sasha Nov 8 '11 at 20:08
@Sasha, new? If only! No, as they say, je suis venu trop tard dans un monde trop vieux... – Did Nov 8 '11 at 21:34
@DidierPiau Sorry, I was not clear. I meant the technique is new to me. – Sasha Nov 8 '11 at 21:47

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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