【参考资料：https://www.ituring.com.cn/book/tupubarticle/7121
#马尔科夫链
注意从时间(time)和空间(which state)的两个维度理解马尔可夫链。
Markov property
当一个随机过程在给定现在状态及所有过去状态情况下，未来与过去无关。
Mathematically
如果$X(t),t>0$为一个随机过程，则：
$Pr[X(t+h)=y｜X(s)=x(s),s\le t]=Pr[X(t+h)=y|X(t)=x(t)]$
Markov process
A random process which has Markov property is called Markov process
时齐
Mathematically
如果$X(t),t>0$为一个随机过程，则：
$Pr[X(t+h)=y｜X(t)=x(t)]=Pr[X(h)=y|X(0)=x(0)]$
马尔科夫链的概率分布
令$\pi^t$未马尔可夫链在时刻t的状态分布
$\pi^t=P(X_t)=x$.
$t=0$，就是初始的概率分布
马尔科夫链X的绝对分布由其初始分布和一步转移概率完全确定。
平稳分布
$\pi P=\pi,\pi$叫做马尔可夫链的平稳分布，$\pi P^2=\pi PP=\pi P=\pi $
平稳分布的存在性与唯一性的讨论(马尔可夫链收敛定理)
Q1：是否每个马尔可夫链都具有一个稳态分布？(存在性)
Q2：该稳态分布是否唯一？(唯一性)
Q3：πn 是否总是趋向于稳态分布？(收敛性)
不可约+非周期=充要=平稳分布唯一存在
所有状态的周期都不为1，平稳分布也不存在。
不可约
强连通
非周期
所有状态的周期均为1。
一些定理
- 如果x和y是连通的，那么$d_x=d_y$
PageRank
PageRank通过计算网页的”重要程度”来对网页进行排序。
如何定义网页的级别/重要程度?
定义网页$i$的级别$\pi(i)$为一个正数，
$\pi(i)=\sum \pi(j)P(j,i) $,$P(j,i)$指我在状态j转移到i的的概率。
这里$P(A,B)=\frac{1}{2}$,
有一个方程：$\begin{cases}\pi_A=\pi_Cp(c,a)+\pi_Dp(d,a)\\pi_b=\pi_ap(a,b)+\pi_Dp(d,b)+\pi_Ep(e,b)\…\end{cases}$，以此类推。
注意到，这里只有未知数$\pi_i,i\in(A,B,C,D,E)$
设$\pi=(\pi_A,\pi_B,\pi_C,\pi_D,\pi_E)$,$P_{n\times n}=P(i,j)$是一个以$P(i,j)$为元素的方针。
这个方程很牛逼，我们叫它平衡方程。
这里我们注意到，如果一个向量 π 是这个方程的解，那么 π 的任意倍数也是这个方程的解．为方便起见，我们将解归一化，使得所有网页的级别之和为1：$\sum \pi(i)=1$。
我们怎么在PageRank中引入马尔可夫链模型的?
想象一下你正在浏览网页：假设你在网页 i 上浏览了一个单位时间，然后随机点击进入了网页 i 指向的一个网页．在这个过程中，从网页 i 到网页 j 的概率正好为P(i, j )，与前面的例子相同．
