I read a very interesting math riddle recently, which inspired this blog post.

Let’s say I give you a fair coin and offer you a bet on the outcome of its flips. If I bet on heads and you bet on tails, we have an equal chance of winning/losing. If I bet on the sequence heads-tails, and you bet on heads-heads, we both have a 1/4 chance of winning and a 3/4 chance of losing. The pattern continues from there – every combination of heads and tails is equally likely to win as any other combination of heads and tails- however, as the combinations get larger, the probability that they don’t occur grows exponentially larger.

But what if I place a bet on which sequence will appear first? If I bet on head-head, and you bet on tail-head, we keep flipping the coin until either of our sequence shows up. What is the probability of either of us winning now?

If you are thinking 50-50, you are wrong. Once we enter the realm of sequences, it is no longer a series of independent events- each event affects how likely a certain outcome becomes. Let’s observe heads-heads (denoted HH) versus tail-heads (denoted TH), and look at all the possible sequence of flips (permutations generated in Mathematica by executing “With[{length = 4}, Map[StringJoin, Tuples[{“H”, “T”}, length]]]”).

  • 2 flips: {HH, HT, TH, TT} -> HH has 1 winning chance, TH has 1 winning chance.
  • 3 flips: {HHH,HHT,HTH,HTT,THH,THT,TTH,TTT} -> Some of the permutations can’t occur (HH will have already won), so TH has 2 winning chances, HH has none.
  • 4 flips: {HHHH, HHHT, HHTH, HHTT, HTHH, HTHT, HTTH, HTTT, THHH, THHT, THTH, THTT, TTHH, TTHT, TTTH, TTTT} -> Excluding impossible permutations, HH has 1 winning chance, TH has 3.

As you can see, it isn’t a 50-50 game- some combinations of flips are more likely to show up than others. In the case of HH vs. TH, the chances to win divided by total chances is 2/14 for HH, and 6/14 for TH. So, you are 3 times more likely to win if you pick TH than if you pick HH (75% odds are in your favor), after 4 flips of the coin. It doesn’t apply to other strings of flips, because after each flip, one gets more likely than the other. We’ll look at where the probabilities converge to later in this post.

But what about “HHHTHTH” vs. “HTHHTHH”?

This nifty little coin trick is something that people instinctively believe is a 50-50 chance. So if you’re ever down on your luck, strike a bet for HH vs. TH on a series of coin flips- the Law of Large Numbers guarantees that you will win. This post should allow readers of this blog to exploit the general population that doesn’t read this blog- but in how many ways?

What if I bet on “HHT” and the other person bet on “TTH”? Is there any quick and easy way to find out our odds? There is the intuitive method- if I bet on HHT, and you bet on HTT, and a HH shows up in the flipping, I am guaranteed to win. Think about this- if a HH has shown up, and the next flip is T, I win- if the next flip is H, neither of us can win, and I will just bide my time until the next rounds until a T finally shows up. Once it does show up, I’ll already have won- there’s no way a HTT can occur without a HHT occurring first. If this doesn’t make sense, try drawing out the tree diagram (shown below) and check it for yourself.

But what is the magical formula?

For the most part, there is none. But maybe with a little help from Mathematica, we can brute-force test the odds, and develop a generic way of testing pairs of sequences to find which one is more likely to occur.

Using the combinatorics functions built into Mathematica, we can create lists of possible strings of coin flips.

Then, defining a function that lists all the combinations of heads and tails in a sequence, whose length ranges from min to length.

Here, I’ve defined a function that selects combinations that don’t contain the “winning” sequence. However, this function won’t do us any good when comparing two sequences, because if we are comparing “HHTT” and “HTHT”, we need to define a way to parse and collect sequences such as “HHTTHTHT”, which contain both the sequences, but in different orders. In the case of “HHTTHTHT”, both sequences have won, but HHTT won first, so the win would belong to HHTT and not HTHT. To compare two sequences while doing this, I created the beast below.

The module goes through all the possible sequences, storing the winners for each sequence in a list. Then, it parses out winning sequences for one sequence that would have occurred after the second sequence. For example, if we were checking “HHT” vs. “HHH”, the sequence “HHHT” would not be a win for “HHT” because the other sequence would have occurred already, but for “HHH”, it would be a win.

In this example, the sequences “HHT” and “HTT” are compared in a 6-coin-flip simulation. Each list contains the possible winning coin flip combinations – the last  number is the total possible combinations of choices (inclusive of lesser-level combinations). To make sense of this hard-to-read output, we define a probability function, as such:

This function analyzes the probabilities and returns a list with the probability of each occurring. The final output:

So, after 12 flips, the odds of H vs. T is the same, the odds are very much in TH’s favor, and HHT is certainly the wiser bet. I’ve also added a longer sequence to show that pretty much any arbitrary sequence can be tested against another to find the probability after a certain number of flips. Remember, these are not the absolute probabilities (the probability after 100 flips, or 200 flips, etc) – eventually, the probabilities converge to a given value, but this would require a different approach because calculating 2^100 permutations is a foolish and time-consuming venture.

Viewing the data

Here is a basic view of the winnerCount function, which counts how many winners for each successive flip. The first and second rows correspond to the first and second combination, and the last row is the total number of combinations (backwards inclusive).
When we look at the differences between each successive term, we see they are formed by an elegant generating function.

There definitely is something mathematical working in the shadows here, but we’ll let the magical elves of the generating function do their work while we analyze the data they produce. However, if we were to find a generating function for the number of winners from each sequence for each game, we could find the exact odds of each game instead of the approximate odds given here.

This table is the odds of winning for the vertical column when playing against the horizontal column (i.e. the 5th row, 1st column says that THH has a 107/108 chance of winning against HHH after 10 coin flips).

We can define a function to create these tables so that we can generate even larger tables.

Here we’ve tested the basic level-2 permutations after 6 coin tosses. We can also generate larger tables:

Here, I called a testAll[4,9] (it takes a few seconds to compute). We can see some interesting patterns in the table (if it is unreadable, you can view/download the table here). I am currently in progress of calculating testAll[4,20] (about a million combinations) to see if I can get some more accurate probabilities.

Conclusion

So there you have it! An analysis of an interesting riddle, with all the ease and glory of Mathematica‘s powerful tools. If you want to download the .nb Mathematica file and try it yourself, check out the downloads page.

DISCLAIMER: I take no responsibility for any money, property, arms, or legs you choose to gamble on the odds stated here.

About these ads