Derivatives Foundation puzzles, solved step by step

Puzzles
100
Traced to a firm
66
Topics
12
Hard
29
Topic
All topicsMental maths and estimation9Random walks and Markov chains7Conditional probability and Bayes7Volatility and correlation7Option pricing intuition7Expected value and optimal stopping10Market making11Option payoffs and no-arbitrage10Probability and counting11Distributions and statistics8Games and logic8Betting and sizing5
Level
AnyWarm upCoreHard
Source
AnyReported at a firmStandard
Showing 1–1 of 1 · filtered from 100Clear filters
  1. 021You roll a fair die again and again and keep a running total. What is the probability that the running total is ever exactly 10? And what does the probability of hitting a given target settle to as the target grows large?Probability and countingHardQuant trading

    Try it first

    Before any recursion: for a very large target, the chance the running total lands on it exactly is closest to

    Show the worked solution

    For 10 the chance is 0.2893, and for large targets it settles at 2/7, about 0.286. The total lands on n only by landing on one of the six numbers before it and then rolling the exact gap, so p(n) is the average of the previous six values, starting from p(0) = 1. Running that recursion gives p(10) = 17,492,167/60,466,176. In the long run the total advances 3.5 per roll, so it lands on one number in 3.5.

    How do you set up the recursion?

    Think of climbing a staircase by jumping one to six steps at a time, each jump picked at random. To stand on step 10 you must at some point stand on one of steps 4 to 9 and then make exactly the right jump. The running total equals n only if it first equals one of n minus 1 down to n minus 6 and then the next roll is exactly the gap, and those six routes cannot both happen, so p(n) is the sum of p(n minus k) times 1/6 for k from 1 to 6. In words, each value is the average of the six before it, with p(0) = 1 because you start at zero and p of a negative number = 0.

    The relationship
    p(n)=16∑k=16p(n−k),p(0)=1,p(n<0)=0,p(10)=17,492,16760,466,176≈0.2893p(n) = \frac{1}{6}\sum_{k=1}^{6} p(n-k),\qquad p(0) = 1,\quad p(n<0) = 0,\qquad p(10) = \frac{17{,}492{,}167}{60{,}466{,}176} \approx 0.2893
    p(n)the probability that the running total ever equals n exactly
    p(n - k)the chance the total visits the number k below the target
    1/6the chance the next roll is exactly the gap k
    What it says in wordsThe chance of hitting a number is the average of the chances of hitting each of the six numbers just below it.
    np(n)np(n)
    10.166760.3602
    20.194470.2536
    30.226980.2681
    40.264790.2804
    50.3088100.2893
    100.2893
    The hit probability climbs to a peak of 0.3602 at six, falls back to 0.2536 at seven, and by ten is already within half a percentage point of its long-run level of 2/7.
    Chance the running total ever equals n: up to a peak at 6, then settling at 2/70.10.20.30.412345678910111213141516171819202/7 = 0.2860.360p(10) = 0.2893each bar = average of the six before it1 to 6: (1/6)(7/6) to the n-1target n
    The chance the running total ever equals n climbs from 0.167 at one to a peak of 0.360 at six, drops at seven, and then wobbles in towards 2/7 = 0.286, with p(10) = 0.2893, because each bar is the average of the six bars before it.

    Why does it settle at 2/7?

    If you walk down a long street taking steps that average 3.5 paving stones, then over a kilometre you will have stepped on about one stone in every 3.5. A long run of rolls moves the total forward 3.5 per roll on average, so the totals visited are a share 1/3.5 = 2/7 of all the numbers passed, and far from the start every number is equally likely to be one of them. That is the renewal argument, and it gives the limit without any recursion. It also explains why the answer is not 1/6: the total does not get one try at each number, it passes every number and either lands on it or steps over it.

    Why the hump at 6, and what is the desk point?

    Small totals have many routes compared with their distance from zero: you can reach 6 in one roll, or in two, three, up to six rolls. For n from 1 to 6, p(n) = (1/6)(7/6) to the power n minus 1, so it grows each step and peaks at 0.360 at six; after that the averaging takes over and damps the swings. The interview point, often set as a coding task, is dynamic programming: one pass, six additions per number, no enumeration of paths. The limitation to say out loud is that the 2/7 limit needs a fair die and nothing that depends on the total so far; a rule such as skip your turn above 50 breaks it.

    Where candidates lose it

    The common answer is 1/6, as though the total gets a single roll at landing on 10. It gets many chances, from 4, 5, 6, 7, 8 and 9, and the whole question is about adding those routes without double counting.

    The second loss is trying to count sequences of rolls that sum to 10 and weight each by its length. It works in principle and collapses under the arithmetic in the room. The recursion on p(n) is the answer the interviewer is waiting for, followed by the 2/7 limit from the average step.

    What the interviewer asks next

    • Write the recursion as a loop and say how much work it takes to reach n = 1,000.
    • The die is replaced by a coin that moves the total 1 or 2. What is the long-run hit chance, and what is p(n) exactly?
    • What is the expected number of rolls until the running total first reaches 10 or more?