Katkat
Back

Compute answers to probability and counting puzzles

SIG (Susquehanna)Data Scientist · Technical Screen
HardData ScientistTechnical ScreenStatistics & Math

Last updated

This problem tests your ability to model sequential probabilistic events using combinatorics and conditional probability, specifically requiring the calculation of expected outcomes in a game of chance.

Problem Statement

You are playing a game with a fair, six-sided die. You roll the die repeatedly and record the sequence of outcomes. The game ends as soon as you roll a '6'.

  1. What is the expected number of rolls to see the first '6'?
  2. Suppose instead that you continue rolling until you see a '6' immediately preceded by a '5'. What is the expected number of rolls to see this specific sequence (e.g., in the sequence [2, 3, 5, 6], the game ends on the 4th roll)?

Provide the derivation for both parts. For part 2, clearly define your state space or use linearity of expectation to justify your approach.

Constraints

  • The die is fair (probability of any face is 1/6).
  • Rolls are independent.

Examples

  • Sequence [1, 2, 6]: Game ends at roll 3.
  • Sequence [5, 5, 6]: The '5' followed by '6' only occurs at the end; game ends at roll 3.

Edge Cases

  • Consider if the sequence '5' followed by '6' is overlapped by other rolls (e.g., does a '5' followed by a '5' followed by a '6' count as ending on the third roll? Yes).

Hints

Hint 1

For the first part, recognize that the number of trials until the first success follows a Geometric distribution with parameter p = 1/6.

Hint 2

For the second part, define E as the expected total rolls, and consider sub-states: E0 (no progress), E1 (last roll was a 5), and E2 (terminal state).

Hint 3

Set up a system of linear equations based on the transitions between these states: E0 = 1 + (1/6)E1 + (5/6)E0 and E1 = 1 + (1/6)(0) + (1/6)E1 + (4/6)E0.

Follow-up questions

  • How would the expected value in the second scenario change if the die were biased such that '6' appears with probability 1/4 and all other sides appear with probability 3/20?
  • If we were looking for the sequence '6' followed by '6' instead of '5' followed by '6', how would the state space transition equations change?
  • Can you derive the variance of the number of rolls in the first scenario, and why is it higher than the square of the mean?