Quant puzzles, solved step by step

Puzzles
100
Traced to a firm
71
Topics
12
Hard
30
Topic
All topicsLogic and algorithmic reasoning10Conditional probability and Bayes7Counting and combinatorics8Continuous and geometric probability9Correlation, regression and linear algebra9Market making, betting and sizing9Expected value and optimal stopping9Statistics and estimation9Pricing, options and index maths7Games and strategic reasoning8Markov chains and random walks7Mental maths and number sense8
Level
AnyWarm upCoreHard
Source
AnyReported at a firmStandard
Showing 1–2 of 2 · filtered from 100Clear filters
  1. 079You may draw numbers uniform on 0 to 1, one after another. Each draw costs 0.02, and when you stop you keep the last number drawn. What is your optimal stopping threshold, and what is the game worth?Expected value and optimal stoppingHardQuant tradingQuant research

    Try it first

    What threshold should you stop at?

    Show the worked solution

    Stop at the first draw of 0.8 or more; the game is worth 0.8 after all fees. Holding x, one more draw improves you by (1 - x)^2 / 2 on average, which equals the 0.02 fee at x = 0.8. Check: you expect 5 draws costing 0.10 in total, and the draw you keep averages 0.90, so the net value is 0.80.

    How do you decide whether one more draw is worth it?

    Think of hunting for a flat. Each viewing costs you an evening. If the flat in hand is already good, another viewing rarely beats it, and when it does it only beats it by a little. The value of one more look is the chance of beating what you hold times the average margin when you do, and you stop when that falls below the price of looking. With a uniform draw and a current value x, the chance of beating x is 1 - x and the average margin is (1 - x)/2, so the expected gain is (1 - x)^2 / 2.

    Draw again only while the expected improvement beats the 0.02 feegain above cost:draw againgain below cost:stop and keep xcost of a draw, 0.02gain from one more draw = (1 - x)^2 / 2threshold x* = 0.80.50.60.70.80.91.00.050.100current value x
    The expected gain from one more draw, (1 - x)^2 / 2, falls below the 0.02 cost exactly at x = 0.8, so you keep drawing while you hold less than 0.8 and stop at the first draw above it.
    The relationship
    V=E[max⁡(U,V)]−c=V+(1−V)22−c  ⇒  (1−V)22=c  ⇒  V=1−2c=0.8V = \mathbb{E}[\max(U, V)] - c = V + \frac{(1-V)^2}{2} - c \;\Rightarrow\; \frac{(1-V)^2}{2} = c \;\Rightarrow\; V = 1 - \sqrt{2c} = 0.8
    Vthe value of the game before paying for the next draw
    Uthe next uniform draw
    cthe cost per draw, 0.02
    What it says in wordsThe game is worth one draw plus the option to walk away with it, less the fee, and solving that gives both the threshold and the value, 0.8.

    Why are the threshold and the value the same number?

    Because the game has no memory. After a disappointing draw you are back where you started, facing the same game worth V. You should accept a draw exactly when it beats what the fresh game is worth, so the threshold equals the value. This is the same logic as a reservation price: you walk away from any offer below what the next round is worth to you. The arithmetic check is worth saying: with threshold 0.8 a draw succeeds with probability 0.2, so you expect 5 draws and 0.10 of fees, and an accepted draw is uniform on 0.8 to 1 with mean 0.9. The net is 0.9 - 0.10 = 0.8. A seeded simulation of 200,000 games gives 0.800.

    What happens as the cost changes?

    The threshold is 1 - sqrt(2c), so it responds to the square root of the cost. A fee of 0.005, four times cheaper, only moves the threshold from 0.8 to 0.9. At a fee of 0.5 or more, the threshold hits zero and you take the first draw, because even the first draw's average of 0.5 barely covers what you paid. The limitation of the model is that draws are independent and the distribution is known; if you were learning the distribution as you drew, the first few draws would be worth more than this rule says.

    Where candidates lose it

    The common wrong threshold is 0.98, from reasoning that one more draw is worth it whenever the cost is less than what you could gain at best. That compares the fee with the best case, not with the average improvement, and it draws far too many times.

    The second loss is getting 0.8 as a threshold and then quoting the value as the average of the kept draw, 0.9. The fees paid on the way, 0.10 on average, come off. Say the check out loud: 0.9 minus 0.1 is 0.8.

    What the interviewer asks next

    • What if you are only allowed at most two draws in total?
    • What if each draw is uniform on 0 to 100 and costs 1?
    • Now the fee is charged only on draws after the first. What changes?
  2. 091Turn over the cards of a well-shuffled 52-card deck one at a time until the first ace appears. What is the expected number of cards you turn over, counting the ace?Expected value and optimal stoppingHardQuant tradingProp trading firms

    Try it first

    Before you calculate: how many cards do you expect to turn?

    Show the worked solution

    10.6 cards, which is 53/5. Each of the 48 non-aces comes before all four aces with probability 1/5, because among that card and the four aces each is equally likely to be first. So on average 48/5 = 9.6 non-aces precede the first ace, and counting the ace itself gives 10.6. For n cards with m special ones the rule is (n + 1)/(m + 1).

    Why isn't the answer 13?

    Drop four red counters at random into a line of 48 white ones. Nothing distinguishes the stretch of white before the first red from the stretch between the second and third reds, or the stretch after the last red. The four reds cut the whites into five stretches, and by symmetry each stretch holds the same number on average, 48/5 = 9.6. The answer 13 imagines the aces spread evenly from the top of the deck, but that leaves no room for the stretch after the last ace, which is just as long on average as the others.

    Four aces cut the other 48 cards into five gaps of 9.6 on averageOn average: five equal gaps of 48/5 = 9.6 cards9.6A9.6A9.6A9.6A9.6first ace at card 9.6 + 1 = 10.6One real shuffle: gaps of 6, 23, 7, 8, 4. Unequal, yet each gap averages 9.6623784Tempting but wrong: 52 / 4 = 13aces evenly spaced from the top, no gap left after the last ace
    The four aces split the 48 other cards into five gaps that average 9.6 cards each, so the first ace arrives at card 10.6 on average; a single shuffle gives unequal gaps such as 6, 23, 7, 8, 4, and spacing the aces evenly at 13 ignores the fifth gap.
    The relationship
    E[X]=1+∑j=148P(card j precedes all four aces)=1+48×15=535=10.6\mathbb{E}[X] = 1 + \sum_{j=1}^{48} P(\text{card } j \text{ precedes all four aces}) = 1 + 48 \times \tfrac{1}{5} = \tfrac{53}{5} = 10.6
    Xthe position of the first ace, counting the ace
    card jone of the 48 non-aces
    1/5the chance card j is first among itself and the four aces
    What it says in wordsCount the non-aces that come before the first ace one card at a time, add up their probabilities, and add one for the ace.

    How do you make the symmetry argument rigorous?

    Use indicators. Pick any non-ace, say the seven of clubs. It is turned before the first ace exactly when it comes first among five cards: itself and the four aces. Those five cards sit in a random order, so that happens with probability 1/5. An expected count is the sum of the probabilities, even when the events depend on each other, so 48 x 1/5 = 9.6 non-aces come first on average and the ace makes it 10.6. The exact sum of the chances that the first ace is later than card k, over k from 0 to 48, gives 53/5 as well, and a seeded simulation of 100,000 shuffles gives 10.63.

    The mean hides a skewed shape. The first ace is in the top five cards 34.1% of the time, and the median position is 9, below the mean of 10.6, because a few shuffles bury all four aces deep in the deck and drag the average up. If the interviewer asks for the most likely position, the answer is the very first card: each later position needs every earlier card to be a non-ace, so the chances fall card by card.

    How does it generalise, and where is it useful?

    With n cards and m special ones, the m specials cut the n - m others into m + 1 gaps, so the first special arrives at (n - m)/(m + 1) + 1 = (n + 1)/(m + 1). Check it with one ace: (52 + 1)/2 = 26.5, the middle of the deck, which is what you would expect. The first spade, with 13 specials, arrives at card 53/14, about 3.79. The same gap symmetry gives the expected wait for the first default in a pool or the first fill among queued orders, provided every ordering is equally likely. That proviso is the limitation: if defaults cluster in time or the deck is stacked, the gaps stop being exchangeable and the rule fails.

    Where candidates lose it

    The quick wrong answer is 13, from 52 cards divided by 4 aces. That spaces the aces evenly from the top and forgets that the stretch after the last ace is, on average, as long as the stretch before the first.

    The second loss is reaching 9.6 and stopping. That is the number of cards before the ace; the question counts the ace itself, so add one to get 10.6. Say which you are quoting, because interviewers vary the wording to catch exactly this.

    What the interviewer asks next

    • What is the expected position of the second ace?
    • What is the expected number of cards turned until the first spade?
    • Which is more likely: the card after the first ace is the ace of spades, or it is the two of clubs?