赌徒输光问题 马尔科夫链求解,杨阳 肖瑞 王明仪,Content,问题简介,2014.11.07,Part one,问题简介,在“公平”的赌博中， 任 一 个拥有有限赌本的赌徒,一次赌博中， 任意一个赌徒都有可能会赢。 谁输谁赢是偶然的。,一直赌下去,输光,Part two,马尔可夫链,马尔可夫链,因安德烈马尔可夫（A.A.Markov，18561922）得名，是数学中具有马尔可夫性质的离散事件随机过程。该过程中，过去的状态（即当前以前的历史状态）对于预测将来（即当前以后的未来状态）是无关的。,科学中的大量问题都可归结为随机游动问题。赌徒输光问题：即具有两个吸收壁的随机游动问题作了几点讨论，计算了赌徒输光的概率,0,1,2,N-1,N,q0,q1,qn-1,q2,qn-2,pn,rn-1,r2,p2,p1,ro,r1,rn,设E=0,1,2.,N,图为其状态转移图，一步转移概率为,（1）ro=1，q0=0，rn=1，pn=0，pi+ri+qi=1，i=1,2，.,n-1该随机游走被称为具有两个吸收壁的随机游动 （2）ro=0，q0=1，rn=0，pn=1，pi+ri+qi=1，i=1,2，.,n-1该随机游走被称为具有两个反射壁的随机游动 （3）ro0，q00，pi+ri+qi=1，i=1,2，.,n-1该随机游走被称为具有两个弹性壁的随机游动,Part Three,赌徒输光,赌徒输光问题：两个赌徒甲、乙进行一系列赌博。在每一局中甲获胜的概率为p，乙获胜的概率为q，p+q=1，每一局后，负者要付一元给胜者。如果起始时甲有资本a元，乙有资本b元，a+b=c，两个赌徒直到甲输光或乙输光为止，求甲输光的概率,我们以Xn表示赌了n局后手中的赌金。 可以看出，这是一个齐次马尔科夫链，状态空间为E=0,1.,c,转移矩阵为：,由于终止条件为输光，所以还有P00=1,Pcc=1. 显然，0、c为吸收状态，其余为非常返态状态 简记从状态i到状态c的概率为,根据条件概率，有,化简该式子，并采用递推的方法：,由此可推出：,=,根据上述等式，我们知道，当两人进行公平赌博时，赌徒甲、乙输光的概率分别为b/(a+b)和a/(a+b) 这表明谁的初始赌本大谁就处于有利的地位。,由此可推出：,甲、乙输光的概率分别为b/(a+b)和a/(a+b),结论： 1、若甲乙赌金相同，每局取胜概率均相等，则输光的概率也相等。 2、若甲乙每局取胜概率相等，则谁的赌金多谁赢的概率就大。,由此可推出：,甲、乙输光的概率分别为b/(a+b)和a/(a+b),结论：3、对手赌金无限。徒必输光，即所谓“十赌九输”。,Thank you for attention！,