Alex_McAvoy

想要成为渔夫的猎手

马尔可夫链的状态

【状态的基本属性】

首达概率与迟早概率

设马尔可夫链 {Xn,n0},当 i,jS,称:

fij(n)=P(Xn=j,Xkj,k=1,2,,n1|X0=i)

{Xn,n0}0 时刻从状态 i 出发,经过 n 步转移后,首次达到状态 j 的概率,简称为首达概率,称

fij=n=1fij(n)=P(n=1(Xn=j,Xkj,k=1,2,,n1)|X0=i)

{Xn,n0}0 时从状态 i 出发,经过有限步转移后,迟早要达到状态 j 的概率,简称为迟早概率,称

fij(+)=P(Xnj,n=1,2,,n1)|X0=i)

{Xn,n0}0 时从状态 i 出发,永远也无法达到状态 j 的概率


对于首达概率和迟早概率,其与马尔可夫链的转移概率有如下关系:

0fij(n)pij(n)fij1pij(n)=l=1nfij(l)pjj(nl)fij(n)=i1ji2jin1jpii1pi1i2pin1j

首达时刻

设马尔可夫链 {Xn,n0},当 jS,称

Tj=min{n|n1,Xn=j}

{Xn,n0} 首次到达状态 j 的时间,简称首达时刻,显然,Tj 是一个随机变量

{n|n1,Xn=j}=,即 n1,Xnj 时,定义

Tj=+

即系统在有限时间内,不可到达状态 j


首达时刻与首达概率和迟早概率有如下关系:

fij(n)=P(Tj=n|X0=i)fij=P(Tj<+|X0=0)

平均转移步数与平均返回时间

设马尔可夫链 {Xn,n0},当 jS 时,其首达时刻为 Tj,称

μij=E(Tj|X0=i)=n=1nfij(n)

为从状态 i 出发,首次到达状态 j平均转移步数,称

μjj=E(Tj|X0=j)=n=1nfjj(n)

为从状态 j 出发,首次返回状态 j平均返回时间

周期

设马尔可夫链 {Xn,n0},当 iS,若 {n|n1,pii(n)>0},则称

di=GCD{n|n1,pii(n)>0}

为状态 i周期,若 {n|n1,fii(n)>0},则有

hi=GCD{n|n1,fii(n)>0}

对于 dihi,有如下性质:

1)若 pij(n)>0,则存在 m1,使得

n=mdi

2)若 fij(n)>0,则存在 m1,使得

n=mhi

3)若 dihi 中一个存在,则另一个也存在,且

di=hi

【状态】

可约与不可约

设马尔可夫链 {Xn,n0},对任意 i,jS,若存在任一时刻 t>0,满足:

P(Xt=i|X0=j)>0

即在 0 时刻从状态 j 出发,在 t 时刻到达状态 i 的概率大于 0,则称马尔可夫链 {Xn,n0}不可约的,否则称是可约的

直观上,一个不可约的马尔可夫链,从任意状态出发,当经过充分长时间后,可以到达任意状态


如下马尔可夫链状态转移图所示,其转移概率矩阵

[01201000121]

其平稳分布 π=(0,0,1)T,即该马尔可夫链转移到状态 3 后,就在该状态上循环,无法到达状态 1 与状态 2,故该马尔可夫链是可约的

周期与非周期

设马尔可夫链 {Xn,n0},对任意 iS

  • 若状态 i 的周期 di>1,则称状态 i 为周期为 di周期状态,称该马尔可夫链为周期的
  • 若状态 i 的周期 di=1,则称状态 i非周期状态,称该马尔可夫为非周期的

直观上,一个非周期性的马尔可夫链,不存在一个状态,从这个状态出发,再返回到这个状态时所经历的时间呈周期性


如下马尔可夫链状态转移图所示,其转移概率矩阵

[001100010]

其平稳分布 π=(13,13,13)T,即该马尔可夫链从每个状态出发,返回该状态的时刻都是 3 的倍数,具备周期性,最终停留在每个状态的概率都是 13,故该马尔可夫链是周期的

常返与非常返

设马尔可夫链 {Xn,n0},对任意 iS

  • 若从状态 i 到状态 i 的首达概率 fii=1,则称状态 i常返状态或返回状态,称该马尔可夫链为常返的
  • 若从状态 i 到状态 i 的首达概率 fii<1,则称状态 i非常返状态或滑过状态,称该马尔可夫链为非常返的

正常返与零常返

设马尔可夫链 {Xn,n0},对任意 iS

  • 若状态 i 为常返状态,且状态 i 的平均返回时间 μii<+,则称状态 i正常返状态,称该马尔可夫链为正常返的
  • 若状态 i 为常返状态,且状态 i 的平均返回时间 μii=+,则称状态 i零常返状态或消极常返状态,称该马尔可夫链为零常返的

直观上,一个正常返的马尔可夫链,其中任意一个状态,从其他任意一个状态出发,当时间趋于无穷时,首次转移到这个状态的概率不为 0

对于不可约、非周期且正常返的马尔可夫链,有唯一平稳分布存在


如下马尔可夫链状态转移图所示,其转移概率矩阵

[pp00q0p00q0p00q0]

p>q 时,其平稳分布 π=(qp)i(pqp),i=1,2,,即当时间趋于无穷时,转移到任何一个状态的概率不为 0,故该马尔可夫链是正常返的

pq 时,不存在平稳分布,故该马尔可夫链是零常返的

遍历与非遍历

设马尔可夫链 {Xn,n0},对任意 iS

  • 若状态 i 为不可约、正常返,且是非周期的,则称状态 i 为正常返非周期状态或遍历状态,称该马尔可夫链为遍历的
  • 若状态 i 为不可约、正常返,且是周期的,则称状态 i 为正常返周期状态或非遍历状态,称该马尔可夫链为非遍历的

不可约、正常返、非周期保证了当时间趋于无穷时,到达任一状态的概率不为 0

【遍历定理】

对于马尔可夫链的遍历状态,有如下的遍历定理

设马尔可夫链 {Xn,n0},若其是不可约、非周期、正常返的,即该马尔可夫链是遍历的,那么该马尔可夫链有唯一分布 π=(π1,π1,)T,且转移概率的极限分布是马尔可夫链的平稳分布,即:

limtP(Xt=i|X0=j)=πi,i=1,2,;j=1,2,

f(X) 是定义在状态空间 S 上的函数,且 f(X) 关于平稳分布 π=(π1,π1,)T 的数学期望 Eπ[|f(X)|]=if(i)πi<,则该函数的样本均值 ft^=1ts=1tf(xs) 以概率 1 收敛于 Eπ[|f(X)|],即:

P{ft^Eπ[|f(X)|]}=1

遍历定理的直观解释是:满足不可约、非周期、正常返的马尔可夫链,当时间趋于无穷时,马尔可夫链的状态分布趋于平稳分布,随机变量的函数的样本均值以概率 1 收敛于该函数的数学期望

遍历定理实际上表达了马尔可夫链遍历性的含义:样本均值可以认为是时间均值,数学期望可以认为是空间均值,当时间趋于无穷时,时间均值等同于空间均值

实际应用时,通常是取一个足够大的整数 m,经过 m 次迭代后便认为状态分布就是平稳分布,此时从第 m+1 次迭代到第 n 次迭代的均值,被称为遍历均值,即:

E^f=1nmi=m+1nf(xi)

【状态的可达与互通】

设马尔可夫链 {Xn,n0},当 i,jS,若存在 n1,使得

pij(n)>0

则称状态 i 可达状态 j,记为 ij

若状态 i 可达状态 j,且状态 j 可达状态 i,即

ij,ji

则称状态 i 与状态 j 互通,记为 ij


对于状态的可达与互通,有:

  • 可达的传递性:若 ij,jk,则 ik
  • 互通的传递性:若 ij,jk,则 ik
  • 互通的对称性:若 ij,则 ji

此外,对于互通的两个状态 i,jS,他们有相同的类型,即设 i,jS,且 ij,则 i,j 有:

  • 两者同为非常返状态
  • 两者同为零常返状态
  • 两者同为遍历状态
  • 两者同为非遍历状态且周期相同
感谢您对我的支持,让我继续努力分享有用的技术与知识点!
0 comments
Anonymous
Markdown is supported

Be the first person to leave a comment!