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. 067A staircase has 10 steps and you climb either one or two steps at a time. How many different ways are there to reach the top?Probability and countingWarm upTower Research CapitalNew York · 2012

    Try it first

    Ten steps, singles or doubles. How many routes?

    Show the worked solution

    89 ways. Think about the last move. Either it was a single step from step 9 or a double step from step 8, and those two cases cannot overlap, so ways(10) = ways(9) + ways(8). With ways(1) = 1 and ways(2) = 2, the sequence runs 1, 2, 3, 5, 8, 13, 21, 34, 55, 89. It is the Fibonacci rule, shifted by one place.

    Why count by the last move rather than the first?

    Ask how many ways there are to arrive at a railway junction and you count the lines coming in, not the stations people set out from. Every route to step n arrives from exactly one of two places, step n - 1 by a single or step n - 2 by a double, so the routes to n are the routes to those two places added together. The first move works just as well, but the last move makes the recursion read naturally from the top down, and it is the habit that generalises to harder counting problems where you condition on the final event.

    The last move is a single or a double, so ways(n) = ways(n - 1) + ways(n - 2)11 step22 steps33 steps54 steps85 steps136 steps217 steps348 steps559 steps8910 steps3 + 5 = 834 + 55 = 89Why the rule holdsLast move is a single stepso you were on step n - 1: ways(n - 1) routesLast move is a double stepso you were on step n - 2: ways(n - 2) routesThe two cases cannot overlap and cover everything, so add them: 10 steps give 89 ways
    Each count is the sum of the two before it, because the last move is a single step from n - 1 or a double from n - 2, and from ways(1) = 1 and ways(2) = 2 the sequence reaches 89 at ten steps.

    How do you check 89 a second way?

    Count by how many doubles you use. With k doubles and 10 - 2k singles you make 10 - k moves in total, and the number of orderings is 10 - k choose k, so the total is the sum over k from 0 to 5 of C(10 - k, k). That is 1 + 9 + 28 + 35 + 15 + 1 = 89, the same answer by a route that does not use the recursion at all. Two methods agreeing is the thing to say out loud; it also hands you the next question, since the terms tell you that four doubles and two singles is the most common shape of route.

    The relationship
    w(n)=w(n−1)+w(n−2),w(1)=1, w(2)=2  ⇒  w(10)=89=∑k=05(10−kk)w(n) = w(n-1) + w(n-2), \quad w(1) = 1,\ w(2) = 2 \;\Rightarrow\; w(10) = 89 = \sum_{k=0}^{5}\binom{10-k}{k}
    w(n)the number of ways to climb n steps in singles and doubles
    kthe number of double steps used in a route
    C(10 - k, k)the ways to place k doubles among 10 - k moves
    What it says in wordsThe count follows the Fibonacci rule and equals the sum over the number of doubles of the ways to arrange them.

    Where does this pattern appear in trading, and where does it stop?

    In anything built from steps of two sizes: the number of ways a price can move up to a level in ticks of one and two, or the number of paths in a recombining tree. The recursion is also the warm-up for dynamic programming, where the value of a position is built from the values of the positions it can reach, which is how an American option is priced on a lattice. The limitation is that Fibonacci only appears when every move is a one or a two; allow a three-step jump and the rule becomes a sum of the previous three terms, with 274 ways for ten steps.

    Where candidates lose it

    The common wrong answer is 2 to the 10, from imagining a free choice at every step. A double skips a step, so the choices are not independent. Set up the recursion by the last move and the structure appears.

    The second loss is starting the sequence at the wrong place. Ways(1) is 1 and ways(2) is 2, so ten steps give 89 and not 55 or 144.

    What the interviewer asks next

    • Now you may also take three steps at a time. How many ways for 10 steps?
    • How many of the 89 routes use exactly three double steps?
    • What is the probability a random route uses no doubles at all?
    • How is this recursion related to pricing an option on a binomial tree?

    Asked at Tower Research Capital, Intern Interview -, New York, 2012 (Wall Street Oasis): How many ways can you jump up stairs if you can only jump either 1 or 2 steps? Answer: Fibonacci sequence.

  2. 085You draw two cards without replacement and win if the first is black and the second red. Would you rather draw from one 52-card deck or from a 104-card double deck?Probability and countingWarm upOld Mission CapitalNew York · 2014

    Try it first

    Before you compute: which deck, and why?

    Show the worked solution

    The single deck, 25.49% against 25.24%. The first card is black with probability 1/2 in either deck. The second draw is where they differ: with one deck, 26 reds remain in 51 cards, 50.98%; with two decks, 52 remain in 103, 50.49%. Multiply: 26/52 x 26/51 = 25.49% and 52/104 x 52/103 = 25.24%. Removing a black card tilts a small deck towards red more than it tilts a large one.

    Why does the size of the deck matter when the mix is the same?

    Take one boy out of a class of 20 with 10 boys and 10 girls, and the class is 10 girls in 19, 52.6% girls. Take one boy out of a school of 2,000 split evenly, and it is 1,000 in 1,999, 50.03%. The same removal is a bigger share of a smaller group. Drawing without replacement makes the second draw depend on the first, and the dependence is stronger the smaller the deck, which is exactly what the game rewards. You want a black card to make red more likely next, and a single deck gives you more of that lean.

    Removing one black card tilts a small deck more than a big one1246810number of 52-card decks shuffled together25.0%25.2%25.4%25.6%P(black then red); the axis starts at 25%, not zerolimit with infinite decks: 25.00%25.49%25.24%25.12%25.05%The second drawone deck26 / 51 = 50.98%two decks52 / 103 = 50.49%the first draw is 50%in both; only this differs
    The chance of black then red is 25.49% with one deck, 25.24% with two and 25.12% with four, falling towards the 25% that independent draws would give, because the second draw after a black card is 26 of 51 in a single deck but only 52 of 103 in a double deck.

    What is the general pattern, and what is its limit?

    With n decks shuffled together, the chance is 1/2 x 26n/(52n - 1). As n grows the second factor falls towards 1/2 and the product towards 1/4, which is the answer you would get if the draws were independent. Every finite deck beats 25%, and the smallest deck beats it by the most, because the minus one in the denominator is a larger share of a smaller count. The whole effect is small, a quarter of a percentage point between one deck and two, which is also worth saying: the interviewer wants the direction and the reason more than the third decimal.

    The relationship
    Pn=26n52n⋅26n52n−1=12⋅26n52n−1  →  14P_n = \frac{26n}{52n}\cdot\frac{26n}{52n-1} = \frac{1}{2}\cdot\frac{26n}{52n-1} \;\to\; \frac{1}{4}
    nthe number of 52-card decks combined
    26n/(52n - 1)the chance of red once one black card is gone
    1/4the limit as the deck becomes infinitely large
    What it says in wordsThe first draw is always a half; the second draw's lean towards red shrinks as the deck grows.

    Then show you can flip it. If the game paid on black followed by black, the single deck would be worse: 26/52 x 25/51 = 24.51% against 52/104 x 51/103 = 24.76%, and the big deck wins. Same mechanism, opposite sign. Saying that unprompted is what turns a one-line puzzle into evidence that you understand sampling without replacement rather than remembering an answer.

    Where candidates lose it

    The fast wrong answer is that the decks are the same because both are half red. That is true of the first draw and false of the second; the question is about the pair.

    The second loss is computing 25.49% and 25.24% and then picking the double deck because there are more reds in it. More reds and more blacks in the same ratio is not more red; only the removal effect differs, and it favours the small deck.

    What the interviewer asks next

    • Now you win on black then black. Which deck?
    • What is the chance of black then red if you draw with replacement?
    • Three cards: black, red, black. Which deck, and does the answer still favour the smaller one?

    Asked at Old Mission Capital, Quantitative Research, New York, 2014 (Wall Street Oasis): If your goal is to draw a black card followed by a red card, which deck would you choose?