Penney Ante is a gambling game in which two players each name a different sequence of outcomes of coin tosses, where both sequences must have the same length. For example heads-heads-tails, or HHT. Then a coin is flipped repeatedly until one of the sequences appears. The player who named that sequence, wins the game.

Penney Ante

Is there any strategy that gives one player a higher probability of winning the game than the other player? Strangely, there is. The famous mathematician John Conway even proposed a beautiful algorithm to compute the probability that one chosen sequence will win against another sequence. We will give an initial explanation of the algorithm for triplets (sequences of length three), but Conway's algorithm is very powerful in that it can be used to compute probabilities for sequences of any length, even for sequences of dissimilar length.

First, we put the two triplets one above the other with their letters aligned, as we've done below for the two triplets THH and HHH. Now we compare the two triplets: if they are the same, put a 1 above the first letter of the first triplet, if not put a 0.

0
THH
HHH

Next, remove the first letter from the upper triplet and shift the remaining letters to the left, aligning the leading letters of the two triplets. Then, compare the first two letters of the upper sequence to the first two letters in the lower sequence: if they are the same, place a 1 above the leading letter of the upper sequence, or a 0 otherwise.

1
HH
HHH

Repeat this procedure through the last letter of the upper sequence, each time comparing the remaining letters in the upper sequence with the same number of leading letters in the lower sequence (if the lower sequence has fewer letters than the upper sequence, we write a 0 by definition).

1
H
HHH

Finally we compile all obtained ones an zeros into a single sequence, which we can represented in the following way:

011
THH
HHH

The resulting sequence of zeros and ones is called a bit sequence. Such a bit sequence expresses the amount of overlap between the two sequences of consecutive coin tosses, and can be read as a binary number. In the above example we obtained the bit sequence 011, which is equal to the decimal number 3 when interpreted as a binary number.

Now that we have learned how to determine bit sequences, this gives us a way of working out the odds for two given sequences $$A$$ and $$B$$. We will write the bit sequence obtained when using sequence $$A$$ both as the upper and lower sequence as $$b_{AA}$$, the bit sequence obtained when using sequence $$A$$ as the upper sequence and sequence $$B$$ as the lower sequence as $$b_{AB}$$, and so on. The odds $$k_A\!:\!k_B$$ in a game of Penney Ante where sequences $$A$$ and $$B$$ compete against each other, are given by the following equations: \[ \begin{aligned} k_A &= b_{BB} - b_{BA} \\ k_B &= b_{AA} - b_{AB} \end{aligned} \] where the decimal values of the bit sequences are used in the subtractions at the left hand sides of the equations. If we consider the example where $$A$$ = HHH and $$B$$ = THH, we can first determine the bit sequences:

  111       000
A:HHH     A:HHH
A:HHH     B:THH

  100       011
B:THH     B:THH
B:THH     A:HHH

Converting these four bit sequences to decimal numbers (the sequence 111 in binary equals 7, the sequence 000 equals 0, the sequence 100 equals 4 and the sequence 011 equals 3) and substituting them into the above equations, we have \[ \begin{aligned}k_A &= (100)_2 - (011)_2 = 4 - 3 = 1 \\ k_B &= (111)_2 - (000)_2 = 7 - 0 = 7 \end{aligned} \] So the odds for sequence $$A$$ to win against sequence $$B$$ are $$k_A\!:\!k_B = 1\!:\!7$$. Note that it is uncommon to report the odds themselves. Instead we report the normalized odds that are obtained by dividing $$k_A$$ and $$k_B$$ by their greatest common divisor. For example, we do not write the odds as $$4\!:\!2$$, but as $$2\!:\!1$$.

If we use $$p_A$$ for the probability that sequence $$A$$ wins and $$p_B$$ for the probability that sequence $$B$$ wins, we have \[ p_A = \frac{k_A}{k_A + k_B} = \frac{1}{ 1 + 7} = \frac{1}{8},\ p_B = \frac{k_B}{k_A + k_B} = \frac{7}{ 1 + 7} = \frac{7}{8} \] Note that in computing these probabilities, it doesn't matter whether we use the odds or the normalized odds.

Assignment

In this assignment we will represent the outcome of a coin toss using an uppercase letter: H for heads and T for tails. This way we can represent a sequence of outcomes of coin tosses as a string that only contains the letters H and T. Your task:

The two sequences of outcomes of coin tosses that are passed to the functions bitsequence, odds and probabilities should not necessarily have the same length and can also be the same sequence.

Example

>>> winner('HHH', 'THH', 'HTHTHHHHTHHHTTTTHTHH')
2
>>> winner('THT', 'TTH', 'HTHTHHHHTHHHTTTTHTHH')
1
>>> winner('THH', 'HHT', 'HHHHHHHHHHHHHHHHHHHH')
0
>>> winner('THH', 'THH', 'HHHHHHHHHHHHHHHHHHHH')
Traceback (most recent call last):
AssertionError: sequences cannot be equal
>>> winner('THHT', 'THH', 'HHHHHHHHHHHHHHHHHHHH')
Traceback (most recent call last):
AssertionError: sequences must have equal length

>>> bitsequence('HHH', 'THH')
'000'
>>> bitsequence('THT', 'TTH')
'001'
>>> bitsequence('THH', 'HHT')
'011'

>>> odds('HHH', 'THH')
(1, 7)
>>> odds('THT', 'TTH')
(1, 2)
>>> odds('THH', 'HHT')
(3, 1)

>>> probabilities('HHH', 'THH')
(0.125, 0.875)
>>> probabilities('THT', 'TTH')
(0.3333333333333333, 0.6666666666666666)
>>> probabilities('THH', 'HHT')
(0.75, 0.25)

Resources