Quant puzzles, solved step by step

e, about 2.718. The chance that n uniforms still add to at most 1 is 1/n!, the volume of a corner of the n-dimensional cube. The number of draws N exceeds n exactly when that happens, and an expected count is the sum of the chances of exceeding each n. So E[N] is 1 + 1 + 1/2 + 1/6 + 1/24 and so on, which is e.

Why is two draws the wrong answer?

Fill a one litre jug with cups of random size, each somewhere between empty and full. On average two cups make a litre, but you stop at the first cup that overflows, and some pairs of cups fall short. Averages of the draws do not tell you the average stopping time: you need the chance that you are still short after each draw. After two draws you are still at or below 1 exactly half the time, so a third draw is needed often, and occasionally a fourth.

Where does 1/n! come from?

For two draws, the pairs with a total at or below 1 fill the triangle under the line x + y = 1 in the unit square, area 1/2. For three, they fill a corner of the unit cube, volume 1/6. In general the region where n uniforms add to at most 1 is a corner of the n-dimensional cube with volume 1/n!, because the n! orderings of the coordinates carve the cube into equal pieces. You can also build it by convolutionThe density of a sum of independent variables, found by combining every way the parts can add up to the same total.: the density of the sum below 1 is s to the power n-1 over (n-1)!, and integrating from 0 to 1 gives 1/n!.

How do you check an answer this surprising?

Check the pieces. N is at least 2 always, since one draw never exceeds 1, so the answer must be above 2; the bars for n = 0 and n = 1 are both 1 for that reason. A simulation of 200,000 runs gives an average of 2.721 draws, within a whisker of 2.718. Saying that you would simulate it, and roughly what you expect to see, is a good close in a research interview.

Draw u and v; if u + v is above 1, replace them with 1 - u and 1 - v; then return A + u(B - A) + v(C - A). The plain formula maps the unit square onto a parallelogram twice the size of the triangle, so half the draws, 50.0% in a simulation, land outside. Reflecting through the square's centre folds that half exactly onto the other, keeping the density flat and wasting no draws.

Why does the plain formula give a parallelogram?

Think of a tiled floor where each tile is a parallelogram and you want to pick a spot on one triangular half of a tile. Pick any spot on the tile and half the time you are on the wrong half. A + u(B - A) + v(C - A) with u and v each free on 0 to 1 walks up to one full step along AB and one full step along AC, which covers the parallelogram with corners A, B, C and D = B + C - A, not the triangle. The triangle is exactly the part where u + v is at most 1.

Why does reflecting keep the distribution uniform?

Two facts. The map (u, v) to (1 - u, 1 - v) is a half turn about the square's centre, so it carries the upper triangle onto the lower one without stretching any area; and an affine mapA linear map followed by a shift, such as A + u(B - A) + v(C - A); it scales every area by the same factor. scales every area by the same factor, so a flat density stays flat. Put together, each small patch of the triangle receives draws from exactly two equal patches of the square. A simulation that splits the triangle into four equal pieces finds 24.9%, 25.1%, 25.0%, 25.0% of the points in them, each a quarter.

What other methods would an interviewer accept, and which fail?

Rejection works: throw away draws with u + v above 1. It is correct but wastes half the random numbers. A popular wrong method draws three uniforms and divides each by their sum to get weights on A, B and C; the weights add to 1, but the points pile up near the centre, so the result is not uniform. A correct closed form uses a square root: with r1 and r2 uniform, take (1 - root r1)A + root r1 (1 - r2)B + root r1 r2 C. Name one fast method, prove it, then name the tempting wrong one.

Rs 21. Flip n pays 2 to the n with probability 1/2 to the n, so each of flips 1 to 20 contributes exactly 1 rupee: 20 rupees. Beyond flip 20 the casino pays its whole bank, 2 to the 20, and the chance of getting that far is 1/2 to the 20, which adds 1 more. The famous infinite value collapses to 21 as soon as the payer's bank is finite.

Why is the uncapped game worth infinity?

Each extra flip halves the chance and doubles the prize, so each flip adds the same 1 rupee to the average, forever. An expected value is a sum over outcomes of prize times chance, and when every term is 1 and there are infinitely many terms, the sum has no limit. That is the St Petersburg paradox, discussed by Daniel Bernoulli in the eighteenth century: the mathematics says pay anything, and nobody would pay more than a modest sum.

What exactly does the cap remove?

Picture a lottery that promises to double your prize every day for ever, run by a shop with a small safe. The later promises are worth nothing because the shop cannot keep them. The cap turns every term after flip 20 from 1 rupee into 2 to the 20 divided by 2 to the n, which is 1/2, 1/4, 1/8 and so on, and those add up to exactly 1. So the tail that made the value infinite is now worth a single rupee. The bank is Rs 10,48,576 and the game is worth Rs 21.

What does this teach about pricing a payoff?

Doubling the bank adds only one rupee to the fair price: a bank of 2 to the 30, about Rs 107 crore, makes the game worth Rs 31. The value grows with the logarithm of what the counterparty can pay, so the realistic price of a lottery-like payoff depends on who stands behind it. The same idea appears in trading as counterparty risk: a contract's promised payout in extreme states is only worth what the other side can deliver in those states.

Median about Rs 8.2; 95% interval roughly Rs 1.5 to Rs 45. Log returns add, so after 30 years the log of wealth has mean 30 x 0.07 = 2.1 and standard deviation 0.16 x √30 = 0.88. The median is e to the 2.1, about 8.2. The band is e to the power 2.1 plus or minus 1.96 x 0.88. In rupees it is lopsided, and the mean, about Rs 12, sits above the median.

Why work in log returns rather than percentage returns?

Pay rises compound: 10% and then another 10% is 21%, not 20%. Logs turn that multiplication into addition. Log returns add across years, so the 30-year log return is a sum of 30 yearly pieces, and a sum of independent pieces is close to normal. With mean 0.07 and standard deviation 0.16 a year, the sum has mean 2.1 and variance 30 x 0.16 squared, so a standard deviation of 0.16 x √30, about 0.876. The spread grows with the square root of time, not with time.

Why is the band so lopsided, and where does the mean sit?

Symmetric in the exponent means lopsided in rupees. Going 1.96 standard deviations down divides the median by e to the 1.72, a factor of 5.6; going the same distance up multiplies by 5.6. Dividing and multiplying by the same factor leaves Rs 6.7 of room below the median and Rs 37.3 above it. The same skew separates mean from median. The mean of a lognormalA variable whose logarithm is normally distributed; it is always positive and skewed to the right. variable is e to the power (mean plus half the variance), about Rs 12.0 here, because a few very good paths pull the average up while most paths finish below it.

Close with the limits. The 7% and 16% are illustrative inputs, not a claim about any real index. The calculation assumes independent years and constant volatility; real markets have fat tails and calm and stormy regimes, so treat the band as a floor on the true uncertainty. What the interviewer is testing is whether you scale the mean with t and the volatility with √t, and exponentiate only at the end. One useful extra: the chance the Rs 1 is worth less than Rs 1 is the chance the log falls below zero, about 0.8%.

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.

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.

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.

2 to the power (n - 1) divided by n factorial, which is 16/120 = 2/15 for n = 5. One pass moves every number that is not carried rightwards exactly one place left. So the list ends sorted only if no number starts more than one place right of its final spot. Placing 1, then 2, then 3 and so on, each has two allowed spots and the largest takes the last one, giving 2 to the power (n - 1) orderings.

What does one pass actually do to each number?

Picture a queue at a ticket window where the tallest person seen so far keeps stepping back past anyone shorter. That person travels a long way to the right; everyone they pass shifts one step forward. In one pass, the running maximum is carried right until it meets something larger, and every number it passes moves exactly one place left. Nothing moves left by two in a single pass. That limit is the whole problem.

Which orderings survive, and how do you count them?

Because a number can shift left by one at most, the list sorts only if each number starts no more than one place right of its home. The converse also holds: when every number meets that condition, the pass carries each big number to exactly where it belongs. For five numbers, a brute-force check of all 120 orderings finds exactly the 16 that meet the condition, and all 16 sort.

Now count them without listing. Place the numbers in increasing order. The 1 may sit in position 1 or 2. The 2 may sit anywhere in positions 1 to 3, one of which the 1 already took: two choices. The same holds for 3 and 4: each has k + 1 allowed spots, k - 1 of them already used by smaller numbers, so two choices each. The 5 fills the one position left. That is 2 x 2 x 2 x 2 x 1 = 16.

Check small cases out loud: for n = 2 both orderings sort, 2 of 2; for n = 3 it is 4 of 6. The probability collapses fast, because n factorial outruns 2 to the power n: about 4.4% for n = 6 and 1.3% for n = 7.

7/18, about 0.389, for every n from 3 upwards. A gap is left uncoloured only when it is longer than both gaps beside it, because then neither endpoint has it as its nearest. For three points that gap is simply the longest of three pieces, which averages 11/18, so 7/18 is coloured. For larger n the same 11/18 comes out, so the answer does not depend on n.

When is a gap left uncoloured?

Picture people standing round a circular table, each turning to talk to whoever is closer, left or right. A stretch of table between two people stays silent only if both of them turned away, which means each had a closer person on their other side. A gap is uncoloured exactly when it is longer than both of its neighbouring gaps. A gap coloured from both ends is still coloured once, so the question becomes: what is the expected total length of gaps that are local maxima?

How do you get 11/18 for the uncoloured part?

Start with n = 3, the case you can finish in the room. With three gaps, every gap's two neighbours are the other two gaps, so the only uncoloured gap is the longest one. Three random points cut the circle like a stick broken into three, and the longest of three pieces averages (1/3)(1 + 1/2 + 1/3) = 11/18. So the coloured length is 7/18.

For larger n, use the fact that the n gaps behave like n independent exponentialA random length whose chance of ending is the same at every instant; waiting times between random arrivals follow it. lengths rescaled to add up to 1, and that the rescaling is independent of the shape. For three unit exponentials X, Y and Z, the expected value of X counted only when X is the largest is 1 - 2/4 + 1/9 = 11/18. Each of the n gaps contributes that, divided by the expected total of n, and the n gaps sum to 11/18 again. The uncoloured share is 11/18 whatever n is, so the coloured share is always 7/18.

Say the check: a seeded simulation of 40,000 random circles gives 0.389 for n = 3, 0.388 for n = 5 and 0.389 for n = 10. The limitation is that the exponential step is a known result you should name, not derive, in an interview; the n = 3 case is the part you prove on the spot.

25/48, about 0.521. For a stick broken into n pieces, the expected k-th smallest piece is (1/n)(1/n + 1/(n - 1) + ... ) with k terms. For n = 4 the sorted pieces average 3/48, 7/48, 13/48 and 25/48, which add to 1. The longest is (1/4)(1 + 1/2 + 1/3 + 1/4) = 25/48, more than twice the average piece of 1/4.

Why is the longest piece so much longer than a quarter?

Cut a sheet of dough at three random spots and the pieces are rarely even: one is usually a big slab and one a sliver. Random breaks produce uneven pieces, and the longest piece collects the unevenness, so its average sits far above the average piece. The average piece is always 1/4; the question asks about the largest of four correlated lengths, which is an {term('order statistic', 'The k-th smallest value in a sample, for example the minimum, the median or the maximum.')}.

Where does the harmonic formula come from?

Start with the shortest piece. The chance that all four pieces exceed x is (1 - 4x) cubed: take x off every piece and the three breaks must fit into the remaining length 1 - 4x. Integrating that from 0 to 1/4 gives an expected shortest piece of 1/16. Then the key fact: the step from each sorted piece to the next adds on average (1/n) times 1 over the number of pieces still longer. After the shortest, three pieces remain longer, so the next piece averages 1/16 + (1/4)(1/3); then add (1/4)(1/2), then (1/4)(1). The longest piece is (1/4)(1/4 + 1/3 + 1/2 + 1) = 25/48.

The step rule comes from the fact that the pieces behave like independent exponential lengths scaled to total 1, and the gap between successive minima of exponentials is memoryless. You can name that in the room rather than prove it. The check that the formula is right: the four sorted averages add to exactly 1, and a simulation of 100,000 sticks gives 0.521 for the longest. For n pieces in general, the longest averages (1/n) times the n-th harmonic number, which grows like (ln n)/n.

Bluff with the Q one time in three, and call with the K one time in three. You always bet the A and always check the K; I always call with the A and fold the Q. A Q bluff risks 1 more to win the 2 antes, so I must defend two thirds of hands facing it: the A gives half, the K calling one time in three gives the rest. The game is worth 1/18 per hand to you.

Which hands are easy, and where is the real decision?

Clear away the obvious hands first. With the A you always bet, because you win whether I call or fold. With the K, betting only gets called by the A and folds out the Q, which you beat anyway, so you check. As the caller, I always call with the A and always fold the Q. The whole game comes down to two mixed choices: how often you bluff with the Q, and how often I call with the K.

How do the indifference conditions fix both frequencies?

A teacher who spot-checks homework faces the same logic: check every paper and time is wasted, never check and everyone copies, check at the right rate and copying stops paying. In equilibrium each player mixes at the rate that makes the other indifferent between their two options. Your Q loses 1 by checking. Bluffing loses 2 against my A, and against my K loses 2 if I call and wins 1 if I fold. The two are equal only when I call with the K one time in three. My K loses 1 by folding; calling loses 2 against your A and wins 2 against a bluff, which is worth -1 only when you bluff one time in three.

Check against the pot-odds rule. A bluff risks 1 extra to win the 2 antes, so the caller must defend 2/(2 + 1) = 2/3 of the hands facing it; the A already covers half, and the K calling one time in three covers the other sixth. That two thirds is the number people misremember as the K's calling rate. Put the strategies together and the bettor, who acts first with more information about their own hand, earns 1/18 of a chip per hand. The limitation: with a bigger bet or more cards the ratios change, but the method, indifference on both sides, carries over.

A drift shared by both assets for the whole month can outweigh daily noise that moves them in opposite directions. Within a month the drift is constant, so only the noise shows and the correlation is negative. Summed over 21 days the drift's covariance grows with 21 squared but the noise's only with 21. With noise correlation -0.5 and drift standard deviation 0.3% a day, monthly correlation is +0.48.

What does a three-month example look like?

Picture two shops in the same market street. On any one day, a customer who buys from one did not buy from the other, so their daily takings move against each other. But in festival months the whole street is busy and in the rains the whole street is quiet, so their monthly takings rise and fall together. Correlation at one horizon says nothing on its own about another, because a slow common factor and fast opposing noise can sit in the same data.

Make it numerical with five-day months. In month 1 both assets drift at -0.8% a day, in month 2 at +0.2%, in month 3 at +1.2%. On top, asset A gets daily noise of +0.6, -0.3, 0, +0.3, -0.6 and asset B gets -0.3, +0.3, 0, -0.3, +0.3, which move in opposite directions. Within each month the correlation is -0.95. Summed over each month, the noise nets to zero, so both assets return -4%, +1% and +6%: identical, a monthly correlation of +1. Even all 15 days pooled show +0.71, because the month-to-month swing in drift is larger than the noise.

Why does summing more days push the correlation positive?

Write each daily return as the month's drift m plus noise. Over n days the drift adds up to n times m, while the noise adds up to a sum of n separate shocks. The drift's contribution to covariance scales with n squared, the noise's only with n, so the longer the horizon the more the shared drift wins. Take noise with standard deviation 1% a day and a within-month correlation of -0.5, and a drift whose standard deviation across months is 0.3% a day. For a 21-day month the drift adds 39.69 to the covariance and the noise subtracts 10.5, for a monthly correlation of 29.19/60.69 = 0.48.

The crossover sits where n times 0.09 equals 0.5, about 5.6 days, so even weekly returns of five days would still show a slightly negative correlation, -0.03. A hedge sized on daily correlation can therefore fail at a monthly horizon, which is why a desk measures correlation at the frequency it actually holds risk. The other mechanisms worth naming are mean reversion in the spread between the two assets and stale prices that lag by a day; both also make correlation depend on frequency. The limitation of the example is the assumption that drift is constant inside a month and noise is independent from day to day.