2 Discrete Parameter Markov Chains
2.1 Introduction
A discrete parameter Markov chain process is a modeling approach used to represent systems that evolve over time in discrete steps, where the future state depends only on the current state. This is very useful in analyzing distinct states and transitions. Discrete Parameter Markov Chains is also known as “Discrete-time Markov Chains”.
Definition
Let \(\{X_n; n = 0, 1, 2, ...\}\) be a stochastic process that takes on a finite or countable number of possible values. If \(X_n=i,\) then the process is said to be in state \(i\) at time \(n\).
The discrete-parameter, discrete state stochastic process \(\{X_n; n=0, 1, 2,...\}\) is called a discrete-parameter Markov chain if for all states \(i_0, i_1,...i_{n-1}, i, j\) and all \(n \geq 0\),
\[P(X_{n+1}=j|X_n=i, X_{n-1}=i_{n-1}, ..., X_1=i_1, X_0=i_0) = P(X_{n+1}=j|X_n=i).\]
This means, a stochastic process is a Markov chain if the probability of moving to the next state depends only on the current state and not on the sequence of events that preceded it.
2.2 One-step transition probabilities
We have a set of states, \(S = \{i_0, i_1, i_2,...i_{n-1}, i, j\}\). The process starts in one of these states and moves successively from one state to another. Each move is called a step.
\(P_{nij} = P(X_{n+1}=j|X_n=i, X_{n-1}=i_{n-1}, ..., X_1=i_1, X_0=i_0) = P(X_{n+1}=j|X_n=i)\)
If the chain is currently in state \(i\), then it moves to state \(j\) at the next step with a probability denoted by \(p_{nij}\) , and this probability does not depend upon which states the chain was in before the current state.
The probabilities \(p_{nij}\) are called one-step transition probabilities.
2.3 Time Homogeneous Discrete-Parameter Markov Chain
If the conditional probability \(P(X_{n+1}=j|X_n=i)\) does not depend on \(n\), then the process is known as time homogeneous Markov chain process or stationary Markov chain process. Then we can write the conditional probability \(p_{nij}\) as \(P_{i,j}\). Moreover, when there is no risk of confusion, we can write \(P_{i,j}\) simply as \(P_{ij}\).
2.3.1 Intuition behind time-homogenous Markov chain process
Example 1:
Suppose we observe the condition of crop’s soil moisture on every morning. We record the conditions as dry, normal and wet. Let’s denote the states as follows:
state 0: dry
state 1: normal
state 2: wet
Let’s assume that the soil moisture condition on a given day depends only on the moisture condition of the previous day. Furthermore, in this case conditional probability \(P(X_{n+1}=j|X_n=i)\) actually depend on \(n\). The probability of moving wet to wet \(P(X_{n+1}=2|X_n=2)\) is not same for the whole year. This probability is small during the dry season and very high during the rainy season. If you are living in a country with four seasons, then this probability will vary according to the seasons: winter, summer, spring, and autumn. Hence, this is a non-stationary discrete-parameter discrete-state space Markov chain process. We can use a stationary Markov chain only for a short period of time.
In this book we only consider time-homogeneous Markov chain processes.
Example 2
Let’s consider modeling the mood of a person as a time-homogeneous Markov chain with three states:
state 0: happy
state 1: neutral
state 2: sad
Here is the time homogeneous transition probability matrix
\[P = \left[\begin{array}{cccccccc} p_{00} & p_{01} & p_{02} & ...\\ p_{10} & p_{11} & p_{12} & ...\\ . & . & . & ...\\ p_{i0} & p_{i1} & p_{i2} & ...\\ . & . & . & ... \end{array}\right]\]
2.4 Exercise
- Suppose there are two types of crops (Crop A and Crop B) planted in different fields, and farmers perform certain operations that may affect the composition of crops in each field. After each agricultural season, a random selection of crops from one field is transferred to the other. Let \(X_t\) denote the number of Crop A plants in the first field after the \(t\)th season. What are the parameter space and state space for this agricultural scenario, and can \(\{X_t\}\) be considered a Markov chain given certain conditions on the planting and transfer processes?
2.5 One-step transition probability matrix
Let \(P\) denote the matrix of one-step transition probabilities \(P_{ij}\), so that
\[P = \left[\begin{array}{cccccccc} p_{00} & p_{01} & p_{02} & ...\\ p_{10} & p_{11} & p_{12} & ...\\ . & . & . & ...\\ p_{i0} & p_{i1} & p_{i2} & ...\\ . & . & . & ... \end{array}\right]\]
Since probabilities are nonnegative and since the process must make a transition into some state, we have
\(p_{ij} \geq 0,\) for \(i, j \geq 0\), \(\sum_{j=0}^\infty p_{ij} = 1,\) for \(i = 0, 1, ...\)
2.6 Higher (n-step) transition probabilities
\(P_{ij}\) - One step transition probabilities
\(P^n_{ij}\) - n - step transition probabilities
Probability that a process in state \(i\) will be in state \(j\) after \(n\) additional transitions. That is,
\[P^n_{ij}=P(X_{n+k}=j|X_k=i), \text{ } n\geq 0, \text{ }i, j \geq 0.\]
2.7 Chapman-Kolmogorov equations
\[P_{ij}^{n+m}=\sum_{k=0}^{\infty}P_{ik}^nP_{kj}^m\text{ for all n, m} \geq 0, \text{ all i, j,}\] where, \(P^n_{ik}P^m_{kj}\) represents the probability that starting in \(i\) the process will go to state \(j\) in \(n+m\) with an intermediate stop in state \(k\) after \(n\) steps.
This can be used to compute \(n\)-step transition probabilities
2.8 Exercise
- Show that \(P_{ij}^{n+m}=\sum_{k=0}^{\infty}P_{ik}^nP_{kj}^m\text{ for all n, m} \geq 0, \text{ all i, j.}\)
2.9 \(n\) - step transition matrix
The n-step transition matrix is
\[\mathbf{P}^{(n)} = \left[\begin{array} {rrrr} P_{00}^{(n)} & P_{01}^{(n)} & P_{02}^{(n)} & ...\\ P_{10}^{(n)} & P_{11}^{(n)} & P_{12}^{(n)} & ...\\ . & . & . & ...\\ . & . & . & ...\\ . & . & . & ...\\ \end{array}\right] \] The Chapman-Kolmogrov equations imply
\[\mathbf{P}^{(n+m)}=P^{(n)}P^{(m)}.\]
In particular,
\[\mathbf{P}^{(2)}=\mathbf{P}^{(1)}\mathbf{P}^{(1)}=\mathbf{P}\mathbf{P}=\mathbf{P}^2.\] By induction,
\[\mathbf{P}^{(n)}=\mathbf{P}^{(n-1+1)}=\mathbf{P}^{n-1}\mathbf{P}=\mathbf{P}^n.\]
2.10 \(n\) - step transition matrix
Proposition
\[P^{(n)} = P^n = P \times P \times P \times ... \times P, \text{ } n \geq 1.\] That is, \(P^{(n)}\) is equal to \(P\) multiplied by itself \(n\) times.
2.11 Types of States
Definition: If \(P_{ij}^{(n)}>0\) for some \(n \geq 0,\) state \(j\) is accessible from \(i\).
Notation: \(i \rightarrow j.\)
Definition: If \(i \rightarrow j\) and \(j \rightarrow i\), then \(i\) and \(j\) communicate.
Notation: \(i \leftrightarrow j.\)
2.12 Theorem:
Communication is an equivalence relation:
\(i \leftrightarrow i\) for all \(i\) (reflexive).
\(i \leftrightarrow j\) implies \(j \leftrightarrow i\) (symmetric).
\(i \leftrightarrow j\) and \(j \leftrightarrow k\) imply \(i \leftrightarrow k\) (transitive).
2.13 In-class: Proof
- \(i \leftrightarrow i\) for all \(i\) (reflexive).
2.14 In-class: Proof
- \(i \leftrightarrow j\) implies \(j \leftrightarrow i\) (symmetric).
2.15 In-class: Proof
- \(i \leftrightarrow j\) and \(j \leftrightarrow k\) imply \(i \leftrightarrow k\) (transitive).
2.16 In-class: Proof
2.17 Note:
Two states that communicate are said to be in the same class.
The concept of communication divides the state space up into a number of separate classes.
In-class: demonstration
2.18 Theorem
Definition: An equivalence class consists of all states that communicate with each other.
Remark: Easy to see that two equivalence classes are disjoint.
Example: The following P has equivalence classes \(\{0, 1\}\) and \(\{2, 3\}\)
\(\mathbf{P}\)= \(\left[\begin{array} {rrrr} 0.5 & 0.5 & 0 & 0 \\ 0.5 & 0.5 & 0 & 0\\ 0 & 0 & 0.75 & 0.25\\ 0 & 0 & 0.25 & 0.75\\ \end{array}\right]\)
What about this?
\(\mathbf{P}\)= \(\left[\begin{array} {rrrr} 0.5 & 0.5 & 0 & 0 \\ 0.5 & 0.3 & 0.2 & 0\\ 0 & 0 & 0.75 & 0.25\\ 0 & 0 & 0.25 & 0.75\\ \end{array}\right]\)
2.19 Irreducible
Definition: A MC is irreducible if there is only one equivalence class (i.e., if all states communicate with each other).
What about these?
Example 1
\(\mathbf{P}\)= \(\left[\begin{array} {rrrr} 0.5 & 0.5 & 0 & 0 \\ 0.5 & 0.5 & 0 & 0\\ 0 & 0 & 0.75 & 0.25\\ 0 & 0 & 0.25 & 0.75\\ \end{array}\right]\)
Example 2
\(\mathbf{P}\)= \(\left[\begin{array} {rrrr} 0.5 & 0.5 & 0 & 0 \\ 0.5 & 0.3 & 0.2 & 0\\ 0 & 0 & 0.75 & 0.25\\ 0 & 0 & 0.25 & 0.75\\ \end{array}\right]\)
Example 3
\(\mathbf{P}\)= \(\left[\begin{array} {rr} 0.5 & 0.5 \\ 0.25 & 0.75 \\ \end{array}\right]\)
Example 4
\(\mathbf{P}\)= \(\left[\begin{array} {rrr} 0.25 & 0 & 0.75 \\ 1 & 0 & 0 \\ 0 & 0.5 & 0.5\\ \end{array}\right]\)
2.20 Identify the equivalence classes
Consider a Markov chain with a state space \(S = \{0, 1, 2, 3, 4\}\) and having the following one-step transition probability matrix.
\(\mathbf{P}\)= \(\left[\begin{array} {rrrrr} 0.4 & 0.2 & 0 & 0.4 & 0 \\ 0.2 & 0.4 & 0.1 & 0.3 & 0 \\ 0.1 & 0.2 & 0 .5& 0.1 & 0.1 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ \end{array}\right]\)
2.21 Problems 1
Example 4.10
Example 4.11
Example 4.12
2.22 Theorem
The relation of communication partitions the state space into mutually exclusive and exhaustive classes. (The states in a given class communicate with each other. But states in different classes do not communicate with each other.)
2.23 Definition
Let \(f_i\) denote the probability that, starting in state \(i\), the process will ever re-enters state \(i\), i.e,
\(f_i = P(X_n=i \text{ for some } n \geq 1|X_0=i)\)
Example 1
Consider the Markov chain consisting of the states 0, 1, 2, 3 with the transition probability matrix,
\(\mathbf{P}\)= \(\left[\begin{array} {rrrr} \frac{1}{2} & \frac{1}{2} & 0 & 0 \\ \frac{1}{2} & \frac{1}{2} & 0 & 0\\ \frac{1}{4} & \frac{1}{4} & \frac{1}{4} & \frac{1}{4}\\ 0 & 0 & 0 & 1\\ \end{array}\right]\)
Find \(f_0\), \(f_1\), \(f_2\), \(f_3\).
2.24 Recurrent and transient states
Let \(f_i\) be the probability that, starting in state \(i\), the process will ever re-enter state \(i\). State \(i\) is said to be recurrent if \(f_i = 1\) and transient if \(f_i < 1\).
Example 1
Consider the Markov chain consisting of the states 0,1,2 with the transition probability matrix
\(\mathbf{P}\)= \(\left[\begin{array} {rrr} 0 & \frac{1}{2} & \frac{1}{2} \\ \frac{1}{2} & 0 & \frac{1}{2}\\ \frac{1}{2} & \frac{1}{2} & 0 \\ \end{array}\right]\)
Determine which states are transient and which are recurrent.
Example 2
Consider the Markov chain consisting of the states 0, 1, 2, 3 with the transition probability matrix
\(\mathbf{P}\)= \(\left[\begin{array} {rrrr} 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1\\ \frac{1}{2} & \frac{1}{2} & 0 & 0 \\ 0 & 0 & 1 & 0 \\ \end{array}\right]\)
Determine which states are transient and which are recurrent.
Example 3
Consider the Markov chain consisting of the states 0, 1, 2, 3, 4 with the transition probability matrix
\(\mathbf{P}\)= \(\left[\begin{array} {rrrrr} \frac{1}{2} & 0 & \frac{1}{2} & 0 & 0\\ \frac{1}{4} & \frac{1}{2} & \frac{1}{4} & 0 & 0\\ \frac{1}{2} & 0 & \frac{1}{2} & 0 & 0\\ 0 & 0 & 0 & \frac{1}{2} & \frac{1}{2}\\ 0 & 0 & 0 & \frac{1}{2} & \frac{1}{2}\\ \end{array}\right]\)
Determine which states are transient and which are recurrent.
2.25 Theorem
if state \(i\) is recurrent then, starting in state \(i\), the process will re-enter state \(i\) again and again and again—in fact, infinitely often.
2.26 Theorem
For any state \(i\), let \(f_i\) denote the probability that, starting in state \(i\), the process will ever re-enter state \(i\). If state \(i\) is transient then, starting in state \(i\), the number of time periods that the process will be in state \(i\) has a geometric distribution with finite mean \(\frac{1}{1 - f_i}\).
Proof: In-class
2.27 Theorem
State \(i\) is
\[\text{ recurrent if } \sum_{n=1}^\infty P_{ii}^n=\infty,\]
\[\text{ transient if } \sum_{n=1}^\infty P_{ii}^n < \infty,\]
Proof: In-class
2.28 Corollary 1
If state \(i\) is recurrent, and state \(i\) communicates with state \(j\) (\(i \leftrightarrow j\)), then state \(j\) is recurrent.
Proof: In-class
2.29 Corollary 2
In a Markov Chain with a finite number of states not all of the states can be transient (There should be at least one recurrent state).
Proof: In-class
2.30 Corollary 3
If one state in an equivalent class is transient, then all other states in that class are also transient.
Proof: In-class
2.31 Corollary 4
Not all states in a finite Markov chain can be transient. This leads to the conclusion that all states of a finite irreducible Markov chain are recurrent.
Introduction to Probability Models, Sheldon M. Ross↩︎