Classification of states

Let $l_{i j}(n) = \mathbb {P}\left(X_{n} = j, X_{k} \neq i \text{ for } 1 \leq k < n \mid X_{0} = i\right)$, the probability that the chain passes from $i$ to $j$ in $n$ steps without revisiting $i$. Writing

show that $P_{i j}(s) = P_{i i}(s) L_{i j}(s)$ if $i \neq j$. Deduce that the first passage times and last exit times have the same distribution for any Markov chain for which $P_{i i}(s) = P_{j j}(s)$ for all $i$ and $j$. Give an example of such a chain.

Let $X$ be a Markov chain containing an absorbing state $s$ with which all other states $i$ communicate, in the sense that $p_{i s}(n) > 0$ for some $n = n(i)$. Show that all states other than $s$ are transient.

Show that a state $i$ is recurrent if and only if the mean number of visits of the chain to $i$, having started at $i$, is infinite. That is to say, $i$ is recurrent if and only if $\sum_{n} p_{i i}(n) = \infty$.

Let $V_{j} = \left|\left\{ n \geq 1: X_{n} = j\right\} \right|$ be the number of visits of the Markov chain $X$ to $j$, and define $\eta_{i j} = \mathbb {P}_{i}\left(V_{j} = \infty \right)$. Show that:

The distinct pair $i, j$ of states of a Markov chain is called symmetric if

where $T_{i} = \min \left\{ n \geq 1: X_{n} = i\right\}$. Show that, if $X_{0} = i$ and $i, j$ is symmetric, the expected number of visits to $j$ before the chain revisits $i$ is 1. [Cf. the quotation following Theorem (3.10.18).]

Let $X$ be a Markov chain, and let $T$ be a geometric random variable with $\mathbb {P}\left(T > n\right) = s^{n}$ for $n \geq 0$, which is independent of $X$. By considering the expected number of visits by $X$ to a given state before time $T$, prove Theorem (6.2.3).

Let $X$ be an ergodic Markov chain started from $a$, and assume $X$ is irreducible (in that, for states $i, j$, there exists $m \geq 0$ such that $p_{i j}(m) > 0$). Let $a, b, c$ be distinct states, and let $T(a, b, \neg c)$ be the time until $X$ first visits $b$, with no intermediate visit to $c$. That is, if $X$ visits $b$ before $c$, then $T(a, b, \neg c)$ is that time, and if $X$ visits $c$ before $b$ we set $T(a, b, \neg c) = \infty$. Let

Show that

where, for example, $F_{a b}(s)$ is the probability generating function of the first passage time $T_{a b}$ from $a$ to $b$ irrespective of intermediate visits to $c$. Show further that

where, for example, $\mu_{a b} = \mathbb {E}_{a}\left[T_{a b}\right]$.