Quant puzzles, solved step by step

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

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

011An urn starts with one red ball and one blue ball. Each turn you draw a ball at random, put it back, and add another ball of the same colour. After ten draws, what is the probability that exactly five of the draws were red?Markov chains and random walksCoreQuant researchQuant trading
Try it first
Your first instinct for P(exactly five reds)?
Show the worked solution
1/11, about 9.1%. Any particular sequence with five reds and five blues has probability 5! x 5! / 11!, whatever the order, because the numerators just count up the reds and blues separately. There are 10 choose 5 = 252 such sequences, and 252 x 5! x 5! / 11! = 1/11. The same algebra gives 1/11 for every count from 0 to 10.
Why is this not ten coin flips?
Think of a new café and its first customers. If the first few visitors like it and bring friends, it fills up; if they do not, it stays empty. Early luck compounds. In this urn each red draw adds a red ball, so it raises the chance of the next red: the draws reinforce each other, and runs that start lopsided tend to stay lopsided. That spreads the count of reds far more widely than independent coin flips, which bunch around five.
After ten draws from an urn that starts with one red and one blue ball and adds a ball of the drawn colour each time, every count of reds from 0 to 10 has probability 1/11, a flat line, while ten fair coin flips would pile up at five with 24.6%.
Why does the order of the draws not matter?
Write out one sequence, say five reds then five blues. The chances are 1/2, 2/3, 3/4, 4/5, 5/6 for the reds, then 1/7, 2/8, 3/9, 4/10, 5/11 for the blues. Shuffle the order and the denominators are still 2 up to 11, while the red numerators still run 1 to 5 and the blue ones 1 to 5, so every arrangement of five reds and five blues has the same probability, 5! x 5! / 11!. Draws whose joint probability ignores order are called exchangeableA sequence of random variables whose joint distribution does not change when you reorder them, even though they need not be independent., and that is the property doing the work.
The relationship
$P(k \text{ reds in } n) = \binom{n}{k}\frac{k!\,(n-k)!}{(n+1)!} = \frac{1}{n+1} \qquad n = 10:\; \frac{252 \cdot 120 \cdot 120}{39\,916\,800} = \frac{1}{11}$
\binom{n}{k} the number of orders in which k reds can appear
k!(n-k)!/(n+1)! the probability of any one such order
What it says in wordsThe number of orders times the probability of each order is always one over n plus one.
Is there a picture that makes 1/11 obvious?
Yes. This urn behaves exactly as if nature first picked a hidden red probability p uniformly between 0 and 1, and then flipped ten independent coins with that p. Averaging a binomial over a uniform p gives every count the same weight, 1/(n + 1). The urn is also a small model of momentum and of market share: an early lead makes further gains more likely, so the final split is highly uncertain, even though each step looks like a fair draw.
Where candidates lose it
The fast wrong answer is 252/1024, about 24.6%, from treating the draws as independent coin flips. The reinforcement is the whole question, and it spreads the outcomes out rather than pulling them to the middle.
The second trap is trying to add up paths through a tree of ten levels. Spot that every order of a given mix has the same probability, and the problem collapses to one line.
What the interviewer asks next
What is the probability the eleventh draw is red, given that five of the first ten were red?
What if the urn starts with two red and one blue ball?
As the number of draws grows, what does the fraction of red balls converge to?
062A symmetric random walk starts at 0 and moves up or down by one each step with equal probability. What is the expected number of steps until it first reaches +3 or -3?Markov chains and random walksCoreQuant researchQuant trading
Try it first
What is the expected number of steps to hit +3 or -3 from 0?
Show the worked solution
9 steps. Let E(k) be the expected steps left from state k. Each step costs one and lands on a neighbour with equal chance, so E(k) = 1 + (E(k - 1) + E(k + 1))/2, with E(3) = E(-3) = 0. The solution is E(k) = (3 - k)(3 + k): 9 from 0, 8 from plus or minus 1, 5 from plus or minus 2. A symmetric walk needs about the square of the distance to travel it.
Why is the answer not 3?
Think of someone pacing a narrow corridor, choosing left or right at random with every step. They do reach a wall eventually, but they spend most of their time doubling back. A random walk with no drift covers distance like the square root of time, so covering a distance of 3 takes about 3 squared steps, not 3. The answer 3 would only be right if the walk always moved in one direction. The structure to name in the room is a first-step recursion on the state, which turns the question into seven unknowns with simple links between them.
The expected number of steps left is 9 from the centre, 8 one step out, 5 two steps out and 0 at the walls, tracing the parabola 9 - k squared, which is the product of the distances to the two walls.
How do you solve the recursion quickly?
Use symmetry first: E(1) = E(-1) and E(2) = E(-2). Then three equations remain. From 2: E(2) = 1 + (E(1) + 0)/2. From 1: E(1) = 1 + (E(0) + E(2))/2. From 0: E(0) = 1 + E(1), because both neighbours are worth E(1). Substituting gives E(1) = 8 and E(0) = 9, and every value matches the product of the distances to the two walls. The second differences of E are all minus 2, which is why the answer is a parabola: each step must remove exactly one unit of expected time.
The relationship
$E(k) = 1 + \tfrac12 E(k-1) + \tfrac12 E(k+1),\quad E(\pm 3) = 0 \;\Rightarrow\; E(k) = (3-k)(3+k),\quad E(0) = 9$
E(k) the expected number of steps left from state k
1 the step just taken
E(plus or minus 3) = 0 the walls, where the walk stops
What it says in wordsOne step plus the average of the two neighbouring states, solved, gives the product of the distances to the walls.
How do you check 9 a second way?
Use a martingaleA process whose expected next value, given everything so far, equals its current value: a fair game.. Squaring the position and subtracting the number of steps gives a fair game, because each step adds exactly 1 to the expected square. At the moment the walk stops its square is exactly 9, so the expected number of steps must also be 9. The same argument handles uneven walls: starting between -a and +b, the expected time is a times b. The cousin result is the hitting probability: from +1, the walk reaches +3 before -3 with probability 2/3, the distance to the far wall over the total width.
Where candidates lose it
The trap answers are 3, from treating the walk as if it marched to a wall, and infinity, from a half-remembered fact that a symmetric walk on the whole line takes infinite expected time to reach a given level. With two walls, escape is certain and fast.
The second loss is setting up seven equations and grinding them. Use symmetry to cut to three, then state the product rule and check it with the squared-position argument.
What the interviewer asks next
Starting at 0, what is the expected time to hit +2 or -4?
From +1, what is the probability of reaching +3 before -3?
With only one wall at +3 and no lower wall, what is the expected time to reach it?

\binom{n}{k}	the number of orders in which k reds can appear
k!(n-k)!/(n+1)!	the probability of any one such order

E(k)	the expected number of steps left from state k
1	the step just taken
E(plus or minus 3) = 0	the walls, where the walk stops

Try it first

Why is this not ten coin flips?

Why does the order of the draws not matter?

Is there a picture that makes 1/11 obvious?

Where candidates lose it

What the interviewer asks next

Try it first

Why is the answer not 3?

How do you solve the recursion quickly?

How do you check 9 a second way?

Where candidates lose it

What the interviewer asks next