2009-43.md

course	course_year	question_number	tags	title	year
Markov Chains	IB	43	IB 2009 Markov Chains	Paper 3, Section I, H	2009

Let $\left(X_{n}\right){n \geqslant 0}$ be a simple random walk on the integers: the random variables $\xi{n} \equiv X_{n}-X_{n-1}$ are independent, with distribution

$$P(\xi=1)=p, \quad P(\xi=-1)=q$$

where $0<p<1$, and $q=1-p$. Consider the hitting time $\tau=\inf \left{n: X_{n}=0\right.$ or $\left.X_{n}=N\right}$, where $N>1$ is a given integer. For fixed $s \in(0,1)$ define $\xi_{k}=E\left[s^{\tau}: X_{\tau}=0 \mid X_{0}=k\right]$ for $k=0, \ldots, N$. Show that the $\xi_{k}$ satisfy a second-order difference equation, and hence find them.