MediumProbabilitypr-161

Waiting Time for a Pattern

Problem

Expected number of fair coin flips until a given pattern of H and T appears:

E[T] = sum of 2^k over lengths k where the length-k prefix equals the length-k suffix of the pattern.

For example HTH waits 10 flips on average. Return the expectation.

Hint

Self-overlaps of the pattern add 2^k waiting time for each overlap length k.

case 1

in: ["HTH"]

expected: 10

case 2

in: ["HHT"]

expected: 8

case 3

in: ["HHH"]

expected: 14

case 4

in: ["HT"]

expected: 4

case 5

in: ["HH"]

expected: 6

Starter codePython

def expected_wait_pattern(pattern):
    # Your code here
    pass

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