1、稳态概率稳态概率1.一个常返类，状态有限，非周期的一个常返类，状态有限，非周期的情形：情形：如如果果 j 非常返非常返，则，则 (定理定理4.13)如如果果 j 常返常返，处于状态处于状态j的概率的概率pij(n)趋近于趋近于一个独立于初始状态一个独立于初始状态i的极限值。这个极限的极限值。这个极限值记为值记为 j，有如下表示：，有如下表示：j P(Xn=j)(当当n很很大时大时)，并且称之为并且称之为稳态概率稳态概率。Iipnijn ,0lim)(例例1：因此，稳态概率为因此，稳态概率为 因为因为 1和和 2形成概率分布，形成概率分布，称为称为平稳分布平稳分布 4.06.02.08.0P43
2、limlim)(21)(11 nnnnpp41limlim)(22)(12 nnnnpp41,4321 121 0.8800 0.0400 0.08000.2000 0.7000 0.10000.2000 0.1000 0.7000P 0.7984 0.0712 0.13040.3360 0.5080 0.15600.3360 0.1480 0.51602P23111p12p13p21p22p23p31p32p33p 0.6329 0.1511 0.21600.6118 0.1684 0.21980.6118 0.1624 0.225810P327limlimlim)(31)(21)(11 n
3、nnnnnppp325limlimlim)(32)(22)(12 nnnnnnppp85limlimlim)(33)(23)(13 nnnnnnppp1 2 3 1321 是一概率分布，称为平稳分布是一概率分布，称为平稳分布如果初始分布为如果初始分布为(p1,p2,.,pm),则则n步之后的状步之后的状态分布：态分布：)()(2)(1)(2)(22)(21)(1)(12)(112121),()(,),(),(nmmnmnmnmnnnmnnmmppppppppppppnpnpnp于是于是：)(lim)(lim)(1)(212)(1111nmmnnnnppppppnp 11211 mppp121)
4、(mppp1 同理同理：22)(lim npn当当n足够大时，状态分布是平稳分布，与初始足够大时，状态分布是平稳分布，与初始分布无关。分布无关。)(1)(212)(111limlimlimnmmnnnnnpppppp mmnnp )(lim 4.06.02.08.0P)0,1()0(Tp 4.06.02.08.0)0,1()1(Tp)2.0,8.0()0.2400 0.7600(24.06.02.08.0)0,1()2(Tp如果初始状态分布为如果初始状态分布为：)0.2499 0.7501()5(),5()5(21 pppT)0.25 0.75()(Tp)(21 )4.0,3.0,3.0()0
5、(Tp 0.8800 0.0400 0.08000.2000 0.7000 0.10000.2000 0.1000 0.7000)4.0,3.0,3.0()1(Tp)0.4720 0.2560 0.2720(如果初始状态分布为如果初始状态分布为：20.8800 0.0400 0.08000.2000 0.7000 0.10000.2000 0.1000 0.7000)4.0,3.0,3.0()1(Tp)0.5210 0.2253 0.2538(100.8800 0.0400 0.08000.2000 0.7000 0.10000.2000 0.1000 0.7000)4.0,3.0,3.0()
6、10(Tp)0.6202 0.1597 0.2201()85,325,327()(Tp),(321 4.06.02.08.0P如果初始分布为平稳分布如果初始分布为平稳分布)41,43(),(21 下一时刻的状态分布：下一时刻的状态分布：P ),(21 4.06.02.08.0)41,43()41,43(),(21 于是任意时刻的状态分布都是于是任意时刻的状态分布都是),(21 88.004.008.02.07.01.02.01.07.0P如果初始分布为平稳分布如果初始分布为平稳分布)85,325,327(),(321 则：则：88.004.008.02.07.01.02.01.07.0)85,
7、325,327(),(321P )85,325,327(),(321 任意时刻的状态分布都是任意时刻的状态分布都是),(321 对于只有一个常返类，状态有限，非周期的马对于只有一个常返类，状态有限，非周期的马尔科夫链，状态空间尔科夫链，状态空间I=1,2,.,m,转移矩阵转移矩阵 mmmmmmpppppppppP212222111211平稳分布平稳分布),(21m 则则 mmmmmmmmpppppppppP2122221112112121),(),(),(21m 得到平衡方程组：得到平衡方程组：平衡方程组为：平衡方程组为：又结合归一化方程又结合归一化方程 就可以解出就可以解出 j 11 mkk
8、 mmmmmmmmmmppppppppp .22112222121212121111 实际上，一旦实际上，一旦pij(n)收敛于某一个收敛于某一个 j，考虑，考虑查普曼查普曼科尔莫格洛夫方程：科尔莫格洛夫方程：两边对两边对n取极限，得到平衡方程：取极限，得到平衡方程：当当j=1时，时，当当j=2时，时，.mkkjnnpppikij1)1()(mjpmkkjkj,.,2,1,1 1 1212111.mmppp 2 2222121.mmppp 例例7.5考虑两个状态的马尔科夫链，他们的考虑两个状态的马尔科夫链，他们的转移概率是转移概率是P11=0.8，P12=0.2P21=0.6，P22=0.4
9、平衡方程组为平衡方程组为 注意上面两个方程是相互依赖的，共同等注意上面两个方程是相互依赖的，共同等价于价于 1 214.02.0 2 212111pp 216.08.0 222121pp 213 这是一个一般的结论，可以证明平衡方程这是一个一般的结论，可以证明平衡方程组内的任何方程都可以利用剩下的式子推组内的任何方程都可以利用剩下的式子推导出来。导出来。由于由于 j 满足归一化方程满足归一化方程 它是平衡方程组的一个补充，从而能唯一它是平衡方程组的一个补充，从而能唯一的得到的得到 j 这个结果和我们前面通过迭代查普曼这个结果和我们前面通过迭代查普曼-科尔科尔莫格洛夫方程组得到的结果一致。莫格洛
10、夫方程组得到的结果一致。121 25.0,75.021 稳态收敛定理：稳态收敛定理：考虑一个非周期的，单个常返类的马尔科夫链。考虑一个非周期的，单个常返类的马尔科夫链。状态状态j和它对应的稳态概率和它对应的稳态概率 j具有如下性质。具有如下性质。(a)对于每个对于每个j，我们有：，我们有：(b)j是下列方程组的唯一解：是下列方程组的唯一解：(c)另外有：另外有：inpjijn对对所所有有的的,)(lim mkkmkkjkjmjp111,.,1,jjjj对对所所有有的的常常返返状状态态对对所所有有的的非非常常返返状状态态,0,0 例例7.6 一位健忘的教授有两把雨伞，用于上一位健忘的教授有两把雨
11、伞，用于上下班往返于家和学校之间。如果下雨且在下班往返于家和学校之间。如果下雨且在她所处位置有一把雨伞可用，那么她就会她所处位置有一把雨伞可用，那么她就会带上它。如果没有下雨，她总是忘记带雨带上它。如果没有下雨，她总是忘记带雨伞。假设每次她出门下雨的概率是伞。假设每次她出门下雨的概率是p，且独且独立于其他时候。请问她在路上被淋湿的稳立于其他时候。请问她在路上被淋湿的稳态概率是多少？态概率是多少？解解 利用马尔科夫链模型建立模型，假设以利用马尔科夫链模型建立模型，假设以下状态：下状态：状态状态i：在她所在地有：在她所在地有i把雨伞可用，把雨伞可用，i=0,1,2,转转移概率图和转移概率矩阵如下：
12、移概率图和转移概率矩阵如下：矩阵第一行表示她出门时门口没有伞矩阵第一行表示她出门时门口没有伞,她到达目的她到达目的地门口必定有两把伞地门口必定有两把伞,因此因此p00=0,p01=0,p02=1 第二行表示她出门时门口只有一把伞，以概率第二行表示她出门时门口只有一把伞，以概率p把伞带走，以概率把伞带走，以概率1-p将伞留在原地，这样目的地将伞留在原地，这样目的地门口的状态为门口的状态为1或或2.这个马尔科夫链具有单个常返类，且是非这个马尔科夫链具有单个常返类，且是非周期的周期的(假设假设0p1),所以可以利用稳态收敛所以可以利用稳态收敛定理。其平衡方程组为定理。其平衡方程组为 结合归一化方程结
13、合归一化方程 得到得到 根据稳态收敛定理，教授发现自己所在地根据稳态收敛定理，教授发现自己所在地方没有雨伞的稳态概率是方没有雨伞的稳态概率是 0，那么教授被，那么教授被淋湿的概率为淋湿的概率为10221120,)1(,)1(pppp 1210 pppp 31,31,31210 pppp 3)1(0 例例7.7 一个迷信的教授在一个具有一个迷信的教授在一个具有m扇门的环形建扇门的环形建筑里面工作，筑里面工作，m是奇数。他绝不连续两次打开同是奇数。他绝不连续两次打开同一扇门。相反，他以概率一扇门。相反，他以概率p(或或1-p)以顺时针以顺时针(逆时逆时针针)方向打开他上一次打开的相邻的门。请问选定
14、方向打开他上一次打开的相邻的门。请问选定一扇门将在未来一天被用到的概率？一扇门将在未来一天被用到的概率？解解 利用马尔科夫链模型，有以下利用马尔科夫链模型，有以下m个状态：个状态：状态状态i：教授打开的是第：教授打开的是第i扇门，扇门，i=1,.,m 转移概率矩阵为转移概率矩阵为(图中图中m=5):假设假设0p0;(b)如果至少存在一个信号包在系统中，则如果至少存在一个信号包在系统中，则传送出去一个信号包，发生的概率是传送出去一个信号包，发生的概率是d0,否则概率为否则概率为0；(c)没有新信号到达，也没有已经存在的信没有新信号到达，也没有已经存在的信号包传送出去，号包传送出去，(没有完成传送
15、任务没有完成传送任务)，如果，如果当时的缓冲器中存在至少一个信号包，则当时的缓冲器中存在至少一个信号包，则事件发生的概率为事件发生的概率为1-b-d;如果当时在缓冲器如果当时在缓冲器中没有信号包，则事件发生的概率为中没有信号包，则事件发生的概率为1-b 我们建立一个马尔科夫链，其状态空间为我们建立一个马尔科夫链，其状态空间为0,1,.,m,这些状态表示缓冲器中信号包的这些状态表示缓冲器中信号包的个数。转移概率图如下：个数。转移概率图如下：局部平衡方程组为：局部平衡方程组为：1,.,1,0,1 midbii 定义定义,db 可得可得miii,.,1,0,0 结合归一化方程结合归一化方程m .11
16、0 可得可得).1(10m 以及以及 1,111,1110 mm 稳态概率为稳态概率为mimimii,.,1,0,1,111,1110 下面分析当缓冲器容量下面分析当缓冲器容量m很大，实际中可很大，实际中可以认为无穷的时候，将会发生什么事情。以认为无穷的时候，将会发生什么事情。分两种情况：分两种情况：(a)假定假定bd,或者或者d,或者或者1 这种情况下，新信号到达的可能性大于缓这种情况下，新信号到达的可能性大于缓冲器中信号离开的可能性。缓冲器中信号冲器中信号离开的可能性。缓冲器中信号的数量趋于增加，并且稳态概率的数量趋于增加，并且稳态概率 i随着随着i的的增大而增加。由于我们考虑的缓冲器具有
17、增大而增加。由于我们考虑的缓冲器具有很大的容量很大的容量m，任何状态，任何状态i的概率都是趋近的概率都是趋近于于0的：的：i0，对于所有的，对于所有的I 这意味着，缓冲器中信号的个数将增加到这意味着，缓冲器中信号的个数将增加到无限多个，并且任何特别的状态都只能被无限多个，并且任何特别的状态都只能被访问有限次数。访问有限次数。稳态性质稳态性质 如果有两个或多个常返类，显然如果有两个或多个常返类，显然pij(n)的极的极限值一定依赖于初始状态（例限值一定依赖于初始状态（例2）。所以我）。所以我们将链限定于只有一个常返类，加上一些们将链限定于只有一个常返类，加上一些可能存在的非常返状态。可能存在的非
18、常返状态。由于一个状态一由于一个状态一旦进入一个常返类，它将一直处于这个类旦进入一个常返类，它将一直处于这个类中，所以可以利用单一链的渐近行为去理中，所以可以利用单一链的渐近行为去理解多个常返类的马尔科夫链的渐近行为。解多个常返类的马尔科夫链的渐近行为。4.4 4.4 渐近性质与平稳分布渐近性质与平稳分布 设马尔可夫链转移概率矩阵为设马尔可夫链转移概率矩阵为求每一个不可约闭集的平稳分布。求每一个不可约闭集的平稳分布。5.05.0000005.005.0000005.05.00000000001000010000005.05.000004.02.02.01.01.0P4.4 4.4 渐近性质与平
19、稳分布渐近性质与平稳分布 解解 从状态转移图从状态转移图看出，状态空间可看出，状态空间可分解为两个不可约分解为两个不可约常返闭集常返闭集C1=2,3,4和和C2=5,6,7，一个一个非常返集非常返集N=1。在常返集上求平稳在常返集上求平稳分布。分布。5671243110.10.20.20.50.50.50.50.50.50.50.50.40.14.4 4.4 渐近性质与平稳分布渐近性质与平稳分布在在C1上，对应的转移概率矩阵为上，对应的转移概率矩阵为C1上的平稳分布为上的平稳分布为0,0.4,0.2,0.4,0,0,0同理可求得同理可求得C2上的平稳分布为上的平稳分布为 0,0,0,0,1/3,1/3,1/30011005.05.00P15.05.04323242342 4.02.04.0432
