blog-cover-image

Akuna Capital Quantitative Researcher Intern Interview Question: Expected Tosses to Get Two Consecutive Heads

Quantitative research interviews at top trading firms such as Akuna Capital are known for their challenging probability and brainteaser questions. One classic problem that often appears in these interviews involves analyzing the expected number of coin tosses required to achieve two consecutive heads. This question elegantly tests your understanding of probability, Markov processes, and expectation calculation. In this comprehensive article, we break down the problem, discuss relevant concepts, and provide a detailed, step-by-step solution, ensuring that you are well-prepared for your Akuna Capital Quantitative Researcher Intern interview.

Akuna Capital Quantitative Researcher Intern Interview Question: Expected Tosses to Get Two Consecutive Heads

1. Understanding the Interview Question

The interview question asks: "Suppose you flip a fair coin repeatedly. What is the expected number of tosses required to get two consecutive heads (i.e., HH) for the first time?"

This is a classic problem in probability theory and tests your ability to model random processes and compute expectations.

Key Concepts Involved

Markov Chains and States
Law of Total Expectation
Conditional Probability
Recursive Equations

2. Modeling the Problem: States and Transitions

To solve this problem, we first need to understand it in terms of states. At any point after a toss, we can describe the process by the outcome of the previous toss (if any). Let's define the states:

State S (Start): No tosses yet, or last toss was a Tails.
State H (Head): Last toss was a Heads, but not two consecutive Heads yet.
State HH (Goal): Last two tosses were both Heads (i.e., achieved two consecutive Heads).

Our process starts in state S. We want to determine the expected number of tosses to reach state HH for the first time.

Visualizing the State Transition Diagram

The process can be illustrated as follows:

From S:
- Flip H: Move to H.
- Flip T: Stay in S.
From H:
- Flip H: Move to HH (Success).
- Flip T: Move to S.
From HH: Absorbing state (we stop).

3. Setting Up the Equations

Let’s define:

\( E_S \): Expected number of tosses starting from state S.
\( E_H \): Expected number of tosses starting from state H.
\( E_{HH} \): Expected number of tosses starting from state HH.

Clearly, once we reach state HH, we are done, so \( E_{HH} = 0 \).

Recurrence Relations

Let’s write recursive equations for \( E_S \) and \( E_H \) using the law of total expectation.

From State S:
On the next toss,
- With probability \( \frac{1}{2} \), we get H and move to H (cost: 1 toss + expected value from H).
- With probability \( \frac{1}{2} \), we get T and stay in S (cost: 1 toss + expected value from S).
Thus,
\[ E_S = 1 + \frac{1}{2}E_H + \frac{1}{2}E_S \]
From State H:
On the next toss,
- With probability \( \frac{1}{2} \), we get H and move to HH (cost: 1 toss + expected value from HH, which is 0).
- With probability \( \frac{1}{2} \), we get T and move to S (cost: 1 toss + expected value from S).
Thus,
\[ E_H = 1 + \frac{1}{2} \times 0 + \frac{1}{2}E_S = 1 + \frac{1}{2}E_S \]

Now, with these two equations, we can solve for \( E_S \) and \( E_H \).

4. Solving the System of Equations

Step 1: Expressing Everything in Terms of \( E_S \)

From above:

\( E_H = 1 + \frac{1}{2}E_S \) (1)
\( E_S = 1 + \frac{1}{2}E_H + \frac{1}{2}E_S \) (2)

From (2), bring all terms involving \( E_S \) to one side:

\[ E_S - \frac{1}{2}E_S = 1 + \frac{1}{2}E_H \] \[ \frac{1}{2}E_S = 1 + \frac{1}{2}E_H \] \[ E_S = 2 + E_H \]

Now substitute the value of \( E_H \) from (1):

\[ E_S = 2 + \left(1 + \frac{1}{2}E_S\right) \] \[ E_S = 3 + \frac{1}{2}E_S \] \[ E_S - \frac{1}{2}E_S = 3 \] \[ \frac{1}{2}E_S = 3 \] \[ E_S = 6 \]

Now, substitute back to find \( E_H \):

\[ E_H = 1 + \frac{1}{2}E_S = 1 + \frac{1}{2} \times 6 = 1 + 3 = 4 \]

So,

Expected number of tosses from state S (start): 6
Expected number from H (after one Head): 4

5. Final Answer and Interpretation

The expected number of tosses to get two consecutive heads is 6.

This means that, on average, you need to flip a fair coin 6 times before seeing two Heads in a row for the first time.

6. In-Depth Explanation of the Concepts

Markov Chain Representation

The process of flipping a coin and waiting for two consecutive heads can be modeled as a Markov chain: a random process that moves between states with certain probabilities, and where the next state depends only on the current state.

Here, the states are S, H, and HH, and the transitions are determined by the result of each coin toss.

Law of Total Expectation

This law allows us to break down the expected value based on possible outcomes. In this case, after each toss, the expected value is the immediate cost (1 toss) plus the expected value from the new state, weighted by the probability of each outcome.

Solving Linear Equations

The recursive approach leads to a system of linear equations, which is a common technique for Markov chain first-passage problems.

7. Generalization: Expected Tosses to Get n Consecutive Heads

What if the question asked for the expected number of tosses to get n consecutive heads? Let’s generalize the solution.

Let \( E_k \) be the expected number of tosses to get \( k \) consecutive heads (starting from no heads in a row).

We can use a similar state approach:

Let state \( S_j \) denote "just got \( j \) consecutive heads," for \( 0 \leq j < n \).
Our goal is to reach \( S_n \).

The recurrence:

\[ E_0 = 1 + \frac{1}{2}E_1 + \frac{1}{2}E_0 \] \[ E_j = 1 + \frac{1}{2}E_{j+1} + \frac{1}{2}E_0, \quad \text{for } 1 \leq j < n \] \[ E_n = 0 \]

This system can be solved recursively or using generating functions, but for \( n = 2 \), as already shown, the answer is 6.

8. Simulation Approach: Verifying the Result with Python

Sometimes, it’s instructive to simulate the process to see if the theoretical result matches empirical data. Here’s a Python script that simulates a large number of coin toss sequences and computes the average number of tosses required to get two consecutive heads.


import random

def toss_until_two_heads():
    count = 0
    prev = ''
    while True:
        flip = random.choice(['H', 'T'])
        count += 1
        if prev == 'H' and flip == 'H':
            return count
        prev = flip

# Run simulation
n_trials = 100000
total_tosses = sum(toss_until_two_heads() for _ in range(n_trials))
print("Simulated Expected Tosses:", total_tosses / n_trials)

Running this simulation with a large number of trials (e.g., 100,000) should give a value very close to 6.

9. Alternative Solution Methods

Method 1: Using First-Step Analysis

Let’s revisit the problem and define:

Let \( E \) be the expected number of tosses to get two consecutive heads from the start.

Each toss, you might:

Toss a Tails (\( \frac{1}{2} \)): you’re back where you started, need to start over.
Toss a Heads (\( \frac{1}{2} \)): now you need one more Head in a row.

Let \( F \) be the expected number of additional tosses needed after getting one Head.

With probability \( \frac{1}{2} \), next toss is Tails: go back to starting position (\( E \)).
With probability \( \frac{1}{2} \), next toss is Heads and you’re done.

\[ E = 1 + \frac{1}{2}E + \frac{1}{2}F \] \[ F = 1 + \frac{1}{2}E + \frac{1}{2} \times 0 \] \[ F = 1 + \frac{1}{2}E \] Substitute \( F \) into \( E \): \[ E = 1 + \frac{1}{2}E + \frac{1}{2}(1 + \frac{1}{2}E) \] \[ E = 1 + \frac{1}{2}E + \frac{1}{2} + \frac{1}{4}E \] \[ E - \frac{1}{2}E - \frac{1}{4}E = 1 + \frac{1}{2} \] \[ \frac{1}{4}E = \frac{3}{2} \] \[ E = 6 \] Same result!

10. Common Variations of the Problem

These types of questions can be extended or varied in several ways:

What if the coin is biased?
If the probability of Heads is \( p \), similar equations can be set up, but probabilities will differ.
What about getting k consecutive Heads?
The recursive method generalizes to larger k.
What is the expected number of tosses to see a specific pattern (e.g., HT, THT, etc.)?
Such problems can be solved by extending the state space to remember the recent sequence of outcomes.

11. Frequently Asked Questions

Question	Answer
What is the expected number of tosses to get the pattern HT?	By similar methods, the answer is 4.
Does the solution change if the coin is unfair?	Yes. The recurrence relations involve the probabilities of Heads and Tails, and the expected value changes accordingly.
What if I want three consecutive Heads?	The expected number becomes 14. This can be derived using a similar method, with more states.
How can I generalize to any pattern?	Create a state for each possible "partial progress" towards the pattern, and set up a system of equations.

12. Interview Tips: How to Approach These Problems

Break Down the Problem: Identify the relevant states and transitions.
Write Recursive Equations: Use the law of total expectation to relate expected values.
Check Boundary Conditions: Know when the process stops (absorbing state).
Verify: If possible, simulate or check with small cases to validate your answer.
Explain Clearly: During interviews, walk through your logic step by step.

13 13. Deeper Dive: Why is the Expected Value 6?

It may seem counterintuitive that it takes, on average, 6 tosses to see two heads in a row, especially since the probability of getting heads on a single toss is only 1/2. Let’s analyze why this number is not simply the sum of the expected tosses for two heads (which would be 4), but rather is greater.

Not Just Two Heads, But Two Consecutive Heads

If you were to ask, “How many tosses until you see two heads (anywhere)?” the expected number is 4. This is because each toss has a 1/2 chance of being heads, so the expected number of tosses to get one head is 2, and the second head another 2, totaling 4.

However, requiring consecutive heads is more restrictive. Every time you get a Tails, any 'progress' towards building up a streak of heads is lost. Even after getting a head, if the next toss is tails, you must start over. This “reset” effect increases the expected waiting time.

Memoryless Property and Markov Chains

The process is memoryless: after each tails, you’re in the same situation as at the very start. That’s why the recursive equations reflect the probability of “starting over” after a tails, which is what drives up the expected value.

14. Generalizing Further: Patterns and Waiting Times

Problems involving the expected number of tosses to see a particular sequence of coin tosses are a subset of the broader Pattern Waiting Time problems in probability theory and information theory.

General Formula for n Consecutive Heads

For a fair coin, the general expected waiting time for n consecutive heads is:

\[ E_n = 2^{n+1} - 2 \]

Let’s see this for n = 2:

\[ E_2 = 2^{3} - 2 = 8 - 2 = 6 \]

For n = 3:

\[ E_3 = 2^{4} - 2 = 16 - 2 = 14 \]

This formula is derived by recursively analyzing the states as done above.

n	Expected Tosses to n Consecutive Heads
1	2
2	6
3	14
4	30
5	62

Derivation Sketch

Why is this the case? For each additional consecutive head required, the number of states increases, and each time you get a tails, you must start over. The recursion leads to the formula above.

15. Extending to Biased Coins

Suppose the coin is not fair, i.e., the probability of heads is \( p \) and tails is \( 1-p \). The recurrence relations must be adjusted:

From the start: \( E_S = 1 + p E_H + (1-p)E_S \)
From H: \( E_H = 1 + p \cdot 0 + (1-p)E_S \)

Solving these:

\[ E_H = 1 + (1-p)E_S \] \[ E_S = 1 + p E_H + (1-p)E_S \] \[ E_S - (1-p)E_S = 1 + p E_H \] \[ p E_S = 1 + p E_H \] \[ E_S = \frac{1}{p} + E_H \]

Substitute \( E_H \):

\[ E_S = \frac{1}{p} + 1 + (1-p)E_S \] \[ E_S - (1-p)E_S = \frac{1}{p} + 1 \] \[ p E_S = \frac{1}{p} + 1 \] \[ E_S = \frac{1}{p^2} + \frac{1}{p} \]

For \( p = 0.5 \), this gives \( E_S = 4 + 2 = 6 \), as before.

16. Related Problems: Patterns Beyond Consecutive Heads

In many interviews, you may be asked about more complicated patterns, such as:

Expected tosses until the sequence HTH appears
Expected tosses until getting a run of k consecutive tails
Expected tosses until you see every possible pair (HT, TH, HH, TT)

Each of these can be solved by defining appropriate states and writing recursive equations.

Example: Expected Tosses for Pattern HTH

Define states:

S: Start
H: Last toss H
HT: Last two tosses HT
HTH: Goal

Write recurrences for expected steps from each state, then solve as a system of equations.

17. Code Example: Generalized Simulation for Patterns

Here’s Python code to simulate the expected number of tosses to reach any given pattern:


import random

def pattern_wait_time(pattern, n_trials=100000):
    k = len(pattern)
    total = 0
    for _ in range(n_trials):
        count = 0
        last = []
        while True:
            flip = random.choice(['H', 'T'])
            last.append(flip)
            if len(last) > k:
                last.pop(0)
            count += 1
            if len(last) == k and ''.join(last) == pattern:
                break
        total += count
    return total / n_trials

print("Expected tosses to get 'HH':", pattern_wait_time('HH'))
print("Expected tosses to get 'HTH':", pattern_wait_time('HTH'))

This code can be used to test your calculations for any pattern.

18. Practical Applications in Quantitative Research

Why do interviewers at Akuna Capital and other trading firms care about such problems?

Markov Processes: Many market models and strategies can be represented as Markov processes with discrete states and transitions.
Risk Assessment: Understanding waiting times and event probabilities is crucial for risk modeling and strategy backtesting.
Pattern Recognition: Detecting events or sequences in time series is a key quantitative skill.
Code Implementation: Translating mathematical solutions into efficient code is essential for real-world quant work.

19. How to Prepare for Such Interview Questions

Practice classic probability puzzles involving dice, cards, and coins.
Be comfortable with Markov chains, recurrence relations, and expectation calculations.
Simulate problems in Python or another language to verify your results.
Explain your solution clearly, both verbally and in writing.
Be prepared for variations, such as biased coins or different target patterns.

20. Conclusion: Key Takeaways

The expected number of coin tosses to get two consecutive heads is 6.
This is solved using recursive equations and Markov chain analysis.
The method generalizes to more complex patterns and biased coins.
Understanding these problems is crucial for quantitative interviews and for modeling real-world stochastic processes.

Mastering such problems will not only help you ace your Akuna Capital Quantitative Researcher Intern interview but also build a strong foundation for a career in quantitative finance and algorithmic trading.

21. Further Reading & Resources

22. Appendix: Full Derivation for Three Consecutive Heads

Let’s show the system for three consecutive heads (n = 3) as a further learning example.

S: Start (no consecutive heads yet)
H: Last toss was H (1 head in a row)
HH: Last two tosses were HH (2 heads in a row)
HHH: Done (3 heads in a row)

Let \( E_S, E_H, E_{HH}, E_{HHH} \) be expected tosses from each state, with \( E_{HHH} = 0 \).

Recurrences:

\[ E_S = 1 + \frac{1}{2}E_H + \frac{1}{2}E_S \] \[ E_H = 1 + \frac{1}{2}E_{HH} + \frac{1}{2}E_S \] \[ E_{HH} = 1 + \frac{1}{2}E_{HHH} + \frac{1}{2}E_S = 1 + \frac{1}{2} \times 0 + \frac{1}{2}E_S = 1 + \frac{1}{2}E_S \]

Substitute upwards:

\( E_{HH} = 1 + \frac{1}{2}E_S \)
\( E_H = 1 + \frac{1}{2}(1 + \frac{1}{2}E_S) + \frac{1}{2}E_S = 1 + \frac{1}{2} + \frac{1}{4}E_S + \frac{1}{2}E_S = \frac{3}{2} + \frac{3}{4}E_S \)
\( E_S = 1 + \frac{1}{2}E_H + \frac{1}{2}E_S \rightarrow E_S - \frac{1}{2}E_S = 1 + \frac{1}{2}E_H \rightarrow \frac{1}{2}E_S = 1 + \frac{1}{2}E_H \rightarrow E_S = 2 + E_H \)

Now substitute \( E_H \):

\[ E_S = 2 + E_H = 2 + \frac{3}{2} + \frac{3}{4}E_S = \frac{7}{2} + \frac{3}{4}E_S \] \[ E_S - \frac{3}{4}E_S = \frac{7}{2} \] \[ \frac{1}{4}E_S = \frac{7}{2} \] \[ E_S = 14 \]

Thus, it takes on average 14 tosses to get three consecutive heads.

23. Summary Table: Expected Tosses for Patterns Starting from S

Pattern	Expected Tosses (E)
H	2
HH	6
HHH	14
HT	4
HTH	10

24. Practice Problems for Interview Preparation

What is the expected number of tosses to get the pattern TTH?
Suppose you have a biased coin with \( p(H) = 0.3 \). What is the expected number of tosses to see two consecutive heads?
Extend the method to compute the expected number of tosses to see the sequence HTHH.
Prove that for a fair coin, the expected number of tosses to get n consecutive heads is \( 2^{n+1} - 2 \).

With this understanding, you are well-equipped to tackle interview questions involving expected values, Markov chains, and pattern waiting times. Good luck with your Akuna Capital Quantitative Researcher Intern interview!