= Markov Matrices =

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

<<TableOfContents>>

----



== 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 [[LinearAlgebra/EigenvaluesAndEigenvectors|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 [[LinearAlgebra/Diagonalization|diagonalizable]], so repeated multiplication is characterized by '''''A'''^k^ = '''SΛ'''^k^'''S'''^-1^''. The state of a Markov chain in period ''k'' can be represented as ''u,,k,, = '''A'''^k^u,,0,,''.

'''''A'''^k^u,,0,,'' can also be factored out into ''c,,1,,λ^k^,,1,,x,,1,, + c,,2,,λ^k^,,2,,x,,2,, + ... + c,,n,,λ^k^,,n,,x,,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,,1,,λ^k^,,1,,x,,1,, + c,,2,,λ^k^,,2,,x,,2,,''.

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 [[LinearAlgebra/EigenvaluesAndEigenvectors|eigenvalues]] and there ought to be two independent eigenvectors.

''λ,,1,,'' is always 1 for a Markov matrix. The trace for this matrix is 1.7 and, because eigenvalues sum to the trace, ''λ,,2,,'' 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,,1,,λ^k^,,1,,x,,1,, + c,,2,,λ^k^,,2,,x,,2,,'') in the initial state (''k=0'') reduces to ''[0 1000] = c,,1,,x,,1,, + c,,2,,x,,2,,''. 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,,1,,λ^k^,,1,,x,,1,, + c,,2,,λ^k^,,2,,x,,2,,''

{{{
┌  ┐              ┌  ┐                 ┌  ┐
│ 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,,1,,λ^k^,,1,,x,,1,, + c,,2,,λ^k^,,2,,x,,2,, + ...'':
 * Because ''λ,,1,,'' is always 1 for a Markov matrix, and because 1 raised ot any power is 1, the first term will always approach ''c,,1,,x,,1,,''.
 * 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,,1,,x,,1,,'' 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