Discrete-Time Markov Chains
Sources:
- Jeseph K. Blitzstein & Jessica Hwang. (2019). Markov chains. Introduction to Probability (2nd ed., pp. 497-533). CRC Press.
Discrete-Time Markov Chains
Sources:
- Joseph K. Blitzstein & Jessica Hwang. (2019). Markov chains. Introduction to Probability (2nd ed., pp. 497-533). CRC Press.
Notation
Symbol | Type | Description |
---|---|---|
Random process | A discrete-time Markov chain, where |
|
Set | Finite state space of the Markov chain, with |
|
Total number of states in the Markov chain’s state space |
||
One-step transition matrix, where |
||
Transition probability |
||
Indices representing states in the Markov chain's state space |
||
Probability distribution of the chain at time |
||
Stationary distribution of the Markov chain, satisfying |
||
Number of components in a vector |
Abbreviations
Abbreviation | Type | Description |
---|---|---|
DTMC | Discrete-Time Markov Chain | Refers to a Markov chain in discrete time steps |
LOTP | Law of Total Probability | A theorem stating that probabilities can be broken down based on partitions of the sample space |
r.v. | Random Variable | A variable whose possible values are numerical outcomes of a random phenomenon |
C-K Equations | Chapman-Kolmogorov Equations | Equations that provide relationships for |
Discrete-Time Markov Chains
Consider the random process
for all
A Markov chain is called time-homogeneous if the transition probability
Transition probability matrices
one-step transition probability matrix
Define
where
The probability of transitioning from state
The
where
The Chapman-Kolmogorov Equations
The Chapman-Kolmogorov equations provide a way to compute
For
Proof
We only need to prove
where
Probability distribution of a Markov chain
Let
so that at time
Here,
Proof:
We consider first the
Thus, by considering all values of
It follows that at each step, the distribution gets multiplied by
The vector
Classification of states
In this section we introduce terminology for describing the various characteristics of a Markov chain. The states of a Markov chain can be classified as recurrent or transient, depending on whether they are visited over and over again in the long run or are eventually abandoned. States can also be classified according to their period, which is a positive integer summarizing the amount of time that can elapse between successive visits to a state. These characteristics are important because they determine the long-run behavior of the Markov chain, which we will study in stationary distributions.
Recurrent and transient states
State
Irreducible and reducible chains
A Markov chain with transition matrix
Proposition: In an irreducible Markov chain with a finite state space, all states are recurrent.
Proof. It is clear that at least one state must be recurrent; if all states were transient, the chain would eventually leave all states forever and have nowhere to go! So assume without loss of generality that state 1 is recurrent, and consider any other state
Since the chain visits state 1 infinitely often, we know the chain will eventually reach state
Periodic and aperiodic chains
The period of a state
A state is called aperiodic if its period equals 1 , and periodic otherwise. The chain itself is called aperiodic if all its states are aperiodic, and periodic otherwise.
A Necessary Condition for the Existence of a limiting distribution
If a Markov chain has a limiting distribution, then it has a unique stationary distribution and the limiting distribution is equal to this stationary distribution.
Stationary distributions
A distribution
if
In particular, if the initial distribution
Existence and uniqueness
Every Markov chain has at least one stationary distribution.
The proof is omitted.
For an irreducible chain, there exists a unique stationary distribution where each state has positive probability.
The proof is omitted.
Convergence
Let
The proof is omitted.
Limiting distributions
A probability distribution
Reversibility
We have seen that the stationary distribution of a Markov chain is extremely useful for understanding its long-run behavior. Unfortunately, in general it may be computationally difficult to find the stationary distribution when the state space is large. This section addresses an important special case where working with eigenvalue equations for large matrices can be avoided.
Definition:
A chain with transition matrix
for all states
Proposition: Suppose that
Proof. We have
where the last equality is because each row sum of