Katkat
Back

Solve Classic Probability Questions

CitadelData Scientist · Onsite
HardData ScientistOnsiteStatistics & Math

Last updated

This problem tests your ability to calculate the expected stopping time of a stochastic process and your proficiency with the linearity of expectation in the context of sequential probability.

The Problem: The Incremental Gambler

You are playing a game where you roll a fair 6-sided die repeatedly. You stop rolling as soon as the sequence of the last two rolls forms an increasing pair (i.e., the second roll is strictly greater than the first roll, such as rolling a 2 then a 5).

Let N be the random variable representing the total number of rolls performed when the game stops. Calculate the expected value E[N].

Constraints

  • The die is fair with faces {1, 2, 3, 4, 5, 6}.
  • You must roll at least twice to satisfy the stopping condition.

Example

  • Sequence: [3, 2, 4].
    • Roll 1: 3
    • Roll 2: 2 (Not increasing, continue)
    • Roll 3: 4 (4 > 2 is increasing, stop)
    • N = 3.

Deliverable

Provide a formal derivation of E[N]. Show how you define the state space or the recursive relations to solve for the expected stopping time.

Hints

Hint 1

Define E as the expected number of additional rolls needed given the value of the most recent roll.

Hint 2

Set up a system of linear equations where E_i is the expected number of *future* rolls needed given the last roll was i.

Hint 3

Note that for a roll i, the probability of stopping on the next roll is (6-i)/6, and if you don't stop, you transition to a state j with probability 1/6.

Follow-up questions

  • How does the expected value change if you require the sum of the last two rolls to be at least 7?
  • If the die were biased such that the probability of rolling i is p_i, how would the structure of your system of equations change?
  • Can you derive the variance of N, or is the calculation significantly more complex than the expectation?