Expected first sighting of HHHH versus HHHT in a sequence of coin flips of a fair coin.

HHHT.m

hhhh_transition_matrix = [
  0.5  0.5  0.5  0.5   0   0;
  0.5    0    0    0   0   0;
    0  0.5    0    0   0   0;
    0    0  0.5    0   0   0;
    0    0    0  0.5   0   0;
    0    0    0    0   1   1
  ];

hhht_transition_matrix = [
  0.5  0.5  0.5    0   0   0;
  0.5    0    0    0   0   0;
    0  0.5    0    0   0   0;
    0    0  0.5  0.5   0   0;
    0    0    0  0.5   0   0;
    0    0    0    0   1   1;
  ];

initial_state = [
  1;
  0;
  0;
  0;
  0;
  0
  ];

tosses = 0;
hhhh_state = initial_state;
hhhh_expected = 0;

while tosses <= 10000
    tosses = tosses + 1;
    hhhh_state = hhhh_transition_matrix * hhhh_state;
    hhhh_expected = hhhh_expected + tosses * hhhh_state(5);
end

disp("The approximate expected first sighting of HHHH is after "), disp(hhhh_expected), disp( " coin tosses.");

# output:

# The approximate expected first sighting of hhhh is after 
#  30.000
#  coin tosses.

tosses = 0;
hhht_state = initial_state;
hhht_expected = 0;

while tosses <= 10000
    tosses = tosses + 1;
    hhht_state = hhht_transition_matrix * hhht_state;
    hhht_expected = hhht_expected + tosses * hhht_state(5);
end

disp("The approximate expected first sighting of HHHT is after "), disp(hhht_expected), disp( " coin tosses.");

# output:

# The approximate expected first sighting of hhht is after 
#  16.000
#  coin tosses.

This can be run, if one so desires, in GNU Octave or (presumably) Matlab. The basic idea is to construct a deterministic finite automaton that recognizes the first instance of the desired string. We can then turn the automaton into a Markov Chain by "feeding" it a random sequence of fair coin flips. Here, we calculate the probability vector of the automaton being in any particular state after N coin flips. Then we look at the probability of having just seen our first string that we desire, which corresponds to the probability of being in the 5th state. The sixth state (corresponding to the condition that we've already seen the string we are looking for) isn't strictly necessary for this calculation, but it allows us to maintain the invariant that hhhh_state and hhht_state are probability vectors.