This problem considers repeated tosses of a fair coin. Each outcome, H or T, has probability 1/2. Any specific sequence of tosses of the same length, like HHH or THH, has the same probability (for example, 1/8 for a sequence of length 3).
Now consider the following two-player game. Each player chooses a distinct pattern of possible coin flips having a common fixed length. For example, the first player might predict HHH while the second predicts THH. The game then begins with both players observing the same coin as it is repeatedly flipped, until one of them witnesses their pattern. For example, if the sequence of observed flips begins
The question that interests us is, given the two players\' patterns, how likely is it that the first player wins the game? Because we are flipping a fair coin, many would assume that the patterns are irrelevant and that each player has probability 1/2 of winning the game. However, this is not the case, leading to what is known as the Probability Paradox.
For some patterns, it will be that the first player wins with probability precisely 1/2. For example, by symmetry, the patterns TT and HH have equal chances of occurring first.
However, consider again our original example in which the first player chooses HHH and the second player chooses THH. For this particular match-up, the only way that the first player can win is if each of the first three tosses are H. For if the earliest HHH were to come somewhere other than at the beginning of the game, the pattern could be represented as
where "..." means a possibly empty earliest part of the sequence, and "?" refers to the toss immediately before the HHH. The "?" can not refer to an H, as in
because there would have been an earlier HHH that ended the game, the underlined part of
then the second player would have already won, having observed pattern THH at the underlined ...THHH. Therefore, when considering pattern HHH vs. THH, the first player wins if and only if the first three flips are H, an event that happens with probability 1/8.
As one more example, if the first player chooses TTH and the second chooses THH, the first player will win with probability 2/3. Your job is to write a program that computes such a probability.
TT HH HHH THH TTH THH THHTH HTHTT HTTHHHTHT THHHTHTHH $
1/2 1/8 2/3 15/28 259/452