Quant puzzles, solved step by step

Puzzles
100
Traced to a firm
71
Topics
12
Hard
30
Topic
All topicsLogic and algorithmic reasoning10Conditional probability and Bayes7Counting and combinatorics8Continuous and geometric probability9Correlation, regression and linear algebra9Market making, betting and sizing9Expected value and optimal stopping9Statistics and estimation9Pricing, options and index maths7Games and strategic reasoning8Markov chains and random walks7Mental maths and number sense8
Level
AnyWarm upCoreHard
Source
AnyReported at a firmStandard
Showing 1–1 of 1 · filtered from 100Clear filters
  1. 030We play chess repeatedly. Each game is drawn with probability 1/2; of the decisive games I win 2/3 and you win 1/3. The match ends when one of us wins three games in a row, and a draw breaks any streak. What is the probability I win the match?Markov chains and random walksHardOld Mission CapitalChicago · 2018

    Try it first

    Roughly what is my chance of winning the match?

    Show the worked solution

    86/99, about 86.9%. Track only the current streak: none, me on 1 or 2, you on 1 or 2. Each game I win with probability 1/3, you win with 1/6, and a draw, 1/2, resets the streak. Write my chance of taking the match from each state in terms of the others, solve the five equations, and the start state comes out at 86/99.

    What is the state, and why is the running score not it?

    A door lock that opens after three correct codes in a row does not care how many wrong codes came before the last mistake. The only thing that matters for the rest of this match is the current streak, so the states are: no streak, my streak of 1 or 2, and your streak of 1 or 2. Games won earlier, draws played, games elapsed: all irrelevant once the streak is known. That is the Markov propertyThe future depends on the past only through the present state., and spotting it turns an infinite tree of game sequences into five numbers. Per game, I win with probability 1/2 x 2/3 = 1/3, you win with 1/2 x 1/3 = 1/6, and the rest are draws.

    Five live states, two endings: one equation per live state1/31/61/31/31/61/61/61/31/6 from I on 21/3 from You on 2Startmy chance 86/99I on 129/33I on 210/11You on 128/33You on 28/11I winthe matchYou winthe matchEvery draw (probability 1/2) from any state sends the match back to Start.Grey figure in each box: my chance of winning the match from that state.
    The match has five live states and two endings; solving one equation per state gives my chance of winning as 86/99 from the start, rising to 10/11 when I am on a streak of two and falling to 8/11 when you are.

    How do the equations go, and how do you solve them quickly?

    Let x be my chance from the start, a1 and a2 from my streaks, b1 and b2 from yours. Every equation reads the same way: play one more game, three things can happen. A draw always returns to the start, a win for me always moves to a1 or one step up, and a win for you always moves to b1 or one step up. From a2 my next win ends the match in my favour; from b2 your next win ends it against me.

    The relationship
    x=13a1+16b1+12xa1=13a2+16b1+12xa2=13+16b1+12xb1=13a1+16b2+12xb2=13a1+12x\begin{aligned} x &= \tfrac13 a_1 + \tfrac16 b_1 + \tfrac12 x & a_1 &= \tfrac13 a_2 + \tfrac16 b_1 + \tfrac12 x & a_2 &= \tfrac13 + \tfrac16 b_1 + \tfrac12 x \\ b_1 &= \tfrac13 a_1 + \tfrac16 b_2 + \tfrac12 x & b_2 &= \tfrac13 a_1 + \tfrac12 x \end{aligned}
    xmy chance of winning the match from a fresh start
    a1, a2my chance when I have won the last one or two games
    b1, b2my chance when you have won the last one or two games
    What it says in wordsEach state's value is the average of where the next game can send the match, weighted by the chance of each result.

    Solve by substituting: b2 is in terms of a1 and x, which gives b1 in the same terms; feed that into a2 and a1, and the start equation leaves one unknown. The answers: x = 86/99, a1 = 29/33, a2 = 10/11, b1 = 28/33, b2 = 8/11. Check the ordering: the further I am ahead, the higher the value, and every value sits between 0 and 1. Your chance is 13/99. A quick cross-check: three wins in a row is (1/3) cubed for me and (1/6) cubed for you, a ratio of 8 to 1, which would suggest about 89%; landing within two points of that rough race is a sign no term was dropped.

    Where candidates lose it

    Candidates often forget that a draw resets both streaks, or they let a draw keep a streak alive. The question says draws break any streak, which is why every state has a path back to the start, and dropping that path changes the answer.

    The other loss is trying to add up sequences of games. The sequences never end; the states are five. Name the states first, write one line per state, and the problem becomes algebra.

    What the interviewer asks next

    • What if a draw does not break a streak?
    • What is the expected number of games the match lasts?
    • What if the match needs only two wins in a row?

    Asked at Old Mission Capital, Prop Trading, Chicago, 2018 (Wall Street Oasis): You and I play chess. 1/2 games end in draws and in the other half I win with 2/3 probability