You have been selected to be a member of the prestigious “Supreme Coin Flipper Club.” Congratulations! What an honor!
There are annual dues, however. These dues, appropriately enough, are determined by coin flips.
You are to select a sequence of any five consecutive coin flip outcomes to determine your dues. (Example: you could pick all tails T-T-T-T-T). Once you do, the Club president begins flipping a coin, and after each flip the result is noted. When your predicted sequence finally appears in the string of flips, the flipping stops and your dues are equal to the exact final number of flips that were needed to achieve this outcome. So in the example, if it took 35 flips to get a consecutive string of five tails, then your annual dues are $35.00.
You want to pay the lowest dues possible, of course. Does it matter what sequence you pick?
Let’s take the all tails example. You have a 1/32 chance of hitting it after 5 flips (all 5 tails in a row). Failing that, you can hit it on 6 flips if you have H-T-T-T-T-T with 1/64 overall chance (1/32 for the first 5 times 1/2 for the 6th). You can hit it on 7 flips in 2 different ways (H-H-T-T-T-T-T, T-H-T-T-T-T-T) or 2/128 chance.
Now, let’s say you chose H-T-H-T-H. You again have a 1/32 chance of hitting it after 5 flips. But failing that, you can now hit it on 6 flips in 2 different ways rather than just 1 (H-H-T-H-T-H OR T-H-T-H-T-H). And in 7 flips now in 3 different ways rather than 2 (T-H-H-T-H-T-H, H-H-H-T-H-T-H, T-T-H-T-H-T-H)
You will always have a higher chance of hitting H-T-H-T-H than T-T-T-T-T for a given number of flips, so your expected dues will be lower for the former than the latter.
What is the ‘optimal’ choice of sequence? I suspect either H-T-H-T-H or T-H-T-H-T, but that’s purely based on intuition at the moment.
This sounds a lot like a stopping problem, so I’ll take a look and refresh my admittedly very old knowledge on the subject.
…would want to pick a sequence whose first and last coin choices were opposite. That should given me the best fee since a last-coin failure in the sequence would set me up with the start of the next attempt already in hand.
Multiply ninjaed here—yes, it matters; there is not a unique solution but you want to avoid sequences like TTTTT and even HTHTH over “optimal” sequences like TTHTH or TTHHH. Then again, I should re-check my calculations.
That’s true, but there could be other “inefficiencies”
Ok, did some digging, and as confirmed, the more overlaps within the sequence, the worse off you are. So, the constant T or H sequences are absolutely the worst.
The least subsequent overlaps, the better. So, something like T-H-H-H-H is about as good as you can do. And certainly not unique. There are several that are equally good.
I would think that THHHH would be the best, as it essentially takes the 5 flip requirement and turns it into a 4 flip once you get a single Tails throw. After that first Tails, anytime you fail, the requirement is 4 Heads in a row.
I found that THTTH has the situation if you miss on the 4th flip, you have TH locked in, so it’s only 3 left to get, but that’s only if you miss on the 4th.
It’s an interesting puzzle because intuitively it seems like any sequence is just as likely as any other sequence to appear. You folks have done a good job explaining it because I was having problems wrapping my head around the solution. According to the puzzle author there are 10 optimal solutions.
Here’s the output from a quick sim. Shown is the average number of flips needed, taken over 1M trials for each target string. I’ve grouped them into apparent blocks of equivalence.
and it does not say anything about there being 10 solutions. Which makes sense; why would the guy not know how to solve his own puzzle which is a thin veneer over well-known simple combinatorics?