Introduction to Markov chain

## 什么是Markov chain？

### 定义

$$P(X_{n+m} = j\space| X_{n} = i, X_{n-1} = i_{n-1},…X_{1} = i_{1} ) = P(X_{n+m} = j\space| X_{n} = i)$$
$m = 1$ 时等式成立，则随机变量序列 $X_n$ 是一个马尔可夫链, $X_i$ 的可能值构成的可数集称为该链的状态空间（state space）

### 定义的推论

$$\sum P(A|B\cap C_i)\times P(C_i|B)=\sum \frac{P(A\cap B\cap C_i)}{P(B\cap C_i)}\times P(C_i|B)= \sum \frac{P(A\cap B\cap C_i)}{P(B)P(C_i|B)}\times P(C_i|B) \\= \sum \frac{P(A\cap B\cap C_i)}{P(B)} = \frac{\sum P(A\cap B \cap C_i)}{P(B)} = \frac{P(A\cap B)}{P(B)}= P(A|B)$$

$$P(X_{n+m+1} = k\space|X_n = i, X_{n-1} = i_{n-1},…X_1 = i_1 )\\=\sum_{k’ \in S}P(X_{n+m+1} = k\space|X_{n+m}=k’,X_n = i, X_{n-1} = i_{n-1},…X_1 = i_1)\\ \times P(X_{n+m}=k’\space|X_n = i, X_{n-1} = i_{n-1},…X_1 = i_1)$$

$$P(X_{n+m+1} = k\space| X_{n+m} = k’, X_{n+m-1} = i_{n+m-1},…X_1 = i_1 )\\=P(X_{n+m+1} = k\space| X_{n+m} = k’)\\=P(X_{n+m+1} = k\space| X_{n+m} = k,X_{n} = i_{n})$$

$P(X_{n+m}=k’\space|X_n = i, X_{n-1} = i_{n-1},…X_1 = i_1) = P(X_{n+m} = k’\space|X_n=i_n)$

$$P(X_{n+m+1} = k\space| X_{n+m} = k’, X_{n+m-1} = i_{n+m-1},…X_1 = i_1 )\\ =\sum_{k’\in S} P(X_{n+m+1} = k\space| X_{n+m} = k’,X_{n} = i_{n}) \times P(X_{n+m} = k’\space|X_n=i_n)$$

$$P(A|B\cap C) \times P(B|C) = \frac{P(A\cap B\cap C)}{P(B\cap C)}\times \frac{P(B\cap C)}{P(C)} = \frac{P(A\cap B\cap C)}{P(C)} = P(A\cap B|C)$$

$$P(X_{n+m+1} = k\space| X_{n+m} = k’, X_{n+m-1} = i_{n+m-1},…X_1 = i_1 )\\ =\sum_{k’\in S} P(X_{n+m+1} = k\space| X_{n+m} = k’,X_{n} = i_{n}) \times P(X_{n+m} = k’\space|X_n=i_n) \\ =\sum_{k’\in S} P(X_{n+m+1} = k,X_{n+m} = k’\space|X_{n} = i_{n})\\= P(X_{n+m+1} = k\space|X_n=i_n)$$

## 概率转移矩阵

### 开普曼-柯尔莫哥洛夫公式

$$P(X_{n+m} = j\space | X_{n} = i) = P(X_{n+m+k} = j\space | X_{n+k} = i)$$

$P(m)$ 是以 $m$ 步转移概率$P_{ij}(m)$为元素的矩阵（即 $(P(m))_{ij} = P_{ij}(m)$，也称为该链的 $m$ 步转移矩阵。通常记 $P(1)$ 为 $P$。

• $\forall i,j\in S, 0 < P_{ij}(m) < 1$ .

• $\displaystyle{\forall i, \sum_{j\in S} P_{ij}(m) = 1}$ 换句话说， $P(m)$ 的每一行都是在 $S$ 上的一个概率分布。

• $P(0)$ 是一个单位矩阵。

$\forall m,n, P(m+n) = P(m)P(n)\\$ 亦即，$\forall m,n, P_{ij}(m+n) = \displaystyle{\sum_{k\in S}P_{ik}(m)P_{kj}(n)}$

$$\displaystyle{P_{ij}(m+n) = P(X_{m+n+1} = j \space| X_1 = i)\\ = \sum_{k\in S}P(X_{m+n+1} = j |X_{m+1} = k, X_1 = i)\times P(X_{m+1} = k\space|X_1 = i)\\=\sum_{k\in S}P_{ik}(m)P_{kj}(n)}$$

### 极限概率分布

#### 线性代数的角度

1. 所有元素均为非负数。
2. 每行元素和为 $1$。

1. $P$ 的任意一个特征值 $\lambda$ 满足 $|\lambda| <= 1$。
2. $P$ 有特征值 $1$， 且非重根。

1. 令 $\lambda$ 对应的特征向量 $x = (x_1, x_2,...x_n)^T$, 设 $x_i = max\{x_1,x_2...,x_n\}$。

由于 $Px = \lambda x$, $(Px)_{i} = \displaystyle{\sum_{j=1}^n a_{ij}x_{j}} = \lambda x_i$

两边同时取绝对值，有 $|\lambda| |x_i| = |\displaystyle{\sum_{j=1}^n a_{ij}x_{j}}|\\\leqslant \displaystyle{\sum_{j=1}^n a_{ij}|x_{j}}| \leqslant \displaystyle{(\sum_{j=1}^n a_{ij})|x_i| = x_i}$

因此 $\lambda \leqslant 1$。

2. 很容易发现 $1$ 是一个特征值，我们只需要取 $x = (1,1,..1)^T$，就可以很容易地发现 $Px = x$。

因此我们需要证明的是 $1$ 不是重根。

采用反证法

我们已经知道 $1$ 是一个特征值，如果他是重根的话，那么 $det(P-\lambda I)$ 中至少有两个 $(1-\lambda)$ 的因子。

对于 $det(P-\lambda I)$ ， 我们把每一列的数字累加到第 $n$ 列，可使第 $n$ 列全为 $(1-\lambda)$，这里我们可以提出第一个因子。这时行列式最右一列均为 $1$， 一个很自然的想法是，前 $n -1$ 行减去第 $n$ 行：这样第 $n$ 列就只有一个非零元了。按第 $n$ 列展开，我们得到 $det(P-\lambda I) = (1-\lambda) det(Q-\lambda I’)$。其中$Q$ 为 $n-1$ 阶方阵，且$Q_{ij} = a_{ij} - a_{nj}$；$I’$ 是 $n-1$ 阶单位矩阵。这是很容易验证的。

这时候 $Q$ 必有特征值 $1$.

接下来我们考虑 $Q$ 关于 $1$ 的行特征向量（注意是行特征向量，即 $Q^T$ 的列特征向量）$\beta = (\beta_1,\beta_2,..\beta_{n-1})$。

我们有 $$(\beta Q)_j = \displaystyle{\sum_{i=1}^{n-1}\beta_i(a_{ij}-a_{nj})=\beta_j}$$

接下来讨论 $\beta$ 中元素的正负性。设有 $p$ 个正元素（分别为 $\beta_{s_1},\beta_{s_2},..\beta_{s_p}$）; $q$ 个非正元素（分别为$\beta_{t_1},\beta_{t_2},..\beta_{t_q}$）。另外我们不妨设$\rho = |\beta|\geqslant 0$；因为如果小于 $0$， 我们可以取 $-\beta$ 作为我们讨论的对象。

这样，对 $\beta$ 中的正元素，我们可以将上面的式子改写为：

$$\displaystyle{\sum_{i=1}^{n-1}\beta_ia_{it_k}-\rho a_{nt_k}=\beta_{t_k}}\space\space (k = 1,2,...p)$$ 累加，得到： $$\displaystyle{\sum_{i=1}^{n-1}\beta_i(\sum_{k = 1}^{p}a_{it_k})-\rho( \sum_{k=1}^{p}a_{nt_k})=\sum_{k=1}^p\beta_{t_k}}$$

为了简化式子，不妨令 $d_i = \displaystyle{\sum_{k=1}^{p}a_{it_k} < \sum_{i=1}^{n}a_i = 1}$ ：

$$\displaystyle{\sum_{i=1}^{n-1}\beta_id_i-\rho d_n=\sum_{k=1}^p\beta_{t_k}}$$ $$\displaystyle{\sum_{k=1}^{p}\beta_{s_k}d_{s_k} + \sum_{k=1}^{q}\beta_{t_k}d_{t_k}-\rho d_n=\sum_{k=1}^p\beta_{t_k}}$$ $$\displaystyle{\sum_{k=1}^{q}\beta_{t_k}d_{t_k}-\rho d_n=\sum_{k=1}^p\beta_{t_k} - \sum_{k=1}^{p}\beta_{s_k}d_{s_k} > 0}$$

而等式左边显然是负数，矛盾。这说明 $Q$ 没有特征值 $1$， 也就是说 $P$ 的特征值 $1$ 无重根。

—— 是的， $L$ 的每一行都相同，均为 $P$ 关于 $1$ 的行特征向量。

#### 极限何时存在？

【 最近事务繁多，更新无限期推迟】

This blog is under a CC BY-NC-SA 3.0 Unported License