Hedge Funds puzzles, solved step by step

14.7 rolls. Split the wait into six stages, one per new face. The first roll always shows a new face. With k faces already seen, each roll is new with probability (6 - k)/6, so that stage takes 6/(6 - k) rolls on average. Adding 1 + 1.2 + 1.5 + 2 + 3 + 6 gives 14.7, and the last face alone costs six of those rolls.

Why does the wait get longer as you go?

Collecting a set of six cricket cards from cereal packets feels quick at first: almost every packet brings a new card. By the end you are opening packet after packet for the one card you lack. The chance of something new falls as the collection grows, so the wait for each new face grows too, and the last face dominates. With five faces seen, only one roll in six is any use.

Why is each stage 6/(6 - k) rolls?

Each stage is a run of independent tries with a fixed chance of success, and the average length of such a run is one over that chance. If a new face turns up with probability p on each roll, you wait 1/p rolls on average: 6/5 rolls when five faces are still new, 6/1 when only one is. That rule, the mean of a geometric wait, is the one piece of theory the puzzle needs, and it is worth saying before you start adding.

Where does the same shape show up in markets?

Any wait to see every one of a set of outcomes has a long tail. Waiting until every stock on a thin watch list has traded at least once, or until a survey has reached every group in a sample, behaves the same way: most of the time goes on the last few. The general answer is n times the sum 1 + 1/2 + ... + 1/n, which grows like n times the natural log of n; for 100 equally likely items it is about 519 draws, not 100.

About 3.99, so roughly four. Give each face its own yes-or-no: did it appear at least once? A face is missed in all six rolls with chance (5/6)^6, about 33.5%, so it appears with chance about 66.5%. The expected count is the sum of the six chances: 6 x (1 minus (5/6)^6), which is 3.9906.

Why not work out the chance of seeing exactly 1, 2, up to 6 faces?

You could, but each of those needs a fiddly count. There is a shortcut that works whenever the question asks for an expected count. Think of a teacher checking attendance: the expected number present is simply the sum, over pupils, of each pupil's chance of turning up. Write the total as a sum of yes-or-no indicators, one per face, and the expected total is the sum of their probabilities, whether or not they are independent. That rule is {term('linearity of expectation', 'The expected value of a sum equals the sum of the expected values, even when the parts depend on each other.')}, and it turns a hard count into one line.

What is the chance that a given face shows up?

It is easier to find the chance it does not. Each roll misses the face with chance 5/6, and the six rolls are independent, so the face is missed every time with chance (5/6)^6, which is 15,625 over 46,656, about 33.5%. So each face appears at least once with chance about 66.5%, and six faces give 3.99. The indicators are not independent, since seeing face 1 a lot leaves less room for face 2, but linearity does not care.

Give the general form and a sense check. With n faces and n rolls the answer is n(1 minus (1 minus 1/n)^n), which tends to n(1 minus 1/e), about 63% of n. For a die that predicts 3.79, and the exact 3.99 is a little higher because six is small. The same logic tells a desk how many distinct names a random sample of trades touches.

The chance is 8 in 32, exactly 1/4. Sort the qualifying sequences by where their first run of three heads starts. Starting at flip 1: HHH then anything, 4 sequences. Starting at flip 2: flip 1 must be tails, then HHH, then anything, 2 sequences. Starting at flip 3: flip 2 must be tails and flip 1 is free, 2 sequences. Four plus two plus two is eight.

Why does the obvious count go wrong?

Suppose you count guests at a party by asking each room how many people it holds, while some guests stand in doorways. They get counted twice. A run of three can start in three places, but one sequence can contain a run starting at more than one of them, so three places times four fillings, 12, counts HHHHH three times and two other sequences twice. The fix is to give each sequence exactly one home: the position where its first run starts.

How do you make every sequence count once?

Force the flip just before the run to be tails. If the first run starts at flip 2, flip 1 must be tails; if it starts at flip 3, flip 2 must be tails, and flip 1 can be anything. That gives 4, then 2, then 2. Then check a second way by counting the complement: sequences with no run of three follow a Tribonacci-style rule, each term the sum of the three before, giving 1, 2, 4, 7, 13, 24 for 0 to 5 flips. And 32 minus 24 is 8.

Why would a quant fund ask this?

Streaks are what people notice in trading records and backtests. A run of three heads turns up in a quarter of all five-flip sequences of a fair coin, so a short winning streak is weak evidence of skill. The counting habit matters as much as the number: giving each outcome one home is the same discipline that stops you double counting overlapping signals when you tally how often a strategy fired.

Position 10.6. The four aces split the 48 non-aces into five gaps: before the first ace, between each pair of aces, and after the last. By symmetry, a given non-ace is equally likely to fall in any of the five gaps, so each gap holds 48/5 = 9.6 cards on average. The first ace comes straight after the first gap, at 9.6 + 1 = 10.6.

Why do the gaps have the same size on average?

Picture four red beads threaded at random among 48 white ones on a string. Pick any one white bead: it is as likely to sit before all four reds as between the first and second, or after the last, because a shuffle favours no order. Each non-ace lands in each of the five gaps with probability 1/5, so the expected size of every gap is 48/5 = 9.6 cards. Any single shuffle has uneven gaps; it is only the average that is equal.

How do you turn gap sizes into a position?

The first ace sits immediately after the first gap. Expected position = expected size of the first gap + 1 = 9.6 + 1 = 10.6. The same logic puts the second ace at 21.2, the third at 31.8 and the last at 42.4, evenly spaced 10.6 apart. A quick check: the last ace at 42.4 plus a final gap of 9.6 reaches exactly 52.

Why is 13 the wrong instinct?

Thirteen is the average wait when every draw has a fresh 1-in-13 chance, as if each card were put back and the deck reshuffled. Drawing without replacement makes the aces easier to reach, because every non-ace you turn over raises the share of aces in what is left. The general rule, (n + 1)/(k + 1), is worth keeping: the first spade is expected at 53/14, about card 3.79, and the same shape answers how many trades you expect to check before finding the first of a handful of booking errors in a batch.