Quant puzzles, solved step by step

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.

The standard deviation is sqrt(2.5), about 1.58%, and the kurtosis is 12.72, against 3 for a normal. Moments of a mixture are weighted averages of the pieces' moments. The variance is 0.9 x 1 + 0.1 x 16 = 2.5. A normal's fourth moment is 3 sigma^4, so the fourth moment is 3 x (0.9 x 1 + 0.1 x 256) = 79.5. Kurtosis is 79.5 / 6.25 = 12.72.

Why does mixing two normals create fat tails?

Think of a city's daily traffic: most days are ordinary, and a few days a year there is a festival or a strike and everything is wild. Averaged across the year, the typical day looks calmer than the average suggests, and the extreme days are far more extreme than a single bell curve would allow. Mixing a calm regime with a rare wild one concentrates most days near zero and puts the rest far out, which is exactly what kurtosis measures: a high peak with heavy tails. Every piece is normal; the mixture is not.

How do you compute the moments without integrating?

Condition on the regime. Any moment of a mixture is the weighted average of that moment in each regime, because the density itself is the weighted average of the two densities. The second moment is 0.9 x 1^2 + 0.1 x 4^2 = 2.5, so the standard deviation is about 1.58%. For the fourth, use the fact that a normal with standard deviation sigma has fourth moment 3 sigma^4: 3 x (0.9 x 1 + 0.1 x 256) = 79.5. Kurtosis is the fourth moment over the variance squared.

What does the number mean for risk?

Kurtosis is 3 times the ratio of the average of sigma^4 to the square of the average of sigma^2, so any variation in volatility pushes kurtosis above 3, and the more uneven the regimes, the further it goes. The practical cost shows in the tails. A risk model that fits one normal with a 1.58% standard deviation expects a move beyond 6% about once in 6,766 days, roughly once every 27 years of trading; the mixture produces one about once in 75 days, several times a year. This is the simplest model of volatility clustering, and the reason daily returns on real assets show kurtosis well above 3.

Centre on today's level, about 20,000, with a 90% range of roughly 16,800 to 23,600. Four months is a third of a year, so one standard deviation is 18% x sqrt(1/3), about 10.4%. In log terms the 90% band is 1.645 of those either side, which gives 16,767 and 23,601. The median sits a little below 20,000 and the upside tail is longer than the downside.

Why is a single number the wrong answer?

Ask a cab driver how long the airport run takes and a good one says forty minutes, maybe an hour in traffic. The range is the useful part, because you plan your flight around it. A trading interviewer asking where an index closes wants a distribution, because a market maker quotes against the spread of outcomes, not against a guess. Your central value should not be a view on the economy either: with no edge, the best central estimate of a traded index is roughly its forward, which for four months is close to today's 20,000 once financing and dividends roughly offset.

The width comes from the implied volatility the market already quotes. Volatility grows with the square root of time, because independent daily moves add their variances, not their standard deviations. Four months is a third of a year, so one standard deviation is 18% x sqrt(1/3) = 10.4%, about 2,078 index points.

Why is the range lopsided, and where does the median sit?

A fall of 10% and a rise of 10% are not mirror images in log space. Normal log returns make the upside tail longer: the 90% band stretches 3,601 points up but only 3,233 points down. The same convexity pushes the median below the mean: if the mean is 20,000, the median is 20,000 x exp(-sigma squared T / 2), about 19,892. That gap of about 108 points is small here, but it grows with volatility and time, and a candidate who names it shows they know the difference between the most central outcome and the average one.

What would you add before quoting a market on it?

Two honest caveats. Implied volatility is a price, not a forecast: it tends to sit above the volatility that is later realised, because option sellers charge for bearing crash risk, so the band built from it is usually a little wide. Against that, real index returns have fatter tails than the lognormal, so the 5% tails are more likely to hold a larger move than the curve suggests. Say both, then give your market: a tight two-way price around 20,000 if asked for the level, and the 90% band as the range you would sell outside of.

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.

76. Split 100 into 4 x 25. Any power of 4 is 0 mod 4. Mod 25, Euler's theorem applies because 4 and 25 share no factor, and 3000 is a multiple of phi(25) = 20, so 4^3000 is 1 mod 25. The numbers below 100 that are 1 mod 25 are 1, 26, 51 and 76, and only 76 is divisible by 4.

Why does the obvious Euler shortcut fail?

Euler's theorem says a to the power phi(n) is 1 mod n, and phi(100) = 40, so it is tempting to say 4^3000 = (4^40)^75 ends in 01. The theorem needs the base and the modulus to share no factor, and 4 and 100 share a factor of 4, so it does not apply. A quick sense check kills 01 anyway: every power of 4 is divisible by 4, and a number is divisible by 4 exactly when its last two digits are, which 01 is not.

How do you split the problem so the theorem does apply?

Think of a clock with 100 hours as two smaller clocks running together, one with 4 hours and one with 25. Knowing where both small clocks point fixes the big one exactly. Mod 4 the answer is 0, since 4^3000 is a multiple of 4; mod 25 the answer is 1, since 4 and 25 share no factor and 3000 is a multiple of phi(25) = 20. Now list the numbers below 100 that are 1 mod 25: 1, 26, 51, 76. Only 76 is a multiple of 4. This step is the Chinese remainder theorem, and naming it earns credit.

What is the fastest check if you have a pencil?

Just list the endings. Multiply each ending by 4 and keep the last two digits: 04, 16, 64, 56, 24, 96, 84, 36, 44, 76, and then 76 x 4 = 304, which ends in 04, so the cycle has length 10. Because 76 x 76 = 5,776 also ends in 76, every power of 76 ends in 76, and 4^3000 = (4^10)^300 must end in 76. On a multiple-choice test, this listing takes about thirty seconds and needs no theorem at all.

10/12, about 0.833. A uniform prior on the win rate, updated with 9 wins and 1 loss, gives a Beta(10, 2) posterior. The chance of winning tomorrow is the posterior mean, (9 + 1)/(10 + 2). The answer is below 0.9 because ten days cannot rule out a lower true win rate, and averaging over that uncertainty pulls the estimate towards one half.

Why is 0.9 too confident?

A new restaurant with nine five-star reviews out of ten looks excellent, but you would not bet that the next diner rates it five stars with 90% certainty. Ten reviews is a small sample, and a restaurant that truly earns five stars 70% of the time could easily post nine out of ten. The right forecast averages over every win rate the evidence still allows, and with only ten days that includes plenty of rates below 0.9. The average of that spread of possibilities is what you should quote for tomorrow.

How does the Bayesian update give 10/12?

Start with every win rate p between 0 and 1 equally likely. The chance of the observed record is proportional to p^9 (1 - p), so the posterior is proportional to that, which is the Beta(10, 2) distribution. The chance of a win tomorrow is the average of p over the posterior, and the mean of a Beta(a, b) is a/(a + b), here 10/12. The shortcut is Laplace's rule of succession: add one imaginary win and one imaginary loss to the record, then divide.

When does the pull towards one half stop mattering?

When the record is long. At 90 wins out of 100 the rule gives 91/102, about 0.892, almost exactly the raw 0.9, because a hundred days of data swamp the one imaginary win and loss. The limitation is the prior itself. A uniform prior says a 99% win rate was as plausible as a 50% one before you saw any data, which no trader believes about a new strategy. With a sceptical prior centred near one half, ten days would pull the estimate even further below 0.9. The posterior also tells you more than one number: the chance of winning both of the next two days is (10 x 11)/(12 x 13), about 0.705, not 0.833 squared.

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.

pi/2, about 1.571. Rotate the sphere so the first point sits at the north pole; nothing changes, because the second point is uniform. On a unit sphere the surface distance is the polar angle theta of the second point. The northern and southern hemispheres are mirror images, so theta is as likely to be pi/2 - t as pi/2 + t, and its mean is pi/2.

Why can you put the first point at the pole?

Ask how far apart two random towns are on a perfectly round planet, and you can simply stand in one of them: the globe looks the same from every spot on it. Symmetry lets you fix one point anywhere, so the problem shrinks to one random point and its angle from the pole. On a sphere of radius 1, the distance along the surface between the pole and a point at polar angle theta is theta itself, measured in radians, so the question becomes: what is the average polar angle of a uniform point?

Where does sin theta come from? The circle of latitude at angle theta from the pole has circumference 2 pi sin theta, so a thin band there holds surface in proportion to sin theta: almost none near the poles, the most at the equator. Archimedes put it more neatly: the area of a band is proportional to its height along the axis, so cos theta is uniform between -1 and 1. The density (1/2) sin theta is a mirror image about pi/2, so the mean is pi/2 without doing the integral. Integration by parts confirms it, a numerical integral gives 1.5708, and a seeded simulation of 100,000 pairs gives 1.570.

If a uniform angle gives the same mean, why does the shape matter?

Because the mean survives by luck of symmetry and almost nothing else does. Choosing theta uniformly on 0 to pi crowds points near the poles. Ask for the chance the two points are within 60 degrees of each other and the correct answer is (1 - cos 60 degrees)/2 = 0.25, while the uniform angle says 0.33. Ask for the expected straight-line chord, 2 sin(theta/2), and the correct density gives 4/3, about 1.333, while the uniform angle gives 4/pi, about 1.273. The simulation gives 1.333 for the chord. This is the limitation of the shortcut: it answers this one question and must not be reused for the next.

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.

Set the ask at 106, and by the same logic the bid at 104. If the stock is worth 110, a buy arrives with probability 0.2 + 0.8 x 0.5 = 0.6; if it is worth 100, with probability 0.4. Given a buy, Bayes puts the chance of 110 at 0.6, so the stock is worth 106 to the market maker selling it. The spread of 2 is the price of trading against informed flow.

Why can't the market maker just quote the expected value of 105?

A second-hand car dealer who pays the average price for every car will find that the owners of good cars go elsewhere and the owners of bad ones queue up. Who chooses to trade with you is information. A market maker does not care what the stock is worth on average; it cares what the stock is worth given that someone has just chosen to buy from it. At an ask of 105, noise buyers are harmless, a loss of 5 when the stock is worth 110 and a gain of 5 when it is worth 100. Informed buyers only appear in the 110 world, and they cost 0.5 per arriving trader on average, so 105 is a losing quote.

What sets the width of the spread?

The share of informed traders and the size of what they know. With a share alpha informed, a buy is alpha + (1 - alpha)/2 likely in the high world and (1 - alpha)/2 in the low world, and the ask works out to 105 + 5 alpha. The spread is a fee for adverse selection: it is zero when nobody is informed and widens to the full 100 to 110 range when everyone is. The table runs the formula for a few shares. Order processing and inventory costs add to this in real markets, but the information component is what makes spreads jump around earnings and news.

What happens after the first trade?

The market maker updates. After one buy, the chance of 110 is 0.6, and if a second buy arrives the same Bayes step lifts it to 0.692, so the next ask is about 106.92. Each order moves the quotes towards the true value, which is how prices come to reflect what the informed traders know. The limitation is that the model has one share size, no inventory risk and no competition between market makers; real desks also skew quotes to manage position, which this puzzle leaves out.