擲1000次硬幣，出現連續十次（或以上）正面的概率是多少？

1樓：

高票答案說得很好，唯一問題就是泰勒展開那裡，求1000次導數太不爽了。

這裡有乙個新思路，更適合計算。

已知n,m，在m固定的情況下，設f(n)為「連續扔n次硬幣，其中沒有出現m次連續正面的概率」。則我們要求的的概率p=1-f(n)

當n∈[0,m-1]時，投硬幣的次數不夠多，顯然 f(n)=1

當n>=m時，考慮最後m次擲硬幣結果，可以分成以下幾種情況：

情況（1）：最後1位為「反」。概率為：0.5

情況（2）：倒數第2位為「反」，倒數第1位為「正」。概率為：0.5^2

情況（3）：倒數第3位為「反」，倒數第1~2位為「正」。概率：0.5^3

情況（4）：倒數第4位為「反」，倒數第1~3位為「正」。概率：0.5^4

情況（5）：倒數第5位為「反」，倒數第1~4位為「正」。概率：0.5^5

……情況（m）：倒數第m位為「反」，倒數第1~m-1位為「正」。概率0.5^m

情況（m+1）：倒數第1~m位都為「正」。概率0.5^m

其中，最後一種情況下已經產生m個連續「正」了，所以這種情況下「沒有出現m次連續正面的概率」為0。

其它情況下，對於情況（x）（x∈[1,m]），此時最後x位中沒有不存在連續m次「正」，而且倒數第x位是「反」，也就是說結尾的這些「正」不會延長前面部分的連續「正」的長度。

也就是說，當確定為情況（x）時，這n次「沒有出現m次連續正面的概率」就等於前面n-x次「沒有出現m次連續正面的概率」。

出現情況（x）的概率為0.5^x，前面n-x次「沒有出現m次連續正面的概率」為f(n-x)。所以我們可以得到遞推式：

如果願意的話甚至可以據此求出通項公式。

但是這種式子已經比較簡潔了，用程式計算也足夠方便了，時間複雜度是O(mn)

程式如下(c語言)：

#include

int main() {

int n,m,i,j;

double f[2000];

n=1000;

m=10;

for (i=0;i

輸出得m=10,n=1000時，P=0.385450

2樓：終軍弱冠

受到 @又紅又正的啟發用生成函式，正好自己一直在自學解析組合，把這個問題當成一道習題做一下，順便介紹乙個被稱為Symbolic method的求解計數問題的方法（本質上和又紅又正的解法是一樣的），該方法經常用於求解字串和樹形結構的計數問題，此方法的方便之處在於可以通過組合類的集合化表述「直接」得到生成函式的方程。在表述上這裡可能不太嚴謹，但是理解其思想更重要而且有趣，最後得到的推廣問題的近似結果也有點意思。

考慮字符集上不包含連續10個「正」的字串組成的組合類S，S(z)表示該組合類的生成函式，那麼S(z)中z^n的係數sn等於長度為n的不包含連續10個「正」的字串的數量。原問題的解可以寫成

.為了求解S(z)，我們再定義兩個組合類∶

組合類R表示，其生成函式為

.組合類T表示，其生成函式為

.觀察到每個S中的字串可以用R中的若干個字串和T中的乙個字串拼接而成，將其表述成集合形式

.其中的叉乘×可以理解成笛卡爾積，而 SEQ(R)= ε +R +R×R +R×R×R+...。了解正規表示式的同學可以簡單地理解為S=[R]* [T]。

應用symbolic method將這個集合表述翻譯為對應生成函式的方程

.這裡SEQ(R)的生成函式被翻譯成了1/(1-R(z))，笛卡爾積被翻譯為普通的乘積。然後帶入R(z)和T(z)，得到S(z)

.至於如何得到S(z)中z^n的係數，又紅又正已經說了用Taylor展開，這裡我再說乙個利用函式的奇點（singularity）漸進估計係數的方法。係數的精確值計算起來可能很煩，我們轉而去估計係數的近似值。

將函式放到復平面上來考慮，由於S(z)是有理函式，所以S(z)的奇點就是分母為0的點（即極點Pole）。在這些極點附近函式成指數增長趨勢直到無窮，係數可以表示成若干個指數增長型函式的和，其中那個底數最大的指數增長型函式是增長最快的，而底數正是極點模的倒數。所以需要尋找函式中分母的模最小的零點。

解方程 1-2z+z^11=0，得到模最小的根z0（約為0.50024546），在z0點附近S(z)可以用乙個形入 c/(z-z0) 的函式逼近

.利用冪級數展開得到數列sn的漸進近似表示式

.回到原題中n=1000，計算sn的近似值6.5849887*10^300（準確值是6.

5849588*10^300），原題概率的近似值0.38544696（準確值是0.38544975）。

誤差還不算大。

如果我們再考慮一下推廣的情況（擲n次硬幣，出現連續m次或以上正面的概率是多少？），還可以發現乙個有意思的東西。

同樣定義不包含連續m個「正」的字串組成的組合類U，解出U的生成函式

.類似地用奇點法得到un的漸進近似表示式

.其中z0是方程1-2z+z^(m+1)=0的最小正實數根。然後我們再做一點近似，由於z0接近1/2，我們粗糙地認為z0=1/2+x，x是乙個小量，代入方程得到

接著計算概率，m和n足夠大的話估計是這樣的

這樣就和e扯上關係了！原題中m=10, n=1000，代入後 1-1/e^(1000/2048) 約為0.38631975（準確值是0.

38544975）。可以看到誤差還是有一些的，不過當m和n都足夠大的話應該就會比較接近的吧。

總之，這裡用到了symbolic method和奇點近似，是解析組合（Analytic combinatorics）的兩個主題，算是解析組合的完整應用了吧。

3樓：LLAA

受 @林洵邀來答一發

設事件擲次硬幣，出現連續10次硬幣向上；事件前枚硬幣為正，第枚硬幣為反，其中；事件前10枚硬幣均為正。則與構成一完備事件群。

當時，由全概率公式，可得

而，，，

於是得到遞推公式

最後，乙個迴圈(其實我一開始寫了個遞迴然後算了15分鐘沒出結果←_←)：

4樓：

這道題基本算月經題，用馬爾科夫狀態轉移矩陣來做，簡單易懂。具體做法別人已經貼了，我就不貼了。相似的問題還有: 玩一場遊戲勝率是60%，打n場，出現連敗m場的概率是多少？

5樓：塞申斯

雖然看的腦細胞炸裂都沒看懂，但是就是針對同乙個有趣的問題眾多人提供不同認證方法和思路，這才是真正的知乎，也許大家心目中就想要這麼純淨的地方吧。 @又紅又正

@李中國

@Lightwing

@雨過星辰

6樓：白鹿

1.大學課程裡的概率學，有一章是泰勒公式相關展開用法，好像是這個叫法？用這個可以解，等有時間上計算圖

2.畫馬爾科夫鏈，看狀態矩陣。

3.剛才看到大神的遞迴演算法…抱頭痛哭…

不管如何，先占個坑

7樓：黎尋

誒嘿手機知乎怎麼發圖呀…

各位答主的方法基本都看不懂orz

介紹乙個高中知識範疇內的方法~

我們設擲n枚硬幣時沒有出現連續十枚向上的情形數是an則有：a1=2,a2=4…a9=512,a10=1023an=an-1+an-2+…+an-10 (n＞10,n∈Z)理解這個遞推式的話，可以想成對於an-i個排列方式的每一種都在後面加1黑i-1白，這樣滿足條件還是一一對映，所以加起來就是an的個數~

然後純數學的方法需要一些高中MO的手法，解特徵根方程求通項，算出a1000後計算概率

當然，不如直接寫個程式遞推，時間複雜度O(n)，空間複雜度O(11)以上。

8樓：stonepage

這個感覺像是oi的一道dp題

然後做一點微小的變換就可以矩陣快速冪優化

把10換成100 把1000換成1e18就更像了一筆爛字orz這個矩陣其實就是

【擲1000次硬幣，出現連續十次（或以上）正面的概率是多少？】匿名使用者：… https://www.

（分享自知乎網）

的那個矩陣

這就做為乙個證明吧

9樓：

現在的題主真是懶,維基一下不就有公式了....

令p=0.5,n=1000,m=10;幫你手動把這個公式輸進MathematicaP[n_,m_,p_]:=NSum[(-1)^(j+1)*(1-p)^(j-1)*p^(j*m)*Binomial[n-j*m,j-11-p)*(-(j*m)+n+1))/j+p),]

Chop@P[1000,10,0.5]

(*[Out] = 0.38545*)

思路就是生成函式,沒啥好說的...

其實截斷掉後面95%的項對結果一點影響都沒有...

10樓：

高票答案@又紅又正的做法很好，我非常敬佩，但是敘述有些艱澀，很難搞懂。事實上這個問題完全是高中數競範圍內的計數問題，意味著這個問題我可以給看不懂高票答案的人講乙個故事，用這種辦法說明白高票答案的思路。

一

對於一種確定的擲1000次的方法，我將其寫成,其中到每一項或為零，或為一。例如：代表著1000次擲骰子的結果是第一次為正面，其餘為背面。顯然，這樣的有種。

二

現在我們來對進行改寫（用一種瀰漫著濃厚的高中競賽味道的方法）。

此時我把A後面補乙個零，然後試圖將其分成若干段。

分法如下：使得每一段由零結束，並且這個段恰好只有乙個零，然後將每段的長度依次寫下形成乙個新的數列。記這個新列為。

例如：，此時我們注意到顯然B的各項係數之和為1001（因為我補了乙個0）。

三

我們觀察這個B。不難想清楚，乙個A恰好對應乙個B，不同的A一定對應不同的B。因此，我們構造了這樣的A到B的一一對映。

而乙個B所要求的條件無非三條：長度為1-1001，每項都是正整數，各項係數之和為1001。我們也可以發現，任取這樣的要求的乙個B，恰好存在原先的乙個A與之一一對應。

因此不同的B的數量與不同的A的數量完全相同，都是種

這樣，我對所有不同的A標號為，然後，對都成立。

四

現在問題可以大大地簡化了。如果一種擲法滿足了

擲1000次硬幣，出現連續十次（或以上）正面那麼一定有：它對應的中至少有一項大於等於11

反之，如果不滿足題意，那麼它對應的每項都不超過10。

五

理解了我的約定之後，我們考慮這樣乙個函式：，我可以把它改寫成這樣的形式：，其中共有k個括號。

現在考慮的1001次項係數，記為，我們想一想是怎麼出現的呢？

我們這麼想：把這個式子不管三七二十一強行展開，不合併同類項之前就是乙個個不同的x的若干次方加起來的超級長的式子。現在我們考慮這個式子中的所有形如的項，我們可以想象這些都是由每乙個括號中各取一項乘起來得到的。

舉例：第乙個括號取，...，第k個式子取，那麼這些數乘起來構成了，那麼肯定有，所有這樣的不同總共的個數便一定是

六

如果你還沒有發現什麼蹊蹺的話，把第五段和第三段中B滿足的性質溫習一遍，然後你就會發現：原來乙個不就是乙個長度為k，並且每一項都不超過10的B麼！這樣看來，所有每一項都不超過10的B的數量，便是把所有「乙個長度為k，並且每一項都不超過10的B的數量」按照k=1,2,...

,1001都加起來。

因此，我們也就明白了：如果把不滿足題目條件的排列數記作α，那麼α便等於

七

我們注意到：的定義是的1001次項係數，那麼既然，那麼α就是式子的1001次項係數。注意到其實的k大於等於1002的時候它的1001次項係數就是零，因此無妨將記作，它的1001次項係數照樣是阿爾法。

八

現在我們來計算阿爾法。高票答案已經說得很好了：

由於直接計算前面的係數有點困難，我們先利用等比數列的公式計算

然後對其在x=0處做Taylor展開，取1001次項係數，得到前面的係數記為α=這樣，一共有α種排列A不滿足題意，而一共有種排列A，那麼顯然

最後的結果為最後，感謝@又紅又正答主的思路，站在巨人的肩膀上很開心，希望有更多的人能夠理解這種思路的想法。

擲1000次硬幣，出現連續十次（或以上）正面的概率是多少？

連續擲硬幣直至出現連續4次反面所需投擲次數，其數學期望是16次嗎？

每天連續擲硬幣，直到連續出現兩次正面就停止，第二天繼續，連續一年時間，擲出正面的期望值是多少？

1個骰子連續擲10000次，出現一次以上連續6個6的概率是多少？

其他用戶還看了：