2016-46.md

course	course_year	question_number	tags	title	year
Markov Chains	IB	46	IB 2016 Markov Chains	Paper 1, Section II, H	2016

Let $\left(X_{n}\right){n \geqslant 0}$ be a simple symmetric random walk on the integers, starting at $X{0}=0$.

(a) What does it mean to say that a Markov chain is irreducible? What does it mean to say that an irreducible Markov chain is recurrent? Show that $\left(X_{n}\right)_{n} \geqslant 0$ is irreducible and recurrent.

[Hint: You may find it helpful to use the limit

$$\lim _{k \rightarrow \infty} \sqrt{k} 2^{-2 k}\left(\begin{array}{c} 2 k \\ k \end{array}\right)=\sqrt{\pi}$$

You may also use without proof standard necessary and sufficient conditions for recurrence.]

(b) What does it mean to say that an irreducible Markov chain is positive recurrent? Determine, with proof, whether $\left(X_{n}\right)_{n \geqslant 0}$ is positive recurrent.

(c) Let

$$T=\inf \left{n \geqslant 1: X_{n}=0\right}$$

be the first time the chain returns to the origin. Compute $\mathbb{E}\left[s^{T}\right]$ for a fixed number $0<s<1$.