The Interview Book · Careers

10Probability I

“I roll two dice and tell you that at least one of them is a six. What is the chance that both are?” Half the room says one sixth, a few say one eleventh, and one candidate asks how the interviewer came to say it, which is the only question that settles the answer. Probability questions in interviews are short, and most of them test one of four things: counting without double counting, conditioning on the right event, seeing a symmetry, and knowing that what you are told depends on how you came to be told it.

10.1 Counting

Every finite probability is a ratio of counts over equally likely outcomes, and the difficulty is always in the count. Four tools cover most interview questions: the product rule (choices made in sequence multiply); arrangements of a word with repeated letters, $n!/(k_1!\,k_2!\cdots)$ ; subsets, $\binom nk$ ; and multisets, the number of ways to put $n$ identical items in $k$ labelled boxes, $\binom{n+k-1}{k-1}$ (“stars and bars”), or $\binom{n-1}{k-1}$ if every box must get at least one.

Definition 10.1 (Complementary counting)

Complementary counting computes the probability of an event through its complement, $\P(A) = 1 - \P(A^c)$ , when the complement is a single simple case and the event itself is a union of many overlapping ones: “at least one”, “some two coincide”, “not all different”.

Example 10.2 (Colliding identifiers)

Thirty client order identifiers are drawn uniformly and independently from 10 000 values. The chance that all differ is $\prod_{k=0}^{29}(1 - k/10\,000) \approx 0.957$ , so at least two coincide with probability about 0.043. The approximation $1 - e^{-n(n-1)/(2N)}$ gives the same to three decimals, and it shows the scale: collisions become likely once $n$ is of the order of $\sqrt N$ .

10.2 Conditioning and Bayes

Conditioning restricts the sample space to the outcomes consistent with what is known and renormalises. Bayes’s rule is the same statement written in the direction the question needs. For binary hypotheses it is fastest in odds: posterior odds equal prior odds times the likelihood ratio $\P(\text{data} \mid H)/\P(\text{data} \mid H^c)$ , and independent pieces of evidence multiply their likelihood ratios (One Quant Book 4, chapter 14, on priors and posteriors).

Method 10.3 (Three ways to condition)

Tree: draw the stages in the order they happen, write the probabilities on the branches, and add the leaves consistent with what is known.
Table: when two binary variables are involved, a two-by-two table of counts out of 1 000 or 10 000 makes base rates visible.
Odds: prior odds times likelihood ratio, when the evidence arrives in pieces.

Example 10.4 (A rare event and a good test)

One account in 500 is fraudulent; an alert fires on 95% of fraudulent accounts and on 2% of the others. Out of 100 000 accounts, 200 are fraudulent and 190 of them trigger the alert; of the 99 800 others, 1 996 do. An alert therefore means fraud with probability $190/2\,186 \approx 0.087$ . The prior odds of $1:499$ times the likelihood ratio $0.95/0.02 = 47.5$ give the same answer.

10.3 Symmetry arguments

Definition 10.5 (Symmetry argument)

A symmetry argument computes a probability or an expectation by exhibiting a transformation of the sample space that preserves probabilities and exchanges the outcomes of interest, so that they must have equal probability, without computing either.

Example 10.6 (The first ace)

Where, on average, is the first ace in a shuffled deck? The four aces cut the 48 other cards into five gaps, and by symmetry each gap holds on average $48/5 = 9.6$ cards, so the first ace is at position $9.6 + 1 = 53/5 = 10.6$ on average. An exhaustive count over small decks confirms the formula $(n+1)/(k+1)$ .

The symmetry must be real. “Each of the six strategies is equally likely to be the best next year” is a symmetry only if the strategies are exchangeable; a candidate who says so should say that it is an assumption.

10.4 Paradoxes and what they test

Most probability paradoxes are questions in which the answer depends on a protocol the question does not state: how the information was generated. The interviewer who asks the hook’s question wants to hear that.

Proposition 10.7 (Two dice, two protocols)

Two fair dice are rolled. (A) If the informant reports “at least one six” exactly when there is one, the chance of two sixes given the report is $\tfrac1{11}$ . (B) If the informant looks at one die chosen at random and reports that it shows six, the chance is $\tfrac16$ .

Proof. (A) Eleven of the 36 equally likely outcomes contain a six, one of them two. (B) The report depends only on the die looked at, which is independent of the other die; the other die is a six with probability $\tfrac16$ (Figure 10.1). ∎

The same sentence, “there is a six”, under two protocols. Under (A) the report selects the eleven outcomes with a six; under (B) it tells you about one die only, and the other die is untouched. Exact enumeration and a simulation in iv_prob1.py. — **Figure 10.1.** The same sentence, “there is a six”, under two protocols. Under (A) the report selects the eleven outcomes with a six; under (B) it tells you about one die only, and the other die is untouched. Exact enumeration and a simulation in `iv_prob1.py`.

Method 10.8 (Answering a paradox)

Ask, or state, the protocol: who chose what to reveal, and how.
Write the joint sample space of the hidden state and the report.
Condition on the report, not on the sentence’s literal content.
Give the answer for each plausible protocol if the interviewer declines to choose.

The classic problems of this family, Bertrand’s box (1889), the two-children problem (discussed by Gardner in 1959 and analysed as a protocol question by Bar-Hillel and Falk in 1982) and the three-door problem (Selvin’s letter of 1975), appear in the bank only as variants with their own answers.

10.5 Worked answers

Example 10.9 (Which venue filled it?)

“A router sends an order to venue A with probability 0.7, where it fills with probability 0.4, and otherwise to venue B, where it fills with probability 0.9. The order filled. What is the chance it went to A?” Count in a population of 100 orders: 70 go to A and 28 fill there; 30 go to B and 27 fill there. Of the 55 fills, 28 came from A: $28/55 \approx 0.51$ . Before the fill the answer was 0.7; the fill is evidence for B, which fills more often, and the posterior falls to about a half. Check: if both venues filled at the same rate the fill would carry no information and the answer would stay 0.7; with the counting table the check takes one line.

Example 10.10 (Symmetry before summation)

“Ten days of P&L, independent and identically distributed with a continuous distribution. What is the chance that the best day comes after the worst day? That the best day is the last day? That the last day is the best of the ten and the first day the worst?” Reversing the order of the days maps “best after worst” to “best before worst” and leaves the distribution unchanged, so the chance is $1/2$ . All ten days are equally likely to be the best: $1/10$ . For the last, there are $10 \times 9$ equally likely (best, worst) pairs of days: $1/90$ . The interviewer is scoring whether the candidate reaches for exchangeability before writing a sum; the answer takes fifteen seconds that way and several minutes the other.

10.6 Question bank

Interview question 10.1 ★ trader, developer • any

In how many orders can five different trades be booked? In how many distinct orders can the letters of AABBC be arranged?

Solution

Solution of Interview question 10.1.

$5! = 120$ . For AABBC, $5!/(2!\,2!) = 30$ .

What the interviewer is looking for: the product rule and division by the repeats.

Interview question 10.2 ★ trader • market maker

What is the chance of at least one six in four rolls of a fair die? Is a bet on it at even money favourable?

Solution

Solution of Interview question 10.2.

$1 - (5/6)^4 = 671/1\,296 \approx 0.518$ : slightly favourable at even money, an edge of about 3.5% of the stake.

What the interviewer is looking for: the complement and the translation into a bet’s edge.

Interview question 10.3 ★ trader • market maker

Two cards are dealt from a full deck. What is the chance both are aces?

Solution

Solution of Interview question 10.3.

$\tfrac4{52} \times \tfrac3{51} = \tfrac1{221}$ , or $\binom42/\binom{52}2 = 6/1\,326$ .

What the interviewer is looking for: sequential or combinatorial counting, with the same answer.

Interview question 10.4 ★ developer, researcher • proprietary firm

In how many ways can ten identical child orders be routed to four venues? In how many if each venue must receive at least one?

Solution

Solution of Interview question 10.4.

Stars and bars: $\binom{13}3 = 286$ . With at least one each, give one to every venue and distribute the remaining six: $\binom93 = 84$ .

What the interviewer is looking for: the multiset count and the shift for a minimum.

Interview question 10.5 ★ researcher, mle • systematic fund

Six strategies are exchangeable. What is the chance that strategy A beats strategy B next year? That A is the best of the six? That A beats both B and C?

Solution

Solution of Interview question 10.5.

By exchangeability: A beats B with probability $\tfrac12$ ; A is best with $\tfrac16$ ; A beats both B and C when A is first among the three, $\tfrac13$ . Exhaustive enumeration of the 720 orders confirms all three.

What the interviewer is looking for: symmetry, stated as an assumption about exchangeability.

Interview question 10.6 ★★ developer • proprietary firm

A system draws 1 000 client order identifiers uniformly from a million values. What is the chance that two coincide? About how many identifiers can it draw before the chance reaches one half?

Solution

Solution of Interview question 10.6.

$1 - \prod_{k<1000}(1 - k/10^6) \approx 1 - e^{-1000 \times 999/(2 \times 10^6)} \approx 0.393$ . The chance reaches one half when $n(n-1)/(2N) \approx \ln 2$ , $n \approx \sqrt{2N\ln 2} \approx 1\,177$ . Identifiers should be sequential or wide (64 bits), not small random numbers.

What the interviewer is looking for: the birthday approximation, the square-root scale, and the engineering conclusion.

Interview question 10.7 ★★ risk, researcher • bank

One account in 500 is fraudulent. An alert fires on 95% of fraudulent accounts and 2% of legitimate ones. An alert fires on an account; what is the chance it is fraudulent?

Solution

Solution of Interview question 10.7.

$\frac{0.95 \times 0.002}{0.95 \times 0.002 + 0.02 \times 0.998} = \frac{95}{1\,093} \approx 0.087$ . A good alert on a rare event is mostly false alarms: in a population of 100 000, 190 true alerts against 1 996 false ones.

What the interviewer is looking for: base rates, done by a table of counts or by odds.

Interview question 10.8 ★★ trader, researcher • market maker

“I rolled two dice; at least one is a six. What is the chance both are?” Give the answer under two protocols, and say which question you would ask the interviewer.

Solution

Solution of Interview question 10.8.

If the report means “the outcome contains at least one six”, condition on the 11 such outcomes: $\tfrac1{11}$ . If you looked at one die at random and it showed a six, the other die is independent: $\tfrac16$ (Proposition 10.7). Ask: “How did you come to tell me that: did you check both dice, or look at one?” A simulation of both protocols gives 0.091 and 0.167.

What the interviewer is looking for: recognising that the answer depends on the protocol, and asking for it.

Interview question 10.9 ★★ trader • proprietary firm

On average, how many cards do you turn over from a shuffled deck to see the first ace? Why does the argument not need any summation?

Solution

Solution of Interview question 10.9.

$53/5 = 10.6$ . The four aces divide the other 48 cards into five gaps that are exchangeable, so each gap holds on average $48/5$ cards, and the first ace follows the first gap. The symmetry replaces the sum over positions.

What the interviewer is looking for: the gap symmetry argument.

Interview question 10.10 ★★ risk, mle • bank

In Interview question 10.7, a second, independent alert with the same rates also fires on the account. What is the chance now?

Solution

Solution of Interview question 10.10.

In odds: prior $1:499$ , each alert multiplies by $0.95/0.02 = 47.5$ , so the posterior odds are $47.5^2/499 \approx 4.52$ and the probability $4.52/5.52 \approx 0.819$ . Independence of the two alerts given the account’s status is the assumption that matters; two alerts built on the same data are not independent evidence.

What the interviewer is looking for: odds updating, and the conditional-independence caveat.

Interview question 10.11 ★★★ trader, researcher • market maker

Four envelopes contain tickets: two winning; one winning and one losing; two losing; two winning and one losing. You choose an envelope at random and draw a ticket at random: it is winning. You draw a second ticket from the same envelope. What is the chance it is winning too?

Solution

Solution of Interview question 10.11.

Weight each envelope by the chance of drawing a winning ticket first: $\tfrac14 \times (1, \tfrac12, 0, \tfrac23)$ . Given a winning first draw, the chance that the second is winning is 1 from the first envelope, 0 from the second, and $\tfrac12$ from the fourth (one winning and one losing remain). The answer is $(1 \times 1 + \tfrac12 \times 0 + \tfrac23 \times \tfrac12)/(1 + \tfrac12 + \tfrac23) = \tfrac43 / \tfrac{13}6 = \tfrac8{13} \approx 0.615$ . This is a variant of Bertrand’s box; the trap is to answer $\tfrac12$ by counting envelopes rather than tickets.

What the interviewer is looking for: weighting hypotheses by the likelihood of the observation.

Interview question 10.12 ★★★ trader • proprietary firm

Four doors, one prize. You pick a door; the host, who knows where the prize is, opens one of the other three that is empty, choosing at random among the empty ones. You may stay, or switch to one of the two other closed doors, chosen at random. What is your chance of winning each way?

Solution

Solution of Interview question 10.12.

Staying wins with probability $\tfrac14$ . Switching: with probability $\tfrac34$ the prize is behind one of the other three doors, and after the host opens an empty one it is behind one of the two you may switch to; choosing at random between them wins half the time: $\tfrac34 \times \tfrac12 = \tfrac38$ . Switching is better. An enumeration over the prize’s position, the host’s choice and yours confirms it.

What the interviewer is looking for: conditioning on the host’s informed choice, and the general principle behind the classic three-door answer.

Interview question 10.13 ★★★ developer, researcher • any

Two orders arrive at independent uniform times in the same minute. What is the chance they arrive within ten seconds of each other?

Solution

Solution of Interview question 10.13.

In the 60-by-60 square of arrival times, the orders are more than ten seconds apart in two triangles of legs 50: area $50^2 = 2\,500$ of $3\,600$ . The chance of arriving within ten seconds is $1 - (50/60)^2 = 11/36 \approx 0.306$ .

What the interviewer is looking for: a geometric picture of a joint uniform law.

Interview question 10.14 ★★★ researcher, trader • systematic fund

A trader has two positions, each profitable with probability one half and each opened on a day of the week chosen uniformly, independently. You learn that at least one of them is profitable and was opened on a Monday. What is the chance that both are profitable? Why is the answer not one third?

Solution

Solution of Interview question 10.14.

Each position has 14 equally likely states (profitable or not, times seven days). The outcomes in which at least one position is profitable and opened on Monday number $14^2 - 13^2 = 27$ ; those in which both are profitable and at least one of them was opened on Monday number $7^2 - 6^2 = 13$ . The answer is $13/27$ . It is not $\tfrac13$ (the answer to “at least one is profitable”) because the Monday detail makes the case of two profitable positions nearly twice as likely to produce the report: the more specific the information, the closer the answer to $\tfrac12$ .

What the interviewer is looking for: careful counting of the conditioning event, and the reason extra detail changes it.

Sources and further reading

J. Bertrand, Calcul des probabilités, Gauthier-Villars, 1889 (the box paradox).
M. Gardner, “Mathematical games”, Scientific American, May 1959 (the two-children problem).
M. Bar-Hillel and R. Falk, “Some teasers concerning conditional probabilities”, Cognition 11(2), 1982, 109–122.
S. Selvin, letter to the editor, The American Statistician 29(1), 1975, 67.
One Quant Book 4, chapters 1 and 14 (conditional expectation; Bayesian methods).

Terms defined in this chapter

See all 2333 terms in the glossary