赌徒破产问题(口胡)

自己推了一大版式子推烦了,索性就先只口胡一下这个思想吧。。。

别人的文章:Link1 Link2 Link3

Description

其实并不知道这个模型到底叫什么,网上好像有个这种叫法就暂且这么叫它吧

这类问题一般都是一个这样的模型:

一个赌徒一开始有hh枚金币,每次有pp的概率获得一枚金币或(1p)(1-p)的概率丢掉一枚金币,若他的金币多于TT(赚够收手获胜)或者少于SS(破产)则游戏结束,求他在破产前(在多于SS的前提下)获胜(达到TT)的概率

Solution

f[i]f[i]表示当前收益为ii时刻的条件下能最终获胜的概率,则显然有转移方程:

f[i]=pf[i+1]+(1p)f[i1]f[i] = p\cdot f[i + 1] + (1-p)\cdot f[i - 1]

不难发现这实际上就是一个二阶常系数线性齐次递推式,运用高中课内只是我们可以知道它的特征方程是:

x21px+1pp=0x^2 - \frac{1}{p}x + \frac{1-p}{p} = 0

它有两个特征根:x1=1,x2=1ppx_1 = 1, x_2 = \frac{1-p}{p},于是我们能够得到它的通解为(p=12p=\frac{1}{2}有重根时需要特殊处理一下):

f[n]=c1(1pp)n+c2f[n] = c_1(\frac{1-p}{p})^n + c_2

然后再根据已知条件,一般是与题中S,TS,T相关的信息(如f[S]=0,f[T]=1f[S] = 0, f[T] = 1之类的关系)求出c1,c2c_1, c_2,从而求出f[n]f[n]

Problems

只有口胡

SRM667 Div1 CatsOnTheCircle

Description

只猫围成一圈玩游戏,顺时针编号00N1N-1N1N-1相邻。游戏规则如下:

  • 一开始编号00的猫拿着一个球

  • 每个回合中手里拿球的猫抛硬币,该硬币有P109\frac{P}{10^9}的概率正面朝上,(1P109)(1-\frac{P}{10^9})的概率反面朝上

  • 如果硬币正面朝上,则该猫 jj 把球传给编号为(j+1)%N(j+1) \% N的猫,否则传给编号为(j1+N)%N(j-1+N)\%N的猫

  • 该游戏持续进行直到每只猫至少拿到一次球。且最终拿球的猫赢得游戏

给定N,K,PN, K, P,求编号为KK的猫赢得游戏的概率

Analysis

通过观察发现,如果最后是猫KK拿到球,那么上一轮一定是K1K-1号猫或者K+1K+1号猫拿球,且除了KK号猫之外所有的猫都拿过球,所以答案就是P(K+1K1)+P(K1K+1)P(K+1 | K-1) + P(K-1 | K + 1)

不难发现这实际上就是把上述模型的上下边界调整了一下,直接上模型即可

51nod 1563 夹克赌坊

题意都懒得放了,只不过是分了两段的赌徒破产问题,这样就会有两个特征方程,即要求出c1,c2,d1,d2c_1, c_2, d_1, d_2

因此在题目中多隐藏了两个条件,即在分段函数临界处有两个等量关系

还是利用这些等量关系暴力推系数即可

感谢你的赞赏!