Are you preparing for a SIG Quantitative Researcher interview and want to master advanced probability questions? One of the classic problems you may encounter is about the probability of one coin sequence appearing before another in repeated coin tosses. This article dives deep into the “coin sequence pattern probability” question, providing step-by-step solutions, key concepts, and tips to ace similar interview problems.

SIG Quantitative Researcher Interview Question: Coin Sequence Pattern Probability

Understanding the Problem Statement

Question: A fair coin is flipped repeatedly. What is the probability that the sequence HHT appears before HTH?

This is a classic Markov process and pattern matching problem, often asked in quantitative interviews to assess your probability modeling and reasoning skills. Let’s break down the problem and solve it systematically.

Key Concepts Involved

• Markov Chains: Modeling random processes where the next state depends only on the current state.
• Pattern Probability: Calculating the likelihood of one sequence appearing before another in a random process.
• Recursion and First Step Analysis: Breaking down the problem into states and using equations to solve for probabilities.
• Expected Value and States: Analyzing the process by defining states based on partial matches to the sequences.

Step 1: Defining the Patterns

We are flipping a fair coin (P(Heads) = P(Tails) = 0.5). We’re interested in two patterns:

• Pattern A: HHT
• Pattern B: HTH

We want to find the probability that the first pattern (HHT) occurs before the second pattern (HTH).

Step 2: Modeling the Problem — State Definitions

To model this, we’ll use a Markov chain approach where each state represents the current “memory” of the last few coin flips, as they relate to the beginnings of either HHT or HTH.

Let’s define the possible states based on the most recent flips:

• S₀: Start state (no relevant history)
• S_H: Last flip was H
• S_HH: Last two flips were HH
• S_HT: Last two flips were HT
• S_HHT: Sequence HHT has appeared (absorbing state)
• S_HTH: Sequence HTH has appeared (absorbing state)

Why do we need these states? Because the process of getting to HHT or HTH depends on the partial sequences formed, and what could happen next.

Step 3: Drawing the State Transition Diagram

Let’s visualize the transitions between states as we flip the coin. Here is a summary of the transitions:

Note: Once we reach S_HHT or S_HTH, the process stops, as one of the target sequences has appeared.

Step 4: Assigning Probabilities to States

Let’s define variables for the probability, starting from each state, that HHT happens before HTH:

• P₀: Probability starting from S₀
• P_H: Probability starting from S_H
• P_HH: Probability starting from S_HH
• P_HT: Probability starting from S_HT

We know:

• P_HHT = 1 (since HHT has already appeared)
• P_HTH = 0 (since HTH has already appeared)

Step 5: Setting Up the Recursion Equations

Let’s write the equations for each state, using the law of total probability:

For S₀:

From S₀, the next flip is H or T (each with probability 0.5):

\[ P_0 = 0.5 \cdot P_H + 0.5 \cdot P_0 \]

Rearrange:

\[ P_0 - 0.5 P_0 = 0.5 P_H \] \[ 0.5 P_0 = 0.5 P_H \] \[ P_0 = P_H \]

For S_H:

From S_H, the next flip is H or T:

\[ P_H = 0.5 \cdot P_{HH} + 0.5 \cdot P_{HT} \]

For S_HH:

From S_HH:

• If next flip is H: stay in S_HH
• If next flip is T: move to S_HHT (HHT appears)

\[ P_{HH} = 0.5 \cdot P_{HH} + 0.5 \cdot 1 \] \[ P_{HH} - 0.5 P_{HH} = 0.5 \] \[ 0.5 P_{HH} = 0.5 \] \[ P_{HH} = 1 \]

For S_HT:

From S_HT:

• If next flip is H: move to S_HTH (HTH appears)
• If next flip is T: move to S₀

\[ P_{HT} = 0.5 \cdot 0 + 0.5 \cdot P_0 = 0.5 P_0 \]

Step 6: Solving the Equations

Now, let's collect all the equations:

1. \( P_0 = P_H \)
2. \( P_H = 0.5 P_{HH} + 0.5 P_{HT} \)
3. \( P_{HH} = 1 \)
4. \( P_{HT} = 0.5 P_0 \)

Let’s substitute \( P_{HH} \) and \( P_{HT} \) into the equation for \( P_H \):

\[ P_H = 0.5 \cdot 1 + 0.5 \cdot (0.5 P_0) \] \[ P_H = 0.5 + 0.25 P_0 \]

Recall from earlier: \( P_0 = P_H \), so:

\[ P_0 = 0.5 + 0.25 P_0 \] \[ P_0 - 0.25 P_0 = 0.5 \] \[ 0.75 P_0 = 0.5 \] \[ P_0 = \frac{0.5}{0.75} = \frac{2}{3} \]

So, the probability that HHT appears before HTH is 2/3.

Step 7: Final Answer and Interpretation

Final Answer: The probability that HHT appears before HTH in repeated fair coin flips is:

\[ \boxed{\frac{2}{3}} \]

This is a surprising result for many interviewees, as intuition might suggest a 50/50 chance. The key reason for the asymmetry is in the structure of the patterns and their overlapping prefixes.

Step 8: Intuitive Explanation

Why is the answer not 0.5? Notice that both sequences start with H, but their continuations differ. The structure of the Markov process means that after certain partial matches, it’s easier to finish HHT than HTH:

• Once you see HH, you are one T away from HHT, and if another H comes, you stay at HH (maintain progress).
• For HTH, you need HT and then H. But after HT, if you get T, you’re reset (back to start).

Thus, HHT has a “stickier” progress path, which gives it an edge.

Step 9: Simulation Approach (Python Example)

To verify our analytical result, you can simulate the process. Here’s a simple Python code to estimate the probability:

import random

def simulate_once():
    sequence = ""
    while True:
        sequence += random.choice(['H', 'T'])
        if sequence.endswith('HHT'):
            return 1
        if sequence.endswith('HTH'):
            return 0

# Run simulation many times
trials = 100000
results = [simulate_once() for _ in range(trials)]
estimated_prob = sum(results) / trials
print(f"Estimated Probability that HHT appears before HTH: {estimated_prob:.4f}")

For a large number of trials, the result should converge to approximately 0.6667, confirming our calculation.

Step 10: Generalization and Related Interview Questions

This pattern probability problem can be generalized. For any two sequences, the probability that one appears before the other can be found using similar Markov chain analysis. Some classic interview variants include:

• What is the expected number of flips to see a certain sequence?
• What if the coin is biased?
• Probability that HTT appears before TTH?
• Extending the patterns to longer sequences.

Expected Number of Flips to See HHT

For instance, to find the expected number of flips to see HHT, you would define similar states and write equations for expected values instead of probabilities.

Step 11: Table of State Transitions for Reference

Step 12: Interview Tips for Pattern Probability Questions

• Draw the state diagram for partial matches.
• Assign variables toeach state and write out the transition equations clearly.
• Pay attention to overlapping prefixes between sequences; this determines how states are defined.
• Look for absorbing states (when a pattern is fully matched).
• Check your work by simulating or plugging in simple values (e.g., for short sequences or extreme probabilities).
• Practice with different patterns and biased coins to build intuition.

Step 13: Why This Problem Matters in SIG Quantitative Interviews

SIG (Susquehanna International Group) and other top quantitative trading firms ask questions like these to assess analytical thinking, problem decomposition skills, and the ability to translate real-world randomness into mathematical models. Quantitative researchers must routinely solve problems where outcomes depend on sequences of random events, whether in trading algorithms, risk analysis, or model validation.

Demonstrating mastery over pattern probability problems shows interviewers that you can:

• Model complex stochastic processes using Markov chains or recursive logic
• Translate word problems into mathematical equations
• Solve systems of equations and interpret results meaningfully
• Explain your reasoning clearly and concisely, both in writing and aloud

Step 14: A Deeper Dive — Why the Probability Favors HHT

The asymmetry in probability arises from the way the sequences overlap and reset. Let's break down a few sample paths:

• If the first two flips are HH, you're just one T away from HHT. If you get another H, you stay at HH, maintaining your progress.
• If you get HT, you need an H next for HTH, but if you get T, you're reset to the start. Thus, the sequence HHT has a higher tendency to "stick" to progress while HTH is more easily reset.

This is a subtle but critical point: the structure of the Markov chain (as encoded in the state transitions) encodes this asymmetry.

Step 15: Extending the Problem — Other Pattern Pairs

Let’s generalize this approach to other pattern pairs, such as "HTT vs. TTH" or "HTH vs. THH". The same method applies:

1. Define all possible relevant states, based on partial matches.
2. Write recursive equations for the probability that each state leads to the target pattern.
3. Solve the system to find the probability of interest.

For example, for "HTT vs. TTH", you would define states for H, HT, HTT, T, TT, and TTH, and follow the same logic.

Step 16: Expected Number of Flips Until a Pattern Appears

A natural extension is to ask: How many flips, on average, are needed for HHT to appear?

Define:

• E₀: Expected flips from start
• E_H: Expected flips from state H
• E_HH: Expected flips from state HH
• E_HHT: 0 (pattern found)

Write equations:

• E₀ = 1 + 0.5 E_H + 0.5 E₀
• E_H = 1 + 0.5 E_HH + 0.5 E₀
• E_HH = 1 + 0.5 E_HH + 0.5 × 0

Solving these equations gives you the expected number of flips until HHT appears. (Try this as an exercise!)

Step 17: Advanced — Biased Coin Variant

Suppose the coin is not fair; instead, P(H) = p and P(T) = 1 - p. The method remains the same, but transition probabilities are now:

• p × (next state after H)
• (1 - p) × (next state after T)

You can rewrite the recursive equations with these new weights and solve similarly. This is a common way interviewers extend or follow up on the problem!

Step 18: Penney’s Game — A Related Classic

The "which pattern appears first" problem is closely related to Penney’s Game, a famous non-transitive probability game:

• Players pick different sequences (e.g., HHT vs. THH). The winner is the one whose pattern appears first.
• Surprisingly, there is always a pattern that can "beat" another pattern, in a non-transitive way (A beats B, B beats C, C beats A).

Understanding the logic above helps you analyze and even optimize strategies for Penney’s Game — a favorite topic in quant interviews and probability puzzles.

Step 19: Common Mistakes and How to Avoid Them

• Ignoring overlaps: Overlapping prefixes between sequences change the state structure. Always account for all partial matches.
• Not resetting correctly: When a sequence is partially matched but then broken (e.g., HT followed by T), ensure your states reset correctly.
• Wrong absorbing states: Remember that once a target pattern appears, you stop — those are absorbing states with probability 1 (success) or 0 (failure), depending on which pattern appeared.
• Arithmetic errors: Carefully solve the system of equations; double-check your algebra.

Step 20: Practice Problems for Mastery

Test your understanding with these practice problems:

1. Find the probability that "HTT" appears before "TTH" in repeated fair coin tosses.
2. What is the expected number of flips before "HTH" first appears?
3. Suppose the coin is biased with P(H) = 0.7. What is the probability that "HHT" appears before "HTH"?
4. For sequences of length 4, such as "HTHT" and "THTH", how would you model the problem?

Work through these problems using the Markov chain and recursion techniques described above for deep understanding.

Step 21: Summary Table — Key Steps for Pattern Probability Problems

Step 22: Further Reading & Resources

• Penney's Game (Wikipedia)
• Cut-the-Knot: Penney's Game
• Berkeley: Penney Ante Game Analysis
• Books: "Introduction to Probability" by Grinstead and Snell (see chapters on Markov chains)

Conclusion

The coin sequence pattern probability problem — "What is the probability that HHT appears before HTH?" — is a classic test of both probability reasoning and modeling skills, highly relevant to SIG Quantitative Researcher interviews and similar high-level roles. By methodically defining states, writing recursive equations, and solving the system, we find that the answer is 2/3, not 1/2, due to the subtle interplay of pattern overlaps and state transitions.

Mastering this technique empowers you to tackle a wide range of stochastic process and pattern-matching problems, whether in interviews or on the trading floor. Practice this method, extend it to variations, and you’ll be well-prepared for your next quant interview challenge!

SEO Summary

This detailed guide on the SIG Quantitative Researcher Interview question, "Coin Sequence Pattern Probability," covers state-based Markov modeling, recursion, and simulation, providing a comprehensive answer with math and code. Use this resource to build your understanding and excel in quant interviews.