Wald’s equation

Wald’s equation, a form of linearity of expectation for sums with randomly many terms.

Consider a sum of random variables, where the number of terms is itself a random variable. If each term has expectation at most (or at least) , then the expectation of the sum is at most (or at least) (the bound on the expectation of each term, times the expected number of terms). This holds provided the random variables in the sum are bounded above or below and is a stopping time with finite expectation.

Wald’s equation for dependent increments

A variant of Wald’s equation to use when the expected increment depends on the sum so far.

Wald’s equation applies to any sequence that, with each step, increases (or decreases) in expectation by a constant additive amount. What about sequences where the expected change with each step depends on the current value? For example, suppose Alice starts with coins. In each round , she flips each remaining coin and discards those that come up tails. She stops once all coins are discarded. What is the expected number of rounds?

Markov bound for super-martingales

For any non-negative super-martingale, the probability that it ever exceeds its initial value by a factor of is at most .

Alice goes to the casino with $1. At the casino, she plays the following game repeatedly: she bets half her current balance on a fair coin flip. (For example, on the first flip, she bets 50 cents, so she wins 50 cents with probability 1/2 and loses 50 cents with probability 1/2.) Will Alice’s winnings ever reach$10 or more? The bound here says this happens with probability at most 1/10.

“Stopping-time” Chernoff bounds

Extending the Chernoff bound to handle sums with randomly many terms.

Alice goes to the casino and plays bets on a sequence of fair coin flips. On the th bet, Alice chooses an amount to bet: she wins if this flip is heads, otherwise she loses . Since it’s Vegas, she never stops playing. Fix any . Let be the sum of bets won after the th bet. Let be the sum of bets lost after the th bet.

Expected maximum (or minimum) of many sums

Bounds on the expected maximum (or minimum) among a collection of sums.

It can be technically convenient to work with expectations directly, instead of working with probabilities. Here, given a collection of sums of 0/1 random variables, we bound the expected maximum (or minimum) sum in the collection.

For example, suppose Alice throws balls randomly into bins just until the first bin has balls. The bound says that the expected maximum number of balls in any bin will be at most . Similarly, the expected minimum number of balls in any bin will be at least .

Expected deviation of a sum

Bounds on the expected deviation of a sum from a threshold.

Here are bounds on the expected deviation of a sum of 0/1-random variables above or below some threshold (typically near its mean).

For example, suppose Alice flips a fair coin times. She pays Bob \$1 for each head after the first heads (if any). What is her expected payment to Bob? The bounds here say: at most . For example, if , the expected payment is .