Random Walk Proof Problem

Question

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.

Answer 1

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 :).

Answer 2

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)$.

Also:

$\omega(a)=0$

$\omega(a+1)=p$

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

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

$\omega(a+2)=2p$

$\omega(a+3)=3p$

$\hspace{13mm}\vdots$

$\omega(a+k)=kp$

$1=\omega(b)=\omega(a+b-a)=(b-a)p\Rightarrow$

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