Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

Cheers.

share|improve this question
3  
This will be helpful: math.stackexchange.com/questions/47627/… –  Byron Schmuland Nov 7 '11 at 21:59
add comment

2 Answers 2

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|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
add comment

HINT:

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|improve this answer
    
Thanks, apprecaite it! –  John Southall Nov 8 '11 at 19:37
add comment

Your Answer

 
discard

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.