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.

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.

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.