markov chain是markov process的基础。当然，对markov chain的了解是markov process的基础。
好多概念- -
markov chain
markov chain的核心都是围绕那个概率矩阵展开的。和arrival process不同的是，markov process中很多东西无法直接映射到现实，所以会有很多概念出现。
首先最重要的就是markov chain的定义了。概念的核心就一个式子：
$Pr\left\{X_n=j|X_{n-1}=i,X_{n-2}=k,...,X_0=m\right\} = Pr\left\{X_n=j|X_{n-1}=i\right\}$
举一个简单的例子吧。一个醉汉在一条直线上晃悠(别问我问啥醉汉可以在直线上晃悠)。他当前的运动方向只取决于上一时间点的运动方向。这种假设在nlp中经常出现。
在markov中，一般将 $P\left\{X_n=j|X_{n-1}=i\right\}=P_{ij}$
我们可以将markov chain表示为图的形式：
state 的分类
recurrent state : 对于一个state i, 任何i可以访问的state j都可以访问state i。注意是i可访问的而不是可访问i的。
例如在上图中2是一个recurrent state，1就不是。
与recurrent对应的叫做transient state
Class:class 就是一个state的set，在这个set里面每个statee都可以相互访问。可以证明，一个class里面所有的state都是一种，要么recurrent，要么transient
现在我们引入period的概念。对于一个state i来说，period就是能再次访问到自己所花费的步数。如果period=1，则称该state为aperiodic；如果periodic大于等于2，则称为periodic
一个 recurrent 和 aperiodic class被称为 ergodic class；完全由一个ergodic class组成的markov chain被称为ergodic chain。
可以证明，对于一个ergodic M state markov chain，$P_{ij}^m>0\quad \text{for all i, j and } m\ge(M-1)^2+1$ ，其中 $P_{ij}^m$ 表示经过m步从i到j的概率。
证明：
之前证明过两个互质整数 $a,b$ 所不能表示数字的最大范围 $ab-a-b$ 。
如果我们保持 $a$ 不变，会发现这个数字随 $b$ 的增加而增加。对于一个有M个状态的ergodic markov chain，根据前面的结果，最坏的情况就是两环的长度为M和M-1了。则第k个节点可以被访问到的周期为 $Ma+(M-1)b\quad a\ge 1,b>0$ 而M,M-1互质，所以这两个数字所不能表示的最大数字为 $M(M-1)-M-(M-1)+M = (M-1)^2$
矩阵表示
根据定义，我们可以发现：
$P_{ij}^2 = \sum_{k=1}^M P_{ik}P_{kj}$
这和矩阵的乘法一模一样。所以我们可以用矩阵 $P$ 来表示概率，$P^n$ 可以直接得到概率。
steady state
$P$ 只是表征了节点间转移的概率， 我们用 $\pi_j$ 表示在第j个时间点处于各个state的概率，则：$\pi_{j+1} = \pi_j P$
当存在 $\pi$ 使得 $\pi = \pi P$ 时，我们称 $\pi$ 为 steady-state vector。这只是一个线性方程，只要存在解，解出来并不是很复杂。所以问题来了，什么时候才有解呢？
为了解决这个问题，我们引入unichain的概念。简单来说，unichain就是只有一个recurrent class，但是可能包含多个transient class的markov chain。如果recurrent class 是ergodic，则称为ergodic unichain
下面将证明，只有ergodic chain才有steady-state vector.
易知：
$\max_i P_{ij}^{n+1} = \sum_kP_{ik}P_{kj}^n\le \sum_kP_{ik}\max_l P_{lj}^{n} = \max_l P_{lj}^{n}\\ \min_i P_{ij}^{n+1} = \sum_kP_{ik}P_{kj}^n\ge \sum_kP_{ik}\min_l P_{lj}^{n} = \min_l P_{lj}^{n}$
令 $\alpha = \min_{i,j}P_{ij}$。则有：
$$\begin{aligned}
P_{ij}^{n+1} &= \sum_kP_{ik}P_{kj}^n\\
&\le \sum_{k\neq l_{min}}P_{ik}\max_lP_{lj}^n + P_{il_{min}}\min_lP_{lj}^n\\
& = \max_l P_{lj}^n-P_{il_{min}}(\max_l P_{lj}^n-\min_l P_{lj}^n)\\
&\le\max_l P_{lj}^n-\alpha(\max_l P_{lj}^n-\min_l P_{lj}^n)
\end{aligned}$$
同理，可以推出 $P_{ij}^{n+1} \ge \min_l P_{lj}^n+\alpha(\max_l P_{lj}^n-\min_l P_{lj}^n)$
注意到：
$\max_i P_{ij} \le 1-\alpha \quad \min_i P_{ij} \ge \alpha$
所以有：
$\max_i P_{ij}^{n+1} - \min_i P_{ij}^{n+1} \le (1-2\alpha)(\max_l P_{lj}^n-\min_l P_{lj}^n)\\ \le ...\le (1-2\alpha)^{n}(\max_l P_{lj}-\min_l P_{lj})=(1-2\alpha)^{n+1}$
故 $\lim_{n\to\infty}\max_i P_{ij}^{n} = \lim_{n\to\infty}\min_i P_{ij}^{n}$
令 $h=(M-1)^2-1$ ，由前面的描述可知，当markov chain 为 ergodic 时， 对于任何 $h'>h$ ，均有 $P_{ij}^{h'} >0$ 成立。对于 $v\ge1$ ，
$\lim_{v\to\infty}\max_iP_{ij}^{h(v+1)}=\lim_{v\to\infty}\min_iP_{ij}^{h(v+1)}$
所以有：
$\lim_{n\to\infty}\max_iP_{ij}^{n}=\lim_{n\to\infty}\min_iP_{ij}^{n}$
现给定向量 $u，u_j = \lim_{n\to\infty}\max_mP^n_{mj}= \lim_{n\to\infty}\min_mP^n_{mj}$
故 $u_j = \lim_{n\to\infty}\max_mP^n$
故 $\lim[P^n] = eu\quad \text{where} e = {(1,1,...,1)}^T$
我们假设 $\pi$ 为前面说的steady-state vector，则
$\pi = \pi\lim_{n\to\infty}[P^n] = \pi eu = u$
故 $u$ 为我们所求的steady-state vector
ergodic unichain
对于ergodic unichain来说，上面的结论仍然成立，但是细节方面会有一些改变。
我们将一个矩阵 $P$ 分成4块： $[P] = \begin{bmatrix}[P_T] & [P_{TR}]\\ [0] & [P_R]\end{bmatrix}$
其中 $P_T$ 中的state均为transient state, $P_R$ 中的state均为recurrent state。由于所有transient state最后都会变成recurrent state，所以 $P_T, P_{TR}$ 最后均为0。对于 recurrent state，我们令 $\gamma = \max_{i\in T}\sum_{j \in T} P_{ij}^t < 1$
下面证明：
$\max_{l\in T}P_{ij}^n < \gamma^{\lfloor n/t\rfloor}$
不断向前推，我们就可以得到
$\max_{l \in T} \sum_{j\in T} P_{lj}^{vt} \le \gamma^v$
我们可以证明 $P_R$ 会收敛
$$\begin{aligned}
|P^n_{ij} - \pi_j| &= |\sum_{k \in T}P^m_{ik}P^{n-m}_{kj} + \sum_{k \in R}P^m_{ik}P^{n-m}_{kj} - \pi_j|\\
&=|\sum_{k \in T}P^m_{ik}(P^{n-m}_{kj} - \pi_j) + \sum_{k \in R}P^m_{ik}(P^{n-m}_{kj} - \pi_j)|\\
&\le\sum_{k \in T}P^m_{ik}|P^{n-m}_{kj} - \pi_j| + \sum_{k \in R}P^m_{ik}|P^{n-m}_{kj} - \pi_j|\\
&\le\sum_{k \in T}P^m_{ik} + \sum_{k \in R}P^m_{ik}|P^{n-m}_{kj} - \pi_j|\\
&\le \gamma^{\lfloor m/t\rfloor} + (1-2\beta)^{\lfloor (n-m)/h\rfloor}
\end{aligned}$$
特征值和特征向量
markov chain的所有特征值的绝对值均不大于1.
证明：
令 $\lambda_l$ 为第l个特征根， $\pi_i^l$ 为对应特征向量的第 $i$ 个元素，则：
$$\lambda_j^n \pi_j^l = \sum_i\pi_i^lP_{ij}^n\\
|\lambda_j^n| |\pi_j^l| \le \sum_i|\pi_i^l|P_{ij}^n$$
令 $\beta = \max_i|\pi_i^l|$ ，则：
$|\lambda_j^n| \beta \le \sum_i\beta P_{ij}^n \le \beta M$
对任意n都成立，故 $|\lambda_j|\le1$
当存在k个重复的特征值时，一般存在2种情况：
- markov chain中recurrent class的period为k
- markov chain中存在k个recurrent class
markov chain with reward
在原有的markov chain 中，我们到达state j是没有任何reward的，感觉这种东西直接建模现实世界还是太简单，就加了一个reward。
比如first-passage time，用来表示第一次到达state i所花步数的期望。
我们用 $v_i$ 表示从state i到state 1的期望步数，则：
$$\begin{aligned}
v_2 &= 1+ P_{23}v_3+P_{24}v_4\\
v_3 &= 1+ P_{32}v_2+P_{33}v_3+P_{34}v_4\\
v_4 &= 1+ P_{42}v_2+P_{43}v_3
\end{aligned}$$
可以总结为 $v_i = 1 + \sum_{j\neq1}p_{ij}v_j$
如果我们令 $v_1 = 0$ ，则上式可以抽象为$v=r+Pv$
看完例子之后，我们回到普遍的情况。令 $X_m$ 为m时刻所处的state， $R_m=R(X_m)$ 表示在state m时的reward，则
$$\begin{aligned}
v_i(n) &= E[R(X_m)+R(X_{m+1})+...+R(X_{m+n-1})|X_m=i]\\
&=r_i+\sum_jP_{ij}r_j+...+\sum_jP_{ij}^{n-1}r_j
\end{aligned}$$
以矩阵形式表示就是：$v(n)=r+Pr+...+P^{n-1}r_j$
如果令 $P^0=I$ ，则 $v(n)=\sum_{h=0}^{n-1}P^hr$ 。因为 $\lim_{n\to\infty}P^nr=e\pi r$ ，当$g=\pi r \neq 0$ 时， $v(n)$ 就不会收敛。但是 $v(n)-nge = \sum_{h=0}^{n-1}(P^h-e\pi)r$ 是是显然收敛的。我们称收敛的结果为relative-gain vector，记做 $w$ 。也就是说， $w=\lim_{n\to\infty}\sum_{h=0}^{n-1}(P^n-e\pi)r=\lim_{n\to\infty}v(n)-nge$
对于一个ergodic unichain，很容易证明 $w$ 满足下面的等式：
$w+ge = Pw+r \quad \pi w = 0$
而对于unichain来说，上式有唯一解。
additional final reward
这么整数学家还是觉得不爽，你到终点了结束了再给你来一发好了。这就是additional final reward。用公式表示就是这样的：
$v(n,u) = r+Pr+...+P^{n-1}r + P^nu=\sum_{h=0}^{n-1}P^hr + P^nu$
对于 unichain 来说，有下式成立：
$v(n,u) = nge + w +P^n(u-w)$
证明居然是用数学归纳法证明的Σ( ° △ °|||)︴所以自己证下就好了。。。。。