{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Markov matrices\n", "\n", "A matrix $A$ is a **Markov matrix** if\n", "\n", "* Its entries are all $\\ge 0$\n", "* Each **column**'s entries **sum to 1**\n", "\n", "Typicaly, a Markov matrix's entries represent **transition probabilities** from one state to another.\n", "\n", "For example, consider the $2 \\times 2$ Markov matrix:" ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2×2 Array{Float64,2}:\n", " 0.9 0.2\n", " 0.1 0.8" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "A = [0.9 0.2\n", " 0.1 0.8]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Let us suppose that this represents the fraction of people switching majors each year between math and English literature.\n", "\n", "Let\n", "$$\n", "x = \\begin{pmatrix} m \\\\ e \\end{pmatrix}\n", "$$\n", "\n", "represent the number of math majors $m$ and English majors $e$. Suppose that each year, 10% of math majors and 20% of English majors switch majors. After one year, the new number of math and English majors is:\n", "\n", "$$\n", "m' = 0.9 m + 0.2 e\n", "e' = 0.1 m + 0.8 e\n", "$$\n", "\n", "But this is equivalent to a matrix multiplication! i.e. the numbers $x'$ of majors after one year is\n", "\n", "$$\n", "x' = A x \\,\n", "$$\n", "\n", "Note that the two Markov properties are critical: we never have negative numbers of majors (or negative probabilities), and the probabilities must sum to 1 (the net number of majors is not changing: we're not including new students or people that graduate in this silly model)." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Eigenvalues of Markov matrices\n", "\n", "There are two key questions about Markov matrices that can be answered by analysis of their eigenvalues:\n", "\n", "* Is there a **steady state**?\n", " - i.e. is there an $x_0 \\ne 0$ such that $A x_0 = x_0$?\n", " - i.e. is there $\\lambda_0 = 1$ eigenvector $x_0$?\n", "\n", "* Does the system **tend toward a steady state?**\n", " - i.e. does $A^n x \\to \\mbox{multiple of } x_0$ as $n \\to \\infty$?\n", " - i.e. is $\\lambda = 1$ the **largest** $|\\lambda|$?\n", " \n", "The answers are **YES** for **any Markov** matrix $A$, and **YES** for any *positive* Markov matrix (Markov matrices with entries $> 0$, not just $\\ge 0$). For *any* Markov matrix, all of the λ satisfy $|\\lambda| \\le 1$, but if there are zero entries in the matrix we *may* have multiple $|\\lambda|=1$ eigenvalues (though this doesn't happen often in practical Markov problems)." ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2-element Array{Float64,1}:\n", " 1.0\n", " 0.7" ] }, "execution_count": 2, "metadata": {}, "output_type": "execute_result" } ], "source": [ "eigvals(A)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Let's try just multipling it many times by a \"random\" vector and see whether it is converging to a steady state:" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2-element Array{Float64,1}:\n", " 14.0\n", " 7.0" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "A^100 * [17, 4]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Yes, it seems to be giving a vector that is not changing, which shoud be a multiple $c x_0$ of a steady-state eigenvector:" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2-element Array{Float64,1}:\n", " 14.0\n", " 7.0" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "cx₀ = A^1000 * [17, 4]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Let's check that this is an eigenvector of $A$ with eigenvalue $\\lambda=1$:" ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2-element Array{Float64,1}:\n", " 14.0\n", " 7.0" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "A * cx₀" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "To see why, the key idea is to write the columns-sum-to-one property of Markov matrices in linear-algebra terms. It is equivalent to the statement:\n", "\n", "$$\n", "\\underbrace{\\begin{pmatrix} 1 & 1 & \\cdots & 1 & 1 \\end{pmatrix}}_{o^T} A = o^T\n", "$$\n", "\n", "since this is just the operation that sums all of the rows of $A$. Equivalently, if we transpose both sides:\n", "\n", "$$\n", "A^T o = o\n", "$$\n", "\n", "i.e. $o$ is an eigenvector of $A^T$ (called a **left eigenvector of A**) with eigenvalue $\\lambda = 1$.\n", "\n", "But since $A$ and $A^T$ have the **same eigenvalues** (they have the same characteristic polynomial $\\det (A - \\lambda I) = \\det (A^T - \\lambda I)$ because transposed don't change determinants), this means that $A$ **also has an eigenvalue 1** but with a **different eigenvector**." ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "1×2 RowVector{Float64,Array{Float64,1}}:\n", " 1.0 1.0" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "o = [1,1]\n", "o' * A" ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2-element Array{Float64,1}:\n", " 1.0\n", " 1.0" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "A' * o" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The eigenvector of $A$ with eigenvalue $1$ must be a basis for $N(A - I)$:" ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2×2 Array{Float64,2}:\n", " -0.1 0.2\n", " 0.1 -0.2" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "A - 1*I" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "By inspection, $A - I$ is singular here: the second column is -2 times the first. So, $x_0 = (2,1)$ is a basis for its nullspace, and is the steady state:" ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2-element Array{Float64,1}:\n", " 5.55112e-17\n", " 5.55112e-17" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" } ], "source": [ "(A - I) * [2,1]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Let's check if some arbitrary starting vector $(3,0)$ tends towards the steady state:" ] }, { "cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [ { "data": { "text/html": [ "