Quant puzzles, solved step by step

Puzzles: 100
Traced to a firm: 71
Topics: 12
Hard: 30

Showing 1–3 of 3 · filtered from 100Clear filters

007You roll a fair six-sided die six times. What is the expected number of different faces that appear?Expected value and optimal stoppingCoreQuant tradingProp trading firms
Try it first
Your estimate before any working?
Show the worked solution
About 3.99. Give each face an indicator that equals 1 if that face appears at least once. A given face is missed on all six rolls with probability (5/6) to the 6th, about 0.335, so it appears with probability 0.665. The expected count of distinct faces is the sum of the six indicators' expectations: 6 x 0.665 = 3.99. No case listing is needed.
Why not list the cases?
You could work out the chance of exactly one, two, up to six distinct faces and average them. It works, but it needs Stirling numbersCounts of the ways to split a set of items into a given number of non-empty groups; they appear when counting surjections. or a lot of careful counting, and it is easy to slip. Linearity of expectation lets you ignore how the faces interact: the expected total of several indicators is the sum of their expectations, whether or not they are independent. Here the six indicators are clearly dependent, since seeing many faces leaves fewer rolls for the others, and it does not matter at all.
Each of the six faces appears at least once with probability 66.5%, so the expected number of distinct faces is six times that, 3.99; the exact distribution peaks at four distinct faces and has all six only 1.5% of the time.
How does the indicator trick work step by step?
Think of a teacher counting how many of six friends turn up to a party. Instead of listing every guest list, she asks for each friend separately how likely that friend is to come, then adds. Write the count as I1 + I2 + ... + I6, where I_k is 1 if face k appears; take expectations; each E[I_k] is just the probability face k appears. Face k is missed on one roll with probability 5/6, on all six with (5/6) to the 6th, 0.335. So each indicator averages 0.665 and the total averages 3.99.
The relationship
$E[D] = \sum_{k=1}^{6} P(\text{face } k \text{ appears}) = 6\left(1 - \left(\tfrac{5}{6}\right)^6\right) \approx 6 \times 0.665 = 3.99$
D the number of distinct faces seen in six rolls
(5/6)^6 the chance a given face never appears in six rolls
What it says in wordsThe expected number of distinct faces is six times the chance that any one face appears.
Where does this pattern reappear?
The same shape answers how many distinct birthdays a group of n people has, how many of n hash buckets get used, and how many different stocks a random sample of trades touches. For n faces and n rolls, the expected share of faces seen is 1 - (1 - 1/n) to the n, which tends to 1 - 1/e, about 63.2%, as n grows. Six faces give 66.5%, already close. The exact enumeration of all 46,656 rolls gives a mean of 3.9906, the same number.
Where candidates lose it
The instinctive answer is 6, or something close to it, because six rolls over six faces feels like one of each. In reality repeats are the norm, and all six different faces happen in under 2% of runs.
The costlier trap is starting to enumerate cases under time pressure. Candidates who try to list exactly four distinct faces lose minutes. Say indicator variables and linearity in the first sentence.
What the interviewer asks next
What is the expected number of faces that appear exactly once?
How many rolls do you need, on average, to see all six faces?
What is the variance of the number of distinct faces?
040Game: roll a fair die and receive its face in rupees; whenever you roll a six you also roll again and add the next result, with no limit on repeats. What is the expected payout of the game?Expected value and optimal stoppingCoreQuant tradingOptions market making
Try it first
What is the game worth?
Show the worked solution
Rs 4.20. Every roll pays its face, averaging 3.5, and with probability 1/6 the game then starts again, worth the same V. So V = 3.5 + V/6, which gives (5/6)V = 3.5 and V = 4.2. A second route agrees: the number of rolls averages 1/(5/6) = 1.2, and each averages 3.5, so 1.2 x 3.5 = 4.2.
Why write the game in terms of itself?
A pass that gets a free renewal each time you use it on a lucky day is worth its first use plus, on lucky days, another pass exactly like it. When a game can repeat with no memory, the value after the repeat is the value of the whole game, so one equation replaces an infinite sum. Here, after a six you are paid 6 and then face precisely the game you started with, worth V.
Faces 1 to 5 end the game, and a six pays 6 and restarts the same game, so V = (5/6) x 3 + (1/6) x (6 + V), which solves to V = 4.2; the number of rolls averages 1.2, and 1.2 x 3.5 gives the same 4.2.
How do you set up the equation without slipping?
Condition on the first roll. With probability 5/6 it shows 1 to 5, averaging 3, and you stop. With probability 1/6 it shows 6: you collect 6 and then expect V more. So V = (5/6) x 3 + (1/6) x (6 + V), which simplifies to V = 3.5 + V/6, and V = 3.5 x 6/5 = 4.2. The form 3.5 + V/6 is worth saying: every roll pays 3.5 on average, and one time in six you get another go at the whole game.
The relationship
$V = \tfrac56\cdot 3 + \tfrac16\,(6 + V) \;\Rightarrow\; V = \frac{3.5}{1 - 1/6} = 4.2$
V expected payout of the game, in rupees
3 average of faces 1 to 5
6 + V payout after a six: the six itself plus a fresh game
What it says in wordsThe game's value is one roll's average plus a one-in-six chance of the whole game again.
Check by counting rolls. The chance a roll triggers another is 1/6, so the number of rolls averages 1/(1 - 1/6) = 1.2, and each roll averages 3.5 whatever came before, giving 1.2 x 3.5 = 4.2. Summing the series directly, k sixes and then a stop, also lands on 4.2, but the recursion gets there in two lines. The limitation to name if asked to price it: 4.2 is a fair value for one play; the payout has a long right tail, since two sixes in a row, one time in 36, already pay at least 13.
Where candidates lose it
The usual loss is capping the chain: adding one re-roll, 3.5 + 3.5/6 = 4.08, and stopping. The re-roll can be a six too, and the question says there is no limit.
The second is writing V = 3.5 + V without the 1/6, which has no solution, or forgetting the six itself is paid before the restart. Condition on the first roll and write each branch in full.
What the interviewer asks next
What would you pay to play if a six pays nothing but gives a re-roll?
What is the probability the payout exceeds 12?
Now a one ends the game with zero payout. What is the game worth?
052You roll a fair die repeatedly until the first six appears. What is the expected sum of all the rolls before the six, not counting the six itself?Expected value and optimal stoppingCoreQuant tradingProp trading firms
Try it first
Pick your answer before working it.
Show the worked solution
15. The first six takes 6 rolls on average, so 5 rolls come before it. Each of those rolls is known not to be a six, so it is uniform on 1 to 5 and averages 3. Expected count times expected size gives 5 x 3 = 15. The check: all rolls including the six average 6 x 3.5 = 21, and taking off the final six leaves 15.
How many rolls come before the six?
Picture waiting at a stop where each minute a bus arrives with chance 1 in 6. On average you wait 6 minutes, and the sixth is the one where it comes. The number of rolls up to and including the first six is geometric with mean 1/p = 6, so the number strictly before it is 5. That is the first factor. Most candidates get this far; the loss comes in the second factor.
A typical game has five non-six rolls before the stopping six, and each of those rolls averages 3 because it is known not to be a six, so the expected sum is 5 x 3 = 15; the full-sum check of 6 x 3.5 less the final 6 also gives 15.
Why is each of those rolls worth 3 and not 3.5?
Because you are told something about them. Every roll before the stopping six is, by definition, not a six, so its distribution is the die conditioned on 1 to 5, which averages exactly 3. Using 3.5 gives 17.5, the most common wrong answer. It is the same slip as averaging the income of people who did not win a prize with everyone's income, prize winners included.
The relationship
$E\Big[\sum_{i=1}^{N} X_i\Big] = E[N]\,E[X \mid X \ne 6] = 5 \times 3 = 15 \qquad E = \tfrac56\,(3 + E)\ \Rightarrow\ E = 15$
N the number of rolls before the first six, mean 5
X | X not 6 a roll known not to be a six, uniform on 1 to 5
E the expected sum from any fresh start
What it says in wordsExpected count times the expected size of each piece gives 15, and the one-step recursion confirms it.
How do you check 15 a second way in the room?
Two checks, both fast. The recursion: with chance 5/6 the next roll is not a six, adds 3 on average and you are back where you started, so E = (5/6)(3 + E), which solves to 15. The full sum: Wald's identityFor a stopping time N that does not look into the future, the expected sum of N independent identical draws equals E[N] times the mean of one draw. applied to every roll including the six gives 6 x 3.5 = 21, and the last roll is always exactly 6, so the rest must average 15. Say both; the second one shows you understand why the conditional mean is 3.
Where candidates lose it
The trap is 17.5: the right count, 5, multiplied by the unconditional mean of a die. The interviewer set the question up so that the rolls you sum are selected, not random, and wants to see whether you notice.
The second trap is multiplying 6 rolls by 3.5 and stopping at 21, which includes the six the question told you to exclude. Say what is counted before you multiply.
What the interviewer asks next
What is the expected sum if you do count the six?
What is the expected sum of the rolls before the first time you roll a 1 or a 2?
What is the expected number of rolls until two sixes in a row?

D	the number of distinct faces seen in six rolls
(5/6)^6	the chance a given face never appears in six rolls

V	expected payout of the game, in rupees
3	average of faces 1 to 5
6 + V	payout after a six: the six itself plus a fresh game

N	the number of rolls before the first six, mean 5
X \| X not 6	a roll known not to be a six, uniform on 1 to 5
E	the expected sum from any fresh start

Try it first

Why not list the cases?

How does the indicator trick work step by step?

Where does this pattern reappear?

Where candidates lose it

What the interviewer asks next

Try it first

Why write the game in terms of itself?

How do you set up the equation without slipping?

Where candidates lose it

What the interviewer asks next

Try it first

How many rolls come before the six?

Why is each of those rolls worth 3 and not 3.5?

How do you check 15 a second way in the room?

Where candidates lose it

What the interviewer asks next