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

$$\begin{array}{}\text{(1)}& \sum _{i=1}^n{P}_{ij}=1.\end{array}$$

---

$2\times 2$ Markov matrix - part 1

對於

$2\times 2$ 的 Markov matrix, 我們可以把他表示為

$$\begin{array}{}\text{(2)}& P=\left[\begin{array}{cc}a& b\\ 1-a& 1-b\end{array}\right],\end{array}$$
其中

$0\le a,b\le 1$.

Examples

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

---

對於 Markov matrix 我們最想知道的是在不斷的轉移之後, 會不會"收斂"到某個狀態去. 也就是我們想求

$$\underset{n\to \mathrm{\infty }}{lim}{P}^n\mathbf{x}.$$

Observation

第一件重要的事就是 Markov matrix 他的 column sum 等於

$1$. 因此,

$$\begin{array}{}\text{(7)}& \left[\begin{array}{cc}1& 1\end{array}\right]P=1\cdot \left[\begin{array}{cc}1& 1\end{array}\right].\end{array}$$

也就是說

$[1,1{]}^T$ 是 Markov matrix 的左 eigenvector, 並且 Markov matrix 的 eigenvalue 一定有一個是

$1$.

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

---

Left eigenvector

以下是對

$n\times n$ 方陣左 eigenvector 的定義以及一些性質.

Definition:
Let

$\mathbf{y}\in {\mathbb{R}}^n\setminus \{0\}$ satisfies

$$\begin{array}{}\text{(8)}& {\mathbf{y}}^{T}A=\lambda {\mathbf{y}}^T,\end{array}$$
then

$\mathbf{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\mathbf{y}=\lambda \mathbf{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

$\mathbf{v}\ne 0$ and

$\mathbf{w}\ne 0$ be the right and left eigenvector of

$A$ that corresponds to different eigenvalues, i.e.,

$$A\mathbf{v}={\lambda }_1\mathbf{v},{\mathbf{w}}^{T}A={\lambda }_2{\mathbf{w}}^T,{\lambda }_1\ne {\lambda }_2.$$
Then

${\mathbf{w}}^T\mathbf{v}=0$.

pf:

${\mathbf{w}}^{T}A\mathbf{v}={\mathbf{w}}^T(A\mathbf{v})={\lambda }_1{\mathbf{w}}^T\mathbf{v}$ and

${\mathbf{w}}^{T}A\mathbf{v}=({\mathbf{w}}^{T}A)\mathbf{v}={\lambda }_2{\mathbf{w}}^T\mathbf{v}$.

Therefore

$({\lambda }_1-{\lambda }_2){\mathbf{w}}^T\mathbf{v}=0$, and

${\mathbf{w}}^T\mathbf{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

$\mathbf{1}=[1,1,\cdots ,1{]}^T$.

pf: Using (1) we have

$\mathbf{1}P=\mathbf{1}=1\cdot \mathbf{1}$. Therefore,

$\mathbf{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 我們有

$$\begin{array}{}\text{(9)}& \left[\begin{array}{cc}1& 1\end{array}\right]\left[\begin{array}{c}{y}_1\\ y_2\end{array}\right]=0,\end{array}$$
也就是

$y_1+y_2=0$. 然後就知道這個 eigenvector 的 basis 一定是

$[1,-1{]}^T$.

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

$$\begin{array}{}\text{(10)}& P\left[\begin{array}{c}1\\ -1\end{array}\right]=\left[\begin{array}{c}a-b\\ b-a\end{array}\right]=(a-b)\left[\begin{array}{c}1\\ -1\end{array}\right].\end{array}$$

因此知道 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

${\mathbf{v}}_2=[1,-1{]}^T$.

First eigenvector

接著我們來試著將

$P$ 對角化. 先算一下

$\lambda =1$ 的 eigenvector:

$$P-1I=\left[\begin{array}{cc}a-1& b\\ 1-a& -b\end{array}\right].$$

因此可以很輕易看出 eigenvector 的 basis 是

$[b,1-a{]}^T$. 不過我們把它 normalize 一下, 使它是個機率 (元素和為

$1$):

$${\mathbf{v}}_1=\frac{1}{1+b-a}\left[\begin{array}{c}b\\ 1-a\end{array}\right].$$

Diagonalization

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

假設

$P\ne I$,

$$\begin{array}{}\text{(11)}& P\left[\begin{array}{cc}{\mathbf{v}}_1& {\mathbf{v}}_2\end{array}\right]=\left[\begin{array}{cc}{\mathbf{v}}_1& {\mathbf{v}}_2\end{array}\right]\left[\begin{array}{cc}1& 0\\ 0& a-b\end{array}\right].\end{array}$$

令

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

$$\begin{array}{}\text{(12)}& P=V\left[\begin{array}{cc}1& 0\\ 0& a-b\end{array}\right]V^{-1}.\end{array}$$

並且

$$\begin{array}{}\text{(13)}& P^n=V\left[\begin{array}{cc}1& 0\\ 0& (a-b{)}^n\end{array}\right]V^{-1}.\end{array}$$

---

接著我們再稍微整理一下, 算一下

$V^{-1}$

$$V^{-1}=\left[\begin{array}{cc}1& 1\\ \frac{1-a}{1+b-a}& \frac{-b}{1+b-a}\end{array}\right]=\left[\begin{array}{c}{\mathbf{w}}_1^T\\ {\mathbf{w}}_2^T\end{array}\right].$$

也就是我們得到了

${\mathbf{w}}_1$ 與

${\mathbf{w}}_2$ 分別是

$P$ 的兩個 left-eigenvectors. 而

${\mathbf{w}}_1$ 也如預料中是個元素全為

$1$ 的向量.

---

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

$$\begin{array}{}\text{(14)}& P={\mathbf{v}}_1{\mathbf{w}}_1^T+(a-b){\mathbf{v}}_2{\mathbf{w}}_2^T.\end{array}$$

以及

$$\begin{array}{}\text{(15)}& P^n={\mathbf{v}}_1{\mathbf{w}}_1^T+(a-b{)}^n{\mathbf{v}}_2{\mathbf{w}}_2^T.\end{array}$$

Steady state

最後我們就可以找出 Markov process 的 steady state 了. 假設

$a-b\ne \pm 1$ (也就是

$P$ 不是 identity matrix (3) 或 位置調換的矩陣 (5)), 並且假設

$\mathbf{x}$ 是個機率向量, 元素和為

$1$, 則有

$$\begin{array}{}\text{(16)}& \underset{n\to \mathrm{\infty }}{lim}{P}^n\mathbf{x}={\mathbf{v}}_1.\end{array}$$

這邊我們有利用到

$|a-b|<1$ 以及

$|a-b{|}^n\to 0$.

而如果對

$\mathbf{x}$ 沒有任何條件, 令

$\mathbf{x}=[x_1,x_2{]}^T$, 則有

$$\begin{array}{}\text{(17)}& \underset{n\to \mathrm{\infty }}{lim}{P}^n\mathbf{x}=(x_1+x_2){\mathbf{v}}_1.\end{array}$$

---

$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{\mathbf{v}}_1={\mathbf{v}}_1$ 並且

${\mathbf{v}}_1$ 的元素和為

$1$. 那我們有,

$$\begin{array}{}\text{(18)}& \underset{n\to \mathrm{\infty }}{lim}{P}^n\mathbf{x}={\mathbf{v}}_1.\end{array}$$

對任何元素和為

$1$ 的向量

$\mathbf{x}$ 都會成立.

因此

${\mathbf{v}}_1$ 就是 Markov process 的 Steady state.

所以任給一個 Markov matrix

$P$, 我們目標就是要找他的

${\mathbf{v}}_1$, 這樣就知道最終狀態長怎樣了. 而找

${\mathbf{v}}_1$ 這件事可以利用 power iteration. 再請自行參閱.

• Power method

不過簡單的說, 其實所謂的以 power iteration 找

${\mathbf{v}}_1$ 的作法我們已經在 (18) 說明完了. 就是先隨機生成一個向量

${\mathbf{x}}_0$, 然後再一直以

$P$ 來乘它.

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

然後過程中檢驗看看

${\mathbf{x}}_n$ 收斂了沒即可.

---