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正在寻找。

在此先感谢您的帮助，非常感谢！

你有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)

我想你误解了这个问题。 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模拟。

200次翻转的最长预期连线

相关推荐