Quant puzzles, solved step by step

Puzzles: 100
Traced to a firm: 71
Topics: 12
Hard: 30

Showing 1–3 of 3 · filtered from 100Clear filters

023You flip a fair coin until the pattern HTH appears. What is the expected number of flips? Why is it larger than the expected wait for HTT, when each pattern has the same probability of 1/8 at any given position?Markov chains and random walksHardQuant tradingQuant research
Try it first
Expected flips to see HTH?
Show the worked solution
10 flips for HTH, against 8 for HTT. Track how much of the pattern you currently hold: nothing, H, or HT. For HTH, a tail after HT wrecks everything and you restart from nothing. For HTT, a head after HT breaks the pattern, but that head is itself a fresh start, so you keep an H. Solving the three expected-wait equations gives 10 and 8.
Why do equal probabilities give unequal waits?
Think of a combination lock where a wrong digit sometimes resets you to zero and sometimes lets you keep part of your progress. Two combinations can be equally likely to be dialled at random yet take different times to reach. Each three-flip window is HTH or HTT with the same 1/8 chance, but the windows overlap, and HTH occurrences tend to arrive in clusters, such as HTHTH, which spaces out the first appearance. The waiting time depends on where a near miss leaves you.
Waiting for HTH, a tail from state HT sends you back to the start and the average wait is 10 flips; waiting for HTT, a head from HT leaves you holding an H and the average wait is only 8.
How do you set up the equations?
Let E0, E1 and E2 be the expected remaining flips when you hold nothing, H and HT. Each flip costs one and moves you to the next state with probability one half each way, so each state's wait is 1 plus the average of the two states it can move to. For HTH: E0 = 1 + (E1 + E0)/2, E1 = 1 + (E1 + E2)/2, E2 = 1 + (0 + E0)/2. Solving gives E2 = 6, E1 = 8, E0 = 10. For HTT only the last equation changes, to E2 = 1 + (0 + E1)/2, and the answers become 4, 6 and 8.
The relationship
$E_{HTH} = 2^3 + 2^1 = 10 \qquad E_{HTT} = 2^3 = 8$
2^3 from the whole pattern matching itself
2^1 from HTH's last flip matching its first: the pattern overlaps itself
What it says in wordsFor a fair coin, add 2 to the power k for every length k at which the pattern's start equals its end.
Is there a shortcut an interviewer will accept?
Yes, the overlap rule, which comes from a fair-bet argument known as the ABRACADABRA methodA martingale argument in which gamblers arriving each flip bet on the pattern, used to compute expected waiting times for patterns.. For a fair coin, the expected wait is the sum of 2 to the k over every k where the first k flips of the pattern equal the last k. HTH matches itself at length 3 and at length 1, the single H, giving 8 + 2 = 10. HTT matches only at length 3, giving 8. HHH matches at 1, 2 and 3, giving 14. Derive the states first, then offer the rule as the check.
Where candidates lose it
The trap is answering 8 for every three-flip pattern, reasoning that each has probability 1/8 per window. That confuses frequency with first arrival: over a long run both patterns appear equally often, but HTH comes in overlapping clumps.
The second loss is getting the fall-back wrong in the state diagram. For HTT, after HT a head is not a return to nothing; it is a new H. Drawing that arrow to the start gives 10 for both and hides the whole point.
What the interviewer asks next
What is the expected wait for HHH?
Two players race, one waiting for HTH and one for HTT on the same flips. Who is more likely to win?
With a biased coin that shows heads 60% of the time, what is the expected wait for HTH?
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.
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
$\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}$
x my chance of winning the match from a fresh start
a1, a2 my chance when I have won the last one or two games
b1, b2 my 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
095A knight starts in a corner of an empty chessboard and moves at random, choosing uniformly among its legal moves at every turn. What is the expected number of moves until it first returns to the starting corner?Markov chains and random walksHardQuant researchQuant trading
Try it first
Pick the expected return time.
Show the worked solution
168 moves. A random walk that picks uniformly among a square's moves spends time at each square in proportion to its number of moves, its degree. The degrees on a chessboard sum to 336 and a corner has degree 2, so the knight is in that corner 2/336 of the time. The expected return time is the reciprocal, 336/2 = 168.
Why is the time spent on a square proportional to its number of moves?
Think of a town where every road is two-way and a lost tourist picks a road at random at each junction. Big junctions get more visits simply because more roads lead into them. For a random walk on a network of two-way links, the long-run share of time at a point is its number of links divided by the total, because that split sends exactly as much traffic along every link in each direction. Check it on one knight move from square u to square v: the flow is (d_u/336) x (1/d_u) = 1/336, and the flow back is the same, so nothing piles up anywhere.
The knight's move counts range from 2 in the corners to 8 in the centre and total 336, so the walk spends 2/336 of its time in the starting corner and returns to it every 168 moves on average.
The relationship
$\pi_v = \frac{d_v}{\sum_u d_u}, \qquad \mathbb{E}[\text{return time to } v] = \frac{1}{\pi_v} = \frac{\sum_u d_u}{d_v} = \frac{336}{2} = 168$
d_v the number of legal knight moves from square v
pi_v the long-run share of time the walk spends at v
sum of d_u the total of the move counts over all 64 squares, 336
What it says in wordsThe share of time at a square is its move count over the total, and the average gap between visits is one over that share.
How do you get 336 quickly and check it?
Tally the move counts by symmetry, as in the figure: four corners with 2, eight squares with 3, twenty with 4, sixteen with 6 and sixteen with 8. For a check, count the moves themselves: every knight move is a diagonal of a 2 by 3 or 3 by 2 rectangle, there are 84 such rectangles on the board, each holds 2 moves, so there are 168 two-way moves and 336 move ends. The answer, 168, happens to equal the number of moves, a coincidence of the corner having exactly two.
What are the limits of the trick?
The rule that return time is one over the long-run share holds for any chain that can reach every state and settles down, which is Kac's lemma. The degree formula for that share needs two-way moves chosen uniformly; if the knight preferred some moves, you would have to solve for the share directly. One more subtlety is worth saying: a knight always changes square colour, so it can only return after an even number of moves, and the chance of being in the corner at a fixed time does not settle down. The average return time is unaffected, and a seeded simulation of 100,000 returns gives 168.0. From a central square with 8 moves the return time is 336/8 = 42.
Where candidates lose it
The usual wrong answer is 64, from assuming the knight spends equal time on every square. It does not: squares with more moves are visited more often, and a corner, with only two moves, is one of the rarest.
The second loss is setting up 64 equations for expected hitting times. That works on paper and fails in an interview. Say the degree rule, count the degrees by symmetry, and check the total with the rectangle count.
What the interviewer asks next
What is the expected return time to a central square such as d4?
Answer the same question for a king starting in a corner.
Why does the knight always need an even number of moves to come back?

2^3	from the whole pattern matching itself
2^1	from HTH's last flip matching its first: the pattern overlaps itself

x	my chance of winning the match from a fresh start
a1, a2	my chance when I have won the last one or two games
b1, b2	my chance when you have won the last one or two games

d_v	the number of legal knight moves from square v
pi_v	the long-run share of time the walk spends at v
sum of d_u	the total of the move counts over all 64 squares, 336

Try it first

Why do equal probabilities give unequal waits?

How do you set up the equations?

Is there a shortcut an interviewer will accept?

Where candidates lose it

What the interviewer asks next

Try it first

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

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

Where candidates lose it

What the interviewer asks next

Try it first

Why is the time spent on a square proportional to its number of moves?

How do you get 336 quickly and check it?

What are the limits of the trick?

Where candidates lose it

What the interviewer asks next