Probabilistic Analysis and Randomized Algorithms: The Hiring Problem Explained

Why Randomness Enters Algorithm Analysis

The worst-case, best-case, and average-case running times discussed earlier in this series all assume the algorithm itself behaves deterministically, and any variation comes purely from the input. A different situation arises when either the input distribution is unknown or an algorithm deliberately makes random choices during its own execution. Both situations require the tools of Probabilistic Analysis.

The Hiring Problem: A Motivating Example

Consider a company interviewing candidates one at a time for a position, always hiring the current best candidate seen so far and firing the previous hire. Each interview costs a small amount, but each hire costs significantly more, since it involves paperwork, onboarding, and severance for the person being replaced. The question is: what is the expected total hiring cost across the entire process?

HIRE-ASSISTANT(n):
  best = candidate 0 (a placeholder, ranked worst)
  for i = 1 to n:
      interview candidate i
      if candidate i is better than best:
          best = candidate i
          hire candidate i

If candidates arrive in the worst possible order — already sorted from worst to best — every single candidate is hired, resulting in n hires, a costly worst case. But if the order of candidates is random, far fewer hires are expected on average, since a random arrival order makes it unlikely that many consecutive candidates each set a new record.

Two Approaches to Handling the Order of Inputs

There are two distinct ways to reason about this randomness, and it is important not to confuse them.

• Probabilistic Analysis of a Deterministic Algorithm: assume the input itself comes from some probability distribution (such as a uniformly random ordering of candidates), and analyze the expected running time of a fixed, non-random algorithm over that input distribution.
• Randomized Algorithms: the algorithm itself makes random choices during execution (such as randomly shuffling the candidate order before processing them, regardless of the order they actually arrived in), guaranteeing good expected performance for any input, since the randomness comes from the algorithm rather than an assumption about the input.

The second approach is generally more powerful and reliable in practice, since it removes any dependence on assumptions about how inputs are distributed in the real world, which may not hold. A Randomized Algorithm for the hiring problem simply permutes the candidates randomly before running the same procedure, guaranteeing the same good expected cost regardless of the input's original order.

Indicator Random Variables: A Powerful Analytical Tool

Computing an expected value directly can be complicated when many interacting events are involved. Indicator Random Variables provide an elegant technique that dramatically simplifies such calculations, especially when combined with the linearity of expectation.

For an event A, define the indicator random variable:

I{A} = 1  if A occurs
I{A} = 0  if A does not occur

Key property: E[I{A}] = Pr{A}

The expected value of an indicator variable simply equals the probability of the event it indicates. This becomes powerful when combined with Linearity of Expectation, which states that the expected value of a sum of random variables equals the sum of their expected values, regardless of whether the variables are independent.

E[X1 + X2 + ... + Xn] = E[X1] + E[X2] + ... + E[Xn]

This holds even when the Xi are NOT independent —
a crucial and often surprising fact

Applying Indicator Variables to the Hiring Problem

Let Xi be the indicator random variable for the event that candidate i is hired. The total number of hires is X = X1 + X2 + ... + Xn. By linearity of expectation:

E[X] = E[X1] + E[X2] + ... + E[Xn]
     = Σ Pr{candidate i is hired}

Candidate i is hired precisely when candidate i is the best among the first i candidates seen so far. If the candidates arrive in a uniformly random order, candidate i is equally likely to be the best, second-best, or any rank among the first i candidates, so:

Pr{candidate i is hired} = 1/i

Therefore:
E[X] = Σ (i=1 to n) 1/i = H(n)

This is the Harmonic Series, and H(n) = Θ(ln n)

This remarkable result shows that, despite there being n candidates, the expected number of hires grows only logarithmically with n, a dramatic improvement over the worst-case scenario of n hires. This calculation, made simple through indicator variables, would be considerably more complex using direct probability calculations involving joint distributions.

Why This Technique Generalizes So Widely

The indicator random variable technique is not specific to the hiring problem; it is a general tool applicable whenever a quantity of interest can be expressed as a sum of simpler zero-or-one outcomes, even when those outcomes are correlated with each other. This makes it one of the most broadly useful techniques in the probabilistic analysis of algorithms, and it reappears throughout later topics in this series wherever expected running time needs to be computed.

Why Randomization Matters for Real-World Algorithm Design

Randomized algorithms are used throughout computer science specifically because they can guarantee good expected performance without needing any assumption about the distribution of real-world inputs, protecting against adversarial or unusually structured inputs that could otherwise trigger an algorithm's worst case. A prominent example, explored in depth later in this series, is randomized quicksort, where randomly shuffling the input before sorting protects against the specific input orderings that would otherwise trigger quicksort's quadratic worst case.