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 11–11 of 11 · filtered from 100Clear filters
  1. 090An array of n distinct numbers in random order gets one left-to-right bubble pass: swap the first two if they are out of order, then the new second and third, and so on to the end. What is the probability the array is sorted after that single pass? Work n = 4, then general n.Probability and countingHardJump TradingChicago · 2018

    Try it first

    Where must the smallest number start for one pass to leave it at the front?

    Show the worked solution

    For n = 4 it is 8/24 = 1/3; in general it is 2^(n - 1)/n!. A pass moves any number left by at most one place, so the smallest must start first or second. If it starts first, the rest is the same problem on n - 1 numbers. If it starts second, it swaps to the front and whatever was first becomes the head of a fresh problem on n - 1 numbers. Two choices each time give 2^(n - 1) sortable orders out of n!.

    What can one pass actually do to an array?

    Picture a queue where the tallest person seen so far keeps stepping past whoever is behind them. The tall ones can travel a long way back; everyone else only gets stepped past, and each time that happens they move forward by one place. A single left-to-right pass carries the running maximum to the right and moves every other number left by at most one position. So a number that starts two or more places to the right of where it belongs cannot get home in one pass, and the array cannot come out sorted.

    One pass sorts 4 of the 6 orders of three numbersstartcompare positions 1 and 2compare positions 2 and 3after one pass123123123123sorted132132123123sorted213123123123sorted231231213213not sorted312132123123sorted321231213213not sortedlime = the comparison swapped; the red 1 started two places too far right and can only move onen = 4: 8 of the 24 orders come out sorted, 1/3; in general 2^(n - 1) of n!
    Running all six orders of 1, 2 and 3 through one bubble pass sorts the four that start 1 2 3, 1 3 2, 2 1 3 and 3 1 2 and leaves 2 3 1 and 3 2 1 unsorted, because in those two the 1 starts two places too far right, and the same count for four numbers is 8 of 24, which is 2^(n - 1) of n! in general.

    How does that turn into a count of 2^(n - 1)?

    Look at where the smallest number starts. It must be position 1 or 2. If it is first, the first comparison does nothing and the pass carries on over positions 2 to n, which is the same problem on n - 1 numbers. If it is second, the first comparison swaps it to the front and the number that was first now leads a pass over positions 2 to n, again the same problem on n - 1 numbers. Each step offers exactly two placements for the current smallest number, so the count of sortable orders doubles with each extra element: f(n) = 2 f(n - 1), f(1) = 1, which gives 2^(n - 1). For n = 4 that is 8 of 24, a third.

    The relationship
    P(sorted after one pass)=2 n−1n!,n=3:46,n=4:824=13,n=10:≈0.000141P(\text{sorted after one pass}) = \frac{2^{\,n-1}}{n!}, \qquad n=3: \tfrac{4}{6}, \quad n=4: \tfrac{8}{24} = \tfrac{1}{3}, \quad n=10: \approx 0.000141
    2^(n-1)the number of starting orders one pass sorts
    n!the number of starting orders in all
    What it says in wordsThe sortable orders double with each element while all orders multiply by n, so the chance collapses quickly.

    Then verify on a case you can hold in your head, as the figure does for three numbers: 4 of 6 come out sorted. A brute-force check over every order up to seven numbers gives 1, 2, 4, 8, 16, 32 and 64 sortable orders, as the formula says. The equivalent condition is worth saying too: one pass sorts the array exactly when every number starts no more than one place to the right of its sorted position. The limitation is the assumption that all n! starting orders are equally likely; a nearly sorted array, which is what real data often is, comes out sorted far more often.

    Where candidates lose it

    The common loss is answering with the chance that the array was already sorted, 1/n!, or with the chance that the largest ends last, which is 1. One pass always puts the maximum at the end; the question is whether everything else is home too.

    The second loss is trying to list the n = 4 cases one by one. With 24 orders you will miss some. Find the rule about how far left a number can move and the count follows in two lines.

    What the interviewer asks next

    • What is the probability the array is sorted after two passes?
    • What is the expected number of swaps in one pass?
    • If the pass ran right to left instead, which number would be carried, and does the answer change?

    Asked at Jump Trading, Quantitative Research, Chicago, 2018 (Wall Street Oasis): a math problem about the probability an array is sorted after swapping the first two if they're out of order