扔硬幣遊戲,有關最長連續正面朝上和反面朝上長度的函數的期望值?

遊戲扔硬幣N次(N&<1000),設最長連續正面朝上的序列長度為H,最長連續反面朝上的序列長度為T。如果H&>T, 得到sqrt(H-T);如果H&<=T, 得到0。
求該遊戲精確的價格p(N)。
ps1: 不能用simulation求解
ps2: 我寫了一個程序暴力列舉求解,想問問大家有沒有比較巧妙的想法或者演算法?


你這個問題很有趣....

我想了一會兒沒想出來簡單方法, 覺得自己學了這麼多年統計還是這麼笨....

然後搜出了這篇 paper...

讀完之後發現, 什麼嘛! 原來 paper 里也是暴力推出來的... 我要報警了

這篇 paper 里介紹了連扔 n 次硬幣的最長正反面序列長度的分布問題, 還給你算出了期望和方差, 最後推廣到了 n 無窮大的情形.

R_n 是扔 n 次硬幣之後的最長正面序列長度. 下圖是 n 等於 50, 100, 200時候的分布直方圖 (暴力求和算出來的)

這是期望和方差

這是推廣之後的 limiting distribution

這類問題有什麼已知的應用呢?

paper 里說, 這類問題屬於"Runs Theory" 研究的對象, 在 DNA 序列分析裡面可以用來尋找需要的 pattern..

論文鏈接: http://gato-docs.its.txstate.edu/mathworks/DistributionOfLongestRun.pdf

更多請看這裡( combinatorics).. 這個問題在快300年前就被解決了, 用的是母函數方法. 這裡給出了精確表達式.

看完之後發現自己真特么水... 還需要再學習學習..

到頭來還是沒有解決題主的問題...

(我只是一個互聯網的搬♂ 運♂ 工)


推薦閱讀:

有什麼好看的數學書推薦么?
二次函數解析式怎麼配方?
圓桌上1000個人輪流開槍,最後活下來的是幾號?
此圖像的參數方程應該是什麼?
數學中的「數」如果按照其所描述的範圍,由小到大應該如何排列?

TAG:演算法 | 數學 | 趣味數學 | 概率 | 概率論 |