cswork / libraryOpen practice workspace

Coding questions · Morgan Stanley

Compute win probability in coin-toss game

This question evaluates understanding of probability theory and stochastic processes, focusing on win probability in an alternating coin-toss game and reasoning about pattern occurrence and stopping times in random sequences.

Two players, A and B, play the following game with a fair coin:

  • They toss the coin alternately: A tosses first, then B, then A, then B, and so on.
  • The sequence of results (H for heads, T for tails) is recorded in order.
  • The game ends as soon as the subsequence "HT" (a head immediately followed by a tail on the next toss) appears for the first time.
  • The person who tosses the tail in this first "HT" subsequence wins the game.

Assuming the coin is fair and the game continues indefinitely until it ends, what is the probability that player A wins the game?

Coin Toss HT Win Probability

Return the exact probability that player A wins the alternating fair-coin game that ends at the first HT pattern.

Constraints

  • Return the reduced probability as a string fraction.

Examples

Example 1

Input: ()
Output: '4/9'

Explanation: Solving the four-state recurrence for alternating tosses gives A win probability 4/9.

Hints

  1. Track whose turn it is and whether the previous toss was H.
  2. Solve the resulting linear equations.