【参考资料: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≤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)]
马尔科夫链的概率分布
令πt未马尔可夫链在时刻t的状态分布
πt=P(Xt)=x.
t=0,就是初始的概率分布
马尔科夫链X的绝对分布由其初始分布和一步转移概率完全确定。
平稳分布
πP=π,π叫做马尔可夫链的平稳分布,πP2=πPP=πP=π
平稳分布的存在性与唯一性的讨论(马尔可夫链收敛定理)
Q1:是否每个马尔可夫链都具有一个稳态分布?(存在性)
Q2:该稳态分布是否唯一?(唯一性)
Q3:πn 是否总是趋向于稳态分布?(收敛性)
不可约+非周期=充要=平稳分布唯一存在
所有状态的周期都不为1,平稳分布也不存在。
不可约
强连通
非周期
所有状态的周期均为1。
一些定理
- 如果x和y是连通的,那么dx=dy
PageRank
PageRank通过计算网页的”重要程度”来对网页进行排序。
如何定义网页的级别/重要程度?
定义网页i的级别π(i)为一个正数,
π(i)=∑π(j)P(j,i),P(j,i)指我在状态j转移到i的的概率。
这里P(A,B)=12,
有一个方程:{πA=πCp(c,a)+πDp(d,a)pib=πap(a,b)+πDp(d,b)+πEp(e,b)\…,以此类推。
注意到,这里只有未知数πi,i∈(A,B,C,D,E)
设π=(πA,πB,πC,πD,πE),Pn×n=P(i,j)是一个以P(i,j)为元素的方针。
这个方程很牛逼,我们叫它平衡方程。
这里我们注意到,如果一个向量 π 是这个方程的解,那么 π 的任意倍数也是这个方程的解.为方便起见,我们将解归一化,使得所有网页的级别之和为1:∑π(i)=1。
我们怎么在PageRank中引入马尔可夫链模型的?
想象一下你正在浏览网页:假设你在网页 i 上浏览了一个单位时间,然后随机点击进入了网页 i 指向的一个网页.在这个过程中,从网页 i 到网页 j 的概率正好为P(i, j ),与前面的例子相同.