I have to do the following problem:

Let $(s_n)_{n\geq 0 }$ be a 1-dimensional, unbiased random walk. For $a,b\in\mathbb Z$, let $T_a=\inf\{n>0:s_n=a\}$ and $T_{a,b}=\inf\{n>0:s_n=a\hspace{3mm} or\hspace{3mm} s_n=b\}$. For $x\in\mathbb Z$, let $\omega(x)=\mathbb P(s_{T_{a,b}}=b \mid s_0=x)$.

Prove that for $a<x<b$, $\omega(x)=\frac{1}{2}(\omega(x+1)+\omega(x-1))$, provided we define $\omega(a)=0$ and $\omega(b)=1$. Conclude that:

$\displaystyle \omega(x)=\frac{x-a}{b-a}$

From this result, how can you recover that $\mathbb P(T_b<\infty)=1$?

I don't know where to start with this one. I'd appreciate hints and any help with this.

  • $\begingroup$ Let $a\to-\infty$. $\endgroup$ – user940 Feb 24 '13 at 2:03
  • $\begingroup$ Are you saying find $\displaystyle lim_{a\rightarrow -\infty}\frac{x-a}{b-a}=1$? $\endgroup$ – Chris Feb 25 '13 at 2:53
  • $\begingroup$ Yes. Yes, I am. $\endgroup$ – user940 Feb 25 '13 at 3:01
  • $\begingroup$ Thanks! and $lim_{a\rightarrow -\infty}\frac{x-a}{b-a}=1\Rightarrow \mathbb P(T_b<\infty)=1$? $\endgroup$ – Chris Feb 25 '13 at 3:03
  • $\begingroup$ Yes, that's right. $\endgroup$ – user940 Feb 25 '13 at 3:06

Well, maybe it can be done in a simpler way without the Markov chain theory, but this will definitely work:

The random walk you have can be seen for the purposes of estimating the probability $\omega(x)$ as a markov chain (let us call it $X=(X_t,t \in \mathbb{N_0})$) with a finite state space $S = \{a,a+1,\ldots,b-1,b\}.$ The points $a$ and $b$ are traps (states with a zero escape probability) and the one-step transition matrix looks like this (the first line represents the transition probabilities from the state $a$ and so on, the last one consists of transition probabilities to $b$): $$ A = \begin{pmatrix} 1 & 0 & 0 & 0&0&\cdots & 0 \\ \frac{1}{2} & 0 & \frac{1}{2} &0&0& \cdots & 0 \\ 0 &\frac{1}{2} &0 &\frac{1}{2} &0&\cdots &0 \\ \vdots&\vdots&\ddots & \vdots & \ddots&\vdots&\vdots\\\ 0&0&0&0&0&\cdots&1 \end{pmatrix}$$

So now you have to calculate the probability that the chain $X$ gets trapped in $b$ conditioned by $X_0=x$. If you know the basics of Markov chains, it should be easy from now on. I hope this will help you to start :).

  • $\begingroup$ Hello, thanks so much for the reply! I'm giving this a try now. $\endgroup$ – Chris Feb 23 '13 at 2:36
  • $\begingroup$ Hey, I've thought about this for a bit and I'm not sure how to calculate the probability that the chain $X$ gets trapped in $b$ conditioned by $X_0=x$. If it's not too much could you show me how this is done? $\endgroup$ – Chris Feb 25 '13 at 2:51
  • $\begingroup$ no problem, but you will have to wait till friday, i don't Havel m computer on me right now and typing (especially LaTeX) on touchscreen tablet is really painful. $\endgroup$ – Trademark Feb 25 '13 at 19:38
  • $\begingroup$ Understood. This problem is due tomorrow actually, so don't worry about it. I'll meet a classmate tonight to work more. Thanks for the pointers! $\endgroup$ – Chris Feb 25 '13 at 20:51

We have the formula: $\displaystyle \mathbb P(A)=\mathbb P(A|B)\mathbb P(B)+\mathbb P(A|B^c)\mathbb P(B^c)$

Think of $\omega (x)=\mathbb P(S_n$ gets absorbed at $b)$

Let $A$ be the event "$S_n$ gets absorbed at $b$", and $B=\{s_1=s_0+1\}$

$\mathbb P(B)=\frac{1}{2}$

$\mathbb P(B^c)=\frac{1}{2}$

$\mathbb P(A|B)=\omega(x+1)$

$\mathbb P(A|B^c)=\omega(x-1) \Rightarrow$

$\displaystyle \omega(x)=\frac{1}{2}\omega(x+1)+\frac{1}{2}\omega(x-1)$

$\displaystyle \hspace{10mm}=\frac{1}{2}\left(\omega(x+1)+\omega(x-1)\right)$.





$\omega(x+1)=2\omega(x)-\omega(x-1) \Rightarrow$






$p=\frac{1}{b-a}$, and hence $\omega(x)=\frac{x-a}{b-a}$


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.