Assignment 4

Assigned 2025-09-17, due 2025-10-01

Unless stated otherwise, assume $(X_n)$ is a time homogeneous Markov chain on a finite state space $\mathcal X$ with transition matrix $P$.

Question 1

Prove this lemma showing $\P^x(\tau^{+} > n)$ is summable.
Prove this corollary relating $\pi(x)$ and $\E^x \tau^{+}$. (You should also prove the identity used in this remark, which is used in the proof outline.)

Question 2

Suppose $P$ is a transition matrix of a Markov chain on a finite state space. Let $v$ be a left eigenvector of $P$ with eigenvalue $\lambda \in \C$. This means $v P = \lambda v$; however $v$ need not be a probability distribution. The entries of $v$ may be complex, and need not sum to $1$.

Show that $\abs{\lambda} \leq 1$.
Suppose $P$ is irreducible, and $\pi$ is the unique stationary distribution. If $\lambda = 1$, show that there exists $\alpha \in \C$ such that $v = \alpha \pi$.

Question 3

Prove this lemma showing that for aperiodic chains there exists $\N \in \N$ such that for every $x \in \mathcal X$, and every $n \geq N$, we have $P^n(x, x) > 0$.

Question 4

Let $(X_n)$ be an irreducible Markov chain with transition matrix $P$. Let $(Y_n)$ be the lazy chain with transition matrix $Q$ as defined in this remark.

Show that $Q$ is both irreducible and aperiodic, and has the same stationary distribution as $P$.
Let $S \subseteq \mathcal X$, $\sigma = \min\set{n \in \N \st X_n \in S}$, $\tau = \min\set{ n \in \N \st Y_n \in S}$, $f \colon S \to \R$ and define the functions $u$, $v$ by \begin{equation} u(x) = \E^x f(X_\sigma)\,, \qquad v(x) = \E^x f(Y_\tau) \,. \end{equation} Find a relation between $u$ and $v$, and prove it.
Let $u_n(x) = \P^x( \sigma \leq n )$ and $v_n(x) = \P^x( \tau \leq n )$. Find a relation between $u$ and $v$ and prove it.

The remaining questions are interesting questions related to the material we are covering. In order to keep the length of the homework assignment reasonable, these questions are not part of your homework. They are included here as they might be interesting for some of you (and they may be moved to a later homework in future). There is no extra credit for doing them.

Optional question 5

Let $X$ be an Markov chain with transition kernel $P$. For every $x \in \mathcal X$, define \begin{equation} \mathcal T(x) = \set{ n \in \N \st P^n(x, x) > 0 } \,. \end{equation} If $X$ is irreducible, then show that for every $x, y \in \mathcal X$, we must have $\gcd(T(x)) = \gcd(T(y))$. (The number $\gcd(T(x))$ is then called the period of the chain.)

More optional questions may be added later.