Articles

Quant Interview Probability Bounds: Markov, Chebyshev, and Chernoff

Practice quant probability bounds with Markov, Chebyshev, and Chernoff examples, exact binomial tails, dependence checks, and sample-size reasoning.

A quant interviewer gives you an expected count and asks how likely it is to exceed a threshold. A common mistake is treating a bound as an exact probability, or using independence that was never supplied. Markov, Chebyshev, and Chernoff use different information and make different promises.

A useful answer starts with the event and assumptions, then chooses a justified tool. A numerically smaller bound is useful only when its conditions actually hold.

Evidence boundary: Linked MIT course notes establish the probability inequalities and exponential-moment argument. The count example, dependence counterexample, and comparison ledgers are original exercises and mathematical inference. No candidate reports, employer-specific interview frequency claims, or financial recommendations are made. Start with Quant Probability Brainteasers: Pizza Bounds, Coin Scores, Ant on a Cube, Shoelace Loops, and Paint Mixing and state the available information before calculating.

What must be specified before choosing a bound?

Original decision contract: Write the random variable, threshold, tail direction, and information available. Is the variable nonnegative? Is its variance finite? Is an exponential moment finite? If it is a sum, what dependence assumptions are known?

A probability upper bound must be at least as large as the true probability. It can be loose and still correct. A bound greater than one can be clipped at one, but that does not make the method informative for the requested threshold.

Do not silently replace P(X >= a) with P(X > a). For a discrete count, the mass at the threshold can matter. State which event your formula bounds, especially when comparing an exact calculation with an inequality.

If the full distribution is known and the support is small enough, an exact tail calculation may be preferable. Bounds become especially useful when limited information, a large state space, or a symbolic guarantee makes direct calculation inconvenient.

What does Markov need, and why is nonnegativity essential?

Mathematical fact: For nonnegative X with finite expectation and a positive threshold a,

P(X >= a) <= E[X] / a

On the event X is at least a, X contributes at least a to its expectation. Nonnegative contributions elsewhere cannot cancel that amount. This explains the inequality's central assumption. See MIT's expectation and moment lecture.

Original counterexample: Let X equal 100 with probability one half and negative 100 with probability one half. Its mean is zero, but its chance of exceeding 50 is one half. Applying the displayed formula directly to this signed variable would falsely give an upper bound of zero.

You can sometimes apply Markov to a nonnegative transformation instead. For example, absolute values, squares, or exponentials change both the variable and the event. Name that transformation; you cannot keep the same expectation after changing X.

Original tightness exercise: Let X equal a with probability p and zero otherwise. Its expectation is pa, and the probability of X being at least a is p. Markov gives exactly p. Therefore, with only nonnegativity and the mean, a universal improvement cannot simply be assumed.

Tightness for this constructed distribution does not imply accuracy for every application. It shows why limited information permits some distributions that attain the inequality.

How does Chebyshev use variance?

Mathematical fact: For finite mean mu, finite variance sigma squared, and positive t,

P(abs(X - mu) >= t) <= sigma^2 / t^2

Apply Markov to the nonnegative variable (X - mu)^2. This proof makes clear that Chebyshev is a statement about the variance of X itself; it does not require X to be a sum of independent observations. See the MIT moment lecture.

Original one-sided use: The event X >= mu + t is contained in the two-sided deviation event. Therefore the same right-hand side is a valid upper bound for that upper tail. It can be conservative because it also covers deviations in the other direction.

If X is a sum, calculating its variance requires care:

Var(sum_i X_i)
  = sum_i Var(X_i) + 2 * sum_(i<j) Cov(X_i, X_j)

Independence makes the covariance terms vanish when the moments exist. Some dependent variables can also have zero covariance, but dependence alone does not authorize dropping the terms. Distinguish the inequality's assumptions from assumptions used to obtain its inputs.

If the variance is infinite, writing an estimated sample variance into Chebyshev does not supply the missing population condition. An empirical statistic and a known population moment are different kinds of evidence.

Where does the Chernoff argument come from?

Mathematical fact: For positive theta and a finite relevant exponential moment, apply Markov to exp(theta * X):

P(X >= a) <= exp(-theta * a) * E[exp(theta * X)]

You can minimize this expression over justified positive theta values. The general argument concerns the moment-generating function of X. Independence enters when you factor the exponential moment of a sum into a product, not merely because the word Chernoff appears. See MIT's Chernoff lecture notes.

For independent Bernoulli variables with sum S and mean mu, a common multiplicative upper-tail form is:

P(S >= (1 + delta) * mu)
  <= [exp(delta) / (1 + delta)^(1 + delta)]^mu

Here delta is positive and the independent Bernoulli assumptions are explicit. Other published forms have different constants or parameter restrictions. Do not move a convenient formula to a new setting without checking its stated conditions. See MIT's Chernoff applications notes.

A heavy-tailed variable can have finite mean and variance while lacking a finite positive exponential moment. In that situation, this upper-tail moment method may be unavailable even though a variance bound remains meaningful.

Can you compare all three on one event?

Original exercise: S counts successes across 100 independent Bernoulli trials, each with success probability 0.1. We want P(S >= 20). The mean is ten and the variance is nine.

Method	Calculation	Upper bound or exact tail
Markov	10 / 20	0.5 upper bound
Chebyshev, using containment	9 / (20 - 10)²	0.09 upper bound
Multiplicative Chernoff	(e / 4)^10	About 0.02099 upper bound
Exact binomial sum	Sum of masses for k from 20 through 100	About 0.001979 exact probability

The exact binomial tail is smaller than each displayed bound. The comparison illustrates how more structure can provide a tighter guarantee for this example. It is not a universal ranking of every possible bound at every threshold.

For the Chernoff expression, delta equals one because the threshold is twice the mean. A simplified variant restricted to delta below one cannot be quoted at this boundary without checking whether its statement includes equality. Using the fuller expression avoids that particular ambiguity.

The exact sum uses the complete binomial distribution, not just mean and variance. It therefore answers a different information problem. If the interviewer gives only the mean, you cannot quietly assume the binomial model to obtain its much smaller tail.

What changes when the trials are dependent?

Original counterexample: Let all 100 trials share the same Bernoulli outcome B with success probability 0.1. Every individual trial still has marginal success probability 0.1, but now S equals 100B. It is 100 with probability 0.1 and zero otherwise.

The mean remains ten. However, P(S >= 20) is now 0.1, rather than the independent binomial tail. Its variance is 900, not nine. Both the covariance terms and the exponential-moment factorization changed.

Markov still gives 0.5 because it only uses the nonnegative count and its mean. Chebyshev with the correct variance gives nine, which clips to one and supplies no useful constraint. Substituting nine for the variance would give 0.09, incorrectly below the actual probability.

The independent-Bernoulli Chernoff bound of approximately 0.02099 is also below the true dependent tail and therefore cannot be used here. This example exposes the failed assumption with a concrete violation.

It does not establish that every kind of dependence defeats every concentration result. Particular dependence structures can admit other inequalities. Name and justify such a structure rather than declaring all dependent data unusable or all exchangeable data independent.

How should you check an interview calculation?

Original verification ledger: First check units. A threshold and mean must describe the same variable. Variance has squared units, so its denominator needs a squared deviation. An exponent must be dimensionless under the chosen parameter convention.

Next check the threshold. A deviation from the mean is different from the raw event level. For the count exercise, Chebyshev uses ten as the deviation and Markov uses twenty as the threshold for S.

Then check the limiting behavior. For a fixed mean, Markov's upper bound falls as the positive threshold increases. For a fixed variance, the Chebyshev expression falls quadratically in the deviation. A formula that grows with an increasingly extreme upper threshold probably has a sign or substitution error.

Finally, check that the result is a probability bound, not a probability estimate. Writing “the probability is 0.09” would overstate what Chebyshev established. Say “the probability is at most 0.09 under the stated moment information.”

The article's checks compute the exact binomial sum, compare all three inequalities, and verify the shared-outcome counterexample. They are arithmetic checks of these fixtures, not an empirical claim about trading returns or a simulation-based estimate.

What if the interviewer asks for a sample size?

Original reasoning: Translate the requested accuracy into an event for a sample mean. If observations are independent with a common finite variance sigma squared, the sample mean's variance is sigma squared divided by n. Chebyshev then gives a bound of sigma^2 / (n * epsilon^2) for an absolute error of at least epsilon.

To make that expression at most an error probability q, choose n at least sigma^2 / (q * epsilon^2), rounded up to an integer. The guarantee relies on the stated variance and sampling assumptions; estimating variance from the same finite dataset introduces another uncertainty question.

For bounded independent observations, an appropriate exponential concentration result may produce a smaller sufficient n. State the exact inequality used and its assumptions. Sample size derived from a sufficient bound need not be the smallest sample size achieving the actual tail target.

If observations arrive in correlated batches, dividing variance by n without accounting for dependence can dramatically overstate precision. The shared-outcome example has 100 records but only one random outcome. Counting rows cannot replace an independence argument.

Five questions to extend the probability reasoning

These verified questions provide probability and quantitative practice. They are not presented as candidate reports establishing that an employer asks these exact inequalities.

Question	Bound follow-up
Quant Probability Brainteasers: Pizza Bounds, Coin Scores, Ant on a Cube, Shoelace Loops, and Paint Mixing	Name the random variable and available information.
Bounds on the Probability of Rain on at Least One Weekend Day	Separate a bound from an exact joint probability.
Approximate a Rare-Event Binomial Probability	Compare distribution-based tails with inequalities.
Answer four core statistics questions	State the moment and dependence assumptions.
Solve a Set of Probability and Quantitative Reasoning Problems	Check event direction and threshold substitution.

Continue with Approximate a Rare-Event Binomial Probability. Compare an exact tail with a justified bound, then identify which information made the exact calculation possible.