I toss 5 fair coins and you toss 6 fair coins. What is the probability that you get more heads than I do?

Assignment

Let's consider the more general case where I toss $$m$$ fair coins and you toss $$n$$ fair coins. To compute the probability that you get more heads than I do, we could simply count how often that's the case for all possible outcomes.

In total, there are $$2^{m+n}$$ possible outcomes. Each outcome corresponds to a decimal number in the range $$0, 1, 2, \ldots, 2^{m+n} - 1$$. After all, we can convert any of these decimal numbers into its binary representation with $$m + n$$ digits, with the binary digit $$0$$ representing heads (H) and the binary digit $$1$$ representing tails (T). We consider the first $$m$$ binary digits as my tosses and the last $$n$$ binary digits as your tosses. All that needs to be done is determine for each outcome if you got more heads than I do. The probability we're looking for is equal to the number of outcomes for which this is the case, divided by the total number of possible outcomes ($$2^{m+n}$$).

The following table summarizes all possible outcomes for our original question from the introduction, where $$m = 5$$ and $$n = 6$$.

In that case there are $$2^{5 + 6} = 2^{11} = 2048$$ possible outcomes. For example, outcome 1188 (decimal) corresponds to the binary number 10010100100 of $$5 + 6 = 11$$ digits. If we replace $$0$$ by H (heads) and $$1$$ by T (tails), we get THHTHTHHTHH. Of these, I have tossed the first 5 coins (THHTH; marked in green in the above table) and you have tossed the last 6 coins (THHTHH; marked in red in the above table). For this outcome, I toss 3 heads and you toss 4 heads, so you get more heads than I do. In total, this is the case for 1024/2048 possible outcomes, so the probability is 0.5.

We represent a sequence of coin tosses as a string (str) that only contains the letters H (heads) and T (tails). Your task:

• Write a function heads that takes a sequence of coin tosses (str). The function must return how many coin tosses resulted in heads in the given sequence of coin tosses (int).

• Write a function tails that takes a sequence of coin tosses (str). The function must return how many coin tosses resulted in tails in the given sequence of coin tosses (int).

• Write a function you_more_heads_than_me that takes two sequences of coin tosses (str): i) my sequence of coin tosses and ii) your sequence of coin tosses. The function must return a Boolean value (bool) that indicates if you got more heads than I do.

• Write a function outcome that takes three non-negative integers (int): i) the number $$m$$ of fair coins I toss, ii) the number $$n$$ of fair coins you toss and iii) the decimal representation $$d$$ of a possible outcome of $$m + n$$ coin tosses ($$0 \leq d < 2^{m+n}$$). The function must return a tuple containing my and your sequence of coin tosses that correspond to possible outcome $$d$$.

  Tip

  In Python you can use the built-in function bin to convert a decimal value (int) into a string (str) representation of its binary value. The resulting string always starts with the fixed prefix 0b, indicating it represents a binary value.

  >>> bin(14672002)
  '0b110111111110000010000010'
  

• Write a function probability that takes two non-negative integers (int): i) the number $$m$$ of fair coins I toss, and ii) the number $$n$$ of fair coins you toss. The function must return the probability (float) that you get more heads than I do in that case.

Example

>>> heads('THHTHTHHTHH')
7
>>> heads('HHHHTTTHTHT')
6
>>> heads('THTHTTTHTTH')
4

>>> tails('THHTHTHHTHH')
4
>>> tails('HHHHTTTHTHT')
5
>>> tails('THTHTTTHTTH')
7

>>> you_more_heads_than_me('THHTH', 'THHTHH')
True
>>> you_more_heads_than_me('HHHHT', 'TTHTHT')
False
>>> you_more_heads_than_me('THTHT', 'TTHTTH')
False

>>> outcome(5, 6, 1188)
('THHTH', 'THHTHH')
>>> outcome(5, 6, 117)
('HHHHT', 'TTHTHT')
>>> outcome(5, 6, 1398)
('THTHT', 'TTHTTH')

>>> probability(5, 6)
0.5
>>> probability(6, 5)
0.2744140625
>>> probability(3, 8)
0.88671875

Resources

• Barbeau EJ, Barbeau E, Klamkin MS, Moser WO, Moser WO (1995). Five Hundred Mathematical Challenges. MAA.