Markov Chain

Some Definitions (from MATH 115)

Probability Vector A vector $\vec{s}\in {\mathbb{R}}^n$ is called a probability vector if the entries in the vector are nonnegative and sum to 1.

Stochastic Matrix A square matrix is called stochastic if its columns are probability vectors.

State Vectors, Markov Chains Given a stochastic matrix $P$, a Markov Chain is a sequence of probability vectors $\overrightarrow{s_0},\overrightarrow{s_1},\overrightarrow{s_2},\dots$ where $\overrightarrow{s_{k+1}}=P\overrightarrow{s_k}$ for every nonnegative integer $k$. In a Markov Chain, the probability vectors $\overrightarrow{s_k}$ are called state vectors.

Steady-State Vector If $P$ is a stochastic matrix, then a state vector$\vec{s}$ is called a steady-state vector for P if $P\vec{s}=\vec{s}$. It can be shown that every stochastic matrix has a steady-state vector.

Regular Matrix Definition An $n\times n$ stochastic matrix $P$ is called regular if for some positive integer $k$, the matrix $P^k$ has all positive entries.

To solve a Markov Chain problem (in MATH115)

Theorem 29.6. Let P be a regular$n\times n$ stochastic matrix. Then $P$ has a unique steady- state vector $\vec{s}$ and for any initial state vector ${\vec{s}}_0\in {\mathbb{R}}^n$, the resulting Markov Chain converges to the steady-state vector $\vec{s}$.

1. Read and understand the problem
2. Determine the stochastic matrix $P$ and verify that $P$ is regular
3. Determine the initial state vector $\overrightarrow{s_0}$ if required
4. Solve the homogeneous system $(P-I)\vec{s}=\vec{0}$
5. Choose values for any parameters resulting from solving the above system so that $\vec{s}$ is a probability vector
6. Conclude by Theorem 29.6 that $\vec{s}$ is the steady-state vector
7. Interpret the entries of $\vec{s}$ in terms of the original problem as needed