- 2.5.1 Markov Processes
- 2.5.2 State Vectors
- 2.5.3 Stochastic Matrices
- Definition - Transition Probability
- Example 3 - Student Transition Probabilities
- Definition - Stochastic Matrix
- Example 4 - Assessing Brand Loyalty
- Video Lecture 1 - Markov Matrices
- Theorem 1 - Application of Markov Matrices
- Proof - Proof of Theorem 1
- Example 5 - Freshman Stochastic Matrix
- Exercise 4 - Freshman Relationship Status after 1 Month
- 2.5.4 Markov Chains
- 2.5.5 Steady State
- 2.5.6 Regular Stochastic Matrices
- 2.5.7 State Diagrams
- copyleft
Markov Processes and Stochastic processes are where linear algebra and statistics overlap. Markov processes can be found in many modern applications of matrices in the fields of thermodynamics, mechanics, physics, chemistry, economics, finance, signal processing, information theory, speech processing, and data science. We will look at the basics of stochastic matrices in this course, however you will find many applications of these matrices including page-ranking algorithms.
Applications involving populations or collections can be categorized into separate classes. Each class may be represented by a finite number of conditions, associations, or labels. In mathematics if we have a class of objects, then we can associate each member of the class with an attribute or state.
Technically the state $s$ of each element of a population or group $G$ is the result of a function $f:G\rightarrow S$, where each member of the group $x\in G$ is mapped to a state $s\in S$ in the state space. Generally we are not interested in the function that associates each member of the population with an associated state. We are interested in the size of the group associated with a specific state. The set of all members of the group associated with state $s$ in state space $S$ is given by
$$ f^{-1}(s) = \left\{\, x\in G\,:\,f(x)=s \,\right\} $$
Definition¶
Pre-Image
For any function $f$ with domain $D$ and codomain $R$, or $f:D\rightarrow R$, the pre-image of an element on the codomain $y\in R$ is the set of all elements in the domain that $f$ maps to $y$.
$$ f^{-1}(y) = \left\{\, x\in D\,:\,y=f(x) \,\right\} $$
So $f^{-1}(y)$ is a set of elements of the domain. If there are no elements of the domain mapped to $y\in R$ by $f$, $f^{-1}(y)=\emptyset$. In this way the pre-image is always well-defined. If the pre-image of every element of the codomain is a nonempty singleton set, then we define an inverse function $f^{-1}:R\rightarrow D$. We even use the same notation to make everything more confusing.
The size, $\left|\, f^{-1}(s) \,\right|$ of this set is the number of elements in $f^{-1}(s)$.
Usually we are interested in the ratio of the total population that share the same state.
$$ \frac{\left|\, f^{-1}(s) \,\right|}{\left|\, G \,\right|} $$
This ratio must be in the interval $[0, 1]$, where the ratio is zero when no member of the group is associated with state $s$, and one, when every member of the group is associated with state $s$. This ratio can represent the probability that a random member of the group is associated with state $s$.
Example 1 - Populations¶
- a population of voters may be described as Democratic, Republican, Independent, or affiliated with another political party.
- a population of consumers may purchase an Android$\trademark$, Apple$\trademark$, Samsung$\trademark$ or other brand smart phone.
- a population of tuna may be described as Albacore, Allothunnus, Euthynnus, Frigate, or Skipjack.
In each case we want the relative size of each classification of the group. The relative size of the group is the fraction of the group represented by the classification or state.
Example 2 - Student Population¶
American Mathematical Society Blog about Markov Chains.
Incoming freshman dating prospects can be modeled by a Markov Process. Suppose that $80\%$ of incoming freshman students describe their current dating status as single, $10\%$ identify as in a relationship, and $10\%$ describe their relationship state as an ambiguous state variously termed "it's complicated".
In this example the state space is $R = \left\{\, \text{single},\ \text{relationship},\ \text{complicated} \,\right\}$
The entire population of freshman students $F$ can be divided into three distinct sets by the relationship function $f:F\rightarrow R$,
$$ r = f(x) $$
The population of freshman students $F$ can be divided into three distinct sets.
- The set of single students in $F$, $f^{-1}(\text{single})$
- The set of students in $F$ currently in a relationship, $f^{-1}(\text{relationship})$
- The set of students in $F$ in an ambiguous state, $f^{-1}(\text{complicated})$
The important statistic here is the relative size of each of the sets.
$p_1 = \dfrac{|f^{-1}(\text{single})|}{|F|} = $ fraction of freshman students that are single.
$p_2 = \dfrac{|f^{-1}(\text{relationship})|}{|F|} = $ fraction of freshman students that are in a relationship.
$p_3 = \dfrac{|f^{-1}(\text{complicated})|}{|F|} = $ fraction of freshman students in an ambiguous state.
The ratios are interpreted as the probabilities that a random member of the population will currently be assigned to each state. In our example the probability $P\left( f(x)=s \right)$ that a random member of the population $x\in F$ is associated with state $s$ in the state space is given by
$P\left( f(x)=\text{single} \right) := p_1$
$P\left( f(x)=\text{relationship} \right) := p_2$
$P\left( f(x)=\text{complicated} \right) := p_3$
One may refer to a random state of the system or state vector
$$ \mathbf{X} = \begin{bmatrix} p_1 \\ p_2 \\ p_3 \end{bmatrix}. $$
The sum of the elements of a state vector must add up to one, because we constructed our state space so that every member of the population is associated with exactly one of the states. When constructing a state space, one should always define an other state, like $\text{complicated}$, so that every member of the population is assigned exactly one state in the state space.
Exercise 1 - Freshman State on Day 1¶
In Example 2, what is the state of the incoming freshman students on the first day of class?
View Solution
To denote the system state or a state vector one needs the ratios of the population of each state to the total population of the group.
1. $80\%$ are single
2. $10\%$ are in a relationship
3. $10\%$ describe their relationship status as complicated
Hence the state of the system on the first day is $\mathbf{X} = \begin{bmatrix}\ .80\ \\ \ .10\ \\ \ .10\ \end{bmatrix}$.
What is the probability that a random member of the population $x\in G$ will be associated with state $s\in S$?
Given a relation $f\,:\,G\rightarrow S$, the probability is denoted using a state vector, $\mathbf{X}$, where
$$ P\left( \mathbf{X}(x)=s \right) = P(\mathbf{X}=s) = \frac{\left| f^{-1}(s) \right|}{|G|} $$
To create a state vector, $\mathbf{X}$, we must first order the elements of the state space,
$$ S = \left\{\, s_1,\ s_2,\ \dots,\ s_n \,\right\} $$
This is analogous to ordering the elements of vectors in $\mathbb{R}^n$.
When we write the equation of a plane in 3-dimensional space, $x - 2y + z = 4$, the elements of 3-dimensional space are ordered. A point on the plane $(1, -2, 1)$ only makes sense if we all agree that the first coordinate is the distance along the first ($x$-)axis, the second coordinate is the distance parallel to the second ($y$-)axis, and the third coordinate is the distance parallel to the third ($z$-)axis.
Then we must compute the ratio (probability) of the size of each element of our population $G$ associated with each state. This relationship $f\,:\,G\rightarrow S$, must be a total function.
Every member of the population must be mapped to (associated with) exactly one state.
The relative size (probability) of each state is defined for each $1\le k\le n$:
$$ p_k = \frac{\left|\, f^{-1}(s_k) \,\right|}{\left|\, G \,\right|} $$
Finally we can define the system state or state vector $\mathbf{X} = \begin{bmatrix} p_1 \\ \vdots \\ p_n \end{bmatrix}$.
This seems more abstract than coordinates in $\mathbb{R}^n$, but we can think of each state as an axis, and this makes sense. However, there are more restrictions.
- $p_k \ge 0$ for all $1\le k\le n$.
- $\sum_{k=1}^n p_k = p_1 + \cdots + p_n = 1$.
If the state space has only two states, then the graph of the line $p_1+p_2=1$ must be restricted to the first quadrant of the Cartesian plane.
If the state space consists of three states, the state vectors would all lie on the plane $p_1+p_2+p_3=1$ restricted to the first octant.
The distinction between vectors in $\mathbb{R}^n$ and state vectors lies in how one denotes the $k^{\text{th}}$ coordinate of state vector $\mathbf{X}$.
In our linear algebra class, one denotes the $k^{\text{th}}$ element of a vector with its subscript or position. In statistics, one denotes the $k^{\text{th}}$ coordinate of a vector by the state it represents:
$$ P(\mathbf{X}(x) = s_k) = P(\mathbf{X} = s_k) = p_k = \frac{\left|\, f^{-1}(s_k) \,\right|}{\left|\, G \,\right|} $$
Finally, the ordering of states is not always explicitly stated in the notation. If $s\in S$ is a state in our state space, then it must have an index $s = s_k$. This yields three common notations for the $k^{\text{th}}$ element of a state vector: with both the state and its index, without the index, and with just the index.
$$ P(\mathbf{X}(x) = s_k) = P(\mathbf{X}(x) = s) = P(\mathbf{X}(x) = k) $$
Statisticians also denote these probabilities without the input written explicitly,
$$
P(\mathbf{X}(s) = s_k) = P(\mathbf{X} = s_k) = P(\mathbf{X} = s) = P(\mathbf{X} = k)
$$
Definition¶
State Vector
A state vector for finite (population) space $G$, state space $S$, and state function $f\,:\,G\rightarrow S$, is an $n\times 1$ vector $\mathbf{X} = \begin{bmatrix} p_1 \\ \vdots \\ p_n \end{bmatrix}$ with the properties
- $p_k \ge 0$, for all $1\le k\le n$, and
- $\sum_{k=1}^n p_k = 1$.
State vectors are also called probability vectors. The entries of a probability vector can be identified by an ordered state $s_k\in S$ in the state space $1\le k\le n$, or a state in the state space without its index, $s\in S$, or merely using the index of the state:
$$ P(\mathbf{X}(x) = s_k) = P(\mathbf{X} = s_k) = P(\mathbf{X} = s) = P(\mathbf{X} = k) = \frac{\left|\, f^{-1}(s) \,\right|}{\left|\, G \,\right|} $$
Exercise 2 - Freshman Relationship State After One Month¶
After one month $29.5\%$ of freshman students describe themselves as single, $25.5\%$ as in a relationship, and $45\%$ as, it's complicated. What is the system state after one month?
View Solution
To construct a state vector, one needs the relative frequencies of freshman that describe themselves in each state.
1. $29.5\%$ describe themselves as single
2. $25.5\%$ describe themselves as in a relationship
3. $45\%$ describe their relationship status as complicated
Hence the state of the system after one month is $\mathbf{X} = \begin{bmatrix}\ .295\ \\ \ .255\ \\ \ .450\ \end{bmatrix}$.
The probabilities are the coordinates of the state vector.
Exercise 3 - Freshman Relationship State After Three Months¶
After three months the current state is given by $\mathbf{X} = \begin{bmatrix}\ .282\ \\ \ .401\ \\ \ .317\ \end{bmatrix}$. What is the probability that a randomly selected freshman student will be single three months after start of term?
View Solution
The state $\text{single}$ is the first state in the state vector, so the probability that a randomly selected student will be single three months after start of term is $28.2\%$. This is denoted$$ P(\mathbf{X}(x)=\text{single}) = 28.2\% \text{ for any } x\in F $$
In a Discrete Time Stochastic Process, we divide time into artificially created time steps, or cycles, $\Delta t$. The initial state is the state vector when $t=0$ and this state vector is denoted $\mathbf{X}_0$.
At the $j^{\text{th}}$ time step the state of the stochastic model is denoted $\mathbf{X}_j$. The subscripts denote the number of time steps from zero. $\mathbf{X}_j$ is the state vector of the stochastic model at time step $j$. That is to say, $j\Delta t$ units of time from the initial state. In this way the state of the system evolves throughout time.
This makes a transition probability an example of a conditional probability.
Definition¶
Transition Probability
A transition probability $p_{ij}$ is the conditional probability that a member of a population is currently assigned state $s_i$, given it was assigned to state $s_j$ in the previous time step,
$$ p_{ij} = P(\mathbf{X}_n=s_i\,|\,\mathbf{X}_{n-1}=s_j) $$
This says that $p_{ij}$ is the probability that a member of the population will change to state $s_i$ at time step $n$, given that they are in state $s_j$ at the previous time step.
Within the notation, $s_j$ is called the initial state, and $s_i$ is called the terminal state.
Example 3 - Student Transition Probabilities¶
After one month there is a 30% chance a single student will remain single, a 20% chance they will enter a relationship, and a 50% chance they will enter the complicated state. Notice that the sum of transition probabilities is also one.
The transition probabilities for a single freshman student can be computed:
$$ \begin{align*}f p_{11} &= P(\mathbf{X}_n=s_1\,|\,\mathbf{X}_{n-1}=s_1) = 0.3 \\ p_{21} &= P(\mathbf{X}_n=s_2\,|\,\mathbf{X}_{n-1}=s_1) = 0.2 \\ p_{31} &= P(\mathbf{X}_n=s_3\,|\,\mathbf{X}_{n-1}=s_1) = 0.5 \\ \end{align*} $$
The sum of transition probabilities from an initial state must sum to one because every member of the domain group must transition to exactly one terminal state.
Definition¶
Stochastic Matrix
A stochastic matrix for a state space $S$ with $n$ elements is an $n\times n$ matrix. Each element is a transition probability for one time step:
$$ p_{ij} = P(\mathbf{X}_n=s_i\,|\,\mathbf{X}_{n-1}=s_j) $$
The transition probabilities and the stochastic matrix must have the following properties
$$ \begin{align*} p_{ij} &\ge 0 \\ \sum_{i=1}^n p_{ij} &= 1 \end{align*} $$
A stochastic matrix is also called a transition matrix, transition of probabilities matrix or Markov matrix.
Example 4 - An Empirical Study on Assessing Brand Loyalty¶
Serkan Varol and Alberto Marquez performed a study based on "choice criteria" factors introduced earlier by another researcher. John Oshaughnessy hypothesized that the patterns of choosing a product is often associated with how buyers perceive their purchase.
$$ P = \begin{bmatrix} 0.286 & 0.429 & 0.170 & 0.366 & 0.186 & 0.163 \\ 0.016 & 0 & 0.021 & 0 & 0.023 & 0.047 \\ 0.222 & 0.143 & 0.234 & 0.017 & 0.140 & 0.186 \\ 0.190 & 0.143 & 0.213 & 0.195 & 0.116 & 0.209 \\ 0.143 & 0 & 0.106 & 0.195 & 0.349 & 0.163 \\ 0.143 & 0.286 & 0.255 & 0.073 & 0.186 & 0.233 \end{bmatrix} $$ Serkan Varol and Alberto Marquez published An Empirical Study on Assessing Brand Loyalty in Automobile Industry Using Hidden Markov Model, in the Academy of Marketing Studies Journal, Volume 24, Issue 1, 2020.
Video Lecture 1: Markov Matrices.¶
Transition MatricesTheorem 1¶
Application of Markov Matrices
The product of a Markov Matrix and a State Vector is a State Vector.
Proof of Theorem 1¶
Suppose that $P$ is an $n\times n$ Markov matrix and $\mathbf{X}$ is an $n\times 1$ state vector. This means the sum of the elements of the state vector, $\sum_{j=1}^n \mathbf{X}_j = \sum_{j=1} P(\mathbf{X}=j) = 1$. We must prove that the sum of the prove vector $P\mathbf{X}$ is also $1$. Using the definition of matrix-vector multiplication, the product vector is given by
$$ P\mathbf{X} = \begin{bmatrix} \mathbf{p}^1\mathbf{X} \\ \vdots \\ \mathbf{p}^n\mathbf{X} \end{bmatrix} $$
Hence the sum of the elements of this vector can be written
$$ \sum_{j=1}^n \mathbf{p}^j\mathbf{X} = \sum_{j=1}^n \left( \sum_{k=1}^n p_{jk}x_k \right) = \sum_{k=1}^n \left( \sum_{j=1}^n p_{jk}x_k \right) \\ $$
The finite sums can be performed in any order. Reversing the order allows us to distribute $x_k$ in each inner sum.
$$ \sum_{k=1}^n \left( \sum_{j=1}^n p_{jk}x_k \right) = \sum_{k=1}^n \left( x_k\sum_{j=1}^n p_{jk} \right) $$
Since $P$ is a Markov matrix, the sum of any column is $1$, and the sum of the elements of a state vector are also $1$,
$$ \sum_{k=1}^n \left( x_k\sum_{j=1}^n p_{jk} \right) = \sum_{k=1}^n \left( x_k\cdot1 \right) = \sum_{k=1}^n x_k = 1. \blacksquare $$
System State is Memoryless¶
The system state of discrete time stochastic process at each time step is computed by applying the stochastic matrix to the current state. The state of an individual in the population group $G$ is generally not predictable. Instead the probabilities that an individual will be associated with each state are known. The state vector at each time step is denoted with a subscript; the initial state vector is denoted $\mathbf{X}_0$ and the state vector at the $k^{\text{th}}$ time step is denoted $\mathbf{X}_k$.
$$ \begin{align*} \mathbf{X}_1 &= P\mathbf{X}_0 \\ \mathbf{X}_2 &= P\mathbf{X}_1 = P\left(P\mathbf{X}_0\right) = P^2\mathbf{X}_0 \\ \mathbf{X}_3 &= P\mathbf{X}_2 = P\left(P^2\mathbf{X}_0\right) = P^3\mathbf{X}_0 \\ &\ddots \\ \mathbf{X}_n &= P^n\mathbf{X}_0 \end{align*} $$
Evidently, the state vector of the stochastic system at time step $n$ is computed by applying $P^n$ to the initial state. This property of a stochastic system is called memoryless. The evolution of many applications requires only knowledge of the current state of the system and the stochastic matrix to predict the next state. No knowledge of any of the previous states of the system is required.
Example 5 - Freshman Stochastic Matrix¶
The transition probabilities for freshman relationship status are given in the table below
$$ \begin{array}{cc} & \qquad\qquad\qquad From\ State\ j \\ & \qquad\qquad\qquad\overbrace{\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad } \\ To\ State\ i\ & \left\{ \begin{array}{lccc} & \text{Single} & \text{Relationship} & \text{Complicated} \\ \text{Single} & .30 & .30 & .25 \\ \text{Relationship} & .20 & .60 & .35 \\ \text{Complicated} & .50 & .10 & .40 \end{array} \right. \end{array} $$
Together these transition probabilities $p_{ij}$ form a transition matrix, Markov matrix, or transition of probabilities matrix $P$.
$$ P = \begin{bmatrix}\ .30\ &\ .30\ &\ .25\ \\ \ .20\ &\ .60\ &\ .35\ \\ \ .50\ &\ .10\ &\ .40\ \end{bmatrix} $$
Suppose at the start of orientation 80% of freshman students are single, 10% are in a relationship, and 10% are "it’s complicated".
$$ \mathbf{X}_0 = \begin{bmatrix} .80 \\ .10 \\ .10 \end{bmatrix} $$
Exercise 4 - Freshman Relationship State after 1 Month¶
What percentage of freshman students will be in a relationship in a month?
View Solution
$$ \mathbf{X}_1 = P\mathbf{X}_0 = \begin{bmatrix}\ .30\ &\ .30\ &\ .25\ \\ \ .20\ &\ .60\ &\ .35\ \\ \ .50\ &\ .10\ &\ .40\ \end{bmatrix}\begin{bmatrix}\ .80\ \\ \ .10\ \\ \ .10\ \end{bmatrix} = \begin{bmatrix}\ .295\ \\ \ .255\ \\ \ .45\ \end{bmatrix} \\ $$
Approximately $25.5\%$ of the freshman population will be in a relationship one month after orientation.
Definition¶
Markov Chain
A Markov Chain is a sequence of states $\left\{ X_0, X_1, X_2, \dots \right\} = \left\{ X_n \right\}$ that are related by the equation $X_{k+1} = PX_k$ for some stochastic matrix $P$. The $n^{\text{th}}$ state of the Markov Chain is given by
$$ X_n = P^nX_0 $$
The sequence of state vectors denotes the evolution of the state of the stochastic process over time.
(Notice that I have stopped using a bold font or vector decoration to denote the state vector $X$. I do this for historical reasons, and because, in the case of state vectors, Statisticians do not normally use vector notation for the state vector. Some texts and Statisticians DO use vector notation! You will need to read carefully to recognize when a random variable refers to a vector or a scalar quantity.)
Exercise 5 - Freshman Relationship State after 3 Months¶
How many freshman students will be in a relationship after 3 months? (Use MATLAB, GeoGebra, Desmos, WolframAlpha, or your favorite software)
View Solution
$$ \begin{align*} X_3 &= P\left(P\left(P(X_0)\right)\right) = P^3X_0 \\ \\ &= \begin{bmatrix} .30 & .30 & .25 \\ .20 & .60 & .35 \\ .50 & .10 & .40 \end{bmatrix}^3\begin{bmatrix} .80 \\ .10 \\ .10 \end{bmatrix} \\ \\ &= \begin{bmatrix} 0.2815 & 0.2875 & 0.284 \\ 0.3975 & 0.4195 & 0.408 \\ 0.3210 & 0.2930 & 0.308 \end{bmatrix}\begin{bmatrix} .80 \\ .10 \\ .10 \end{bmatrix} \\ \\ &\approx \begin{bmatrix} 0.28 \\ 0.40 \\ 0.32 \end{bmatrix} \end{align*} $$
Approximately $40\%$ of freshman students will be in a relationship.
Exercise 6 - Freshman Relationship State at the Beginning of Sophomore Year¶
How many students will be in a relationship at the beginning of their sophomore year?
View Solution
$$ \begin{align*} X_{12} &= P^{12}X_0 = \begin{bmatrix} .30 & .30 & .25 \\ .20 & .60 & .35 \\ .50 & .10 & .40 \end{bmatrix}^{12} \begin{bmatrix} .80 \\ .10 \\ .10 \end{bmatrix} \\ \\ &= \begin{bmatrix} 0.2847222199 & 0.2847222240 & 0.2847222220 \\ 0.4097222153 & 0.4097222276 & 0.4097222215 \\ 0.3055555648 & 0.3055555484 & 0.3055555565 \end{bmatrix}\begin{bmatrix} .80 \\ .10 \\ .10 \end{bmatrix} \\ \\ &\approx \begin{bmatrix} 0.28 \\ 0.41 \\ 0.31 \end{bmatrix} \end{align*} $$
Approximately $41\%$ of freshman students will be in a relationship by the beginning of their sophomore year.
Notice that in our first example, the values of the $X_3$ and $X_{12}$ are very close. In fact compute
$$ X_{13} = PX_{12} = \begin{bmatrix}\ 0.2847\dots\ \\ \ 0.4097\dots\ \\ \ 0.3056\dots\ \end{bmatrix} $$
In fact the values of $X_n$ are converging in the sense of calculus to
$$ \overline{X} \approx \begin{bmatrix}\ 0.284722\ \\ \ 0.409722\ \\ \ 0.305556\ \end{bmatrix} $$
This state $\overline{X}$ is called the steady state of the Markov Chain. It is called a steady state because the next state
$$ P\overline{X} = \overline{X} $$
is the same state.
Definition¶
Steady State
A stochastic matrix $P$ has a steady state if the sequence
$$ \left\{ X_0, PX_0, P^2X_0, P^3X_0, \dots, P^nX_0, \dots \right\} $$
converges. That is
$$ \overline{X} = \displaystyle\lim_{n\rightarrow\infty} P^nX_0. $$
$\overline{X}$ is called a steady state because for such a limiting state vector, $P\overline{X} = \overline{X}$.
Video Lecture 2 - Steady State Vectors¶
Steady StateExample 6 - Freshman Steady State¶
Find the steady state for the relationship state of incoming freshman students.
One needs to solve
$$ \begin{align*} P\overline{X} &= \overline{X} \\ P\overline{X} - \overline{X} &= \mathbf{0} \\ P\overline{X} - I\overline{X} &= \mathbf{0} \\ (P - I)\overline{X} &= \mathbf{0} \end{align*} $$
and since the steady state must be a transition probability vector,
$$ x_1 + x_2 + \cdots + x_n = 1\qquad(\text{the overlines will make this too tedious}) $$
Using the stochastic matrix for Example 4:
$$ \begin{align*} \begin{bmatrix}\ .30\ &\ .30\ &\ .25\ \\ \ .20\ &\ .60\ &\ .35\ \\ \ .50\ &\ .10\ &\ .40\ \end{bmatrix}\begin{bmatrix}\ x_1\ \\ \ x_2\ \\ \ x_3\ \end{bmatrix} &= \begin{bmatrix}\ x_1\ \\ \ x_2\ \\ \ x_3\ \end{bmatrix} \\ \\ \left(\begin{bmatrix}\ .30\ &\ .30\ &\ .25\ \\ \ .20\ &\ .60\ &\ .35\ \\ \ .50\ &\ .10\ &\ .40\ \end{bmatrix} - \begin{bmatrix}\ 1\ &\ 0\ &\ 0\ \\ \ 0\ &\ 1\ &\ 0\ \\ \ 0\ &\ 0\ &\ 1\ \end{bmatrix}\right)\begin{bmatrix}\ x_1\ \\ \ x_2\ \\ \ x_3\ \end{bmatrix} &= \mathbf{0} \\ \\ \begin{bmatrix} -.70\ &\ .30\ &\ .25\ \\ \ .20\ & -.40\ &\ .35\ \\ \ .50\ &\ .10\ & -.60\ \end{bmatrix}\begin{bmatrix}\ x_1\ \\ \ x_2\ \\ \ x_3\ \end{bmatrix} &= \mathbf{0} \\ \\ x_1 + x_2 + x_3 &= 1 \end{align*} $$
$$ \begin{align*} \left[ \begin{array}{ccc|c} -.70\ &\ .30\ &\ .25 & 0\ \\ \ .20\ & -.40\ &\ .35 & 0\ \\ \ .50\ &\ .10\ & -.60 & 0\ \\ \ 1\ &\ 1\ &\ 1\ & 1\ \end{array} \right] \begin{array}{l} R_4 \\ 10R_2 \\ 10R_3 \\ 10R_1 \\ \end{array} \rightarrow \left[ \begin{array}{ccc|c} \ 1\ &\ 1\ &\ 1\ & 1\ \\ \ 2\ & -4\ &\ 3.5 & 0\ \\ \ 5\ &\ 1\ & -6 & 0\ \\ -7\ &\ 3\ &\ 2.5 & 0\ \end{array} \right] \begin{array}{l} \\ R_2-2R_1 \\ R_3-5R_1 \\ R_4+7R_1 \\ \end{array} \rightarrow &\left[ \begin{array}{ccc|c} \ 1\ &\ 1\ &\ 1\ &\ 1\ \\ \ 0\ & -6\ &\ 1.5 & -2\ \\ \ 0\ & -4\ & -11 & -5\ \\ \ 0\ &\ 10\ &\ 9.5 &\ 7\ \end{array} \right] \begin{array}{l} \\ -R_3/4 \\ R_2 \\ \\ \end{array} \\ \\ \left[ \begin{array}{ccc|c} \ 1\ &\ 1\ &\ 1\ &\ 1\ \\ \ 0\ &\ 1\ & 2.75 & 1.25\ \\ \ 0\ & -6\ &\ 1.5 & -2\ \\ \ 0\ &\ 10\ &\ 9.5 &\ 7\ \end{array} \right] \begin{array}{l} \\ \\ R_3+6R_2 \\ R_4-10R_2 \\ \end{array} \rightarrow \left[ \begin{array}{ccc|c} \ 1\ &\ 1\ &\ 1\ &\ 1\ \\ \ 0\ &\ 1\ & 2.75 & 1.25\ \\ \ 0\ &\ 0\ &\ 18 & 5.5\ \\ \ 0\ &\ 0\ & -18\ & -5.5\ \end{array} \right] \begin{array}{l} \\ \\ \\ R_4+R_3 \\ \end{array} &\rightarrow \left[ \begin{array}{ccc|c} \ 1\ &\ 1\ &\ 1\ &\ 1\ \\ \ 0\ &\ 1\ & \frac{11}{4} & \frac{5}{4}\ \\ \ 0\ &\ 0\ &\ 18 & \frac{11}{2}\ \\ \ 0\ &\ 0\ &\ 0\ &\ 0\ \end{array} \right] \begin{array}{l} \\ \\ R_3/18 \\ \\ \end{array} \\ \\ \left[ \begin{array}{ccc|c} \ 1\ &\ 1\ &\ 1\ &\ 1\ \\ \ 0\ &\ 1\ & \frac{11}{4} & \frac{5}{4}\ \\ \ 0\ &\ 0\ &\ 1 & \frac{11}{36}\ \\ \ 0\ &\ 0\ &\ 0\ &\ 0\ \end{array} \right] \begin{array}{l} R_1-R_3 \\ R_2 - 11R_3/4 \\ \\ \\ \end{array} \rightarrow \left[ \begin{array}{ccc|c} \ 1\ &\ 1\ &\ 0\ &\ \frac{25}{36}\ \\ \ 0\ &\ 1\ & 0 & \frac{59}{144}\ \\ \ 0\ &\ 0\ &\ 1 & \frac{11}{36}\ \\ \ 0\ &\ 0\ &\ 0\ &\ 0\ \end{array} \right] \begin{array}{l} R_1-R_2 \\ \\ \\ \\ \end{array} &\rightarrow \left[ \begin{array}{ccc|c} \ 1\ &\ 0\ &\ 0\ &\ \frac{41}{144}\ \\ \ 0\ &\ 1\ & 0 & \frac{59}{144}\ \\ \ 0\ &\ 0\ &\ 1 & \frac{11}{36}\ \\ \ 0\ &\ 0\ &\ 0\ &\ 0\ \end{array} \right] \\ \\ \approx \left[ \begin{array}{ccc|c} \ 1\ &\ 0\ &\ 0\ & 0.2847\ \\ \ 0\ &\ 1\ & 0 & 0.4097\ \\ \ 0\ &\ 0\ &\ 1 & 0.3056\ \\ \ 0\ &\ 0\ &\ 0\ &\ 0\ \end{array} \right] &\ \end{align*} $$
The steady state of the Markov Process, or the relationship state for incoming freshman students after many months is
$$ \overline{X} = \begin{bmatrix}\ \frac{41}{144}\ \\ \ \frac{59}{144}\ \\ \ \frac{11}{36}\ \end{bmatrix} $$
Checking
$$ \frac{41}{144} + \frac{59}{144} + \frac{44}{144} = \frac{144}{144} \quad{\color{green}\large{\checkmark}} $$
Definition¶
Absorbing State
An absorbing state $s_j$ is a state whose transition probability $p_{jj}=1$. This means that once a member of the group $x\in G$ is assigned state $s_j$, the member stays in the state and never transitions away from it. Since the $j^{\text{th}}$ column of a transition probabilities matrix that contains $p_{jj}$ must sum to 1, the other entries of column $j$ must be zero.
Definition¶
Absorbing Markov Chain
An Absorbing Markov Chain has a Markov matrix that satisfies two properties
- There is at least one absorbing state.
- Every member of the group $x\in G$ can transition from a non-absorbing state to an absorbing state in a finite number of time steps.
Example 7 - Find the Steady State¶
Find the steady state of the Markov Chain with stochastic matrix $P = \begin{bmatrix}\ .6\ &\ 0\ &\ 0\ \\ \ 0\ &\ 1\ &\ .5\ \\ \ .4\ &\ 0\ &\ .5\ \end{bmatrix}$
Solving the system of equations
$$ \begin{align*} PX &= X \\ x_1 + x_2 + x_3 &= 1 \\ \end{align*} $$
yields
$$ \begin{align*} \left(\begin{bmatrix}\ .6\ &\ 0\ &\ 0\ \\ \ 0\ &\ 1\ &\ .5\ \\ \ .4\ &\ 0\ &\ .5\ \end{bmatrix} - \begin{bmatrix}\ 1\ &\ 0\ &\ 0\ \\ \ 0\ &\ 1\ &\ 0\ \\ \ 0\ &\ 0\ &\ 1\ \end{bmatrix} \right)X &= O \\ \\ \begin{bmatrix} -.4\ &\ 0\ &\ 0\ \\ \ 0\ &\ 0\ &\ .5\ \\ \ .4\ &\ 0\ & -.5\ \end{bmatrix}X &= O \\ x_1 + x_2 + x_3 &= 1 \\ \\ \left[ \begin{array}{ccc|c} -.4\ &\ 0\ &\ 0 & 0\ \\ \ 0\ &\ 0\ &\ .5 & 0\ \\ \ .4\ &\ 0\ & -.5 & 0\ \\ \ 1\ &\ 1\ &\ 1\ & 1\ \end{array} \right] \begin{array}{l} R_4 \\ \\ \\ R_1 \\ \end{array} &\rightarrow \left[ \begin{array}{ccc|c}\ 1\ &\ 1\ &\ 1\ & 1\ \\ \ 0\ &\ 0\ &\ .5 & 0\ \\ \ .4\ &\ 0\ & -.5 & 0\ \\ -.4\ &\ 0\ &\ 0 & 0\ \end{array} \right] \begin{array}{l} \\ 10R_2 \\ 10R_3 \\ 10R_4 \\ \end{array} \rightarrow \left[ \begin{array}{ccc|c}\ 1\ &\ 1\ &\ 1\ & 1\ \\ \ 0\ &\ 0\ &\ 5 & 0\ \\ \ 4\ &\ 0\ & -5 & 0\ \\ -4\ &\ 0\ &\ 0 & 0\ \end{array} \right] \begin{array}{l} \\ \\ R_3+R_4 \\ R_4+4R_1 \\ \end{array} \\ \\ \rightarrow \left[ \begin{array}{ccc|c}\ 1\ &\ 1\ &\ 1\ & 1\ \\ \ 0\ &\ 0\ &\ 5 & 0\ \\ \ 0\ &\ 0\ & -5 & 0\ \\ \ 0\ &\ 4\ &\ 4 & 4\ \end{array} \right] \begin{array}{l} \\ \\ R_3+R_2 \\ R_4/4 \\ \end{array} &\rightarrow \left[ \begin{array}{ccc|c}\ 1\ &\ 1\ &\ 1\ & 1\ \\ \ 0\ &\ 0\ &\ 5 & 0\ \\ \ 0\ &\ 0\ &\ 0 & 0\ \\ \ 0\ &\ 1\ &\ 1 & 1\ \end{array} \right] \begin{array}{l} \\ R_4 \\ R_2/5 \\ R_3 \\ \end{array} \rightarrow \left[ \begin{array}{ccc|c}\ 1\ &\ 1\ &\ 1\ & 1\ \\ \ 0\ &\ 1\ &\ 1 & 1\ \\ \ 0\ &\ 0\ &\ 1 & 0\ \\ \ 0\ &\ 0\ &\ 0 & 0\ \end{array} \right] \begin{array}{l} R_1-R_3 \\ R_2-R_3 \\ \\ \\ \end{array} \\ \\ \rightarrow \left[ \begin{array}{ccc|c}\ 1\ &\ 1\ &\ 0\ & 1\ \\ \ 0\ &\ 1\ &\ 0\ & 1\ \\ \ 0\ &\ 0\ &\ 1 & 0\ \\ \ 0\ &\ 0\ &\ 0 & 0\ \end{array} \right] \begin{array}{l} R_1-R_2 \\ \\ \\ \\ \end{array} &\rightarrow \left[ \begin{array}{ccc|c}\ 1\ &\ 0\ &\ 0\ & 0\ \\ \ 0\ &\ 1\ &\ 0 & 1\ \\ \ 0\ &\ 0\ &\ 1 & 0\ \\ \ 0\ &\ 0\ &\ 0 & 0\ \end{array} \right] \end{align*} $$
Eventually the entire population $G$ will be in state $s_2$.
Definition¶
Periodic State
A periodic state is a state vector $X$ of a stochastic matrix such that for an integer $m>1$, $P^{km}X=X$, for any integer $k\ge 1$, and $m$ is the smallest integer with this property. If $0 < j < m$, then $P^jX\neq X$.
Definition¶
Periodic Markov Chain
A Periodic Markov Chain has a periodic state with period $m>1$. That is a state the system returns to at only times $mk$ for $k=1,2,3,\dots$. The system does not return to the state every time like a steady state, but rather at a specific interval called the period, $m$.
Example 8 - Periodic State¶
The stochastic matrix $P = \begin{bmatrix}\ 0\ &\ 1\ &\ 0\ \\ \ 0\ &\ 0\ &\ 1\ \\ \ 1\ &\ 0\ &\ 0\ \end{bmatrix}$ has no absorbing state. Any member $x\in G$ always transitions from state $s_1$ to state $s_3$, from state $s_3$ to state $s_2$, and from state $s_2$ to state $s_1$.
$$ \begin{align*} (P - I)\overline{X} &= \begin{bmatrix} -1\ & \ 1\ &\ 0\ \\ \ 0\ & -1\ &\ 1\ \\ \ 1\ &\ 0\ & -1\ \end{bmatrix}\overline{X} = O \\ \\ x_1 + x_2 + x_3 &= 1 \\ \\ \left[ \begin{array}{ccc|c} -1\ &\ 1\ &\ 0\ &\ 0\ \\ \ 0\ & -1\ &\ 1\ &\ 0\ \\ \ 1\ &\ 0\ & -1\ &\ 0\ \\ \ 1\ &\ 1\ &\ 1 &\ 1\ \end{array} \right] \begin{array}{l} R_4 \quad\ \ \\ \\ \\ R_1 \end{array} &\rightarrow \left[ \begin{array}{ccc|c}\ 1\ &\ 1\ &\ 1 &\ 1\ \\ \ 0\ & -1\ &\ 1\ &\ 0\ \\ \ 1\ &\ 0\ & -1\ &\ 0\ \\ -1\ &\ 1\ &\ 0\ &\ 0\ \end{array} \right] \begin{array}{l} \\ -R_2 \\ R_3-R_1 \\ R_4+R_1 \end{array} \rightarrow \left[ \begin{array}{ccc|c}\ 1\ &\ 1\ &\ 1 &\ 1\ \\ \ 0\ &\ 1\ & -1\ &\ 0\ \\ \ 0\ & -1\ & -2\ & -1\ \\ \ 0\ &\ 2\ &\ 1\ &\ 1\ \end{array} \right] \begin{array}{l} \\ \\ R_3+R_2 \\ R_4-2R_2 \end{array} \rightarrow \\ \\ \left[ \begin{array}{ccc|c}\ 1\ &\ 1\ &\ 1 &\ 1\ \\ \ 0\ &\ 1\ & -1\ &\ 0\ \\ \ 0\ &\ 0\ & -3\ & -1\ \\ \ 0\ &\ 0\ &\ 3\ &\ 1\ \end{array} \right] \begin{array}{l} \\ \\ \\ R_4+R_3 \end{array} &\rightarrow \left[ \begin{array}{ccc|c}\ 1\ &\ 1\ &\ 1 &\ 1\ \\ \ 0\ &\ 1\ & -1\ &\ 0\ \\ \ 0\ &\ 0\ & -3\ & -1\ \\ \ 0\ &\ 0\ &\ 0\ &\ 0\ \end{array} \right] \begin{array}{l} \\ \\ -R_3/3 \quad \\ \end{array} \rightarrow \left[ \begin{array}{ccc|c}\ 1\ &\ 1\ &\ 1 &\ 1\ \\ \ 0\ &\ 1\ & -1\ &\ 0\ \\ \ 0\ &\ 0\ &\ 1\ &\ \frac{1}{3}\ \\ \ 0\ &\ 0\ &\ 0\ &\ 0\ \end{array} \right] \begin{array}{l} R_1-R_3 \\ R_2+R_3 \\ \\ \\ \end{array} \rightarrow \\ \left[ \begin{array}{ccc|c}\ 1\ &\ 1\ &\ 0 &\ \frac{2}{3}\ \\ \ 0\ &\ 1\ &\ 0\ &\ \frac{1}{3}\ \\ \ 0\ &\ 0\ &\ 1\ &\ \frac{1}{3}\ \\ \ 0\ &\ 0\ &\ 0\ &\ 0\ \end{array} \right] \begin{array}{l} R_1-R_2 \\ \\ \\ \\ \end{array} &\rightarrow \left[ \begin{array}{ccc|c}\ 1\ &\ 0\ &\ 0 &\ \frac{1}{3}\ \\ \ 0\ &\ 1\ &\ 0\ &\ \frac{1}{3}\ \\ \ 0\ &\ 0\ &\ 1\ &\ \frac{1}{3}\ \\ \ 0\ &\ 0\ &\ 0\ &\ 0\ \end{array} \right] \end{align*} $$
$\overline{X} = \begin{bmatrix}\ 1/3\ \\ \ 1/3\ \\ \ 1/3\ \end{bmatrix}$ has the property that $P\overline{X}=\overline{X}$. However $\overline{X}$ is not a steady state. This is a periodic stochastic matrix. It does not have the property that
$$ \lim_{n\rightarrow\infty} P^nX_0 = \overline{X} $$
for any initial state $X_0$. Only when $X_0=\overline{X}$ do we have a constant sequence. State $\overline{X}$ is sometimes referred to as a stationary state.
Definition¶
Regular Stochastic Matrix
A stochastic matrix $P$ is called regular if and only if all of the entries of some positive integer power of $P$ are positive. This implies that the stochastic process has no absorbing state.
Example 9 - Regular Stochastic Matrix¶
The stochastic matrix in Example 4, $P = \begin{bmatrix}\ .30\ &\ .30\ &\ .25\ \\ \ .20\ &\ .60\ &\ .35\ \\ \ .50\ &\ .10\ &\ .40\ \end{bmatrix}$ is a regular stochastic matrix.
Example 10 - Absorbing Stochastic Matrix¶
The stochastic matrix in Example 6, $P = \begin{bmatrix}\ .6\ &\ 0\ &\ 0\ \\ \ 0\ &\ 1\ &\ .5\ \\ \ .4\ &\ 0\ &\ .5\ \end{bmatrix}$ is not a regular stochastic matrix.
Example 11 - Periodic Stochastic Matrix¶
The stochastic matrix in Example 7, $P = \begin{bmatrix}\ 0\ &\ 1\ &\ 0\ \\ \ 0\ &\ 0\ &\ 1\ \\ \ 1\ &\ 0\ &\ 0\ \end{bmatrix}$ is not a regular stochastic matrix.
Theorem 2¶
Regular Stochastic Matrices have a Steady State
The Markov Chain of a regular stochastic matrix
$$ \left\{ X_0, PX_0, P^2X_0, P^3X_0, \dots, P^nX_0, \dots \right\} $$
approaches a steady state
$$ \overline{X} = \displaystyle\lim_{n\rightarrow\infty} P^nX_0. $$
We cannot prove this theorem until we learn about determinants in chapter 3.
Video Lecture 3 - State Diagrams¶
State DiagramsExample 12 - A Line of Steady States¶
Consider the Markov Process with stochastic matrix $\begin{bmatrix}\ 0.4\ &\ 0\ &\ 0.2\ &\ 0\ \\ \ 0.2\ &\ 1\ &\ 0.3\ &\ 0\ \\ \ 0.2\ &\ 0\ &\ 0.4\ &\ 0\ \\ \ 0.2\ &\ 0\ &\ 0.1\ &\ 1\ \end{bmatrix}$. Find the steady state of the Markov Chain.
$$ \begin{align*} \left( \begin{bmatrix}\ 0.4\ &\ 0\ &\ 0.2\ &\ 0\ \\ \ 0.2\ &\ 1\ &\ 0.3\ &\ 0\ \\ \ 0.2\ &\ 0\ &\ 0.4\ &\ 0\ \\ \ 0.2\ &\ 0\ &\ 0.1\ &\ 1\ \end{bmatrix} - \begin{bmatrix}\ 1\ &\ 0\ &\ 0\ &\ 0\ \\ \ 0\ &\ 1\ &\ 0\ &\ 0\ \\ \ 0\ &\ 0\ &\ 1\ &\ 0\ \\ \ 0\ &\ 0\ &\ 0\ &\ 1\ \end{bmatrix} \right)X &= O \\ \\ \begin{bmatrix} -0.6\ &\ 0\ &\ 0.2\ &\ 0\ \\ \ 0.2\ &\ 0\ &\ 0.3\ &\ 0\ \\ \ 0.2\ &\ 0\ & -0.6\ &\ 0\ \\ \ 0.2\ &\ 0\ &\ 0.1\ &\ 0\ \end{bmatrix}X &= O \\ \\ x_1 + x_2 + x_3 + x_4 &= 1 \\ \\ \left[ \begin{array}{cccc|c} -0.6\ &\ 0\ &\ 0.2\ &\ 0 & 0\ \\ \ 0.2\ &\ 0\ &\ 0.3\ &\ 0 & 0\ \\ \ 0.2\ &\ 0\ & -0.6\ &\ 0 & 0\ \\ \ 0.2\ &\ 0\ &\ 0.1\ &\ 0 & 0\ \\ \ 1\ &\ 1\ &\ 1\ &\ 1 & 1\ \end{array} \right] \begin{array}{l} R_5 \\ 10R_2 \\ 10R_3 \\ 10R_4 \\ 10R_1 \end{array} \rightarrow \left[ \begin{array}{cccc|c} \ 1\ &\ 1\ &\ 1\ &\ 1 & 1\ \\ \ 2\ &\ 0\ &\ 3\ &\ 0 & 0\ \\ \ 2\ &\ 0\ & -6\ &\ 0 & 0\ \\ \ 2\ &\ 0\ &\ 1\ &\ 0 & 0\ \\ -6\ &\ 0\ &\ 2\ &\ 0 & 0\ \end{array} \right] \begin{array}{l} \\ R_2-2R_1 \\ R_3-2R_1 \\ R_4-2R_1 \\ R_5+6R_1 \end{array} &\rightarrow \left[ \begin{array}{cccc|c} \ 1\ &\ 1\ &\ 1\ &\ 1 &\ 1\ \\ \ 0\ & -2\ &\ 1\ & -2\ & -2\ \\ \ 0\ & -2\ & -8\ & -2 & -2\ \\ \ 0\ & -2\ & -1\ & -2 & -2\ \\ \ 0\ &\ 6\ &\ 8\ &\ 6 & 6\ \end{array} \right] \begin{array}{l} \\ -R_3/2 \\ R_2 \\ \\ R_5/2 \end{array} \\ \\ \rightarrow \left[ \begin{array}{cccc|c} \ 1\ &\ 1\ &\ 1\ &\ 1 &\ 1\ \\ \ 0\ &\ 1\ &\ 4\ &\ 1 &\ 1\ \\ \ 0\ & -2\ &\ 1\ & -2 & -2\ \\ \ 0\ & -2\ & -1\ & -2 & -2\ \\ \ 0\ &\ 3\ &\ 4\ &\ 3 & 3\ \end{array} \right] \begin{array}{l} \\ \\ R_3+2R_2 \\ R_4+2R_2 \\ R_5-3R_2 \end{array} \rightarrow \left[ \begin{array}{cccc|c} \ 1\ &\ 1\ &\ 1\ &\ 1 &\ 1\ \\ \ 0\ &\ 1\ &\ 4\ &\ 1 &\ 1\ \\ \ 0\ &\ 0\ &\ 9\ &\ 0 &\ 0\ \\ \ 0\ &\ 0\ &\ 7\ &\ 0 & 0\ \\ \ 0\ &\ 0\ & -8\ &\ 0 &\ 0\ \end{array} \right] \begin{array}{l} \\ \\ R_3/9 \\ R_4/7 \\ -R_5/8 \end{array} &\rightarrow \left[ \begin{array}{cccc|c} \ 1\ &\ 1\ &\ 1\ &\ 1 &\ 1\ \\ \ 0\ &\ 1\ &\ 4\ &\ 1 &\ 1\ \\ \ 0\ &\ 0\ &\ 1\ &\ 0 &\ 0\ \\ \ 0\ &\ 0\ &\ 1\ &\ 0 & 0\ \\ \ 0\ &\ 0\ &\ 1\ &\ 0 &\ 0\ \end{array} \right] \begin{array}{l} R_1-R_3 \\ R_2-4R_3 \\ \\ R_4-R_3 \\ R_5-R_3 \end{array} \\ \\ &\rightarrow \left[ \begin{array}{cccc|c} \ 1\ &\ 0\ &\ 0\ &\ 0 &\ 0\ \\ \ 0\ &\ 1\ &\ 0\ &\ 1 &\ 1\ \\ \ 0\ &\ 0\ &\ 1\ &\ 0 &\ 0\ \\ \ 0\ &\ 0\ &\ 0\ &\ 0 & 0\ \\ \ 0\ &\ 0\ &\ 0\ &\ 0 &\ 0\ \end{array} \right] \begin{array}{l} R_1-R_2 \\ \\ \\ \\ \\ \end{array} \\ \\ x_4 &= t\in\mathbb{R} \\ x_3 &= 0 \\ x_2+t &= 1 \\ x_2 &= 1-t \\ x_1 &= 0 \end{align*} $$
There are infinitely many steady state solutions, $\begin{bmatrix}\ 0\ \\ 1-t\ \\ \ 0\ \\ \ t\ \end{bmatrix} = \begin{bmatrix}\ 0\ \\ \ 1\ \\ \ 0\ \\ \ 0\ \end{bmatrix} + \begin{bmatrix}\ 0\ \\ -1\ \\ \ 0\ \\ \ 1\ \end{bmatrix}t$, $t\in[0,1]$. The solution indicates that whatever portion of the population ends up in state 4, the rest of the population remains in state 2.
Definition¶
State Diagram
A Directed Graph or
digraph is a collection of nodes and directed edges:
- The nonempty set of nodes includes one node for each state of the stochastic process
- The nonempty set of directed edges represents the transition probabilities $p_{ij}$ of the stochastic matrix
In a directed graph, the edges are curves connecting two nodes that have a direction indicated by an arrowhead indicating transition from one state to another state. There are three types of edges.
- An in arrow is a directed edge that originates at another node and terminates at the target node. The arrowhead points at the target node or state.
- An out arrow is a directed edge that originates at the target node and terminates at some other node in the graph. The arrowhead points from the target node away to some other node.
- A loop arrow originates and terminates at the same node.
If we designate $S$ as the set of states or nodes, and $E$ as the set of directed edges, then the graph $\Gamma = (S, E)$ is the collection of both the states and the directed edges. This graph $\Gamma$ is the state diagram for a stochastic process.
Example 13 - Freshman Relationships State Diagram¶
A state graph should label each node with the state it represents. Each directed edge should represent the transition probability $p_{ij} = P(\mathbf{X}_n=s_i\,|\,\mathbf{X}_{n-1}=s_j)$. This means that the directed edge should originate from vertex $s_j$ and terminate at vertex $s_i$. When confronted with a word problem, or a spread sheet of transition probabilities, create the state diagram first. This will greatly aid in creating and verifying the stochastic matrix based on the data.
Exercise 7 - Create the State Diagram¶
Create the state diagram for the stochastic matrix in Example 6,
$$ P = \begin{bmatrix}\ .6\ &\ 0\ &\ 0\ \\ \ 0\ &\ 1\ &\ .5\ \\ \ .4\ &\ 0\ &\ .5\ \end{bmatrix} $$
Google PageRank Algorithm¶
The original PageRank algorithm used by Google$\trademark$ creates a state diagram. The vertices are web pages, and the edges are weighted with the number and quality of links from page $s_j$ to page $s_i$. With the total value of all links it computes the transition probability for each edge, the probability vectors, and the Markov matrix. The quality of a web page is the number of links to the web page. Then the algorithm computes the probability eigenvectors of the Markov matrix. We will study eigenvectors in chapter 7.
Exercise 8 - Create the Stochastic Matrix¶
Create the stochastic matrix from the state diagram,
