Markov Chains and Generators - Adam Oberman Math

Formal definitions (Ch 5 of Stuart and Pavliotis)

we introduce Markov chains on a countable state space. Without loss of generality we take this state space to be $\mathcal{I}$ , a subset of the positive integers $\mathbb{N}$ .

A matrix $P$ with entries $p i j$ is a stochastic matrix if

$\sum_{j}p_{ij} = 1, \forall i \in I,$

and $p_{ij} \in [0, 1]$ for all $(i, j) \in \mathcal{I} \times \mathcal{I}$ .

The random sequence $\{z_n \}_{n\geq 0}$ is a discrete-time Markov chain with initial distribution $ρ 0$ , a vector with number of components given by the cardinality of $I$ , and transition matrix $P$ if it is a Markov stochastic process with state space $I$ and

$z 0$ has distribution $ρ 0$ ;
for every $n \geq 0$ we have, when $\mathbb{P}(z_n = i) > 0, \quad \mathbb{P}(z_{n+1} = j|z_n = i) = p_{ij}$ .

The entries of the transition matrix $\{p_{ij} \}_{i,j\in I}$ are called the transition probabilities.

The discrete-time Markov chain has transition probabilities from $z n$ to $z n + 1$ , which do not depend on $n$ .

A continuous-time Markov chain is a Markov stochastic process $\{z(t)\}_{t\in \mathbb{R}^{+}}$ with state space $E = \mathcal{I}$ . Define $L = λ(P I)$ , The matrix $L$ is called the generator of the continuous-time Markov chain.

As for ODEs, ergodicity for Markov chains is concerned with the existence and uniqueness of an invariant measure.

For simplicity, we assume that $\mathcal{I}$ is a finite set. We start by discussing discrete-time Markov chains. The matrix (P − I) has a nonempty null space, including constant vectors, and hence its transpose also has a nonempty null space. As a consequence, there exists a vector $\rho^{\infty}$ such that $P^{T} \rho^{\infty} = \rho^{\infty}$ .

In fact we have the following theorem. Theorem: All eigenvalues of $P$ lie in the closed unit circle. The vector $\rho^{\infty}$ may be chosen so that all of its entries are nonnegative and $<\rho^{\infty}, 1> = 1$ .

The vector $\rho^{\infty}$ is known as the invariant distribution. Note that it defines a probability measure on $\mathcal{I}$ .

Definition: The discrete-time Markov chain is said to be ergodic if the spectrum of $P$ lies strictly inside the unit circle, with the exception of a simple eigenvalue at 1, corresponding to a strictly positive invariant distribution.

Now consider continuous-time Markov chains on $\mathcal{I}$ .

Theorem: All eigenvalues of $L$ lie in the left half-plane. The vector $\rho^{\infty}$ may be chosen so that all of its entries are nonnegative and $<\rho^{\infty}, 1> = 1$ .

The vector $\rho^{\infty}$ is again known as the invariant distribution.

Definition: The continuous-time Markov chain is said to be ergodic if the spectrum of $L$ lies strictly in the left half-plane, with the exception of a simple eigenvalue at zero, corresponding to a strictly positive invariant distribution.