# 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 its maximum ever exceeds a given value is at most .

The Markov bound plays a fundamental role in the following sense: many probabilistic proofs, including, for example, the proof of the Chernoff bound, rely ultimately on the Markov bound. This note discusses a bound that plays a role similar to the Markov bound in a particular important scenario: when analyzing the maximum value achieved by a given non-negative super-martingale.