c++ - 使用 std::rand() 在 C++ 中进行硬币翻转实验，结果不正确

Question

我正在尝试计算字符串 HHHHHHTTTTTTT 在 100 万次翻转中出现的次数。对于抛硬币，我使用了一个简单的 std::rand() % 2. 下面的代码。从数学上讲，预期的答案是

(10^6 - 12 + 1)/2^12 = 244

我从一本概率教科书中得到了这个结果。但是我的代码一直只得到一半左右，即大约 122。这是使用 std::rand() 作为抛硬币算法的问题，还是我的代码中存在错误？

#include <iostream>
#include <cstdlib>
#include <vector>
#include <ctime>

using std::vector;

bool coin_flip(){
  return std::rand() % 2;
}

int count_string(int n, const vector<bool>& s){
  int k=0, res=0;
  for(int i=0; i<n; i++){
    if(coin_flip()==s[k]){
      k++; 
      if(k==s.size()){
        res++;
        k=0;
      }
    }else{
      k=0;
    } 
  }
  return res;
}

int main(){
  std::srand(std::time(0));

  vector<bool> v(12);
  const int a[12] = {1,1,1,1,1,1,0,0,0,0,0,0};
  for(int i=0; i<12; i++){
    v[i] = a[i];
  }

  std::cout << count_string(1000000, v) << '\n'; 
  return 0;
}

Answer 1

假设我们只是在寻找抛硬币字符串 HT。我们开始期待正面。如果第一次抛硬币是正面，很好，我们继续期待反面。现在，如果第二次抛硬币正面朝上会怎样？这不符合我们的预期，所以我们应该重新开始但是我们可以认为这是我们全新序列的第一次翻转!也就是说，我们的下一个状态应该期待尾部。

但这不是您的代码当前正在做的事情。您回到起点，再次期待第三枚硬币正面朝上。第二枚代币基本上会为你消失在以太中。因此，您无法在 HHT 中找到 HT。

从图形上看，您的搜索使用红色状态转换而不是绿色状态转换:

推断出，您目前需要连续 6 个正面，然后是 6 个反面。但是第 7 次正面朝上又回到了开始，您又开始期待 6 次正面朝上，而不是允许超过 7 次正面朝上。由于第 7 次翻转有一半的概率是正面朝上，因此您最终会错过一半的正面事件。