Articles
Linearity of Expectation Interview Questions: Indicator Variables and Dependent Events
Practice linearity of expectation with original indicator problems, dependent events, enumeration checks, and variance traps in worked examples.
When an interview asks for the expected number of matches, collisions, empty bins, or record events, start by naming one event per possible opportunity. Set its indicator to 1 when it occurs and 0 otherwise; then add the probabilities of those events. The events may overlap or depend on each other. Linearity of expectation still gives the mean. Independence enters only when you calculate a joint event probability, a product, or often a variance.
This guide uses original small exercises to make that boundary visible. Official academic facts come from the linked MIT, Berkeley, and CMU course materials. Editorial inference consists of the interview prompts, finite checks, and answer framing; these are not candidate-reported employer questions.
The one-line tool—and its hidden bookkeeping
Let I_i equal 1 if event A_i happens and 0 otherwise. If X counts how many of these events happen, then for every outcome X = I_1 + ... + I_m. Taking expectations gives E[X] = Σ E[I_i] = Σ P(A_i). The first equality is an identity of random variables, not a claim that only one event can occur. MIT’s linearity notes and Berkeley’s probability notes explicitly state that independence is unnecessary.
The hard part is usually defining what one counted object is. For adjacent pairs in a sequence, an opportunity is an index pair, not a sequence containing at least one pair. For fixed points in a permutation, an opportunity is a position. For empty bins, an opportunity is a bin. Those choices make the indicator sum exact. If the question instead asks for the probability of at least one match, summing event probabilities generally overcounts outcomes with several matches. That is a different random variable: the single indicator of the union event.
A useful answer has four parts: define one indicator, prove the sum equals the requested count for each possible outcome, calculate its probability under the specified experiment, and add. State symmetry only when the opportunities really have identical probability. This structure lets an interviewer change one assumption without making you start from an unwieldy distribution of the total.
Exercise one: adjacent heads are dependent
Flip three independent fair coins in order. Let X be the number of adjacent HH pairs. There are two opportunities: positions 1–2 and positions 2–3. Define I_1 and I_2 for those windows. Each has probability 1/4, so E[X] = 1/4 + 1/4 = 1/2.
The indicators are not independent. Both equal 1 when the sequence is HHH, whose probability is 1/8, not P(I_1=1)P(I_2=1)=1/16. Their covariance is 1/8 - 1/16 = 1/16. Linearity survived this overlap because it did not multiply indicator probabilities. The underlying coin flips were independent; the window events were dependent because they share a flip. Saying simply “the flips are independent, therefore the pairs are independent” is the interview trap.
| Three-flip outcome | Adjacent HH count |
|---|---|
HHH | 2 |
HHT, THH | 1 each |
HTH, HTT, THT, TTH, TTT | 0 each |
The eight equally likely outcomes give total count 2 + 1 + 1 = 4 across eight cases, so the finite-enumeration mean is again 1/2. This check catches an indexing error: four flips have three adjacent windows, not four. For n independent fair flips, the same argument gives (n-1)/4 for n≥1. If flips are biased with head probability p and remain independent, the mean is (n-1)p²; if consecutive flips themselves depend, calculate each P(H_i and H_{i+1}) from that model instead of inserting p².
Why the variance needs more work
For the same three-flip exercise, Var(I_i) = (1/4)(3/4) = 3/16. Variance of the sum is Var(I_1)+Var(I_2)+2Cov(I_1,I_2), which is 3/16 + 3/16 + 2/16 = 1/2. Dropping the covariance would give 3/8, the wrong answer. Direct enumeration checks this: E[X²] = (4+1+1)/8 = 3/4; subtract (E[X])² = 1/4 to get 1/2.
This is the precise boundary the interviewer is testing. E[I_1+I_2] always splits. E[I_1 I_2] represents a joint probability and cannot generally be replaced by E[I_1]E[I_2]. A variance calculation expands a square, creating cross terms. Independence is one condition that makes many covariances zero, but uncorrelated variables can also have zero covariance without being independent. Name the property you need at the line where you use it.
For a longer flip sequence, nonoverlapping two-position windows are independent under independent flips, but neighboring windows overlap. You can count neighboring covariance pairs to derive variance, yet do not reach for that machinery if the question only requests a mean. Good interview efficiency means applying the weakest needed assumption, not displaying every formula you know.
Exercise two: fixed points in a random permutation
Choose a uniformly random permutation of n distinct labels. A fixed point is a position whose label stays in that position. Let I_i=1 when position i is fixed. Exactly (n-1)! of the n! permutations fix position i, so P(I_i=1)=1/n and E[X]=n(1/n)=1 for n≥1. MIT’s course uses this classic example to show why finding the whole fixed-point distribution is unnecessary for the mean.
The indicators are again dependent. Once one position is fixed, the remaining permutation is constrained. For n≥2, P(I_i=1 and I_j=1)=1/[n(n-1)] for distinct i,j, whereas the product of marginal probabilities is 1/n². The count of fixed points can be 0, 1, or more; expectation 1 does not say every permutation has one fixed point or that the probability of at least one is 1.
Use n=3 as a sanity check. The identity permutation has three fixed points; three transpositions have one each; two 3-cycles have none. Total fixed points across six equally likely permutations are 3+3=6, so the mean is one. A candidate who claims every nonidentity permutation has zero fixed points will fail this tiny case. The result E[X]=1 is invariant in n, but the detailed distribution changes with n.
If the interviewer asks for P(X=0), linearity alone has finished its job. You now need inclusion–exclusion or derangement counting. Separate that follow-up from the original expected-count question, and do not reverse-engineer the probability from the mean. Two distributions can share the same mean and have very different probabilities of zero.
Exercise three: empty bins after random assignments
Assign three distinguishable balls independently and uniformly to four labeled bins. Let J_b=1 if bin b is empty. For one specified bin, each ball avoids it with probability 3/4, so P(J_b=1)=(3/4)^3=27/64. There are four bins, hence E[empty bins]=4(27/64)=27/16, or 1.6875. The number of occupied bins is 4 - empty bins, so its expectation is 4-27/16=37/16.
Here independence is needed inside each single-bin probability: multiplying three avoidance probabilities assumes independent ball assignments. It is not needed between the four empty-bin indicators when they are summed. In fact, an empty first bin affects the chance that another bin is empty. This two-level distinction—independence within an event, dependence between counted events—is more revealing than saying “linearity works without independence” and stopping there.
If assignments are without replacement from a fixed collection of slots, or if each ball has a different bin distribution, the single-bin probability changes. For independent but nonidentical assignments, it becomes a product of each ball’s avoidance probability for that bin; then sum over bins. For a correlated assignment rule, compute P(bin b empty) from that joint design. The outer sum remains valid whenever the indicators represent the count.
A quick bound is 1≤occupied bins≤3 here, because three balls occupy at least one and at most three bins. 37/16≈2.3125 fits. The empty-bin mean must be between one and three; 27/16≈1.6875 fits too. Bounds do not prove the exact result, but they catch arithmetic such as forgetting the factor of four.
Exercise four: triangles in a random graph
Take five labeled vertices and independently include each possible edge with probability 1/2. Let T_S be the indicator that a particular three-vertex set S forms a triangle. There are C(5,3)=10 possible vertex triples. Each specified triangle requires three independently selected edges, so P(T_S=1)=(1/2)^3=1/8. Therefore the expected number of triangles is 10/8=5/4.
Distinct triangle indicators need not be independent: triangles sharing an edge both require that same edge. The calculation of 1/8 used the model’s edge independence; adding ten triangle probabilities did not use triangle independence. If edges were generated with correlations, perhaps by sampling a fixed number of edges, 1/8 would need revision even though the sum-of-indicators method would still be correct.
This illustrates a general diagnostic: identify the random primitive operations, then identify the derived events being counted. Independence of primitives may justify a product inside P(A_i). It rarely transfers automatically to overlapping derived events. A strong answer says exactly where multiplication occurs.
Fast interview answers and checks
What is an indicator variable? A 0–1 random variable for a named event. Its expected value equals that event’s probability.
Does linearity require independent events? No. A finite sum of integrable random variables has an expectation equal to the sum of their expectations, regardless of dependence.
Can I sum probabilities to find P(any event)? Not generally. That sum is the expected number of events. It exceeds the union probability when outcomes can contain multiple events.
Where might independence still matter? Inside a probability such as three separate edges forming a triangle, or when factorizing joint expectations and simplifying variance.
How do I check an answer? Enumerate a tiny case, test a lower and upper bound, and confirm that the indicator sum equals the requested count on every outcome—not merely on average.
What if events have different probabilities? Sum the individual probabilities; do not multiply one representative probability by m unless symmetry justifies it.