200コインフリップで予想される最も長いヘッドストリーク

Question

私は、200コインフリップで最も長い連続ヘッドストリークの期待値を、Pythonを使って計算しようとしていました。私は仕事が正しいと思うコードを思いついたが、それは必要な計算量とデータ記憶量のために効率的ではなく、誰かが私にこれを手伝ってくれるかどうか疑問に思っていた。私は最後の学期にPythonプログラミングの1つのコースを取っただけで、その主題に関する以前の知識はありませんでした）。

私のコードだった

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を見つけた後、私はその長さの存在であり、その合計は私の期待値Iを与える2^200で割ったどのように多くの筋得るためにそれを反復処理したいです探しています。

ご協力いただきありがとうございました。

Answer 1

これは少し異なる質問に対する回答です。しかし、私は1時間半の時間を投資していたので、私はそれを掻き落としたくありませんでした。

つまり、あなたが以降最初のトスからk連続で頭を取得し、E(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 } 

注意あなたがコインに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. 

を取得したい意味 P(1) = 0.25に対し P(tails in first toss)
ある P(0) = 0.5、すなわち、 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) 

こと

したがって、期待値は

(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 

これは、あなたはすべての順列（実際には、あなたがすることはできません）をしようとする必要はありませんが、あなたは、単純なモンテカルロスタイルのシミュレーションを行うことができます

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

Answer 2

としてn投げに一般化することができます。 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 

また、Pythonシミュレーションを使用せずに正確な計算を行うには、this threadを参照してください。