If you choose two different sets of results to match inside a coin flipping record, does the odds of finding a match depend on what you pick on each?

Question

Example, if you flip a coin 10 times and record the results, and you pick 2 different sets of 5 length (e.g HHTHT and TTHTT where H=heads and T=tails) and the goal is to match any of your two sets anywhere inside the coin results (e.g TTTTHHTHTH contains the example set HHTHT).

The question is, can the combined odds of finding a match on either set be affected depending on the way the sets are chosen?

Also bonus in case the odds vary, explain which strategies could be used to improve and/or worsen the chances of finding a match (if it doesn't matter at all, bonus doesn't apply obviously).

My hypothesis is that if they overlap (e.g set_a = HHHHH and set_b = THHHH) you end up with less odds of finding a match, but usually these kind of problems are counter-intuitive and I couldn't tackle this problem myself, at least not in a non-inductive way.

Answer 1

Yes, the two sets does affect the probability of finding one match.

Indeed, given a set $A$ of length 5, call $p(A) $ the probability that a random set of length 10 contains $A$. Given two sets $A,B$ we have

$$ p(A \text{ or } B) = p(A) + p(B) - p(A \text{ and } B) $$

The probability $p(A) $ depends on the "shift-symmetries" that $A$ has: the more it is symmetric, the less is probable to find a match.

Example 1: HHHHH can appear in first position in $2^5$ possible combinations, all the ways one can choose the last letters. It can also appear in second position in $2^5$ possible combinations. Continuing like this, it can appear in position up to six, yielding $6*2^5$ possible combinations. But wait..! Actually the first and second block of combinations overlap when the word starts by HHHHHH, so we have counted this combinations twice! Taking this complication into account, one obtains

$$6* 2^5 - 5* 2^4 + 4* 2^3 ... -1 = 57 < 192 = 6* 2^5 $$

Example 2: if you take THTTT, the first block overlap with the fifth, and the second overlap with the sixth, and that's all. So you will have $6*2^5- 2* 2^4 = 160$, about three times the odds of the word above!

To conclude, the mixed term roughly gets bigger the smaller word you can find containing both of your $A$ and $B$. Let's call the length of the smallest word containing both the "combined rank". This is only a first approximation of how big is the term. Since it has a minus sign, the combined probability gets bigger if the combined rank is high.

Example: $THTTT$ and $HTHHH$ are cool words, because the shortest word containg both is 10 long, and singularly the words have few shift symmetries. Explicitly you get that the possible combinations are $160+160-2 = 318$.

On the other side, if you take $HHHHH$ as first word and $HHHHHH$ as second, this has a very small probability, because they have a lot if shift symmetries and the combined rank is 5. You get $57$ possibilities, way less than above.

Answer 2

Yes, your choice of sequence can make a difference. Let's look at one of the very simplest cases: HH vs. TH in a sequence of three flips. Then the sequences that contain HH are HHH, HHT and THH; therefore, your chances are $3/8$ of a match. OTOH, the sequences that contain TH are HTH, THH, THT, and TTH, so your chances of matching there are $1/2$. This gap only gets longer with longer sequences; there are $F_{n+1}$ sequences of coin flips of length $n$ with no HH in them (try to prove this yourself; it's a pretty classic appearance of the Fibonacci numbers), so the number of 'hits' on HH is $2^n-F_{n+1}$, and your hit probability is $1-\frac{F_{n+1}}{2^n}\approx 1-\phi\cdot\left(\frac\phi2\right)^n$. OTOH, the only sequences with no TH in them are those of the form H$^*$T$^*$ and there are only $n+1$ of these, so your hit probability is $1-\frac{n+1}{2^n}$; your chances of a miss are exponentially smaller than they are on HH.

Abstractly, this is a question of how many words of a given length have a given-length subword; my first instinct would be to use Fibonacci words but you 'clearly' want a word of density 1/2 if you can. It's possible that Thue-Morse sequences are ideal, but that's something that will take quite a bit more digging...