马尔可夫算法

随机过程

研究随机现象变化过程的概率规律性的学科。

定义1：
设{ξt，t∈T}是一族随机变量，T是一个实数集合，若对任意实数t∈T，ξt是一个随机变量，则称{ξt，t∈T}为随机过程。设\{ξ _ t，t∈T\}是一族随机变量，T是一个实数集合，若对任意实数t∈T，ξ _ t是一个随机变量，则称\{ξ _ t，t∈T\}为随机过程。 设{ξt​，t∈T}是一族随机变量，T是一个实数集合，若对任意实数t∈T，ξt​是一个随机变量，则称{ξt​，t∈T}为随机过程。
T为参数集合，参数t可以看作时间。ξ _ t的每一个可能取值所构成的集合称为状态空间，记为E。当参数T为非负整数集时，随机过程又称为随机序列。马尔可夫 （Markov） 链就是一类特殊的随机序列。

在随机过程中有很多这样的现象：某一系统在已知现在的情况下，系统未来时刻的情况只与现在有关，而与过去的历史无直接关系。

已知现在，且来与过去无关。描述这类随机现象的数学模型称为马尔可夫模型

定义2：
设{ξn,n=1,2,...}是一个随机序列，状态空间E为有限或可列集，对于任意的正整数m,n，若i,j,ik∈E(k=1,...,n−1),有P{ξn+m=j∣ξn=i,ξn−1=in−1,...,ξ1=i1}=P{ξn+m=j∣ξn=i}——(1)则称{ξn,n=1,2,...}为一个马尔科夫链（马氏链）。设\{ξ_n,n=1,2,...\}是一个随机序列，状态空间E为有限或可列集，对于任意的正整数m,n，若i,j,i_k∈E(k=1,...,n-1),有\\ P\{ξ_{n+m}=j|ξ_n=i,ξ_{n-1}=i_{n-1},...,ξ_1=i_1\}=P\{ξ_{n+m}=j|ξ_n=i\}——(1)\\ 则称\{ξ_n,n=1,2,...\}为一个马尔科夫链（马氏链）。 设{ξn​,n=1,2,...}是一个随机序列，状态空间E为有限或可列集，对于任意的正整数m,n，若i,j,ik​∈E(k=1,...,n−1),有P{ξn+m​=j∣ξn​=i,ξn−1​=in−1​,...,ξ1​=i1​}=P{ξn+m​=j∣ξn​=i}——(1)则称{ξn​,n=1,2,...}为一个马尔科夫链（马氏链）。
定义3：
设{ξn,n=1,2,...}是一个马氏链，如果等式(1)右边的条件概率与n无关，即P{ξn+m=j∣ξn=i}=Pij(m)——(2)则称{ξn,n=1,2,...}为时齐的马氏链设\{ξ_n,n=1,2,...\}是一个马氏链，如果等式(1)右边的条件概率与n无关，即\\ P\{ξ_{n+m}=j|ξ_n=i\}=P_{ij}(m)——(2)\\ 则称\{ξ_n,n=1,2,...\}为时齐的马氏链 设{ξn​,n=1,2,...}是一个马氏链，如果等式(1)右边的条件概率与n无关，即P{ξn+m​=j∣ξn​=i}=Pij​(m)——(2)则称{ξn​,n=1,2,...}为时齐的马氏链
P_{ij}(m)称为系统由状态 i 经过m个时间间隔（或m步）转移到状态 j 的概率。（2）式称为时齐性。它的含义是：系统由状态i到状态j的转移概率只依赖与时间间隔的长短，与起始的时刻无关。

转移概率矩阵

对于一个马尔可夫链{ξn,n=1,2,...}，称以m步转移概率Pij(m)为元素的矩阵P(m)=(Pij(m))为马尔科夫链的m步转移矩阵。当m=1时，记P(1)=P为马氏链的一步转移矩阵，或简称转移矩阵。它们具有三个基本性质：(1)对一切i,j∈E，0≤Pij(m)≤1；(2)对一切i∈E，∑j∈EPij(m)=1；(3)对一切i,j∈E，pij(0)=δij={1,i=j0,i≠j对于一个马尔可夫链\{ξ_n,n=1,2,...\}，称以m步转移概率P_{ij}(m)为元素的矩阵P(m)=(P_{ij}(m))为马尔科夫链的m步转移矩阵。\\ 当m=1时，记P(1)=P为马氏链的一步转移矩阵，或简称转移矩阵。它们具有三个基本性质：\\ (1)对一切i,j∈E，0≤P_{ij}(m)≤1；\\ (2)对一切i∈E，\sum_{j∈E}P_{ij}(m)=1；\\ (3)对一切i,j∈E，p_{ij}(0)=δ_{ij}= \begin{cases} 1,i=j\\ 0,i≠j \end{cases} 对于一个马尔可夫链{ξn​,n=1,2,...}，称以m步转移概率Pij​(m)为元素的矩阵P(m)=(Pij​(m))为马尔科夫链的m步转移矩阵。当m=1时，记P(1)=P为马氏链的一步转移矩阵，或简称转移矩阵。它们具有三个基本性质：(1)对一切i,j∈E，0≤Pij​(m)≤1；(2)对一切i∈E，j∈E∑​Pij​(m)=1；(3)对一切i,j∈E，pij​(0)=δij​={1,i=j0,i=j​

马氏链模型

描述一类重要的随机动态系统（过程）的模型

• 系统在每个时期所处的状态是随机的
• 从一时期到下时期的状态按一定概率转移
• 下时期状态只取决于本时期状态和转移概率
  已知现在，将来与过去无关（无后效性）

马氏链 (Markov Chain)——时间、状态均为离散的随机转移过程

当实际问题可以用马氏链来描述时，首先要确定它的状态空间及参数集合，然后确定它的一步转移概率。

关于这一概率的确定，可以由问题的内在规律得到，也可以由过去经验给出，还可以根据观察数据来估计。

转移概率的极限分布

1. 柯尔莫哥洛夫-开普曼定理：
   对于马尔可夫链而言，pij(n+m)=∑k∈Epik(n)pkj(m)对于马尔可夫链而言，p_{ij}(n+m)=\sum_{k∈E}p_{ik}(n)p_{kj}(m) 对于马尔可夫链而言，pij​(n+m)=k∈E∑​pik​(n)pkj​(m)

2. 设P是转移矩阵（概率向量为行向量）,P ^ (0)是初始的概率分布。则第n步的概率发布为P ^ (0) P ^ n

3. 若P是正则的，转移概率P_ij ^ (n)存在与i无关的极限lim_n->∞P_ij ^ (n)=π_j，则称此马尔可夫链具有遍历性

4. 在3的基础上，若∑ _ j π _ j = 1，则称π ~ 为马尔可夫链的极限发布，同时它也是π ~ =π ~ P的唯一解

马氏链的基本方程

系统状态Xn=1,2,...k(n=0,1,...)状态概率ai(n)=P(Xn=i)转移概率pij=P(Xn+1=j∣Xn=i)基本方程ai(n+1)=∑j=1kaj(n)pji,i=1,2,...,k∑i=1kai(n)=1n=0,1,...pij≥0,∑j=1kpij=1,i=1,2,...,ka(n)=(a1(n),a2(n),...,ak(n))状态概率向量P={pij}k×k转移概率矩阵（非负，行和为1）a(n+1)=a(n)P——>a(n)=a(0)Pn系统状态X_n=1,2,...k(n=0,1,...)\\ 状态概率a_i(n)=P(X_n=i)\\ 转移概率p_{ij}=P(X_{n+1}=j|X_n=i)\\ 基本方程 \quad a_i(n+1)=\sum_{j=1}^ka_j(n)p_{ji},i=1,2,...,k\\ \sum_{i=1}^ka_i(n)=1\quad n=0,1,...\quad p_{ij}≥0,\sum_{j=1}^kp_{ij}=1,i=1,2,...,k\\ a(n)=(a_1(n),a_2(n),...,a_k(n)) ~ 状态概率向量\\ P=\{p_{ij}\}_{k×k} ~ 转移概率矩阵（非负，行和为1）\\ a(n+1)=a(n)P——>a(n)=a(0)P^n 系统状态Xn​=1,2,...k(n=0,1,...)状态概率ai​(n)=P(Xn​=i)转移概率pij​=P(Xn+1​=j∣Xn​=i)基本方程ai​(n+1)=j=1∑k​aj​(n)pji​,i=1,2,...,ki=1∑k​ai​(n)=1n=0,1,...pij​≥0,j=1∑k​pij​=1,i=1,2,...,ka(n)=(a1​(n),a2​(n),...,ak​(n)) 状态概率向量P={pij​}k×k​ 转移概率矩阵（非负，行和为1）a(n+1)=a(n)P——>a(n)=a(0)Pn

马氏链的两个重要类型

1. 正则链~从任一状态出发经有限次转移能以正概率到达另外任一状态
   正则链↔∃N,PN>0正则链→∃w,a(n)→w(n→∞)正则链↔∃N,P^N>0\\ 正则链→∃w,a(n)→w(n→∞) 正则链↔∃N,PN>0正则链→∃w,a(n)→w(n→∞)
   w~稳态概率

   1. w满足wP=w
   2. w满足∑wi=1

2. 吸收链~存在吸收状态（一旦到达就不会离开的状态i，p_ii=1），且从任一非吸收状态出发经有限次转移能以正概率到达吸收状态。

   有r 个吸收状态的吸收链的转移概率阵标准形式
   P=[Ir×rORS]R有非零元素P= \begin{bmatrix} I_{r×r} & O\\ R & S\\ \end{bmatrix} \quad R有非零元素 P=[Ir×r​R​OS​]R有非零元素
   其中I为r阶单位阵，O为r×s零阵，R为s×r矩阵，S为s×s矩阵。

   （注：非标准形式可经对状态重新编号 ）
   在吸收链中，令M=(I−Q)−1=∑s=0∞QS，则M称为基矩阵。在吸收链中，令M=(I-Q)^{-1}=\sum_{s=0}^∞Q^S，则M称为基矩阵。 在吸收链中，令M=(I−Q)−1=s=0∑∞​QS，则M称为基矩阵。
   对具有标准形式转移矩阵的吸收链，可以证明以下定理：

   • 吸收链的基矩阵M 中的每个元素，表示从一个非吸收状态出发，过程达到每个非吸收状态的平均转移次数。

   • 令y=(y1,y2,...,yk−r)=Mee=(1,1,...,1)T则yi表示从第i个非吸收状态出发，被某个吸收状态吸收之前的平均转移次数。令y=(y_1,y_2,...,y_{k-r})=Me \quad e=(1,1,...,1)^T\\ 则y_i表示从第i个非吸收状态出发，被某个吸收状态吸收之前的平均转移次数。 令y=(y1​,y2​,...,yk−r​)=Mee=(1,1,...,1)T则yi​表示从第i个非吸收状态出发，被某个吸收状态吸收之前的平均转移次数。