抛硬币 直到连续出现两次字为止
題目：
[plain]?view plaincopy上面這個題目我第一次見到是在pongba的TopLanguage的一次討論上，提出問題的人為Shuo Chen，當時我給出了一個解法，自認為已經相當簡單了，先來考慮一下拋硬幣的過程：首先先拋一枚硬幣，如果是花，那么需要重頭開始；如果是字，那么再拋一枚硬幣，新拋的這枚如果也是字，則游戲結束，如果是花，那么又需要重頭開始。根據這個過程，設拋硬幣的期望次數為T，可以得到關系
T = 1 + 0.5T + 0.5( 1 + 0.5 * 0 + 0.5T)
解方程可得到 T = 6. 由于上面這個方法只能得到期望，而無法得到方差以及具體某個事件的概率，后來我又仔細分析了一下，推出了概率生成函數為（推導的過程暫時略過，后面你會看到一個更一般、更簡單的推導）
于是可以算出方差 V = G''(1) + G'(1) - G'(1)^2 = 22。將G(z)根據Rational Expansion Theorem [CMath 7.3]展開，可以得到需要拋n次硬幣的概率為
其中Fn是Fibonacci數列的第n項。到這里，我覺得這個問題似乎已經完全解決了，直到昨天看到Matrix67的牛B帖。在此帖中Matrix67大牛用他那神一般的數學直覺一下將需要連續拋出n個字的一般情形給解決了，而且得出的結果相當簡潔：Tn = 2^(n+1) - 2，其中Tn為首次出現連續的n個字的期望投擲數。這也給了我一些啟發，我試著將上面的過程進行推廣，居然得到一個簡單得出人意料的解法（甚至比上面n=2的推導過程還簡單）。這個解法的關鍵在于下面這個遞推關系
Tn = Tn-1 + 1 + 0.5 * Tn
也即是有?Tn = 2 * Tn-1 + 2。由于 T1 = 2，因此可以得到?Tn = 2^(n+1) – 2。上面的遞推關系是怎么來的呢，一個直觀的理解是這樣的：首先先拋擲Tn-1次，得到連續的n-1個字，然后再拋一次，若是字，則游戲結束；否則需要重頭開始，也就是說又需要 Tn 次。
期望投擲次數已經得出來了，但是我們還想知道方差、恰好需要投擲 m 次的概率等其它一些更具體的性質。為了方便理解概率的分布情況，我先用程序生成了一個概率表如下所示。在下表中，第n行、第m列的元素為 Pnm，表示首次出現連續n個字的投擲數為m的概率。
| 1/2 | 1/4 | 1/8 | 1/16 | 1/32 | 1/64 | 1/128 | 1/256 | 1/512 | 1/1024 |
| 0 | 1/4 | 1/8 | 2/16 | 3/32 | 5/64 | 8/128 | 13/256 | 21/512 | 34/1024 |
| 0 | 0 | 1/8 | 1/16 | 2/32 | 4/64 | 7/128 | 13/256 | 24/512 | 44/1024 |
| 0 | 0 | 0 | 1/16 | 1/32 | 2/64 | 4/128 | 8/256 | 15/512 | 29/1024 |
| 0 | 0 | 0 | 0 | 1/32 | 1/64 | 2/128 | 4/256 | 8/512 | 16/1024 |
仔細觀察上表，你發現什么有趣的性質沒？如果忽略掉分母的話，那么第n行恰好是一個n階Fibonacci數列。例如可以考查各行的最后一列，有
第一行：1 = 1
第二行：34 = 21 + 13
第三行：44 = 24 + 13 + 7
第四行：29 = 15 + 8 + 4 + 2
第五行：16 = 8 + 4 + 2 + 1 + 1
怎么解釋這個現象呢？我們再來仔細考慮一下擲硬幣的過程，為方便在下文中用1表示字，用0表示花，于是我們的目標是要恰好使用m次投擲，得到連續的n個1.
若第一次的結果為 0，那么剩下的任務就是恰好使用m-1次投擲得到到連續的n個1.
若前兩次的結果為 10, 那么剩下的任務就是恰好使用m-2次投擲得到到連續的n個1.
若前三次的結果為 110, 那么剩下的任務就是恰好使用m-3次投擲得到到連續的n個1.
若前四次的結果為 1110, 那么剩下的任務就是恰好使用m-4次投擲得到到連續的n個1.
…
若前n-1次的結果為 1…10(n-2個1), 那么剩下的任務就是恰好使用1次投擲得到到連續的n個1.
你或許已經看出來了，這里實際上是在枚舉首次出現0的位置。由于首個0出現在位置i的概率為1/2^i，于是得到Pnm的遞推公式
于是根據初始條件：，，我們可以推出所有事件的概率。現在來推一下概率生成函數，設需要得到連續n個1的投擲數的概率生成函數為Gn(z)，于是有
根據上面的遞推公式和初始條件，可以得到
于是可解得
分別代入 n = 1 和 n = 2 可以得到
以我們前面得到的結果一致，這證明這個概率生成函數的確是正確的。有了生成函數后，我們又多了一種計算期望的方式
而方差也可以非常容易的得到
至此，這個拋硬幣的問題終于應該算是被完全解決了，完。
題目： 一個骰子，6面，1個面是 1， 2個面是2， 3個面是3， 問平均擲多少次能使1、2、3都至少出現一次。
方法： 面對面試概率題幾乎屢試不爽的分叉樹遞歸列方程法。
這是一個求數學期望的問題，最終是求1，2，3出現至少一次的最短長度的期望。
這樣分叉樹的每個節點是一個期望狀態，而每個分叉是一次投擲結果。將后續期望出現1、2、3各至少一次的情形記作L123（即題目所求），將后續期望出現1、2各至少一次（3無關）情形記作L12，而1至少一次（2，3無關）情形L1，其余數值符號類推，則樹結構如下（列出4級結構已經足夠）：
| 第一級（樹根） | 第二級 | 第三級 | 第四級別 |
| L123 | 擲1->L23 | 擲1->L23 | 同狀態 |
| ? | ? | 擲2->L3 | 根據投擲結果，或繼續期待L3，或已經達到目標 |
| ? | ? | 擲3->L2 | 根據投擲結果，或繼續期待L2，或已經達到目標 |
| ? | 擲2->L13 | 擲1->L3 | 根據投擲結果，或繼續期待L3，或已經達到目標 |
| ? | ? | 擲2->L13 | 同狀態 |
| ? | ? | 擲3->L1 | 根據投擲結果，或繼續期待L1，或已經達到目標 |
| ? | 擲3->L12 | 擲1->L2 | 根據投擲結果，或繼續期待L2，或已經達到目標 |
| ? | ? | 擲2->L1 | 根據投擲結果，或繼續期待L1，或已經達到目標 |
| ? | ? | 擲3->L12 | 同狀態 |
接下來，就是要排出方程，因為一共7個未知數，如果排出7個線性方程就能解決問題。
這方程組里的未知數對應上述的狀態，而其數值則是一個對長度（投擲次數）的數學期望。
根據這個樹狀結構和其中的遞歸關系，這個方程組就是：
L123?= p1?(L23+ 1) +?p2?(L13+1) + p3?(L12?+ 1) = p1?L23?+p2?L13+?p3?L12?+ 1
（以這個L123為例，解釋，投擲1的概率是p1而由此得到的結果是需要期待后續2和3各至少出現一次，于是長度期望是L23+ 1，加1是因為投擲了一次，亦即即增進一級）
L23?=?p1?L23?+p2?L3+?p3?L2?+ 1
L13?=?p1?L3?+p2?L13+?p3?L1?+ 1
L12?=?p1?L2?+p2?L1+?p3?L12?+ 1
L1?=p1?+?p2?L1+?p3?L1?+ 1
（這里實際上是?L1?=p1?·1 + p2?(L1+1) + p3?(L1?+1)?=p2?L1+?p3?L1?+ 1，因為對L1情形，如果投了1就目的達到終止了）
L2?=p2?+?p1?L2?+??p3?L2?+ 1
L3?=p3?+?p1?L3?+p2?L3+ 1
其中?p1，p2?和?p3分別是擲出1，2和3的概率，即1/6，1/3，1/2。
于是求解這個方程，得到：
L1?= 6，?L2?= 3，?L3?= 2
L12?= 7，?L13?= 13/2，?L23?= 19/56
L123?=?219/30 = 7.3?259/36 ~= 7.14
故以上如果沒有計算錯誤，該題結果是，平均擲7.3?約7.14次可出現這些面值各至少一次。
（轉自：http://www.cnblogs.com/atyuwen/archive/2010/09/12/coin.html）
問題：
一個骰子，6面，1個面是 1， 2個面是2， 3個面是3， 問平均擲多少次能使1,2,3都至少出現一次？
一共有三種方法可以解此問題：概率公式、分叉樹遞歸列方程法、指示器變量法。
1. 方法一：概率公式
化為概率的表示是：
1發生 的概率是1/6,? 2發生的概率是2/6,? 3發生的概率是3/6，求1,2,3至少出現一次的投擲次數的期望。
思路：
第一二次肯定不可能出現這種情況
第x(x?>?2)次三個都出現的情況分三種（x?^?y?表示?x?的?y?次方）
1：第x次出現?1，那么前面出現的必然是?2?和?3?，且至少出現一次???
???出現1的概率為?1?/?6，前面x-1次不出現1的概率為(1?-?1?/?6)?^?(x?-?1)，但是其中包含全是?2?和全是?3?的情況，去掉全?2?的概率?(1?/?2)?^?(x?-?1)，全部為3的概率(1?/?3)?^?(x?-?1)，那么情況?1?的概率為?((1?-?1?/?6)?^?(x?-?1)?-?(1?/?2)?^?(x?-?1)?-?(1?/?3)?^?(x?-?1))?*?(1?/?6)
2：第x次出現2，那么前面出現的必然是?1?和?3?，且至少出現一次
???同樣，概率為?((1?-?1?/?3)?^?(x?-?1)?-?(1?/?2)?^?(x?-?1)?-?(1?/?6)?^?(x?-?1))?*?(1?/?3)
3：第x次出現3，那么前面出現的必然是?1?和?2?，且至少出現一次
???同樣，概率為?((1?-?1?/?2)?^?(x?-?1)?-?(1?/?3)?^?(x?-?1)?-?(1?/?6)?^?(x?-?1))?*?(1?/?2)
p(x)就為上面三種情況的和
那么，根據期望公式，平均值就等于從x?=?3?到?n（無窮）求(x?*?p(x))的和
利用錯位相減法計算極限值
到此可以算出期望為7.3。
2. 方法二：分叉樹遞歸列方程法
方法： 面對面試概率題幾乎屢試不爽的分叉樹遞歸列方程法。
這是一個求數學期望的問題，最終是求1，2，3出現至少一次的最短長度的期望。
這樣分叉樹的每個節點是一個期望狀態，而每個分叉是一次投擲結果。將后續期望出現1、2、3各至少一次的情形記作L123（即題目所求），將后續期望出現1、2各至少一次（3無關）情形記作L12，而1至少一次（2，3無關）情形L1，其余數值符號類推，則樹結構如下（列出4級結構已經足夠）：
| 第一級（樹根） | 第二級 | 第三級 | 第四級別 |
| L123 | 擲1->L23 | 擲1->L23 | 同狀態 |
| ? | ? | 擲2->L3 | 根據投擲結果，或繼續期待L3，或已經達到目標 |
| ? | ? | 擲3->L2 | 根據投擲結果，或繼續期待L2，或已經達到目標 |
| ? | 擲2->L13 | 擲1->L3 | 根據投擲結果，或繼續期待L3，或已經達到目標 |
| ? | ? | 擲2->L13 | 同狀態 |
| ? | ? | 擲3->L1 | 根據投擲結果，或繼續期待L1，或已經達到目標 |
| ? | 擲3->L12 | 擲1->L2 | 根據投擲結果，或繼續期待L2，或已經達到目標 |
| ? | ? | 擲2->L1 | 根據投擲結果，或繼續期待L1，或已經達到目標 |
| ? | ? | 擲3->L12 | 同狀態 |
接下來，就是要排出方程，因為一共7個未知數，如果排出7個線性方程就能解決問題。
這方程組里的未知數對應上述的狀態，而其數值則是一個對長度（投擲次數）的數學期望。
根據這個樹狀結構和其中的遞歸關系，這個方程組就是：
L123?= p1?(L23+ 1) +?p2?(L13+1) + p3?(L12?+ 1) = p1?L23?+p2?L13+?p3?L12?+ 1
（以這個L123為例，解釋，投擲1的概率是p1而由此得到的結果是需要期待后續2和3各至少出現一次，于是長度期望是L23+ 1，加1是因為投擲了一次，亦即即增進一級）
L23?=?p1?L23?+p2?L3+?p3?L2?+ 1
L13?=?p1?L3?+p2?L13+?p3?L1?+ 1
L12?=?p1?L2?+p2?L1+?p3?L12?+ 1
L1?=p2?L1+?p3?L1?+ 1
（這里實際上是?L1?=p1?·1 + p2?(L1+1) + p3?(L1?+1)?=p2?L1+?p3?L1?+ 1，因為對L1情形，如果投了1就目的達到終止了）
L2?=?p1?L2?+?p3?L2?+ 1
L3?=?p1?L3?+p2?L3+ 1
其中p1，p2和p3分別是擲出1，2和3的概率，即1/6，1/3，1/2。
于是求解這個方程，得到：
L1?= 6，?L2?= 3，?L3?= 2
L12?= 7，?L13?= 13/2，?L23?= 19/5
L123?=?219/30 = 7.3?
平均擲7.3 次可出現這些面值各至少一次。
3. 方法三：指示器變量法
【另一解法】感謝4樓aaaxingruiaaa同學提供的答案（指示器變量法），整理如下：
定義隨機變量Xn，其可能值為0或1，其值為1表示“前n次擲骰子，1，2，3沒能都至少出現一次”的事件，其值為0表示這個事件沒有發生，即“前n次擲骰子，1，2，3各至少出現一次”。
令pn為“擲n次骰子，1，2，3沒能都至少出現一次”的概率，所以顯然pn?= Pr{Xn=1}，于是pn?= 1·Pr{Xn=1} + 0·Pr{Xn=1} = E[Xn]，即這個隨機變量的數學期望。
令隨機變量X表示1，2，3剛好全部出現過需要的投擲次數。可見題目要求的就是E[X]。
關鍵等式：X =?Sigma(n=0 to?Inf;?Xn) （這里Sigma是求和號，求和范圍是n從0到無窮大）
說明一下，等式兩邊都是隨機變量，假設對于某個隨機實例（例如，這里指一次具體的投擲序列），其對應事件是：“投了K次恰好1，2，3都出現了”，于是等式左邊顯然等于K；而等式右邊，對于n < K，由于這些項的對應定義事件發生了（即1，2，3沒能出現），所以他們的實例值是1，而對于n?K，則由于對應定義事件都沒發生，實例值為0，可見這個和也是K。故兩側相等。（為了達到這個相等關系，可以看出需要把X0包含在內的必要性）
值得注意的是（但對于解這道題也可以不去注意，但注意一下有利于比較深入地理解），對n < 3，Xn顯然恒為1。而對于n?3，這些隨機變量不是獨立的。他們的相關性是不容易求出的，唯一容易知道的是，當序列中一個項為0時，其后的項均為0。好在對于這題我們不需要擔憂這個相關性。
由于數學期望的加性與隨機變量的相關性無關（這是數學期望一個很令人高興的性質），所以即便這樣，E[X]也能容易求出：
E[X] =?Sigma(n=0 to Inf; E[Xn]) =?Sigma(n=0 to?Inf;?pn)
pn的比較直觀的求法也由aaaxingruiaaa同學提供了，即所謂容斥原理。稍微解釋一下，由于pn考慮的是n次投擲三者沒有全部出現，于是就是其中兩者出現或僅一者出現。假設單次投擲1，2和3出現的概率分別為：r1，r2和r3。于是(r1+r2)n表征n次投擲只出現1或2的概率，這其中包括了出現全1和全2的情形，于是求pn可由這樣的項求和并剔除重復計算的單面值情形，于是：
pn?= (r1+r2)n+ (r1+r3)n+ (r2+r3)n-r1n-r2n-r3n，當n > 0；?而p0?= 1 （由定義；同時也可以檢驗看出，這個pn在n為1和2的時候都是1）
于是由等比級數（等比數列求和）公式：
E[X] =?1 + Sigma(n=1 to Inf; (r1+r2)n+ (r1+r3)n+ (r2+r3)n-r1n-r2n-r3n= 1 + (1 -?r3) /?r3?+ (1 -?r2) /?r2?+ (1 -?r1) /?r1-?r1?/ (1 -?r1) -?r2?/ (1 -r2) -r3?/ (1 -?r3) = 7.3
http://blog.csdn.net/quanben/article/details/6918209
假設有一個硬幣，拋出字（背面）和花（正面）的概率都是0.5，而且每次拋硬幣與前次結果無關。現在做一個游戲，連續地拋這個硬幣，直到連續出現兩次字為止，問平均要拋多少次才能結束游戲？注意，一旦連續拋出兩個“字”向上游戲就結束了，不用繼續拋。
上面這個題目我第一次見到是在pongba的TopLanguage的一次討論上，提出問題的人為Shuo Chen，當時我給出了一個解法，自認為已經相當簡單了，先來考慮一下拋硬幣的過程：首先先拋一枚硬幣，如果是花，那么需要重頭開始；如果是字，那么再拋一枚硬幣，新拋的這枚如果也是字，則游戲結束，如果是花，那么又需要重頭開始。根據這個過程，設拋硬幣的期望次數為T，可以得到關系：
T = 1 + 0.5T + 0.5( 1 + 0.5 * 0 + 0.5T)?
解方程可得到 T = 6。
或者根據公式，需要連續拋出n個字的一般情形，結果相當簡潔：Tn = 2^(n+1) - 2，其中Tn為首次出現連續的n個字的期望投擲數。
公式證明如下：
方法一：
設出現連續k次正面的期望是a[k]
則出現連續k+1次正面的期望為a[k+1]
在出現連續k次正面后，有下面幾種情況：
i)下一個是正面，概率1/2，總次數a[k]+1;
ii)下一個是反面，概率1/2，則接下來平均仍需a[k+1],總次數a[k]+1+a[k+1]。
因此a[k+1]=(a[k]+1)/2+(a[k]+1+a[k+1])/2
整理得(a[k+1]+2)/(a[k]+2)=2
a[n]=(a[1]+2)*2^(n-1)-2
顯然a[1]=2;a[n]=2^(n+1)-2
方法二：
轉自matrix67 ?http://www.matrix67.com/blog/archives/3638
設想有這么一家賭場，賭場里只有一個游戲：猜正反。游戲規則很簡單，玩家下注 x 元錢，賭正面或者反面；然后莊家拋出硬幣，如果玩家猜錯了他就會輸掉這 x 元，如果玩家猜對了他將得到 2x 元的回報（也就是凈賺 x 元）。
讓我們假設每一回合開始之前，都會有一個新的玩家加入游戲，與仍然在場的玩家們一同賭博。每個玩家最初都只有 1 元錢，并且他們的策略也都是相同的：每回都把當前身上的所有錢都押在正面上。運氣好的話，從加入游戲開始，莊家拋擲出來的硬幣一直是正面，這個玩家就會一直贏錢；如果連續 n 次硬幣都是正面朝上，他將會贏得 2^n 元錢。這個 2^n 就是賭場老板的心理承受極限——一旦有人贏到了 2^n 元錢，賭場老板便會下令停止游戲，關閉賭場。讓我們來看看，在這場游戲中存在哪些有趣的結論。
首先，連續 n 次正面朝上的概率雖然很小，但確實是有可能發生的，因此總有一個時候賭場將被關閉。賭場關閉之時，唯一賺到錢的人就是賭場關閉前最后進來的那 n 個人。每個人都只花費了 1 元錢，但他們卻贏得了不同數量的錢。其中，最后進來的人贏回了 2 元，倒數第二進來的人贏回了 4 元，倒數第 n 進來的人則贏得了 2^n 元（他就是賭場關閉的原因），他們一共賺取了 2 + 4 + 8 + … + 2^n = 2^(n+1) - 2 元。其余所有人初始時的 1 元錢都打了水漂，因為沒有人挺過了倒數第 n + 1 輪游戲。
另外，由于這個游戲是一個完全公平的游戲，因此賭場的盈虧應該是平衡的。換句話說，有多少錢流出了賭場，就該有多少的錢流進賭場。既然賭場的錢最終被贏走了 2^(n+1) - 2 元，因此賭場的期望收入也就是 2^(n+1) - 2 元。而賭場收入的唯一來源是每人 1 元的初始賭金，這就表明游戲者的期望數量是 2^(n+1) - 2 個。換句話說，游戲平均進行了 2^(n+1) - 2 次。再換句話說，平均拋擲 2^(n+1) - 2 次硬幣才會出現 n 連正的情況。
總結
以上是生活随笔為你收集整理的抛硬币 直到连续出现两次字为止的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： C++ struct construct
- 下一篇： google面试