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–1 of 1 · filtered from 100Clear filters
  1. 067Five traders drop their business cards in a bowl and each draws one at random. What is the probability that nobody draws their own card, and what does it approach as the number of traders grows?Counting and combinatoricsHardQuant tradingQuant research

    Try it first

    As the number of traders grows very large, the chance nobody gets their own card...

    Show the worked solution

    44/120, about 36.7%, and it tends to 1/e, about 36.8%. Count the orderings with no fixed point by inclusion and exclusion: 5! times (1 - 1 + 1/2! - 1/3! + 1/4! - 1/5!) = 44 of the 120 ways. The bracket is the start of the series for e^(-1), so the answer barely moves with the number of traders: it is within about 0.001 of 1/e at five people and closer still after that.

    Why does the answer not go to 0 or to 1?

    Think of a secret gift exchange at the office. With more people, each person is less likely to draw their own name, but there are more people who could. Each trader matches with chance 1/n and there are n traders, so the expected number of matches is exactly 1 at every size, and the chance of zero matches settles rather than vanishing. That is why the answer converges to a constant. It is also why the question is asked: it checks whether you can count an event defined by an absence, which needs inclusion and exclusion.

    The no-match chance settles at 1/e almost at once1/e = 0.3680.10.20.30.40.50n = 10/10.500n = 21/20.333n = 32/60.375n = 49/240.3667n = 544/1200.3681n = 6265/7200.3679n = 71854/50400.3679n = 814833/40320Five traders: 1 - 1 + 1/2 - 1/6 + 1/24 - 1/120 = 44/120Each extra trader adds a smaller correction, alternating in signNumber of traders, with derangements over all orderings
    The chance that nobody draws their own card swings above and below 1/e for small groups and is 44/120 = 0.3667 for five traders, against 1/e = 0.3679, so the number of traders barely matters once there are more than four.

    How does inclusion and exclusion give 44?

    Count the orderings where at least one trader gets their own card, then subtract. Fix any one trader: 4! orderings each, five traders, 120 in total, but that counts orderings with two fixed traders twice. Alternately subtract and add the counts with one, two, three, four and five traders fixed, and you get 120 - 120 + 60 - 20 + 5 - 1 = 44 orderings with no match. Dividing by 120 gives the probability as 1 - 1 + 1/2 - 1/6 + 1/24 - 1/120, and each term is the e^(-1) series truncated.

    The relationship
    P(no match)=Dnn!=∑k=0n(−1)kk!  ⟶  e−1D55!=44120=0.3667P(\text{no match}) = \frac{D_n}{n!} = \sum_{k=0}^{n} \frac{(-1)^k}{k!} \;\longrightarrow\; e^{-1} \qquad \frac{D_5}{5!} = \frac{44}{120} = 0.3667
    D_nthe number of orderings of n items with no item in its own place, a derangement count
    (-1)^k / k!the inclusion and exclusion term for k traders fixed
    What it says in wordsThe chance of no match is the alternating series for e to the minus 1, cut off after n terms.

    How do you check 44 another way?

    Use the recursion. Trader 1 takes some other trader's card, say trader j's, in n - 1 ways. Either j takes trader 1's card back, leaving n - 2 traders to derange, or j does not, which is the same as deranging n - 1 traders. So D(n) = (n - 1)(D(n - 1) + D(n - 2)), and from D(1) = 0 and D(2) = 1 you get 2, 9 and then 4 x (9 + 2) = 44. The number of matches is close to Poisson with mean 1 for any decent n, so exactly one match has about the same chance as none: for five traders it is 3/8 = 45/120.

    Where candidates lose it

    The trap is answering (4/5)^5, about 33%, by treating each trader's miss as independent. The draws are without replacement, so the events are linked; the right answer is close but not equal, and the reasoning is wrong.

    The second loss is getting 44/120 and stopping, when the follow-up about large groups is the point. Say the series is the start of e^(-1), so the answer is about 37% for any number of traders.

    What the interviewer asks next

    • What is the expected number of traders who draw their own card?
    • What is the probability that exactly one trader draws their own card?
    • With 100 traders, roughly what is the chance that at least two draw their own card?