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

别人的文章: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=0 x^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]

19.3.5 UPD

今天翻出这篇文章,想着还是补一下这个比较通用的结论:

初始点为xx,在数轴区间[a,b],x[a,b][a,b],x\in [a, b]上随机游走,每次往左右概率均等,走到aa点或bb点停止。

那么先走到aa的概率为bxba\frac{b-x}{b-a},先走到bb的概率为xaba\frac{x-a}{b-a}

Problems

只有口胡

SRM667 Div1 CatsOnTheCircle

Description

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

  • 一开始编号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

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

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