coin flip experiment in C++ using std::rand() giving incorrect result

Question

I'm trying to count the number of occurrences of the string HHHHHHTTTTTT in 1 million flips. For the coin flip, I'm using a simple std::rand() % 2. The code below. Mathematically, the expected answer is

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

I got this result from a probability textbook. But my code is consistently getting only about half of that, i.e. around 122. Is this an issue with using std::rand() as a coin flip algorithm, or is there a bug in my code?

#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

Let's pretend we're just looking for the coin flip string HT. We start off expecting heads. If the first coin flip is a heads, great, we move on to expecting a tails. Now, what happens if the second coin flip comes up heads? This doesn't match our expectation, so we should start over but we could then consider this the first flip of our brand new sequence! That is, our next state should be expecting tails.

But that isn't what your code is currently doing. You revert to the beginning and go back to expecting heads again for the 3rd coin. The 2nd coin basically disappears into the ether for you. As a result, you fail to find HT in HHT.

Pictorially, your search uses the red state transition instead of the green one:

Extrapolating out, you currently want 6 heads in a row followed by 6 tails. But a 7th head reverts back to the beginning and you start expecting 6 heads again, instead of allowing for 7+ heads too. Since the 7th flip comes out heads half the time, you end up missing half the positive events.