搜索
马尔可夫链应用分析举例例1：赌徒输光问题：两个赌徒进行一系列赌博，在每一局赌博中甲获胜的概率是p，乙获胜的概率是1-p，每一局后，负者要付一元给胜者。如果起始时甲有资本a元，乙有资本b元，a+b=c，两人赌博直到甲输光或乙输光为止。求甲输光的概率。解：第n时刻甲的资本为ξ，状态空间是I：{}cL,2,1,0，1,1,≥≥+=babac。状态转换图为：这个问题实际是带有两个吸收壁的随机游动问题问题是从a点出发，到达0状态的概率，即被0状态吸收的概率。设cj0，ju为质点从j点出发到0状态的概率。由全概率公式有11−++=jjjqupuu边界条件为：010==cuu构造：)()()()()(111111jjjjjjjjjjjuupquuuuquupqupuuqp−=−−=−+=+−+−+−+定义rpq),cj0(,)(1=≤=−+jjjduu，相应的差分方程是：)0(,0221cjdrdrrddjjjj====−−L设1≠r，0100101010011)(drrdrduuuuucciiciiciiic−−===−=−=∑∑∑−=−=−=+0101111)(drrrdrduuuuucjcjiicjiicjiiicjj−−===−=−=∑∑∑−=−=−=+ccjccjjpqpqpqrrru)/(1)/()/(1−−=−−=ccaccaapqpqpqrrru)/(1)/()/(1−−=−−=设1＝r，01001010100)(cddrduuuuuciiciiciiic===−=−=∑∑∑−=−=−=+010111)()(djcdrduuuuucjiicjiicjiiicjj−===−=−=∑∑∑−=−=−=+cjcuj−=cbcacua=−=同样道理，可以得到乙先输光的概率，当1≠r，caapqpqu)/(1)/(1−−=，当1＝r，caub=。该例题是有两个吸收壁的特例，建立了边界条件、递推关系、首先概率表达式，该例题着重研究对称和非对称的赌徒输光的问题。例2：网球比赛网球比赛在选手A和B之间进行。网球的计分制是15，30，40和60分，如果选手A赢了第一球，比分是15:0，否则比分是0:15。如果选手A接着赢了第二球，比分为30:0，如果A接着赢了第三球，比分为40:0，如果A再接着赢了第四球，则比分为60:0，选手A赢得该局比赛。当选手A赢了第一球而输了第二球，对手B得15分，从而比分为15:15。平分是指第六球后双方分数相同(例如30:30，40:40，…)。在平分后，接下来的一球如果选手A得分/失分，则称此时的状态为A占先/B占先。如果A在占先后再得分，则选手A赢得该局。如果选手B在占先后再得分，则选手B赢得该局。一旦第一局比赛结束，选手进入第二局比赛，直到一方赢得至少6局且至少领先对手两局，这样该方获得一盘比赛的胜利。因而，一盘结束时的比分为下列情形之一：6:0，6:1，6:2，6:3，6:4，7:5，8:6，…或是它们的逆序等等(实际规则中采用了决胜局的办法避免一盘比赛的时间过长，此处不详细讨论)。一盘结束后，进行另一盘，直到一方赢得三盘中的两盘（或五盘中的三盘），从而赢得整场比赛。试对网球比赛中一局比赛的规则进行分析讨论。题意分析：整个题目都是在分析网球比赛规则，而分析规则的目的在于得出不同实力的选手在这种规则下赢球的概率。换句话说，假如有两个选手，选手A赢一球的概率为p，选手B赢一球的概率为q=1-p，那么若pq，但是两者接近，例如p=0.52，q=0.48，网球比赛的赛制能否保证选手A在经过长时间的较量后最终有很大的概率战胜对手？相反，若两者实力悬殊，例如p=0.8，q=0.2，赛制能否保证选手A很快就能将B淘汰出局。这些都是我们分析比赛规则时要关注的问题，并应该最后得出一个结论。分出胜负的最小的单位是分，再上是局，局之上是盘（一方赢得至少6局且至少领先对手2局，这样取得一盘比赛的胜利），然后再上是一场比赛（可能是五盘三胜，也可能是三盘二胜）。我们这里暂时只分析一局比赛的规则。建模：具有两个吸收壁，五个状态的随机游动1．一局比赛的建模问题：一局比赛共有多少个状态很多，例如15:0就是一个状态，40:15又是一个状态。还是回到我们分析比赛规则的目的上来，我们是为了得到两名选手最终赢球与输球的概率，那么当一局比赛打到30:40的时候，如果选手B再取胜一球，则30:60，选手B获胜，而之前这局比赛到底是怎么打到30:40的并不是我们关心的问题，我们只关心一局比赛会打到30:40的概率（初始概率）以及之后由状态30:40打到状态30:60的概率（转移概率）。这是典型的马尔科夫链。那么我们实际要做的事情就是如何确定比赛中对我们的分析有用的状态以及这些状态的概率，状态之间相互转移的概率。首先我们对一局比赛中的所有状态分类，可以分为6大类：(1)“过渡”的状态，例如15:0这样的状态。(2)A赢的状态，例如60:15,60:30,60+2:60,60+4:60+2，…这种状态是吸收态(3)B赢的状态，例如15:60,30:60,40:60+1,60+1:60+3,…这种状态是吸收态(4)A占先的状态，也即A再赢一球就取胜，而即使A再输一球也只是平分的状态，例如40:30,60:40(5)B占先的状态，也即B再赢一球就取胜，而即使B再输一球也只是平分的状态，例如30:40,40:60(6)平分的状态，例如30:30,40:40,60:60,60+1:60+1,…值得注意的是，15:15不是平分状态，因为平分状态后再打一球，状态应该转移到A占先或者B占先的状态，而15:15不符合这个概念。总结上面的分析，我们应该关心的是后面五种状态的初始概率以及这五种状态之间的转移概率，而在得到后面五种状态的初始概率时会需要考虑“过渡”的状态，得到初始概率后就不用考虑“过渡”的状态了。下面一幅图是一局的状态转移示意图：图1一局比赛的状态转移图在完成了上述的分析后，我们需要做的就只是确定图1中的五状态随机游动中，各状态的初始概率了。记：状态0：A赢4404Pppq=+状态1：A占先3214Ppq=状态2：平分2226Ppq=状态3：B占先2334Ppq=状态4：B赢4444Pqqp=+其中状态0和状态4是两个吸收壁，因此初始概率分布为4432222344(0)[4,,6,4,4]pppqpqpqpqqqp=+4+该随机游动的转移概率矩阵为1000000000000000001pqPpqpq⎡⎤⎢⎥⎢⎥⎢⎥=⎢⎥⎢⎥⎢⎥⎣⎦到此，网球比赛的输赢问题已经被我们转化成了类似赌徒输光的问题，所不同的是一般讨论赌徒输光时我们认为赌徒具有初始资金a的初始概率为1，而我们这里“赌徒”可能有各种各样的“初始资金”，即各状态的初始概率都不为0。定义,0kf为从状态k最终回到状态0的吸收概率，结合以前关于赌徒输光的结论可知：当pq≠时(我们不讨论当pq=时的概率，因为根据对称性，这样的两个选手在本规则中赢下比赛的概率肯定相等)I）确定,0kf根据全概公式(吸收概率方程组)，有：,01,01,0kkkfqfpf+−=+这是一个差分方程，其边界条件为：0,04,010ff==改写差分方程为：,01,01,0()kkkqpfqfpf+−+=+,01,01,0,0()()kkkkpffffq+−−=−根据边界条件，并迭代上式，可得：40,04,00,01,01()1()1pqffffpq−−==−−4,04,0,00,01,0()()()1kkkppqqfffffpq−−==−−结合上述两式，可解得：44,044()()1(/)1(/)1()kkkppqpqqfpqpq−−−==−−II)选手A赢得一局比赛的概率4444400,0440[1(/)]1(/){A}1(/)1(/)kkkkkkgkkkpqppqppPpfqpqp−−===−−====−−∑∑∑选手赢一局选手实力之比与赢下一局比赛的概率的关系的具体数值分析，：选手技术赢一局的概率pqPg1-Pg0.750.250.9490.0510.660.340.8560.1440.60.40.7360.2640.550.450.6230.3770.520.480.550.450.510.490.5250.475从上表中可以看出，当选手的实力相差悬殊时，例如选手A赢一球的概率是0.75，而选手B赢一球的概率是0.25，那么选手A拿下一局比赛的概率几乎接近1，因此选手A可以轻松的取得整个比赛的胜利；而当选手A与选手B实力接近，例如选手A赢一球的概率是0.51时，选手A拿下一局比赛的概率只是0.525。因此网球比赛在局的规则基础上又设置了盘和场的规则，如果再分析盘和场的规则可以看到，通过盘和场的规则设置，相当于“放大”了选手A在一局比赛里赢下的概率。即使A的实力只是略胜于B，A在最终战胜B的可能性也很大。对完整的分析感兴趣的同学可参考帕普里斯《概率、随机变量与随机过程》（第四版）P607页例15-26。例3：分组数据on-off信源设有一个时隙化的on-off信源。信源处于on状态时，它将以概率onp继续发送分组，以概率)1(onp−结束发送；信源处于off状态时，它将以概率)1(offp−开始发送分组，以概率offp继续停止发送。(1)求它的渐进稳态分布(2)求发送分组长度的分布(3)求发送间歇长度的分布(4)求发送的平均分组长度、平均间歇长度解：第一步：确定状态空间设on状态记作0，off状态时记作1，第二步：确定转移概率矩阵和状态转换图绘出系统的状态转换图是：系统的一步转移概率矩阵是：11ononoffoffppPpp−⎡⎤=⎢⎥−⎣⎦(1)求稳态分布第三步：列稳态方程并求解设)(),(nwnwoffon是时刻n系统处于on状态、off状态的概率。可以得到稳态的状态方程，()()⎟⎟⎠⎞⎜⎜⎝⎛−−⎟⎟⎠⎞⎜⎜⎝⎛=⎟⎟⎠⎞⎜⎜⎝⎛offoffononToffonToffonppppnwnwnwnw11)()()()(()()offoffononoffoffoffonononpnwpnwnwpnwpnwnw⋅+−⋅=−⋅+⋅=)(1)()(1)()()(有归一化条件为：1)()(=+nwnwoffon由此得到稳态概率分布：1()21()2onoffoffonoffonoffonpwnpppwnpp−=−−−=−−(2)确定发送分组长度的分布即：求on状态持续时间的分布研究发送分组长度的分布，就是研究从on状态到off状态的转移时间的分布；可以假设on状态是一个非常返态，off状态是一个吸收态，通过研究从on状态到达off吸收态的吸收时间的概率分布，得到发送分组长度的分布。假设系统的初态处于on状态，经过1步首次到达off状态的概率是，()onoffonpp−=→1)1(经过2步首次到达off状态的概率是()LLononoffonppp−=→1)2(以此类推，经过n步首次到达off状态的概率是()onnonoffonppnp−=−→1)(1此即为发送分组长度为n的概率。也可以通过求发送长度分布概率的母函数求解：从on状态到达off状态的概率母函数可以记作)(spoffon→。相应概率母函数方程为：()()()()2233()1()1()()()1()1()111offoffonoffonoffoffononoffonoffonononoffononoffonononononPsPspsPspsPsPspspsPspsPspspspspsps→→→→→→→==−⋅+⋅=−+⋅−=−⎡⎤=++++−⎣⎦L在概率母函数记作()onoffps→的级数展开式中，s的n次幂的系数就是经过n步到达吸收态的概率。(3)确定间歇长度的分布即：求off状态持续时间的分布，通过求间歇长度分布概率的母函数求解研究间歇长度长度的分布，应该假设off状态是一个非常返态，on状态是一个吸收态，就是研究从off状态到on状态的随机过程。研究从off状态到达on吸收态的概率分布。假设系统的初态处于off状态，经过1步首次到达on状态的概