Compute win probability in coin-toss game
Company: Morgan Stanley
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Technical Screen
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?
Quick Answer: 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.
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
Input: ()
Expected Output: '4/9'
Explanation: Solving the four-state recurrence for alternating tosses gives A win probability 4/9.
Hints
- Track whose turn it is and whether the previous toss was H.
- Solve the resulting linear equations.