How to solve Expected value questions

Harder probability: waiting times, order statistics, optimal stopping, gambler's ruin, Kelly, symmetry tricks. The level reported for SIG, IMC, Citadel Securities, DRW and trader phone screens.

How to solve them

Patterns

1. Cue: "until HTH appears".
2. Method: E = sum of 2^k over every k where the pattern's first k letters equal its last k letters (for a fair coin).
3. Anchors: HT = 4, HH = 6, HHH = 14, HTH = 10.
4. Check: patterns that overlap themselves take longer.
5. Say the setup out loud before calculating. Interviewers care about the method as much as the number.

Order stats

1. Cue: "highest", "lowest", "second smallest".
2. Discrete: E[max] = sum over k of P(max >= k) = sum of (1 - P(all below k)).
3. Uniform: n points cut [0, 1] into n + 1 equal expected gaps, so the k-th smallest averages k/(n + 1).
4. Anchors: max of 2 dice = 4.47, max of 3 dice = 4.96.
5. Say the setup out loud before calculating. Interviewers care about the method as much as the number.

Optimal stopping

1. Cue: "may roll again", "stop or continue".
2. Method: work backwards from the last roll. Keep a roll only if it beats the expected value of continuing.
3. Anchors: 1 roll 3.5, 2 rolls 4.25, 3 rolls 4.67, 4 rolls 4.94.
4. Say the setup out loud before calculating. Interviewers care about the method as much as the number.

Ruin

1. Cue: "stop at $0 or $N", unfair bets.
2. Method: r = q/p and P(reach N from i) = (1 - r^i)/(1 - r^N).
3. Fair game (p = 1/2): P = i/N.
4. Check: a small edge compounds. At p = 0.6 you usually win.
5. Say the setup out loud before calculating. Interviewers care about the method as much as the number.

Kelly

1. Cue: "fraction of bankroll", "maximise long-run growth".
2. Method: f = p - q/b. For even money (b = 1) that is just p - q, the edge.
3. Check: if f is negative, do not bet.
4. Say the setup out loud before calculating. Interviewers care about the method as much as the number.

Linearity

1. Cue: "expected number of ..." or a payoff that is a sum or product.
2. Method: write the count as a sum of indicators and add their probabilities. Dependence does not matter.
3. Independent factors: E[XY] = E[X]E[Y].
4. Anchors: E[die] = 3.5, E[die^2] = 91/6 = 15.17.
5. Say the setup out loud before calculating. Interviewers care about the method as much as the number.

Waiting

1. Cue: "until you see", "how many tries".
2. Method: a geometric wait with success probability p takes 1/p tries on average. Chain several waits by adding them.
3. Anchor: all 6 faces takes 6(1 + 1/2 + ... + 1/6) = 14.7 rolls.
4. Say the setup out loud before calculating. Interviewers care about the method as much as the number.

Variance

1. Cue: "variance", "standard deviation" of a sum.
2. Method: variances of independent pieces add. One die has variance 35/12 = 2.92.
3. The standard deviation is the square root, and it grows with the square root of n.
4. Say the setup out loud before calculating. Interviewers care about the method as much as the number.

Symmetry

1. Cue: the question looks hard but every position or ball is interchangeable.
2. Method: k special cards cut the rest into k + 1 equal expected groups. Any position in a shuffled order is like the first.
3. Anchor: cards up to and including the first ace = 53/5 = 10.6.
4. Say the setup out loud before calculating. Interviewers care about the method as much as the number.

Derangement

1. Cue: "nobody gets their own".
2. Method: D(n) = (n - 1)(D(n - 1) + D(n - 2)): 1, 2, 9, 44, 265 for n = 2 to 6.
3. Shortcut: for n >= 4 the probability is 0.375 or 0.367 or 0.368, all close to 1/e.
4. Say the setup out loud before calculating. Interviewers care about the method as much as the number.

Geometric

1. Cue: random points on a circle or stick.
2. Method: pick a special point (the first one clockwise), and the events become disjoint, so you can add them.
3. Anchors: 3 points in a semicircle = 3/4. A stick broken at 2 random points forms a triangle with probability 1/4.
4. Say the setup out loud before calculating. Interviewers care about the method as much as the number.

Worked examples

• An urn has 2 red and 8 blue balls. You draw them all one at a time without replacement. What is the probability ball number 10 is red? Answer as a decimal (3 places).

  Answer: 0.2

  1. By symmetry every position is equally likely to hold any given ball. The order you look at them does not matter.
  2. So P = 2/10 = 0.200, the same as the first ball.

• An urn has 3 red and 6 blue balls. You draw them all one at a time without replacement. What is the probability ball number 4 is red? Answer as a decimal (3 places).

  Answer: 0.3333333333333333

  1. By symmetry every position is equally likely to hold any given ball. The order you look at them does not matter.
  2. So P = 3/9 = 0.333, the same as the first ball.

• You roll 2 fair dice and are paid the highest number showing. What is the fair price of this game? Answer to 2 decimals.

  Answer: 4.472222222222222

  1. E[max] = sum over k of P(max >= k), and P(max >= k) = 1 - ((k - 1)/6)^2.
  2. Terms for k = 1 to 6: 1.000, 0.972, 0.889, 0.750, 0.556, 0.306.
  3. Sum = 4.47.

Firms that test this

SIG · IMC · Citadel Securities · DRW · Five Rings · Jane Street

All guides