Markov Chains

Example

Let's say you have a small country with 1,000,000 people. 60% of people live in cities, and 40% live in the suburbs.

Every year, 95% of people who live in cities stay there. Also, 97% of people who live in suburbs stay there.

We can calculate the percent of city dwellers by counting the people who remained + people who moved in. That equals $$(.6)*(.95) + (.4)*(.03) = 0.582$$ The percent of suburbians equals the people who remain + move in. This equals $$(.4)*(.97) + (.6)(.05) = .418$$We can write this as a matrix: $$\begin{bmatrix}\text{city}_{k+1}\\\text{suburb}_{k+1}\end{bmatrix} = \begin{bmatrix}.95 & .03\\.05 & .97\end{bmatrix} \begin{bmatrix}\text{city}_k\\\text{suburb}_k\end{bmatrix}$$ Now, if you look 30 years in advance, for example, you get 40% city folk, but does it stabilize to some percent? The answer is $\boxed{\text{yes}}$. Before we get to that, we should define Markov Chains.

What is a Markov Chain?

A Markov chain is a sequence of vectors {$x_0$, $x_1$ ... $x_n$} such that $x_1 = Px_0$, $x_2 = Px_1$, etc. where P is a stochastic matrix.

A stochastic matrix is a matrix whose columns are composed of probabilities.

Steady-State Vector

I created a markov chain of length 100 for the population example starting at p = 0.6 and p = 0.3, and they both converged to the same value. 

Shown above, both populations approach something like 37% urban population. What does this mean?

This is called a steady-state vector. It's the long term solution to a Markov chain. If the steady-state vector is called q This can be written as $$q = Pq \to Iq = Pq \to (P-I)q = 0$$ In our case, this equals $$q = \begin{bmatrix}.95 & .03\\.05 & .97\end{bmatrix}q \to \begin{bmatrix}-.05 & .03\\.05 & -0.03\end{bmatrix}\begin{bmatrix}\text{city}\\\text{suburbs}\end{bmatrix} = 0$$ Solving the system of equations, we get one equation (the second one is equaivalent). $$-0.05\text{city} + 0.03\text{suburbs} = 0 \to \dfrac{3}{5}\text{suburbs} = \text{city}$$ $$\begin{bmatrix}\text{city}\\\text{suburbs}\end{bmatrix} = \text{suburbs}\cdot\begin{bmatrix}\frac{3}{5}\\1\end{bmatrix}$$ If we want the vector in terms of percentages, we divide by $\frac{3}{5} + 1 = \frac{8}{5}$ $$q = \begin{bmatrix}\frac{3}{8} \\ \frac{5}{8}\end{bmatrix} = \begin{bmatrix}0.375 \\ 0.625\end{bmatrix}$$ This always convergence, regardless of what you start with.

Significance

What does this mean? The steady-state vector signifies the long-term solution to the Markov Chain. This means in the long-term (100 years), 37.5% of people will live in cities. 

Steady-state vectors may also define long-term probabilities. For example, one possible Markov Chain problem is about predicting weather. 90% of time, if it's sunny today, it'll be sunny tomorrow. 50% of the time, if it's rainy today, it'll be rainy tomorrow. In this problem, the steady-state vector means the overall probability. 

How do we know this will converge?

When we defined steady-state vectors, they were written like this:

$$q = Pq \to 1q = Pq$$ This means that 1 is an eigenvalue. We want to prove that for every matrix with columns as probability vectors, 1 will be an eigenvalue. Let's look at 2x2 matrices, for the sake of simplicity. $$\begin{bmatrix}a & b\\1-a & 1-b\end{bmatrix}$$ Now, we need to calculate the eigenvalues: $$\begin{vmatrix}\lambda - a & b\\1-a & \lambda - (1-b)\end{vmatrix} = 0$$ The characteristic polynomial equals $$(\lambda - a)(\lambda - (1-b)) - b + ab = 0$$ $$\lambda^2 + (-a - 1 + b)\lambda + a -ab - b + ab$$ $$\lambda^2 + (b-a - 1)\lambda + a - b$$ Here, we can see that (b-a-1) = -(a - b + 1) which is perfect! $$(\lambda - 1)(\lambda - (a-b)) = 0$$ So, one eigenvalue is guaranteed to be 1. Therefore, there will always be a steady-state solution.