Quant puzzles, solved step by step

Stake 10% of the bankroll; that grows wealth by about 0.97% a bet, and twice Kelly grows it by only about 0.07%. Kelly is edge over odds: (2 x 0.4 - 0.6)/2 = 0.1. The growth rate is 0.4 ln(1.2) + 0.6 ln(0.9). At 20% the losses compound away almost the whole edge, and above about 20.4% the bankroll shrinks in the long run despite a positive expected value.

Why not bet as much as possible on a good bet?

Think of a shopkeeper with a profitable weekly sale who puts the entire shop's stock on it every week. The average week is good, but one bad week ends the business. With repeated bets, wealth multiplies, so what matters is the average of the log of each outcome, not the average outcome, and a big loss costs more in log terms than an equal gain earns. This bet has a clear edge: each rupee staked returns 0.4 x 2 - 0.6 = Rs 0.20 on average. The question is how much of that edge survives compounding at each stake size.

How do you get the Kelly fraction and the growth rate?

Stake a fraction f. A win multiplies wealth by 1 + 2f, a loss by 1 - f, so the growth per bet is g(f) = 0.4 ln(1 + 2f) + 0.6 ln(1 - f). Set the derivative to zero: 0.8/(1 + 2f) = 0.6/(1 - f), giving f = 0.1. The Kelly stake is the edge divided by the odds, (bp - q)/b = 0.2/2 = 10%. Plugging in, g = 0.4 x 0.1823 - 0.6 x 0.1054, about 0.97% a bet, so the typical path doubles its wealth roughly every 71 bets.

Why is overbetting so much worse than underbetting?

Near the peak the growth curve is close to a parabola, so the cost of a sizing error grows with its square. Half Kelly gives up only about a quarter of the growth, while twice Kelly gives up nearly all of it, and three times Kelly shrinks wealth at about 2.6% a bet. Real edges are estimated, not known, so a trader who thinks the win rate is 40% but faces 35% is already overbetting at the full 10%. That asymmetry is why desks size at a fraction of Kelly.

9 steps. Let E(k) be the expected steps left from state k. Each step costs one and lands on a neighbour with equal chance, so E(k) = 1 + (E(k - 1) + E(k + 1))/2, with E(3) = E(-3) = 0. The solution is E(k) = (3 - k)(3 + k): 9 from 0, 8 from plus or minus 1, 5 from plus or minus 2. A symmetric walk needs about the square of the distance to travel it.

Why is the answer not 3?

Think of someone pacing a narrow corridor, choosing left or right at random with every step. They do reach a wall eventually, but they spend most of their time doubling back. A random walk with no drift covers distance like the square root of time, so covering a distance of 3 takes about 3 squared steps, not 3. The answer 3 would only be right if the walk always moved in one direction. The structure to name in the room is a first-step recursion on the state, which turns the question into seven unknowns with simple links between them.

How do you solve the recursion quickly?

Use symmetry first: E(1) = E(-1) and E(2) = E(-2). Then three equations remain. From 2: E(2) = 1 + (E(1) + 0)/2. From 1: E(1) = 1 + (E(0) + E(2))/2. From 0: E(0) = 1 + E(1), because both neighbours are worth E(1). Substituting gives E(1) = 8 and E(0) = 9, and every value matches the product of the distances to the two walls. The second differences of E are all minus 2, which is why the answer is a parabola: each step must remove exactly one unit of expected time.

How do you check 9 a second way?

Use a martingaleA process whose expected next value, given everything so far, equals its current value: a fair game.. Squaring the position and subtracting the number of steps gives a fair game, because each step adds exactly 1 to the expected square. At the moment the walk stops its square is exactly 9, so the expected number of steps must also be 9. The same argument handles uneven walls: starting between -a and +b, the expected time is a times b. The cousin result is the hitting probability: from +1, the walk reaches +3 before -3 with probability 2/3, the distance to the far wall over the total width.

Decline it: same colour comes up 25 times in 51, so the bet loses about Rs 1.96 per Rs 100. Whatever the first card is, 25 of the remaining 51 share its colour and 26 do not. The bet is fair only if a win pays Rs 26 for every Rs 25 risked, that is Rs 104 on a win against Rs 100 on a loss.

Why is same colour less likely than different colour?

Imagine a classroom with 26 girls and 26 boys. Pick one child, then pick a second: the second is slightly more likely to be of the other sex, because the first pick removed one of their own. Drawing without replacement makes the second card lean away from the first card's colour, since that colour is now short by one. The first card is irrelevant to the answer, whichever colour it is. Only what is left in the deck matters: 25 matching cards and 26 non-matching.

What is the bet worth, and what makes it fair?

Expected value is the win times its chance less the loss times its chance: 100 x 25/51 - 100 x 26/51 = -100/51, about Rs -1.96. A bet is fair when the payout ratio equals the odds against winning, here 26 to 25, so the win must pay Rs 104 for each Rs 100 at risk. Quoting it as odds rather than a probability is how a trader would answer: you would take the bet at 26 to 25 or better, and decline anything worse.

Why would an interviewer offer such a small edge?

To see whether you notice it at all, and then whether you size your response to it. An edge of about 2% per bet is small for one play but decisive over many, so the right answer is to decline at even money and quote the price at which you would play. It also tests whether you separate the first card, which is free, from the conditional chance of the second. With replacement, or with an infinite deck, the bet would be exactly fair; the whole edge comes from the deck being finite, and it shrinks as more decks are shuffled together.

I show heads 3/8 of the time; so should you; and the game is worth -1/8 to you per round. At my mix q, your heads pays 3q - 2(1 - q) and your tails pays -2q + (1 - q). Setting them equal gives q = 3/8, where both pay -1/8. By the same algebra your 3/8 mix makes my choices equal, so neither of us can improve: the table looks fair and is not.

Why do I randomise to make you indifferent, not to help myself?

Think of a penalty taker and a goalkeeper. If the taker shoots left more often than he should, the keeper dives left and gains; any pattern is exploited. In a zero-sum game, the mix that protects you is the one that leaves your opponent with nothing to exploit, which means making every one of their choices pay the same. So I do not pick my heads probability by looking at my own payoffs in isolation; I pick it so that your heads and your tails earn you equal amounts. Then it no longer matters what you do.

How do the two equations give 3/8 and -1/8?

Let q be my chance of heads. Your heads earns 3q - 2(1 - q) = 5q - 2 and your tails earns -2q + 1(1 - q) = 1 - 3q, and they are equal when 8q = 3, at q = 3/8. Plug back in: 5(3/8) - 2 = -1/8. For your side, let p be your chance of heads; my payoffs are the negatives of yours, and because the table is symmetric the same algebra gives p = 3/8. At those mixes, each cell's frequency is HH 9/64, TT 25/64 and the two mismatches 15/64 each: 3(9) + 1(25) - 2(30) = -8, over 64, is -1/8.

Why does a table with equal wins and losses favour me?

Because the cells are not played equally often. Your big win needs both of us on heads, and I can make that cell rare; the mismatches, where I win, happen 30 times in 64 at equilibrium. If I played heads half the time you could earn +1/2 by always showing heads, so a naive 50/50 from me would be a gift. In trading the same idea sets a market maker's quotes: they are placed so that the informed side has no choice that beats the others, not so that the market maker profits on any one trade.

About 1, 3, 6 and 12 correct digits: the count roughly doubles each step. The update is x(next) = (x + 2/x)/2: 1.5 gives 17/12 = 1.41667, then 577/408 = 1.4142157, then 665857/470832 = 1.41421356237469. Each new error is about the old error squared divided by 2x, so if the error is 10^-k, the next is about 10^-2k. That is quadratic convergence.

Where does the update rule come from?

Think of guessing a side of a square room whose area is 2. If your guess is too big, 2 divided by your guess is too small, and the truth sits between the two. Newton's method for x squared minus 2 is exactly that: replace x with the average of x and 2/x. Formally, Newton follows the tangent of f(x) = x^2 - 2 down to zero, x - f(x)/f'(x) = x - (x^2 - 2)/(2x), which simplifies to (x + 2/x)/2. The averaging form is the one to use in your head.

How do you get the iterates without a calculator?

Keep fractions. From 3/2, the next value is (3/2 + 4/3)/2 = 17/12, then (17/12 + 24/17)/2 = 577/408, and the pattern continues: if x = p/q, the next is (p^2 + 2q^2)/(2pq). 17/12 is 1.41667, already right to 1.41. 577/408 is 1.4142157 against 1.4142136, right to 1.41421. The third step's fraction, 665857/470832, is too big for mental division, but you can predict its accuracy without doing it, which is the point of the question.

Why is it the digits that double, and when does that fail?

Subtract the root from the update and the algebra collapses to (x - root 2)^2 / 2x. Squaring an error of 10^-3 gives 10^-6, so each step doubles the number of correct digits once you are close. The errors here run about 0.09, 0.0025, 2 x 10^-6 and 1.6 x 10^-12. The doubling needs a good start and a simple root: far from the root, or where the slope is zero, Newton can creep or jump away. Bisection, by contrast, gains one binary digit per step whatever happens, which is why desk code often brackets with bisection and finishes with Newton when solving for implied volatility.

A^10 has 29,525 on the diagonal and 29,524 off it. A has eigenvalue 3 along (1, 1) and eigenvalue 1 along (1, -1). Writing A = Q D Q^T with D = diag(3, 1), the tenth power is Q D^10 Q^T, and only the numbers 3 and 1 get raised to the tenth. The entries are (3^10 + 1)/2 and (3^10 - 1)/2.

Why look for eigenvectors at all?

Think of a photocopier set to 300% on one axis and 100% on the other. Copy a copy ten times and you do not need to simulate every pass: that axis is 3 to the tenth times longer and the other is unchanged. An eigenvector is a direction the matrix only stretches, so applying the matrix ten times along it is just multiplying by the eigenvalue ten times. Symmetric matrices always have a full set of such directions at right angles, which is what makes this matrix easy.

Find them by inspection. Adding the two rows of A gives 3 in each, so A(1, 1) = (3, 3): eigenvalue 3. Subtracting gives 1, so A(1, -1) = (1, -1): eigenvalue 1. The trace is 4 and the determinant is 3, and 3 + 1 = 4 and 3 x 1 = 3, which confirms both in one line.

Is there an even faster route for this particular matrix?

Yes. Write A = I + J, where J is the all-ones matrix. J squared is 2J, so every power of J is a multiple of J, and (I + J)^n collapses to I + ((3^n - 1)/2) J. For n = 10 that is I + 29,524 J, which gives 29,525 on the diagonal and 29,524 off it: the same answer, and a good cross-check to say aloud. A brute-force multiplication in code agrees exactly.

Say why this matters on a desk. A covariance matrix with equal variances and one common correlation has exactly this shape, and its eigenvectors are the market direction and the spread directions. Powers of transition matrices in Markov chains are computed the same way, and the eigenvalue closest to 1 tells you how fast the chain forgets where it started.

400. Since 1,000 = 2^3 x 5^3, a number shares a factor with 1,000 exactly when it is divisible by 2 or by 5. There are 500 multiples of 2 and 200 of 5, but the 100 multiples of 10 sit in both lists, so 600 numbers share a factor and 400 do not. Euler's formula agrees: 1,000 x 1/2 x 4/5 = 400.

Which numbers share a factor with 1,000?

Picture a hall of 1,000 people where everyone wearing a red badge or a blue badge is asked to leave. To count who stays, you need the red-badge count, the blue-badge count, and how many wear both, because they would otherwise be counted out twice. Write 1,000 as 2^3 x 5^3: a number shares a factor with it exactly when it is divisible by 2 or by 5, so only two badges matter, and the powers 3 do not add any new conditions. Every multiple of 4 or 8 is already a multiple of 2, and every multiple of 25 or 125 is already a multiple of 5.

Why does the quick product formula work here?

Half of all numbers are odd, and among those, four in five are not multiples of 5. Because 1,000 is a multiple of 10, the numbers 1 to 1,000 contain exactly 100 full blocks of ten, and in each block exactly 4 numbers, 1, 3, 7 and 9, survive both tests, so 100 x 4 = 400. The strip of 1 to 20 in the figure shows the pattern repeating, 8 survivors in 20. The product is exact only when the range is a whole number of such blocks: for 1 to 1,234 it gives 493.6, while a direct count gives 494.

Where does a question like this lead in an interview?

Usually to powers and remainders. Euler's theorem says a number coprime to n, raised to the power phi(n), leaves remainder 1 when divided by n, and that is the engine behind last-digit puzzles: phi(100) = 40, so 3^40 ends in 01 and so does 3^400. It also leads to probability: the chance that two large random integers share no factor tends to 6/pi^2, about 0.608. The habit the question tests is factorising first: once you see only the primes 2 and 5 matter, a counting question becomes a two-circle Venn diagram.