Skip to content

Instantly share code, notes, and snippets.

@lpsmith
Created January 23, 2019 00:37
Show Gist options
  • Save lpsmith/a0e8e4c057ef1e73df35ced1823bb843 to your computer and use it in GitHub Desktop.
Save lpsmith/a0e8e4c057ef1e73df35ced1823bb843 to your computer and use it in GitHub Desktop.
Expected first sighting of HHHH versus HHHT in a sequence of coin flips of a fair coin.
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.
@lpsmith
Copy link
Author

lpsmith commented Jan 23, 2019

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment