使用std :: rand()给出错误结果的C++中的硬币翻转实验

Question

我正在尝试计算HHHHHHTTTTTT100万次翻转中字符串的出现次数.对于硬币翻转,我使用的是一个简单的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.我们开始期待头脑.如果第一个硬币翻转是头,很棒,我们继续期待尾巴.现在,如果第二个硬币翻转头部会发生什么？这与我们的期望不符,所以我们应该重新开始,但我们可以认为这是我们全新序列的第一次翻转!也就是说,我们的下一个州应该期待尾巴.

但这不是您的代码目前正在做的事情.你回到了开头,回到第三枚硬币再次期待头.第二枚硬币基本上会为你消失.其结果是,你无法找到HT在HHT.

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

根据推断,您目前需要连续6个头,然后是6个尾巴.但是第7个头回到了开头,你又开始期待6个头,而不是允许7个头.由于第7次翻转出现了一半的时间,你最终失去了一半的积极事件.