連續拋硬幣，遇到「正反反」停止和遇到「正反正」停止，兩種情況下拋硬幣的平均次數是否相同？

12-14

事件A，拋硬幣直至遇到連續的三次是「正反反」停止，記錄次數為N（共拋了N+2次）。事件B，拋硬幣直至遇到連續的三次是「正反正」停止，記錄次數為M（共拋了M+2次）。儘可能多的重複事件A得到N的平均值是多少？重複事件B得到的M的平均值是多少？N的均值與M的均值是否相等？

列一個期望的方程組可以得到答案：
我們假設exp[0]表示從還沒開始投到停止的期望次數，exp[1]表示從"正"到停止的期望次數，exp[2]表示"正反"到停止的期望次數，exp[3]表示從「正反反」到停止的期望次數。顯然，exp[0]就是我們需要的答案，而exp[3]等於0.

exp[0] = (exp[1] + 1) * 1/2 + (exp[0] + 1) * 1/2 ------ (1)
exp[1] = (exp[1] + 1) * 1/2 + (exp[2] + 1) * 1/2 ------ (2)
exp[2] = (exp[1] + 1) * 1/2 + (exp[3] + 1) * 1/2 ------ (3)
exp[3] = 0 ------ (4)

每個式子的含義就是從當前的狀態投一次幣會到達哪個狀態。

這樣解得： exp[0] = 8.

類似的方法可以求得"正反正"的期望即：遇到"正反正"停止的期望是10.兩者不相同。

不相等
出現【正反】的概率是一樣的，之後
正反反」錯了可以繼續從正開始「正反正錯了就要重頭再來

正反反的出現概率高

其實對於丟硬幣出現某個序列的期望值完全可以不必動用自動機類型的求法，有一種簡便快捷的方法，原理可以參見《具體數學》8.4 Flipping Coins。

方法簡要說明如下：
假設需要出現的序列是A，長度為m，A的頭k個元素組成的序列是 $A^{(k)}$ ，後k個元素組成序列是 $A_{(k)}$ ,那麼結果就是 $sum_{k=1}^{m}{2^{k}[A^{(k)}=A_{(k)}]}$ ，方括弧運算符表示裡面邏輯為true時為1，false時為0。

用於本提問的問題：
對於「正反反」，期望步數為[正=反]*2+[正反=反反]*4+[正反反=正反反]*8=0+0+8=8；
對於「正反正」，期望步數為[正=正]*2+[正反=反正]*4+[正反反=正反正]*8=2+0+8=10；

通過鞅(martingale)來解此題：假設拋出「正」的概率為p，那麼

「正反反」：期望為 $frac{1}{p^3}$
「正反正」：期望為 $frac{1}{p^3}+frac{1}{p}$

假設每次拋出「正」和「反」的概率相同，即 $p=frac{1}{2}$ ，則兩者的期望分別等於8和10。

matrix67的博客說過這個問題：Penney 的遊戲：正所謂後發制人，先發制於人

如果說還有什麼有意思的地方的話，大概是考慮KMP演算法和這道題的聯繫。

一樣

用窮舉法得出結果為：前者為6次，後者為8次。

註：
1. 使用問題中N+2的統計方式，如果算上前兩次，結果應該分別為8和10。
2. 正=&>1 反=&>0。所以「正反反」為100, 「正反正」為101。

代碼如下：

def roll(re)
i = -2
n = 0
until n==re do
n = ((n0b11)&<&<1)+rand(0..1)
i += 1
end
i
end

def batch(re)
total = 0
iter = 999999
print ">&>&>尋找#{re.to_s(2)}&>&>&>"
iter.times do |i|
total += roll(re)
end
print "平均: #{total/iter.to_f}次/輪."
end

batch(0b100)
batch(0b101)