Quant puzzles, solved step by step

Bid nothing. If a bid of b is accepted, the owner has told you the company is worth less than b to them, so its value is uniform on 0 to b and averages b/2. In your hands that is 1.5 x b/2 = 0.75b, a quarter less than you paid. Expected profit is (b/100) x (0.75b - b) = -b squared/400, negative for every positive bid. This is the winner's curse in its purest form.

Why does 75 look right and fail?

Picture buying a used car from someone who knows its history while you do not. If they agree to your price at once, that is itself news: sellers of good cars refuse low offers. Acceptance is not random; it happens exactly in the states where the company is worth less than you offered, so the average value you actually receive is the average below your bid, not the average overall. The naive 75 uses the unconditional average of 50 and forgets that you only trade when the owner is happy to sell.

How do you set up the expected profit?

Split it into the chance of a deal and the profit given a deal. A bid of b is accepted with probability b/100; given acceptance the owner's value is uniform on 0 to b, averaging b/2, so your value averages 0.75b and your profit averages minus 0.25b. Multiply: minus 0.25b x b/100, which is minus b squared over 400. At a bid of 50 that is minus 6.25 crore: you win half the time and lose 12.5 crore on average when you do.

When would bidding make sense, and where does this show up on a desk?

The multiplier is the lever. With a multiplier m, the profit given a deal is (m/2 - 1)b, so bidding pays only if you add more than double the owner's value; at exactly 2 you break even, and above 2 you should bid the full 100. On a trading desk the same logic is called adverse selectionThe tendency for the trades you actually get to come from counterparties with better information than you, so they are worse on average than a random trade.: the orders that fill against you are disproportionately the ones from people who know more. A quote that looks profitable against the average counterparty loses against the ones who choose to trade.

You get 0.75, not 1. Regressing y on x1 alone gives a slope of 1 + 0.5 = 1.5, because x1 soaks up the half of x2 that moves with it. The residual is x2 - 0.5x1 + noise, whose slope on x2 is 1 - 0.5 squared = 0.75. To recover 1, residualise x2 on x1 as well and regress the residual of y on the residual of x2: the Frisch-Waugh-Lovell theorem.

Where does the missing quarter go?

Picture two salespeople who often work the same client. If you credit all joint sales to the first before looking at the second, the second looks worse than they are, because some of their work was already booked to the first. Stage one regresses y on x1 alone, and since x2 is correlated with x1, the coefficient on x1 rises to 1.5: it takes credit for 0.5 of x2. That piece has been removed from the residual, so stage two can only find what is left of x2's effect.

How do you get 0.75 exactly?

Write the residual out. y - 1.5x1 = x2 - 0.5x1 + noise, and the slope of that on x2 is its covariance with x2 over the variance of x2: (1 - 0.5 x 0.5)/1 = 0.75. The formula generalises to 1 - rho squared times the true coefficient, so the bias gets worse as the regressors get more correlated: with rho = 0.9 you would find only 0.19. A simulation of 100,000 observations gives 1.506 for stage one and 0.752 for stage two.

What does Frisch-Waugh-Lovell tell you to do?

To get a variable's coefficient from a multiple regression in stages, partial the other regressors out of both y and that variable, then regress residual on residual. Here that means regressing x2 on x1 as well, keeping the orthogonal part x2 - 0.5x1, and regressing the stage-one residual on it. The slope comes back as exactly 1; the simulation gives 1.003. This is why factor-neutralising a signal before testing it, rather than after, matters in quant research: the order of the stages changes the answer.

Fire into the air. B and C each target the other, the bigger threat, so while both live nobody shoots at you. Aiming in the air gives survival of 2/3 x 3/7 + 1/3 x 1/3 = 25/63, about 39.7%. Aiming at C gives 31.2%, because a hit leaves you in a duel with B shooting first. Aiming at B gives 26.5%, because a hit leaves C, who never misses, to shoot you.

Who does everyone else aim at?

Start with the stronger players, because their choices fix yours. B aims at C, because if B shot you instead, C would kill B next turn for certain; C aims at B, the more dangerous of the two remaining threats. So while all three are alive, nobody is shooting at you. Think of two large firms in a price war while a small competitor stays out of it: the small firm's best move is often to let the giants weaken each other.

How do you work out the two-player duels?

Against B with you shooting first, you win if you hit now, or if both miss and the same duel restarts. Call your survival x: x = 1/3 + (2/3)(1/3)x, so x = 3/7; if B shoots first, you must survive B's first shot, 1/3 of the time, giving 1/7. Against C you get exactly one shot, since C never misses: 1/3 if you shoot first, 0 if C does. Now combine. In the air: B hits C two times in three, giving you the 3/7 duel; otherwise C kills B and you get your one shot at C, 1/3. Total 25/63.

What is the general lesson?

In a game with several players, weakening one rival can hurt you if it frees the strongest remaining player to turn on you. Your best shot is the one that keeps the others focused on each other. Say the limitation too: the answer depends on the hit rates and the order. Change the order of shooting, or let C aim at you, and the tree changes; the interviewer will often change a number or the order to see whether you rebuild the tree or repeat the slogan.

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.

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.

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.

V = S and V = K e^(-r(T-t)) satisfy it; V = S squared does not. The first is the stock itself and the second is a zero-coupon bond paying K at T, both traded assets that must earn r. S squared has gamma 2 and leaves (r + sigma squared) S squared unbalanced. Multiplying by e^((r + sigma squared)(T-t)) fixes it, which is the price of a claim paying S squared at expiry.

What is the equation actually saying?

Think of a household budget rule that any fair arrangement must obey: over one day, what you hold must earn the same as the same money in a savings account, once the risk has been hedged away. The Black-Scholes equation says that for a delta-hedged position, time decay plus the gamma term plus the financing of the hedge equals r times the value. Written in {term('greeks', 'Theta is the change in value with time, delta with the stock price, and gamma is the change in delta with the stock price.')}, it is theta + half sigma squared S squared gamma + r S delta = r V. A candidate price passes only if its greeks balance that line.

Why do the two that pass make sense as trades?

Anything that is itself a traded, self-financing asset must satisfy the equation, because the equation is only the statement that no hedged position earns more than r. V = S is just holding the stock: delta 1, no gamma, no decay, and the financing term rS matches rV. V = K e^(-r(T-t)) is a zero-coupon bond: it does not depend on S at all, and its value grows at exactly r as it approaches T. The stock and the bond are also the two pieces of the call price formula, which is why the check is worth a minute.

Why does S squared fail, and how do you repair it?

S squared has gamma 2, so the half sigma squared S squared gamma term adds sigma squared S squared, the delta term adds 2rS squared, and subtracting rV leaves (r + sigma squared) S squared with nothing to cancel it. A convex payoff gains from every move, so a fair price for it has to decay over time to pay for that gain, and S squared on its own has no decay. Try V = S squared times f(t): the equation forces f' = -(r + sigma squared) f, so the price of a claim paying S squared at T is S squared e^((r + sigma squared)(T - t)). At S = 100, r = 5%, sigma = 20% and one year, that is about 10,942, not 10,000, and the extra is the value of volatility.

Pick THH; you win 7 times in 8. HHH can only win if the first three flips are all heads, which has chance 1/8. In any other run, the first HHH is preceded by a tail, and that tail with the next two heads spells THH, which is completed one flip before HHH. So THH wins every game except the one that opens with three heads.

Why is this not a fair race between two 1/8 sequences?

Think of two runners on the same track where one always starts one step ahead of the other on the only route to the finish. Their speeds are identical but the race is not even. In a race between patterns, what matters is not how often each appears but which one tends to appear first, and that depends on how the patterns overlap. THH is built from HHH's own first two heads with a tail placed in front, so it ambushes HHH whenever HHH has not already won at the start.

How do you prove 7/8 without a Markov chain?

Look at the first time HHH appears. If it does not start at flip 1, the flip immediately before it must be a tail, because otherwise an earlier HHH would already have appeared. That tail plus the first two heads of the HHH is THH, finished one flip before HHH. So HHH wins only if flips 1 to 3 are heads, chance 1/8, and THH wins otherwise: 7/8. The proof is one sentence, and interviewers want to hear it rather than a transition matrix.

What is the general lesson for the second mover?

This is Penney's gameA coin sequence race in which the second player, choosing after seeing the first, can always pick a sequence that wins more than half the time., and the second player always has an edge because the winning relation among three-flip sequences is not transitive: every sequence has another that beats it. The recipe: take the opponent's first two flips, and put in front of them the opposite of the opponent's second flip. Against HHH that gives THH at 7/8; against HTH it gives HHT at 2/3. In trading terms, a strategy that looks as good as any other in isolation can still lose systematically to one designed around it.

44/120, about 36.7%, and it tends to 1/e, about 36.8%. Count the orderings with no fixed point by inclusion and exclusion: 5! times (1 - 1 + 1/2! - 1/3! + 1/4! - 1/5!) = 44 of the 120 ways. The bracket is the start of the series for e^(-1), so the answer barely moves with the number of traders: it is within about 0.001 of 1/e at five people and closer still after that.

Why does the answer not go to 0 or to 1?

Think of a secret gift exchange at the office. With more people, each person is less likely to draw their own name, but there are more people who could. Each trader matches with chance 1/n and there are n traders, so the expected number of matches is exactly 1 at every size, and the chance of zero matches settles rather than vanishing. That is why the answer converges to a constant. It is also why the question is asked: it checks whether you can count an event defined by an absence, which needs inclusion and exclusion.

How does inclusion and exclusion give 44?

Count the orderings where at least one trader gets their own card, then subtract. Fix any one trader: 4! orderings each, five traders, 120 in total, but that counts orderings with two fixed traders twice. Alternately subtract and add the counts with one, two, three, four and five traders fixed, and you get 120 - 120 + 60 - 20 + 5 - 1 = 44 orderings with no match. Dividing by 120 gives the probability as 1 - 1 + 1/2 - 1/6 + 1/24 - 1/120, and each term is the e^(-1) series truncated.

How do you check 44 another way?

Use the recursion. Trader 1 takes some other trader's card, say trader j's, in n - 1 ways. Either j takes trader 1's card back, leaving n - 2 traders to derange, or j does not, which is the same as deranging n - 1 traders. So D(n) = (n - 1)(D(n - 1) + D(n - 2)), and from D(1) = 0 and D(2) = 1 you get 2, 9 and then 4 x (9 + 2) = 44. The number of matches is close to Poisson with mean 1 for any decent n, so exactly one match has about the same chance as none: for five traders it is 3/8 = 45/120.

Stop at the first draw of 0.8 or more; the game is worth 0.8 after all fees. Holding x, one more draw improves you by (1 - x)^2 / 2 on average, which equals the 0.02 fee at x = 0.8. Check: you expect 5 draws costing 0.10 in total, and the draw you keep averages 0.90, so the net value is 0.80.

How do you decide whether one more draw is worth it?

Think of hunting for a flat. Each viewing costs you an evening. If the flat in hand is already good, another viewing rarely beats it, and when it does it only beats it by a little. The value of one more look is the chance of beating what you hold times the average margin when you do, and you stop when that falls below the price of looking. With a uniform draw and a current value x, the chance of beating x is 1 - x and the average margin is (1 - x)/2, so the expected gain is (1 - x)^2 / 2.

Why are the threshold and the value the same number?

Because the game has no memory. After a disappointing draw you are back where you started, facing the same game worth V. You should accept a draw exactly when it beats what the fresh game is worth, so the threshold equals the value. This is the same logic as a reservation price: you walk away from any offer below what the next round is worth to you. The arithmetic check is worth saying: with threshold 0.8 a draw succeeds with probability 0.2, so you expect 5 draws and 0.10 of fees, and an accepted draw is uniform on 0.8 to 1 with mean 0.9. The net is 0.9 - 0.10 = 0.8. A seeded simulation of 200,000 games gives 0.800.

What happens as the cost changes?

The threshold is 1 - sqrt(2c), so it responds to the square root of the cost. A fee of 0.005, four times cheaper, only moves the threshold from 0.8 to 0.9. At a fee of 0.5 or more, the threshold hits zero and you take the first draw, because even the first draw's average of 0.5 barely covers what you paid. The limitation of the model is that draws are independent and the distribution is known; if you were learning the distribution as you drew, the first few draws would be worth more than this rule says.

10.6 cards, which is 53/5. Each of the 48 non-aces comes before all four aces with probability 1/5, because among that card and the four aces each is equally likely to be first. So on average 48/5 = 9.6 non-aces precede the first ace, and counting the ace itself gives 10.6. For n cards with m special ones the rule is (n + 1)/(m + 1).

Why isn't the answer 13?

Drop four red counters at random into a line of 48 white ones. Nothing distinguishes the stretch of white before the first red from the stretch between the second and third reds, or the stretch after the last red. The four reds cut the whites into five stretches, and by symmetry each stretch holds the same number on average, 48/5 = 9.6. The answer 13 imagines the aces spread evenly from the top of the deck, but that leaves no room for the stretch after the last ace, which is just as long on average as the others.

How do you make the symmetry argument rigorous?

Use indicators. Pick any non-ace, say the seven of clubs. It is turned before the first ace exactly when it comes first among five cards: itself and the four aces. Those five cards sit in a random order, so that happens with probability 1/5. An expected count is the sum of the probabilities, even when the events depend on each other, so 48 x 1/5 = 9.6 non-aces come first on average and the ace makes it 10.6. The exact sum of the chances that the first ace is later than card k, over k from 0 to 48, gives 53/5 as well, and a seeded simulation of 100,000 shuffles gives 10.63.

The mean hides a skewed shape. The first ace is in the top five cards 34.1% of the time, and the median position is 9, below the mean of 10.6, because a few shuffles bury all four aces deep in the deck and drag the average up. If the interviewer asks for the most likely position, the answer is the very first card: each later position needs every earlier card to be a non-ace, so the chances fall card by card.

How does it generalise, and where is it useful?

With n cards and m special ones, the m specials cut the n - m others into m + 1 gaps, so the first special arrives at (n - m)/(m + 1) + 1 = (n + 1)/(m + 1). Check it with one ace: (52 + 1)/2 = 26.5, the middle of the deck, which is what you would expect. The first spade, with 13 specials, arrives at card 53/14, about 3.79. The same gap symmetry gives the expected wait for the first default in a pool or the first fill among queued orders, provided every ordering is equally likely. That proviso is the limitation: if defaults cluster in time or the deck is stacked, the gaps stop being exchangeable and the rule fails.

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.

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.