# Occurrences of permutations in sequences of 4 coin flips

I was reading this interesting article on hot hands and streaks in sports. The article revolves around the 16 possible sequences of 4 coin flips (H = heads, T = tails):

HHHH
HHHT
HHTH
HHTT
HTHH
HTHT
HTTH
HTTT
THHH
THHT
THTH
THTT
TTHH
TTHT
TTTH
TTTT


The article states the following:

[I]n the sixteen length-four sequences, there are only eight that have any occurrence of HH, but there are eleven that have an occurrence of HT. That is, the distribution of HH and HT is not uniform in the fourteen (sic!) sequences.

NB: The quote mentions fourteen sequences, because in the linked article, only 14 of the 16 sequences are considered.

And then there is a footnote:

At first, this may seem paradoxical since the two counts might be expected to be equal by “symmetry”. But, the two occurrences are not symmetric, which I leave you to ponder.

Since then I try to think of an explanation on why this is the case? Why are there more sequences in which at least one HT occurs than there are sequences where at least one HH occurs?

Of course, by simply looking at each sequence, I can see (and count) the HH and HT occurrences, but I would like to know why exactly (which property of the sequences) leads to this fact.

• closest I can get is this numberphile video on penney's game youtube.com/watch?v=Sa9jLWKrX0c – user451844 Sep 30 '17 at 15:37
• I assume the penultimate word in the first quote should be sixteen rather than fourteen. – N. F. Taussig Sep 30 '17 at 16:09
• the quote is correct mentioning 14 sequences. see my edit. – beta Sep 30 '17 at 17:03
• @beta they ignored HHHH and TTTT. They state (HH) (HT) should be symmetrical in 14 sequences. – kimi Tanaka Oct 1 '17 at 0:24
• Probably you got it in other SE. – kimi Tanaka Oct 1 '17 at 0:26

It is important to keep in mind that we are counting sequences in which the subsequence HH occurs at least once, not the total number of appearances of HH. For instance, HH appears three times in the sequence HHHH, but we only count that sequence once. The subsequence HT will occur in any sequence with both heads and tails provided that not all the tails appear before the first head.

Consider cases.

Four heads: There is $\binom{4}{4} = 1$ such sequence.

The subsequence HH must occur.

The sequence HT cannot occur since there are no tails.

Three heads and a tail: There are $\binom{4}{3} = 4$ such sequences.

The subsequence HH must occur in all of these sequences.

The subsequence HT must occur unless T occurs in the first position, so three of these four sequences contain the subsequence HT.

Two heads and two tails: There are $\binom{4}{2} = 6$ such sequences.

For the subsequence HH to occur, it must begin in the first, second, or third position. Hence, three of these sequences contain the subsequence HH.

The subsequence HT will occur unless both heads occur after both tails. Hence, five of these sequences contain the subsequence HT.

One head and three tails: There are $\binom{4}{1} = 4$ such sequences.

The subsequence HH cannot occur since there are not enough heads.

The subsequence HT will occur unless heads is in the final position. Hence, the subsequence HT will occur in three of these four sequences.

Four tails: There is $\binom{4}{0} = 1$ such sequence.

Since there are no heads, neither the subsequence HH nor the subsequence HT can occur.

We have a pair (HH) 3 in HHHH, 2 in HHHT, 1 in HHTH, 1 in HHTT 1 in HTHH, 2 in THHH, 1 in THHT, 1 in TTHH$. In total$12$. We have a pair (HT): 1 in HHHT, 1 in HHTH, 1 in HHTT, 1 in HTHH, 2 in HTHT, 1 in HTTH, 1 in HTTT, 1 in THHT, 1 in THTH, 1 in THTT, 1 in TTHT. In total 12. You can count (TH), (TT) are also the same in total 12. Since (HH) can appear in a way: (1st H 2nd H),(2nd H, 3rd H), (3rd H, 4th H) in a 4 coin tosses as a sequence, you can use maximum 3 (HH) pairs in a sequence. And you count it as a single time. Whereas, (HT) can appear in a way (1st H 2nd T),(3rd H 4th T) in a sequence. So, you can use maximum 2 pairs in a sequence. And you count it as a single time. Therefore you have more(HT) than (HH). • I mean at least one. That is, no double counts. – beta Sep 30 '17 at 15:44 • @beta So, the probability of 1/4: (HH) can occur 12 times if you allowed over counts ex:(HHHH) as 1st 2nd (HH), 2nd 3rd (HH), 3rd 4th (HH) in a (HHHH) sequence. so you have used 3 (HH) tuples in the total of 12 (HH) tuples in 16 sequences. And you count it as only 1. HT appears more often as only one (HT) tuple-form in one of the16 sequences. So you have 11(HT) to 8(HH). – kimi Tanaka Sep 30 '17 at 16:05 • @beta I mean (HH) should appear as same times as (HT) in 64 coin tosses. You can divide (1st, 2nd), (2nd,3rd), (3rd,4th) in (1st, 2nd, 3rd, 4th) of one coin toss. So you have 48 tuples. And (TT),(TH),(HT),(HH) all appear at same times. – kimi Tanaka Sep 30 '17 at 16:17 I believe this is a mistake in comprehension. If there are$x\text{HH}$sequences, then there must be$x\text{TT}$sequences.$\text{HT}$sequences are not related. The number of$HT$sequences must be same as the number of$TH$sequences. • I think you misunderstand. I am talking about the number of sequences that contain at least one$\text{HT}$(that is, 11 sequences) and the number of sequences that contain at least one$\text{HH}$(that is, 8 sequences). – beta Sep 30 '17 at 15:35 • @beta How is$HH$related to$HT$? Logically, since Heads is opposite to Tails, the symmetrically opposite expression of$HH$must be$TT$, just like the one of$HT$is$TH$. See how the number of$HH$sequences is$8$, and the number of$TT$also$8$. The number of$HT$is$11$, and$TH$also$11\$. See? – DynamoBlaze Sep 30 '17 at 15:56