Gambler's Ruin（賭徒破產問題概率論） - 台部落

Problem Statement · Definition · Limits · Notes · Constraints · Examples. 請輸入正確的登錄賬號或密碼 註冊 忘記密碼 首頁 概率DP 正文 Gambler'sRuin（賭徒破產問題概率論） 原創 solotzg 2018-08-2406:25 賭徒破產問題，做tc時遇到，順便拿來好好研究下 英文原版地址爲：Gambler'sRuin 問題如下： 一個賭徒有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 再來看topcodersrm667div1500的題 ProblemStatement   ThereareNcatssittingaroundacircle.Thecatsarenumbered0throughN-1inclockwiseorder.Notethatastheysitaroundacircle,catN-1isadjacenttocat0.Thecatsareplayingagameandthewinner willgetaprize! Thegamelooksasfollows: Thereisasingleball.Initially,cat0holdstheball.Ineachroundofthegame,thecatwhocurrentlyholdsaballflipsabiasedcoin.Thecoinwillcomeupheadswithprobabilityp/1,000,000,000andtailswithprobability1-(p/1,000,000,000).Ifthecoincameupheads,thecurrentcatwillhandtheballtothenextcatclockwise,otherwisethecurrentcatwillhandtheballtothenextcatcounterclockwise.Formally,ifthecurrentcatiscatj,headsmeansthattheballgoestocat(j+1)modN andtailsmeansthatitgoestocat(j-1)modN.Thegameisplayeduntileachcatheldtheballatleastonce.Thecatwhoholdstheballattheendofthegameisthewinner.Inotherwords,thewinneristhelastcattotouchtheball.Notethatcat0holdstheballatthebeginning,andthisdoescountasholdingtheball.Hence,ifthereismorethanonecat,cat0canneverwinthegame. CatKwonderswhatistheprobabilitythatshewillwintheprize.YouaregiventheintsN,K,and p.ReturntheprobabilitythatcatKwins. Definition   Class: CatsOnTheCircle Method: getProb Parameters: int,int,int Returns: double Methodsignature: doublegetProb(intN,intK,intp) (besureyourmethodispublic) Limits   Timelimit(s): 2.000 Memorylimit(MB): 256 Stacklimit(MB): 256 Notes - Yourreturnvaluemusthaveanabsoluteorrelativeerrorsmallerthanorequalto1e-6 Constraints - Nwillbebetween3and1,000,000,000,inclusive. - Kwillbebetween1andN-1,inclusive. - pwillbebetween1and999,999,999,inclusive. Examples 0)     3 1 300000000 Returns:0.6999999999999985 ThisgamehasN=3cats,labeled0,1,2.Wehavep=30,000,000,hencethecoinwillcomeupheadswithprobability30,000,000/1,000,000,000=0.3andtailswithprobability0.7.Thegamecanlookasfollows: Cat0isgiventheball.Cat0flipsthecoin.Thecoincomesuptails.Cat0handstheballtocat(0-1)mod3=cat2.Cat2flipsthecoin.Thecomesuptailsagain.Cat2handstheballtocat(2-1)mod3=cat1.Atthismoment,eachcathasheldtheball.Thegameendsandcat1getstheprize. Thisparticularsequenceofeventshasprobability0.7*0.7ofoccuring.Itcanbeshownthattheprobabilitythatcat1winsthegameis0.7. 1)     6 2 500000000 Returns:0.2 Thecointhatisflippedwillcomeupheadswithprobability1/2,andtailswithprobability1/2. 2)     6 5 500000000 Returns:0.2 3)     10 2 666666666 Returns:0.00391389439551009 4)     999999999 999999996 777777777 Returns:0.05830903870125612 5)     1000000000 4 300000000 Returns:0.044981259448371 6)     534428790 459947197 500000000 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的貓 、該遊戲持續進行直到每隻貓至少拿到一次球。

且最終拿球的貓贏得遊戲 現在給定NKP，求出編號爲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 #include #include #include #include #include #include #include #include typedeflonglongintll; #definerp(i,b)for(inti=(0),__tzg_##i=(b);i<__tzg_ usingnamespacestd constdoubledenominator="1e9;" constdoubleeps="1/Denominator;" structcatsonthecircle doublegamblers_ruin doubleq="1.0-p;" if return1.0>p) return1-gamblers_ruin(n,n-h,q); doubler=q/p; return(pow(r,h)-1)/(pow(r,n)-1); } doublegetProb(intN,intK,int_p){ doublep=_p/Denominator; doubleq=1.0-p; doubleo=gamblers_ruin(N-2,N-K-1,p); doubleu=gamblers_ruin(N-2,K-1,q); returno*gamblers_ruin(N-1,1,q)+u*gamblers_ruin(N-1,1,p); } }; 發表評論 登录 所有評論 還沒有人評論，想成為第一個評論的人麼?請在上方評論欄輸入並且點擊發布. 相關文章 第四屆省賽題解-Thenumberofsteps（概率DP+數學期望） 拂袖秋波 2018-08-2512:38:50 POJ2096（概率DP基礎） QiHang_QiHang 2018-08-2323:23:34 SGU495KidsandPrizes（概率DP基礎） QiHang_QiHang 2018-08-2323:23:31 ZOJ3640（概率DP） QiHang_QiHang 2018-08-2323:23:29 【BZOJ1426】收集郵票概率DP論文題推公式題 空灰冰魂 2018-08-2311:59:01 【BZOJ3566】【SHOI2014】概率充電器樹形DP概率DP 空灰冰魂 2018-08-2311:59:00 【BZOJ4008】【HNOI2015】亞瑟王概率DP 空灰冰魂 2018-08-2311:58:59 【BZOJ3036】綠豆蛙的歸宿概率DP 空灰冰魂 2018-08-2311:58:59 【BZOJ1415】【Noi2005】聰聰和可可概率DP記憶化搜索 空灰冰魂 2018-08-2311:58:38 【BZOJ3450】【Tyvj1952】Easy概率DP 空灰冰魂 2018-08-2311:58:38 【BZOJ2318】【spoj4060】gamewithprobabilityProblem概率DP 空灰冰魂 2018-08-2311:58:38 【BZOJ3270】博物館概率DP高斯消元 空灰冰魂 2018-08-2311:58:37 ZOJ_3329OnePersonGame sumword_ 2018-08-2220:10:19 poj2096_CollectingBugs sumword_ 2018-08-2220:10:01 poj3071_Football概率DP、二進制的應用 sumword_ 2018-08-2220:10:01 S solotzg 24小時熱門文章 最新文章 hdu4992PrimitiveRoots（推導+證明） 最大流最小割合集 數位DP合集 hdu5021RevengeofkNNII（樹狀數組） hdu5091BeamCannon（線段樹） 最新評論文章 線上留言 機械手相機9點座標標定-基於C#+EmguCV 台北/板橋/學/生/賴fb852台中上/門/服/務/高雄小/模/高/檔/茶 台北/板橋/學/生/賴fb852台中上/門/服/務/高雄小/模/高/檔/茶 台北/板橋/學/生/賴fb852台中上/門/服/務/高雄小/模/高/檔/茶 台灣本土吃魚喝茶加小番茄賴fb852喝茶覓小姐羅莉學生咩高雄妹技?平价好喝碗電報：sm20290大台北嫖娼林口龜山淫淫正妹思春看照選妹頻道： t.me/linesm20290 台灣本土吃魚喝茶加小番茄賴fb852喝茶覓小姐羅莉學生咩高雄妹技?平价好喝碗電報：sm20290大台北嫖娼林口龜山淫淫正妹思春看照選妹頻道： t.me/linesm20290 台北/板橋/學/生/賴fb852台中上/門/服/務/高雄小/模/高/檔/茶 台灣本土吃魚喝茶加小番茄賴fb852喝茶覓小姐羅莉學生咩高雄妹技?平价好喝碗電報：sm20290大台北嫖娼林口龜山淫淫正妹