200次翻轉的最長預期連線

我正試圖計算200次硬幣翻轉中使用python的最長連續首長連線的預期值。我想出了一個代碼，我認爲這個代碼是正確的，但由於計算和數據存儲量的需要，效率並不高，我想知道是否有人能夠幫助我解決這個問題，使其更快，更高效（我在上一學期只學習了一門Python課程，而沒有任何關於此主題的知識）。200次翻轉的最長預期連線

我的代碼是

import numpy as np 
from itertools import permutations 

counter = 0 
sett = 0 
rle = [] 

matrix = np.zeros(200) 

for i in range (0,200): 
    matrix[i] = 1 
    for j in permutations(matrix): 
     for k in j: 
      if k == 1: 
       counter += 1 
      else: 
       if counter > sett: 
        sett == counter 
       counter == 0 
     rle.append(sett)

發現RLE後，我迭代它得到其長度有多少條紋也有，他們的總和除以2^200分會給我的預期值I正在尋找。

在此先感謝您的幫助，非常感謝！

來源

2017-02-25 Alessandro Gravellini

你有200！（幾乎8e374）排列每個矩陣，所以你的整個生活將不足以嘗試所有。你最好嘗試一種完全不同的方法！ –

最長連勝的期望值是指最可能連續得到的頭數？ – frederick99

我仍然沒有看到我的答案中出現了什麼問題，但我會閱讀它。現在我已經刪除了我的答案。 – frederick99

這是一個稍微不同的問題的答案。但是，因爲我已經投入了一個半小時的時間，所以我不想把它刮掉。

讓E(k)表示一個k頭連勝，即你從第一折騰起連續k頭。

E(0): T { another 199 tosses that we do not care about } 
E(1): H T { another 198 tosses... } 
. 
. 
E(198): { 198 heads } T H 
E(199): { 199 heads } T 
E(200): { 200 heads }

注意P(0) = 0.5，這是P(tails in first toss)
而P(1) = 0.25，即P(heads in first toss and tails in the second)

P(0) = 2**-1 
P(1) = 2**-2 
. 
. 
. 
P(198) = 2**-199 
P(199) = 2**-200 
P(200) = 2**-200 #same as P(199)

如果你擲硬幣2**200倍這意味着，你會得到

E(0) 2**199 times 
E(1) 2**198 times 
. 
. 
E(198) 2**1 times 
E(199) 2**0 times and 
E(200) 2**0 times.

因此，預期值減少到

(0*(2**199) + 1*(2**198) + 2*(2**197) + ... + 198*(2**1) + 199*(2**0) + 200*(2**0))/2**200

這個數字幾乎是等於1

Expected_value = 1 - 2**-200

我是如何得到的差異。

>>> diff = 2**200 - sum([ k*(2**(199-k)) for k in range(200)], 200*(2**0)) 
>>> diff 
1

這可以推廣到n擲作爲

f(n) = 1 - 2**(-n)

來源

2017-02-25 17:02:35 frederick99

我想你誤解了這個問題。 OP正在尋找最長連勝時間長度的[期望值]（https://en.wikipedia.org/wiki/Expected_value）。 –

預計價值不是意味着最大概率的那個？ @ das-g – frederick99

我明白了，謝謝！ – frederick99

你不必去嘗試所有的排列（其實你不能），但你可以做一個簡單的蒙特卡洛風格的模擬。重複200次硬幣翻轉多次。平均你獲得的最長條紋的長度，這將是一個很好的預期值的近似值。

def oneTrial (noOfCoinFlips): 
    s = numpy.random.binomial(1, 0.5, noOfCoinFlips) 
    maxCount = 0 
    count = 0 
    for x in s: 
     if x == 1: 
      count += 1 
     if x == 0: 
      count = 0 
     maxCount = max(maxCount, count) 
    return maxCount 


numpy.mean([oneTrial(200) for x in range(10000)]) 

Output: 6.9843

另請參閱this thread準確計算而不使用Python模擬。

來源

2017-02-25 17:54:34

200次翻轉的最長預期連線

回答

相關問題