Gambler's Ruin（赌徒破产问题 概率论）

赌徒破产问题，做tc时遇到，顺便拿来好好研究下

英文原版地址为：Gambler's Ruin

问题如下：

一个赌徒有h枚金币，每次有概率a获得一枚金币或者概率（1-a）丢掉一枚金币，直到其所有的金币总数达到N或0则游戏结束，求赌徒最终赢得N枚金币的概率P(N|h)。

对于两个状态我们可以确定，即P(N|N)=1、P(N|0)=0。同时得出状态转移公式（概率的推导和普通的DP还是很不一样的，好好体会下）：

P(N|h) = a*P(N|h+1) + (1-a)*P(N|h-1)

这类公式可以表示为二阶线性递归关系，其特征多项式为（自行百度）：

x^2 - 1/a * x + (1-a)/a = 0

求出特征方程的根为1和r=(1-a)/a，针对a==1/2的情况需要特殊处理。得到公式的通解为：

P(N|h) = A*(1^h) + B*(r^h)

根据已知条件P(N|N)=1、P(N|0)=0得：

1 = A + B*(r^N)

0 = A + B

A = -1/(r^N - 1)、B = 1/(r^N - 1)

得到最终解 P(N|h) = (r^h - 1)/(r^N - 1)

但是当a==1/2时，特征方程有重根，因此这种情况下通解为

P(N|h) = A+B*h

A = 0、B=1/N

即P(N|h) = h/N

再来看topcoder srm 667 div1 500的题

Limits

Notes

-Your return value must have an absolute or relative error smaller than or equal to 1e-6

Constraints

-Nwill be between 3 and 1,000,000,000, inclusive.-Kwill be between 1 andN-1, inclusive.-pwill be between 1 and 999,999,999, inclusive.

Examples

0)

Returns: 0.6999999999999985

1)

Returns: 0.2

2)

Returns: 0.2

3)

Returns: 0.00391389439551009

4)

Returns: 0.05830903870125612

5)

Returns: 0.044981259448371

6)

Returns: 1.871156682766205E-9

题意：

N只猫围成一圈玩游戏，顺时针编号0~N-1，N-1与0相邻。游戏规则如下：

、一开始编号0的猫拿着一个球

、每个回合中手里拿球的猫抛硬币，该硬币有P/1000000000的概率正面朝上，(1-P/1000000000)的概率反面朝上

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

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

现在给定N K P，求出编号为K的猫赢得游戏的概率。

分析：

1. 如果最终猫K拿到球并结束游戏，那么之前一回合必然是猫K-1或K+1拿球，且除K外的猫都至少拿过一次球。则最终的结果为P(K+1,K-1) + P(K-1,K+1)，既猫K+1先拿到球的前提下K-1拿到球的概率加上猫K-1先拿到球的前提下K+1拿到球的概率。这样就可以了，因为当全局只剩下K没有拿过球，K必然是最后一个拿到球的。

2. 这种情况和赌徒破产问题有什么类似之处呢？再来回顾下赌徒破产问题，该问题求的是当前有h枚金币的情况下，赢得N枚金币的概率。不如我们换一种表述方式，即该赌徒一开始最多能连续输掉h枚金币。放到这题的环境中，我们假设顺时针走等于金币加一，逆时针走等于金币减一。

3. 以求解P(K-1,K+1)为例，需要将其拆分为两种概率的乘积：P(a)=从0出发向左走最多到达K+2，且向右走必然到达K-1；P(b)=从K-1出发向右最多到达K-1，且向左走必然到达K+1；这样一来就可以套赌徒破产问题了。

4. 大于1.0的浮点数求幂可能会爆，需要控制一下

总结：

概率真是tm的神奇

#include <cstdio>#include <iostream>#include <string>#include<assert.h>#include <algorithm>#include <vector>#include <cstring>#include <queue>#include <set>typedef long long int ll;#define rp(i,b) for(int i=(0),__tzg_##i=(b);i<__tzg_##i;++i)#define rep(i,a,b) for(int i=(a),__tzg_##i=(b);i<__tzg_##i;++i)#define repd(i,a,b) for(int i=(a),__tzg_##i=(b);i<=__tzg_##i;++i)#define mst(a,b) memset(a,b,sizeof(a))using namespace std;const double Denominator = 1e9;const double eps = 1/Denominator;struct CatsOnTheCircle {double gamblers_ruin(int n, int h, double p) {double q = 1.0-p;if (fabs(p-q) < eps)return 1.0*h/n;if (q > p)return 1-gamblers_ruin(n, n-h, q);double r = q/p;return (pow(r,h)-1)/(pow(r,n)-1);}double getProb(int N, int K, int _p){double p = _p/Denominator;double q = 1.0-p;double o = gamblers_ruin(N-2, N-K-1, p);double u = gamblers_ruin(N-2, K-1, q);return o*gamblers_ruin(N-1, 1, q) + u*gamblers_ruin(N-1, 1, p);}};