Notation and Terminology¶

This section sets out some of the notation we will be using when we work with Markov Chains. It also describes some basic properties and terminology that will useful for organizing our analyses.

The Markov Chain¶

$X_0, X_1, X_2, \ldots $

The State Space¶

A finite or countably infinite set $S$, consisting of all the possible values or states of $X_n$ for all $n$.

Unconditional Distribution at Time $n$¶

$P_n$, defined by $$ P_n(i) = P(X_n = i), ~~~ i \in S $$

One-Step Transition Probabilities¶

These are conditional probabilities $P(i, j)$ defined by $$ P(i, j) = P(X_1 = j \mid X_0 = i) $$ for $i$ and $j$ in $S$.

In the chains that we will study, all one-step transition probabilities will be time homogenous – they won't depend on $n$. So

$$ P(i, j) = P(X_{n+1} = j \mid X_n = i) ~~~ \text{for all } n $$

These one-step transition probabilities are the elements of the transition matrix of the chain. That's the matrix $\mathbb{P}$ whose $(i, j)$th element is $P(i, j)$.

$n$-Step Transition Probabilities¶

For $n \ge 0$, these are conditional probabilities $P_n(i, j)$ defined by $$ P_n(i, j) = P(X_n = j \mid X_0 = i) $$ for $i$ and $j$ in $S$.

Notice that $P_1(i, j)$ is the same as $P(i, j)$. We lazily drop the subscript 1 because we use the one-step transitions in many calculations.

The Markov property implies the $n$-step transitional probability is the same for any $n$ consecutive steps: $$ P_n(i, j) = P(X_{m+n} = j \mid X_m = i) ~~~ \text{for all } m $$

Communication¶

If it is possible for the chain to get from state $i$ to state $j$, we say that $i$ leads to $j$ and we write $i \rightarrow j$. Usually you can decide whether $i$ leads to $j$ just by examining the transition behavior of the chain. As a formal definition, $i \rightarrow j$ if:

• There is a path of positive probability that starts at $i$ and ends at $j$.
• Equivalently, there is some $n > 0$ such that $P_n(i, j) > 0$.

We say that $i$ communicates with $j$ if $i \rightarrow j$ and $j \rightarrow i$.

If all the states of a chain communicate with each other, the chain is called irreducible.

Period¶

Working in discrete time has disadvantages. One of them is that states can be periodic. Let's start with the example of a random walk where the steps are based on tosses of a fair coin. Suppose the walk starts at state 0. Then it can return to 0 only at even times: the number of heads up to that point has to exactly equal the number of tails, and thus the number of tosses has to be even. We say that the state 0 has period 2.

A state $i$ has period $d$ if, starting at $i$, the chain can come back to $i$ only at times that are multiples of $d$. That is, $d$ is the greatest common divisor of the set all $n$ such that $P_n(i, i) > 0$.

In the random walk described above, all states have period 2.

Period causes trouble with statements about long-run behavior. For example, if state $i$ has period 3, then the sequence $P_n(i, i)$ might look like "0, 0, positive, 0, 0, positive, $\ldots$", so limit statements might become complicated.

In this course we will study the long run behavior of chains in which all states are aperiodic, that is, they have period 1. In other words there is no cyclical pattern to when the chain can return to any state.

How do you check if all states are aperiodic? If the chain is irreducible, it turns out that all the states must have the same period. The proof of this fact isn't terribly hard but we won't go through it. What it implies is that if a chain is irreducible, which is easy to check, all you have to do is figure out the period of one of its states. Then all the others must have the same period.

Some states are easy to identify as aperiodic. If the one-step transition probability $P(i, i)$ is positive, then the state $i$ has to be aperiodic – since the chain can stay at $i$ for arbitrary lengths of time, its "returns" are not cyclical.

Example: Deconstructing a Chain¶

Consider the chain with transition matrix given by

	a	b	c	d	e
a	0	1	0	0	0
b	1	0	0	0	0
c	0	1/3	1/3	1/3	0
d	0	0	0	1/3	2/3
e	0	0	0	4/5	1/5

• States $a$ and $b$ communicate with each other and with no other state. The little matrix

	a	b
a	0	1
b	1	0

is a transition matrix it own right, albeit of a rather boring chain that goes deterministically back and forth between $a$ and $b$. Both $a$ and $b$ have period 2.

• States $d$ and $e$ form their own communicating class and are aperiodic.

	d	e
d	1/3	2/3
e	4/5	1/5

• State $c$ communicates with itself, but once it gets to either $b$ or $d$, it can't return.