Discrete Markov-Chains

Introduction

Markov chains describe motions of a particle on a set $S$. They are foundational in the study of probability and stochastic systems, and they’ll let us test out our formalism.

A Markov chain, named after its creator, Andrei Markov, is composed of three ingredients:

1. A set of states, $S$, which is finite or countable;
2. An initial distribution $\{\nu_i\}_{i \in S}$ of probabilities of starting in state $i$ and summing to one;
3. And transition probabilities $\{p_{ij}\}_{i,j\in S}$ which describe the probability of moving from state $i$ to state $j$.

It is clear that we must have $\sum_i p_{ij} = 1$. We also have the more formal definition which follows.

Note that for the above definition to fit with our previous definitions of random variables, we need $S \subseteq \mathbf{R}$. However, if we allow for general extensions to spaces with associatee $\sigma$-algebras as co-domains of random variables, this isn’t an issue.

It follows almost immediately that

$$\htmlId{eq-2}{\mathbf{P}(X_1 = j) = \sum_{i \in S} \nu_i p_{ij}.} \tag{2}$$

We can write this in matrix notation for a more compact form, and let’s us use all of our linear algebra tools.

$$\htmlId{eq-3}{\mathbf{P}(X_1 = j) = [P^{\mathsf{T}} \nu]_j,} \tag{3}$$

where $p_{ij} = [P]_{ij}, P \in \mathbf{R}^{|S| \times |S|}$ and $\nu \in \mathbf{R}^{|S|}$. While this particular notation applies especially when $S$ is finite, it can be extended to linear operators which are infinite. We simply stop talking about matrices.

Conditional Probabilities

We can view Markov chains from the perspective of conditional probabilities. Recall that $\mathbf{P}(A | B) = \mathbf{P}(A \cap B) / \mathbf{P}(B)$, provided that $\mathbf{P}(B) > 0$. Intuitively, this is the proportion of the event $B$ which is also contained in the event $A$. Thus, for a Markov chain with $\mathbf{P}(X_k = i) > 0$, we have

$$\htmlId{eq-4}{\begin{aligned} \mathbf{P}(X_{k+1} = j | X_k = i) &= \frac{\mathbf{P}(X_{k+1} = j \cap X_k = i)}{\mathbf{P}(X_k = i)} \\ &= \frac{\sum_{i_0,i_1,\dotsc ,i_{k-1}} \nu_{i_0} p_{i_0 i_1} \cdots p_{i_{k-1} i} p_{ij}} {\sum_{i_0,i_1,\dotsc ,i_k} \nu_{i_0} p_{i_0 i_1} \cdots p_{i_{k-1} i}} \\ &= p_{ij}. \end{aligned}} \tag{4}$$

This rigorously shows that this is in fact a valid way to interpret or define Markov chains. Notice that there’s no dependence on $k$! We call this property time-homogeneity. For the definition we gave above, all Markov chains are time-homogenous. However, more general definitions of Markov chains allow for this property not to hold. Notice also that we didn’t define Markov chains using conditional probabilities because this definition does not apply if $\mathbf{P}(X_k = i ) = 0$ , which is certainly a possibility.

We can similarly compute $n$-step transition probabilities:

Notice again that there’s no dependence on $k$ (the indices are only cosmetic). By convention, we set $p_{ij}^{(0)} = \delta_{ij}$.

An Existence Theorem

If we want to be pedantic, we technically haven’t shown that Markov chains ever exist. How do we know that such a sequence of random variables can be produced or defined? We’ll prove it now, and constructively, too!

Transience, recurrence, and irreducibility