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–2 of 2 · filtered from 100Clear filters
  1. 008You roll a fair die again and again, adding each face to a pot. But if you roll a 1, the whole pot is wiped out and the game ends. You may stop and bank the pot at any time. When should you stop, and why?Expected value and optimal stoppingHardQuant tradingProp trading firms

    Try it first

    First instinct: with 15 in the pot, should you roll once more?

    Show the worked solution

    Roll while the pot is below 20 and stop once it reaches 20 or more. One more roll loses the pot with probability 1/6 and otherwise adds a face of 2, 3, 4, 5 or 6, which sum to 20. The expected change is (20 minus pot) over 6: +3.33 from an empty pot, +0.83 at 15, zero at 20 and negative beyond. The number of rolls so far is irrelevant; only the pot matters. Played this way, the expected bank from an empty pot is about 8.14.

    What does one more roll actually buy you?

    Think of a street game where you can keep picking envelopes that each add a few rupees to your winnings, but one envelope in six says lose everything. Whether to pick again depends on how much you already hold, not on how many envelopes you have opened. The expected change from one more roll is the chance of adding, five sixths, times the average addition, 4, minus the chance of ruin, one sixth, times the pot you would lose. That is (20 minus pot) over 6, and it is positive exactly while the pot is under 20.

    One more roll is worth (20 minus pot) / 6: positive below a pot of 20, negative above0102030pot already held-2+2+4expected gain from one more rollpot = 20: gain is exactly zeroempty pot: +3.33pot 30: -1.67ROLL AGAINBANK ITone more roll adds valueone more roll loses value
    The expected gain from one more roll falls in a straight line from +3.33 with an empty pot to zero at a pot of 20 and to -1.67 at 30, so rolling adds value on the left of 20 and destroys it on the right, and the stopping rule is simply to bank at 20 or above.
    The relationship
    E[Δ∣pot=p]=56×4−16×p=20−p6⇒stop when p≥20E[\Delta \mid \text{pot}=p] = \frac{5}{6}\times 4 - \frac{1}{6}\times p = \frac{20 - p}{6} \quad\Rightarrow\quad \text{stop when } p \ge 20
    pthe pot already held
    5/6 x 4the chance of surviving the roll times the average of the faces 2 to 6
    p/6the pot at risk, times the one-in-six chance of a 1
    What it says in wordsOne more roll is worth the expected addition minus the expected loss, and the two balance when the pot is 20.

    Why is the one-step rule the whole answer here?

    In many stopping problems you cannot trust a one-step look: a roll that loses value today might open a bigger gain tomorrow. Here the gain from one more roll only falls as the pot grows, so once rolling stops being worth it, it never becomes worth it again, and the one-step rule is optimal. You can check it by valuing the whole game for each stopping threshold: stopping at 20 (or 21, which is equivalent because the roll at exactly 20 is worth zero) gives an expected bank of about 8.14, stopping at 15 gives 7.85 and at 25 gives 8.00. Say the word monotone if you know it; say the reason either way.

    What would a desk add to the textbook answer?

    That the rule maximises expected value and nothing else. A player who cannot afford to lose the pot, or who is paid on a target rather than on the average, would stop earlier, and a trader who sizes positions knows that expected value is only the first thing to check. The limitation is the same in the puzzle and on the desk: expected value is right for a game you can play many times, and this game is played once.

    Where candidates lose it

    Candidates who answer by feel either stop far too early, because a one-in-six wipe-out sounds frightening, or never stop, because the pot keeps growing. The question is asking for the point where the two forces balance, and that point is a number: 20.

    The second loss is using 3.5 as the average face. The faces that keep you in the game are 2 to 6, averaging 4, and their total is 20. Using 3.5 gives a threshold of 21 and shows the ruin branch has been counted twice.

    What the interviewer asks next

    • Now rolling a 1 costs you only half the pot. What is the new stopping rule?
    • What is the expected bank from an empty pot under the optimal rule, and how would you compute it?
    • Suppose you must pay 1 for every roll. Does the threshold go up or down, and by how much?
  2. 091I deal a shuffled deck face up one card at a time. At any moment you may say stop; if the next card is red you win, otherwise you lose. What strategy maximises your chance of winning, and what is that chance?Expected value and optimal stoppingHardJump TradingChicago · 2018

    Try it first

    You decide to wait until more reds than blacks remain, then stop. How does that compare with stopping straight away?

    Show the worked solution

    Every strategy wins with probability exactly 1/2, so there is nothing to optimise. The chance that the next card is red equals the share of red left in the deck, and that share is a fair game: whatever has been dealt, its expected value one card later is its value now. A neat way to see it: the card after you say stop has the same chance of being red as the last card in the deck, and the last card is red with probability 1/2 whatever you do.

    Why can't waiting for a good moment help?

    Imagine a jar of 26 red and 26 black sweets that a friend pulls out one at a time, and you bet on the colour of the next one. When more reds are left you feel you have edge, but the jar only gets red-heavy after blacks come out, and you do not control which comes out. The share of red remaining has the same expected value one card from now as it has now, so any rule for when to stop is a bet on a fair game and cannot beat 1/2. The fancy name is a martingale: a quantity whose best forecast of its next value is its current value.

    The share of red left is a fair game: no stopping rule beats 1/2010203040510%25%50%75%100%cards already dealtshare of red among the cards still in the deckdeck A: reds lead after 7 cards, stop at 51.1%deck B: reds never lead,last card is blacklime line: expected share from any point, 1/2Stop when reds leadthe moment comes in26/27usually right after a black,at only 26 of 51 redif it never comes, thelast card is always blackchance of winning1/2same as stopping at once
    Two simulated deals show the share of red among undealt cards wandering around 1/2, with deck A going red-heavy after 7 cards and deck B never going red-heavy and ending on a black card, and the rule of stopping when reds lead gets its chance in 26 deals out of 27 yet wins exactly 1/2, because the deals where it never comes are certain losses.

    What is the one-line proof the interviewer wants?

    Whatever rule you use, you say stop at some point and win if the next card is red. Swap that bet for a bet on the last card of the deck. Given everything dealt so far, the next card and the last card are both a random draw from the same set of undealt cards, so they are red with the same probability. Every stopping rule wins with the same probability as a bet on the bottom card of the deck, and the bottom card is red half the time. That holds for any strategy, so 1/2 is both the best and the worst you can do. A full check of every position from 26 red and 26 black confirms that the best achievable chance from r red and b black is exactly r/(r + b), the chance of stopping right there.

    The relationship
    E ⁣[Rk+1Nk+1  |  RkNk]=RkNk  ⇒  P(win)=R0N0=2652=12E\!\left[\frac{R_{k+1}}{N_{k+1}} \;\middle|\; \frac{R_k}{N_k}\right] = \frac{R_k}{N_k} \;\Rightarrow\; P(\text{win}) = \frac{R_0}{N_0} = \frac{26}{52} = \frac{1}{2}
    R_kred cards still undealt after k cards
    N_kall cards still undealt after k cards
    R_k / N_kthe chance the next card is red if you stop now
    What it says in wordsYour winning chance at any moment has the same expected value tomorrow as today, so no rule for when to stop can raise its starting value of a half.

    Put a number on why the waiting rule fools people. Starting from an even deck, the first black card dealt leaves 26 red in 51, so reds lead immediately half the time, and over the whole deal the moment arrives in 26 deals out of 27. But it typically arrives at a share only just above 1/2, and in the 1 deal in 27 where it never arrives, the last card is black for certain. The edge in the good deals is paid for exactly by the sure loss in the bad ones. The limitation of the result is the payoff: if you were paid more for winning late, or could bet different amounts, the game would no longer be fair and timing could matter.

    Where candidates lose it

    The common loss is proposing the wait-for-reds-to-lead rule and claiming a small edge, usually around 51%. The interviewer then asks what happens if reds never lead, and the edge disappears. Count both branches before you claim anything.

    The second loss is starting a dynamic programme over 27 by 27 states in the room. It works, but it takes far too long. The last-card argument settles it in one sentence and is what the question is testing.

    What the interviewer asks next

    • Now you win Rs 2 if the next card is red and lose Rs 1 if black, and you must stop at some point. Does timing matter?
    • With 3 red and 1 black, what is your chance, and can any strategy change it?
    • What changes if you may skip a card without it being revealed?

    Asked at Jump Trading, Research, Chicago, 2018 (Wall Street Oasis): I'm dealing a deck of poker, you can stop me anytime. If the next card is red, you win.