Expected Value of Number of Attempts to Get Pattern

In this post, I talk about how to find the expected value of the number of coin tosses needed to find a specific pattern for the first time.

The Setup

You toss a fair coin until you reach a specific pattern. Example HH. How many tosses would you need on an average to get to this pattern for the first time.

---

Solution

To tackle this problem, I thought about the solution in terms of conditional probability.

Given that I have not seen the pattern yet, if the last toss was an H, how many more tosses can I expect before I see the pattern? Call this H. Given that I have not seen the pattern yet, if the last toss was a T, how many more tosses can I expect before I see the pattern? Call this T.

\[ H = 0.5*1 + 0.5*(1+T) \]

The explanation of the equation above is, as follows: Given that we have not seen the pattern yet, and we tossed an H, with 0.5 probability we can get the pattern. With another 0.5 probability we need (1+T). 1 because of the T we just rolled, and T is the expected number given the last toss was T.

\[ T = 0.5(1+H) + 0.5(1+T) \]

We now have a system of linear equations. On solving this, we get \[ \begin{aligned} H = 4\\ T = 6\\ E = 6 \end{aligned} \]

Simulate the Results

import numpy as np
import random


def simulate_game(p=0.5):
    last_res = None
    last_but_one_res = None
    n_trials = 0
    while not ((last_res == "H") & (last_but_one_res == "H")):
        last_but_one_res = last_res
        if random.uniform(0, 1) > p:
            last_res = "H"
        else:
            last_res = "T"
        n_trials += 1
    return n_trials


def simulate_expected_value(n, p):
    trials_list = []
    for i in range(n):
        trials_list.append(simulate_game(p))

    return np.mean(trials_list)


def find_conf(conf_n, n, p, conf_per=95):
    res_list = []
    for i in range(conf_n):
        res_list.append(simulate_expected_value(n, p))
    lower = np.quantile(res_list, (100 - conf_per) / 200)
    upper = np.quantile(res_list, (conf_per + (100 - conf_per) / 2) / 100)
    return (lower, upper)

Expanding Further

What if we have

• A pattern HHH?
• Unfair dice?
• Is the expected value to get HHH the same as HTH? What about TTH?
• If the pattern is HH OR HT?
  • What is the probability we get HH before HT?