Markov Chains

Probability Vector, State Vector, Stochastic Matrix

Definition

A vector is a probability vector if the entries in the vector are nonnegative and sum to .

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

Given a stochastic matrix , a Markov Chain has a sequence of probability vectors , where

for every nonnegative integers .

In a Markov chain, the probability vectors are called state vectors.

Steady State Vector

Definition

If is a stochastic matrix, then a state vector is called a steady-state vector for if

It can be shown that every stochastic matrix has a steady-state vector.

Finding the Steady State Vector

To algebraically determine any steady-state vectors, we start with . Then

Where is the identity matrix and is the zero vector. This way, we have a homogeneous system.

Then solve the system for

Example

Given:

Find

Carry the matrix to RREF

Now setting to the free variable , we find that , so , so

Since ,

Regular

Definition

An stochastic matrix is regular if for some positive integer , the matrix has all positive entries

Theorem

Let be a regular stochastic matrix.
has a unique steady-state vector for any initial state vector , the resulting Markov chain converges to the steady-state vector .

Example Problem

In a zombie apocalypse, a person exists in exactly one of two states: human or zombie
If a person is a human on any given day, then that person will become a zombie on the next day with probability
If a person is a zombie on any given day, then that zombie has a chance of being cured the next day
We are interested in computing the probability that a person is a human or zombie days after the onset of the zombie apocalypse

From		To
Human	Zombie
		Human
		Zombie

For example, a zombie has a chance of staying a zombie
Notice how each column adds up to 1

For , let be the probability that a person is a human on day , and be the probability that a person is a zombie on day

Since of humans on day will remain human the next day, and of zombies on day will become human the next day, we have that

And

This gives us a system of equations

Now let

Since a person cannot be both a human and a zombie, we have . (Probability Vector, State Vector, Stochastic Matrix)

Suppose on day , everyone is still human. Thus
We can now compute

We can see that the sequence converges to

In fact,

Thus, if the system reaches state , then the probabilities that a given person is a human or zombie no longer change over time. (Steady State Vector)

We can also find the steady-state vector algebraically.