---
title: Markov matrix
tags: Linear algebra
GA: G-77TT93X4N1
---

# Markov matrix

> Markov matrix, 又稱為轉移矩陣, 是用來描述 Markov chain 的轉變的矩陣.
>
> 矩陣裡每一個元素都代表機率, 因此是個介於 $0$ 與 $1$ 之間的實數, 並且 column sum 等於 $1$.

---

## General $n\times n$ Markov matrix

Let $P\in M_{n\times n}$ be a Markov matrix, then $0\le P_{ij} \le 1$ and $$\tag{1}
\sum^n_{i=1} P_{ij} = 1.
$$

---

## $2\times 2$ Markov matrix - part 1

對於 $2\times 2$ 的 Markov matrix, 我們可以把他表示為
$$\tag{2}
P = \begin{bmatrix}
a & b \\ 1-a & 1-b
\end{bmatrix},
$$
其中 $0\le a, b\le 1$.

### Examples

* $(a, b) = (1, 0)$, 那 $P$ 就變成 identity matrix,
$$\tag{3}
P = \begin{bmatrix}
1 & 0 \\ 0 & 1
\end{bmatrix}.
$$
* (3) 這個矩陣的 eigenvalues 是兩個 $1$, eigenvector 的 basis 則是 $(1, 0)^T$ 以及 $(0, 1)^T$.
* 此外, $P{\bf x}={\bf x}$, 所以這個轉移矩陣完全沒有做任何事, 轉移完後還是同樣的狀態.
* $(a, b) = (1, 1)$,
$$\tag{4}
P = \begin{bmatrix}
1 & 1 \\ 0 & 0
\end{bmatrix}.
$$
* (4) 這個矩陣的 eigenvalues 是 $1$ 與 $0$, 相對應的 eigenvector 的 basis 則是 $(1, 0)^T$ 以及 $(1, -1)^T$.
* 如果初始狀態是個機率, ${\bf x} = [x_1, x_2]^T$ 並且 $x_1+x_2=1$, 則
$$
P \begin{bmatrix}
x_1 \\ x_2
\end{bmatrix} = \begin{bmatrix}
x_1 + x_2 \\ 0
\end{bmatrix} = \begin{bmatrix}
1 \\ 0
\end{bmatrix}.
$$
也就是說這個轉移矩陣是把所有狀態堆到第一個元素去.
* $(a, b) = (0, 0)$. 基本上同 $(a, b) = (1, 1)$, 不過這個轉移矩陣是把所有狀態堆到第二個元素去
* $(a, b) = (0, 1)$,
$$\tag{5}
P = \begin{bmatrix}
0 & 1 \\ 1 & 0
\end{bmatrix}.
$$
* (5) 這個矩陣的 eigenvalues 是 $1$ 與 $-1$, 相對應的 eigenvector 的 basis 則是 $(1, 1)^T$ 以及 $(1, -1)^T$.
* 如果初始狀態是 ${\bf x} = [x_1, x_2]^T$, 則
$$
\tag{6}
P \begin{bmatrix}
x_1 \\ x_2
\end{bmatrix} = \begin{bmatrix}
x_2 \\ x_1
\end{bmatrix}.
$$
也就是說這個轉移矩陣是把兩個狀態對調.

---

對於 Markov matrix 我們最想知道的是在不斷的轉移之後, 會不會"收斂"到某個狀態去. 也就是我們想求
$$
\lim_{n\to\infty} P^n {\bf x}.
$$

### Observation

第一件重要的事就是 Markov matrix 他的 column sum 等於 $1$. 因此,

$$
\tag{7}
\begin{bmatrix}
1 & 1
\end{bmatrix}P = 1\cdot \begin{bmatrix}
1 & 1
\end{bmatrix}.
$$

也就是說 $[1, 1]^T$ 是 Markov matrix 的左 eigenvector, 並且 Markov matrix 的 eigenvalue 一定有一個是 $1$.

接著我們看一下左 eigenvector 以及其相關性質.

---

## Left eigenvector
> 以下是對 $n\times n$ 方陣左 eigenvector 的定義以及一些性質.

**Definition:**
Let ${\bf y}\in\mathbb{R}^n\setminus\{0\}$ satisfies
$$
\tag{8}
{\bf y}^TA = \lambda {\bf y}^T,
$$
then ${\bf y}$ is called the *left* eigenvector of $A$ that corresponds to the eigenvalue $\lambda$.

**Remark:**
Taking tranpose to each side of (8) we have $A^T{\bf y} = \lambda {\bf y}$. So the left eigenvector is also the eigenvector of $A^T$.

**Lemma 1:** $A$ and $A^T$ share exactly the same eigenvalues.
> pf: $\text{det}(A - \lambda I) = \text{det}(A^T - \lambda I)$. So the roots are exactly the same.

**Lemma 2:** Let ${\bf v}\ne 0$ and ${\bf w}\ne 0$ be the right and left eigenvector of $A$ that corresponds to *different* eigenvalues, i.e.,
$$
A{\bf v} = \lambda_1 {\bf v}, \quad {\bf w}^TA = \lambda_2 {\bf w}^T, \quad \lambda_1\ne \lambda_2.
$$
Then ${\bf w}^T {\bf v} = 0$.
> pf: ${\bf w}^TA{\bf v} = {\bf w}^T(A{\bf v}) = \lambda_1 {\bf w}^T{\bf v}$ and ${\bf w}^TA{\bf v} = ({\bf w}^TA){\bf v} = \lambda_2 {\bf w}^T{\bf v}$.
>
> Therefore $(\lambda_1-\lambda_2){\bf w}^T{\bf v}=0$, and ${\bf w}^T{\bf v}=0$ due to $\lambda_1\ne \lambda_2$.

---

因此, 對一般 $n\times n$ 的 Markov matrix, 我們也知道它一定有一個 eigenvalue 是 $1$.

**Lemma 3:** An $n\times n$ Markov matrix has an eigenvalue $1$ and corresponding *left* eigenvector ${\bf 1} = [1, 1, \cdots, 1]^T$.
> pf: Using (1) we have ${\bf 1} P= {\bf 1} = 1\cdot {\bf 1}$. Therefore, ${\bf 1}$ is the left eigenvector corresponds to eigenvalue $1$, and Markov matrix has an eigenvalue $1$.

---

## $2\times 2$ Markov matrix - part 2

利用 Lemma 2 我們可以推論一件*有一點點*神奇的事. 我們已經知道 (2) 的這個 $P$ 矩陣他一定有個 eigenvalue 是 $1$. 那假設他另一個 eigenvalue 不是 $1$, 並且假設這個對應的 eigenvector 叫做 $[y_1, y_2]^T$, 那根據 Lemma 2 我們有

$$
\tag{9}
\begin{bmatrix} 1 & 1 \end{bmatrix}\begin{bmatrix} y_1 \\ y_2 \end{bmatrix}=0,
$$
也就是 $y_1+y_2=0$. 然後就知道這個 eigenvector 的 basis 一定是 $[1, -1]^T$.

然後我們再反過來算一下它的 eigenvalue

$$
\tag{10}
P \begin{bmatrix} 1 \\ -1 \end{bmatrix} = \begin{bmatrix} a-b \\ b-a \end{bmatrix} = (a-b) \begin{bmatrix} 1 \\ -1 \end{bmatrix}.
$$

因此知道 eigenvalue 是 $a-b$, eigenvector 是 $[1, -1]^T$.

那這個推論的原始假設是"第二個 eigenvalue 不是 $1$". 因此只有 $a-b=1$ 的時候推論才會錯. 而由於 $0\le a,b\le 1$, 可以發現只有在 $(a, b)=(1, 0)$ 的時候才會有 $a-b=1$. 也就是 $P$ 是 identity matrix.

**Lemma 4:** Let $P$ be a $2\times 2$ Markov matrix, written as (2). Assume $P$ is not an identity matrix, then it has eigenvalue $\lambda_2 = (a-b)$ with corresponding eigenvector ${\bf v}_2 = [1, -1]^T$.

### First eigenvector

接著我們來試著將 $P$ 對角化. 先算一下 $\lambda=1$ 的 eigenvector:

$$
P - 1 I = \begin{bmatrix}
a-1 & b \\ 1-a & -b
\end{bmatrix}.
$$

因此可以很輕易看出 eigenvector 的 basis 是 $[b, 1-a]^T$. 不過我們把它 normalize 一下, 使它是個機率 (元素和為 $1$):

$$
{\bf v}_1 = \frac{1}{1+b-a}\begin{bmatrix}
b \\ 1-a
\end{bmatrix}.
$$

### Diagonalization

有了所有的 eigenvalue 跟 eigenvector 我們就可以將矩陣對角化.

假設 $P\ne I$,

$$
\tag{11}
P \begin{bmatrix}
{\bf v}_1 & {\bf v}_2
\end{bmatrix} = \begin{bmatrix}
{\bf v}_1 & {\bf v}_2
\end{bmatrix}\begin{bmatrix}
1 & 0 \\ 0 & a-b
\end{bmatrix}.
$$

令 $V = [{\bf v}_1, {\bf v}_2]$, 那我們就有

$$
\tag{12}
P = V \begin{bmatrix}
1 & 0 \\ 0 & a-b
\end{bmatrix} V^{-1}.
$$

並且

$$
\tag{13}
P^n = V \begin{bmatrix}
1 & 0 \\ 0 & (a-b)^n
\end{bmatrix} V^{-1}.
$$

---

接著我們再稍微整理一下, 算一下 $V^{-1}$

$$
V^{-1} = \begin{bmatrix}
1 & 1 \\ \frac{1-a}{1+b-a} & \frac{-b}{1+b-a}
\end{bmatrix} = \begin{bmatrix}
{\bf w}^T_1 \\ {\bf w}^T_2
\end{bmatrix}.
$$

也就是我們得到了 ${\bf w}_1$ 與 ${\bf w}_2$ 分別是 $P$ 的兩個 left-eigenvectors. 而 ${\bf w}_1$ 也如預料中是個元素全為 $1$ 的向量.

---

因此對角化 (12) 可以改寫為

$$
\tag{14}
P = {\bf v}_1 {\bf w}_1^T + (a-b) {\bf v}_2{\bf w}^T_2.
$$

以及

$$
\tag{15}
P^n = {\bf v}_1 {\bf w}_1^T + (a-b)^n {\bf v}_2{\bf w}^T_2.
$$

### Steady state

最後我們就可以找出 Markov process 的 steady state 了. 假設 $a-b\ne \pm 1$ (也就是 $P$ 不是 identity matrix (3) 或 位置調換的矩陣 (5)), 並且假設 ${\bf x}$ 是個機率向量, 元素和為 $1$, 則有

$$
\tag{16}
\lim_{n\to \infty} P^n{\bf x} = {\bf v}_1.
$$

這邊我們有利用到 $|a-b|<1$ 以及 $|a-b|^n\to 0$.

而如果對 ${\bf x}$ 沒有任何條件, 令 ${\bf x} = [x_1, x_2]^T$, 則有

$$
\tag{17}
\lim_{n\to \infty} P^n{\bf x} = (x_1 + x_2){\bf v}_1.
$$

---

## $n\times n$ Markov matrix

對於一般的 Markov matrix $P$ 我們也有類似的結果.
> Markov matrix 的條件為元素介於 $0$ 跟 $1$ 之間以及 column sum 為 $1$.

根據 Lemma 3 我們知道 $P$ 有一個 eigenvalue 是 $1$. 我們做以下兩個假設

1. $\text{dim}(\text{Null}\{P - I\}) = 1$. 也就是 $\lambda=1$ 的 eigenvector 是個一維的子空間.
2. $-1$ 不是 $P$ 的 eigenvalue.

那麼, 假設 $P{\bf v}_1 = {\bf v}_1$ 並且 ${\bf v}_1$ 的元素和為 $1$. 那我們有,

$$
\tag{18}
\lim_{n\to \infty} P^n{\bf x} = {\bf v}_1.
$$

對任何元素和為 $1$ 的向量 ${\bf x}$ 都會成立.

因此 ${\bf v}_1$ 就是 Markov process 的 Steady state.

所以任給一個 Markov matrix $P$, 我們目標就是要找他的 ${\bf v}_1$, 這樣就知道最終狀態長怎樣了. 而找 ${\bf v}_1$ 這件事可以利用 power iteration. 再請自行參閱.

* [Power method](https://teshenglin.github.io/post/2023_power_method_1/)

不過簡單的說, 其實所謂的以 power iteration 找 ${\bf v}_1$ 的作法我們已經在 (18) 說明完了. 就是先隨機生成一個向量 ${\bf x}_0$, 然後再一直以 $P$ 來乘它.

$$
{\bf x}_n = P {\bf x}_{n-1}, \quad n\ge 1.
$$

然後過程中檢驗看看 ${\bf x}_n$ 收斂了沒即可.

---