Offensive Security Researcher & Quantum Cryptography Analyst

Indicator Random Variables in Probabilistic Analysis: Complete Guide

Abdul Wahab Junaid
Indicator Random Variables in Probabilistic Analysis

I consider indicator random variables to be one of the most powerful “small ideas” I’ve come across in algorithm analysis — the technique itself is almost embarrassingly simple (a variable that’s either 0 or 1), yet it lets me compute expected values for wildly complicated quantities without ever needing to work out a full probability distribution. I used this exact technique in my articles on Randomized Algorithms and QuickSort to derive the $O(n \log n)$ expected running time, and in this article I want to isolate the technique itself and explain it thoroughly using its classic teaching example: the hiring problem.

History and Background

The technique of using indicator variables combined with linearity of expectation is a foundational tool in probability theory generally, with roots going back to the early development of probability as a mathematical discipline. Its specific popularization within algorithm analysis is closely tied to the “hiring problem” formulation, which I use as my central example in this article, and which is presented prominently in Cormen, Leiserson, Rivest, and Stein’s Introduction to Algorithms (CLRS) as an accessible entry point into probabilistic algorithm analysis.

I find this technique’s history less about a single inventor and more about a gradual recognition, across statistics and computer science, that linearity of expectation — the fact that $E[X+Y] = E[X] + E[Y]$ regardless of whether $X$ and $Y$ are independent — makes indicator variables an unusually convenient tool. This property lets me break a complicated random variable into a sum of simple 0/1 variables, compute each one’s expectation trivially, and add them up, sidestepping what would otherwise require complex joint probability calculations.

Problem Statement

The general problem I’m addressing is this: I often need to compute the expected value of some complicated random variable $X$ that counts how many times a certain event occurs across a random process — for example, the number of times I hire a new candidate while interviewing a sequence of applicants in random order, or the number of comparisons a randomized algorithm performs.

Directly computing $E[X]$ by enumerating every possible outcome and its probability is often intractable. Indicator random variables give me a systematic way to compute $E[X]$ by decomposing it into simpler pieces.

Core Concepts

How It Works

Here’s the general method I follow whenever I want to compute an expected value using this technique:

  1. Identify the random variable $X$ I want to analyze, and express it as a count of how many times some event occurs (e.g., “number of hires,” “number of comparisons”).
  2. Define an indicator random variable $X_i$ for each individual instance where the event could occur (e.g., one indicator per candidate, or one per pair of elements).
  3. Express $X$ as the sum of these indicator variables: $X = \sum_i X_i$.
  4. Compute $E[X_i] = P(\text{the event occurs for instance } i)$ for each indicator — this individual probability is often much easier to compute than reasoning about the whole process at once.
  5. Apply linearity of expectation to conclude $E[X] = \sum_i E[X_i] = \sum_i P(\text{event}_i)$, even if the individual events are not independent of each other.

Working Principle

What makes this technique so powerful, in my view, is that linearity of expectation holds regardless of dependence between the variables being summed. In the hiring problem, whether I hire the 5th candidate is not independent of whether I hired the 3rd candidate (since hiring decisions depend on all previous candidates seen). Despite this dependence, I can still add up the individual expectations directly — I never need to worry about conditional probabilities or joint distributions between the indicator variables, which is what would be required if I tried to compute $E[X]$ through a more direct combinatorial approach.

This is the mathematical trick that let me, in my QuickSort and Randomized Algorithms articles, sidestep an otherwise very complex joint analysis of how every pair of elements interacts during partitioning, and instead just compute a simple pairwise probability for each pair independently, then sum them all up.

Mathematical Foundation

Let me formalize the hiring problem, since it’s the cleanest illustration of this technique.

I interview $n$ candidates, presented to me in a uniformly random order (equivalent to assuming their relative rank order is a random permutation of $1$ to $n$). I hire a candidate whenever they are better than every candidate I’ve interviewed so far (including the very first, who is always hired, since there’s no prior candidate to compare against).

Let $X$ be the total number of candidates hired. I define an indicator variable for each candidate $i$ (where $i$ ranges from 1 to $n$, representing their position in the interview order):

$$ X_i = \begin{cases} 1 & \text{if candidate } i \text{ is hired} \ 0 & \text{otherwise} \end{cases} $$

so that:

$$ X = \sum_{i=1}^{n} X_i $$

The key insight is that candidate $i$ is hired if and only if they are the best among the first $i$ candidates interviewed (positions 1 through $i$). Since the order is uniformly random, candidate $i$ is equally likely to be the best, second-best, …, or worst among these first $i$ candidates — meaning the probability that candidate $i$ specifically is the best among them is exactly:

$$ P(X_i = 1) = \frac{1}{i} $$

By linearity of expectation:

$$ E[X] = \sum_{i=1}^{n} E[X_i] = \sum_{i=1}^{n} \frac{1}{i} = H_n $$

where $H_n$ is the $n$-th harmonic number. Using the well-known approximation:

$$ H_n \approx \ln n + \gamma $$

(where $\gamma \approx 0.5772$ is the Euler-Mascheroni constant), I get the clean asymptotic result:

$$ E[X] = \Theta(\ln n) $$

This tells me something genuinely surprising: even though I might interview 1,000 candidates, I expect to hire only around $\ln(1000) \approx 6.9$ of them — a strikingly small number relative to $n$, and one that would be difficult to derive without this decomposition technique.

Diagrams

Here’s the general workflow of applying indicator random variables:

flowchart TD
    A["Complicated random variable X (a count)"] --> B["Decompose into indicator variables X_i"]
    B --> C["Express X as sum of X_i"]
    C --> D["Compute E(X_i) = P(event_i) for each i"]
    D --> E["Apply linearity of expectation"]
    E --> F["E(X) = sum of E(X_i), regardless of dependence"]

And here’s a diagram specific to the hiring problem’s logic:

flowchart LR
    A["Candidate i interviewed"] --> B{"Is candidate i best among first i candidates?"}
    B -- Yes, probability 1/i --> C["X_i = 1: candidate i is hired"]
    B -- No, probability (i-1)/i --> D["X_i = 0: candidate i is not hired"]
    C --> E["Sum all X_i to get total hires X"]
    D --> E
    E --> F["E(X) = H_n (harmonic number)"]

Pseudocode

Since this article centers on a probabilistic analysis technique, I present the pseudocode for simulating the hiring problem itself, which I use to empirically verify the theoretical result:

SIMULATE-HIRING(candidates, n)
    hireCount = 0
    best = -infinity

    for i = 1 to n
        if candidates[i] > best
            best = candidates[i]
            hireCount = hireCount + 1

    return hireCount

EXPECTED-HIRES-EMPIRICAL(n, trials)
    totalHires = 0
    for t = 1 to trials
        shuffle candidates array of size n uniformly at random
        totalHires = totalHires + SIMULATE-HIRING(candidates, n)

    return totalHires / trials

Step-by-Step Example

Let me work through the theoretical expectation for $n = 10$ candidates by hand, then compare it against an empirical simulation.

Theoretical calculation:

$$ E[X] = H_{10} = \sum_{i=1}^{10} \frac{1}{i} = 1 + \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{10} $$

Computing this sum directly:

$$ H_{10} \approx 2.9290 $$

Empirical verification: I ran my tested C simulation, shuffling 10 distinctly-ranked candidates uniformly at random across 100,000 independent trials, and averaging the number of hires observed in each trial. This produced an empirical average of approximately 2.9263 hires — remarkably close to the theoretical value of 2.9290, with the small difference attributable to the expected statistical noise from a finite number of trials.

This close agreement between the hand-derived formula and the simulation gives me strong confidence that the indicator random variable technique, despite its abstract derivation, correctly predicts real, measurable behavior.

Time Complexity

Since this article’s central focus is a mathematical analysis technique rather than a standalone algorithm, I frame the complexity in terms of my verification simulation:

Space Complexity

Correctness Analysis

The correctness of the indicator random variable technique rests on two well-established facts from probability theory, both of which I can state and justify directly.

Fact 1 — $E[X_A] = P(A)$: By definition, an indicator variable $X_A$ takes value 1 with probability $P(A)$ and value 0 with probability $1 – P(A)$. Its expectation is therefore:

$$ E[X_A] = 1 \cdot P(A) + 0 \cdot (1 – P(A)) = P(A) $$

This is a direct, immediate consequence of the definition of expectation for a discrete random variable.

Fact 2 — Linearity of expectation: For any random variables $X_1, \dots, X_n$ (defined on the same probability space, regardless of any dependence between them):

$$ E\left[\sum_{i=1}^{n} X_i\right] = \sum_{i=1}^{n} E[X_i] $$

This is a foundational theorem of probability theory, provable directly from the definition of expectation as a sum (or integral) weighted by probability, and it holds unconditionally — independence is never required.

Combining these two facts: if I express a complicated random variable $X$ as a sum of indicator variables $X = \sum_i X_i$, then:

$$ E[X] = E\left[\sum_i X_i\right] = \sum_i E[X_i] = \sum_i P(A_i) $$

This chain of equalities is exactly valid, with no approximation involved — the only “work” I need to do is correctly identify the indicator variables and compute each $P(A_i)$, both of which are usually far more tractable than analyzing $X$ directly.

Advantages

Disadvantages

Applications

Implementation in C

Since this article centers on a mathematical technique, I present my verification simulation, which empirically confirms the theoretical harmonic number result for the hiring problem:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

// Simulates the hiring problem: interview n candidates in random order,
// hire whenever a candidate is better than all previous ones.
// Returns the number of times a hire occurred.
int simulateHiring(int n, int *candidates) {
    int hireCount = 0;
    int best = -1;

    for (int i = 0; i < n; i++) {
        if (candidates[i] > best) {
            best = candidates[i];
            hireCount++;
        }
    }
    return hireCount;
}

// Fisher-Yates shuffle to randomize candidate order uniformly
void shuffle(int *arr, int n) {
    for (int i = n - 1; i > 0; i--) {
        int j = rand() % (i + 1);
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

int main() {
    srand(7);
    int n = 10;
    int trials = 100000;
    long totalHires = 0;

    int candidates[10];
    for (int i = 0; i < n; i++)
        candidates[i] = i + 1; // ranks 1..10, distinct

    for (int t = 0; t < trials; t++) {
        shuffle(candidates, n);
        totalHires += simulateHiring(n, candidates);
    }

    double empirical = (double)totalHires / trials;

    // Theoretical expected value: H_n = sum(1/i) for i=1..n
    double harmonic = 0.0;
    for (int i = 1; i <= n; i++)
        harmonic += 1.0 / i;

    printf("n = %d, trials = %d\n", n, trials);
    printf("Empirical average number of hires: %.4f\n", empirical);
    printf("Theoretical H_n (expected hires):   %.4f\n", harmonic);

    return 0;
}

Sample Input and Output

Input: $n = 10$ candidates with distinct ranks 1 through 10, simulated across 100,000 independent random trials.

Output (verified by compiling and running the code above):

n = 10, trials = 100000
Empirical average number of hires: 2.9263
Theoretical H_n (expected hires):   2.9290

The close match between the empirical simulation (2.9263) and the theoretical harmonic number (2.9290) confirms the correctness of the indicator random variable derivation.

Optimization Techniques

Since this article centers on an analysis technique rather than a performance-critical algorithm, I frame optimization here in terms of applying the technique effectively:

Common Mistakes

Further Reading

Exit mobile version