Penney's Game Probability

Problem

Penney's game: fair coin flips continue until either pattern_a or pattern_b appears. Return the exact probability that pattern_b appears first, computed by solving the absorbing Markov chain whose states are the current prefix matches of both patterns. Return 0.0 if either pattern is empty or the patterns are equal.

Hint

Set up one linear equation per prefix-match state and solve the system.

Test cases

case 1

in: ["HHH","THH"]

expected: 0.875

case 2

in: ["THH","HHT"]

expected: 0.25

case 3

in: ["HTH","HHT"]

expected: 0.6666666666666666

case 4

in: ["HHH","HHT"]

expected: 0.5

case 5

in: ["HHH","HHH"]

expected: 0

Starter codePython

def penney_game_probability(pattern_a, pattern_b):
    # Your code here
    pass

5 test cases · run your code against them in the editor