Markov Matrices

A Markov matrix is a linear transformation representing a Markov chain.

Definition

A Markov matrix has these defining characteristics:

• all values are greater than or equal to 0
• each column sums to 1

From these characteristics, it is immediately proven that:

• one of the eigenvalues is 1

  • Eigenvalues are characterized by the test |A - λI| = 0

  • Subtracting the identity matrix from A means subtracting 1 from each column which, as stated, sum to 1. Therefore, the difference has columns which sum to 0.

  • The determinent of this difference is clearly 0, so the test holds.

• all other eigenvalues are characterized by |λ_i| < 0

Fomulation

A Markov matrix is diagonalizable, so repeated multiplication is characterized by A^k = SΛ^kS^-1. The state of a Markov chain in period k can be represented as u_k = A^ku₀.

A^ku₀ can also be factored out into c₁λ^k₁x₁ + c₂λ^k₂x₂ + ... + c_nλ^k_nx_n.

If 10% of the population on the left will move to the right every period, and 20% of the population on the right will move to the left every period, then this linear transformation can be characterized as:

┌  ┐   ┌      ┐ k┌     ┐
│ l│   │ .9 .2│  │ l r │
│ r│ = │ .1 .8│  └     ┘0
└  ┘k  └      ┘

...and also as u_k = c₁λ^k₁x₁ + c₂λ^k₂x₂.

If the initial state is [0 1000], then trivially the state after one period is [200 800].

Note that in the litarature, Markov matrices are usually written in transpose form. That is, the matrix is multiplied on the right hand side of the initial state vector.

┌  ┐   ┌  ┐ ┌      ┐ k
│ l│   │ l│ │ .9 .1│
│ r│ = │ r│ │ .2 .8│
└  ┘k  └  ┘0└      ┘

Solution for Any Period

There are two eigenvalues and there ought to be two independent eigenvectors.

λ₁ is always 1 for a Markov matrix. The trace for this matrix is 1.7 and, because eigenvalues sum to the trace, λ₂ must be 0.7.

The eigenvector for λ=1 can trivially be found as [2 1].

(0.9-λ)u + (0.2)v = 0
-0.1u + 0.2v = 0
0.2v = 0.1u
2v = u

Less trivially, the eigenvector for λ=0.7 can quickly be found as [-1 1].

(0.9-λ)u + (0.2)v = 0
0.2u + 0.2v = 0
u + v = 0
v = -u

Subsitute these eigenvectors and the initial state (u_k) into the second formulation to solve for the coefficients.

The second formulation (u_k = c₁λ^k₁x₁ + c₂λ^k₂x₂) in the initial state (k=0) reduces to [0 1000] = c₁x₁ + c₂x₂. Now that x_i have been found, the initial state can be solved for the coefficients.

0 = 2a - b
b = 2a

1000 = a + b
1000 = a + (2a)
1000 = 3a
1000/3 = a

b = 2a
b = 2(1000/3)
b = 2000/3

Altogether, the Markov matrix can be solved in any period as u_k = c₁λ^k₁x₁ + c₂λ^k₂x₂

┌  ┐              ┌  ┐                 ┌  ┐
│ l│              │ 2│               k │-1│
│ r│ = (1000/3) 1 │ 1│ + (2000/3) 0.7  │ 1│
└  ┘k             └  ┘                 └  ┘

Stable State

Because Markov chains are repeated, it is useful to consider the limit of A^k as k approaches infinity.

From the factorization as c₁λ^k₁x₁ + c₂λ^k₂x₂ + ...:

• Because λ₁ is always 1 for a Markov matrix, and because 1 raised ot any power is 1, the first term will always approach c₁x₁.

• Because all other λ_i are characterized by |λ_i| < 0, and because exponentiation with bases between 1 and -1 always trends towards 0, all other terms will always approach 0.

Altogether, it is trivial to demonstrate that a Markov matrix approaches c₁x₁ as the chain is repeated.

In this example, that limit is (1000/3) [2 1], or [2000/3 1000/3].

Programming in Julia

julia> using LinearAlgebra

julia> A = [0.9 0.2; 0.1 0.8]
2×2 Matrix{Float64}:
 0.9  0.2
 0.1  0.8

julia> u0 = [0 1000]'                                 # initial state
2×1 adjoint(::Matrix{Int64}) with eltype Int64:
    0
 1000

julia> A * u0                                         # first period
2×1 Matrix{Float64}:
 200.0
 800.0

julia> A^100 * u0                                     # really far off period approaching the stable state
2×1 Matrix{Float64}:
 666.6666666666707
 333.3333333333358

CategoryRicottone