Azuma's inequality

Azuma's inequality bounds the probability that a martingale deviates substantially from its initial value when each increment is bounded.

Martingale: A stochastic process whose next value has conditional expectation equal to its current value, given its history. Azuma's inequality applies to martingales, not arbitrary sequences of random variables.
Doob martingale: A martingale formed from conditional expectations of a random variable as information is revealed. It converts a function of independent inputs into a process to which Azuma can be applied.
Hoeffding's inequality: A tail bound for sums of independent bounded random variables. Azuma extends a Hoeffding-style bound to martingale differences that need not be independent.
Conditional expectation: The expected value of a random variable given specified information. Martingale increments have zero conditional expectation with respect to the past.
Martingale difference sequence: A sequence of random variables with conditional mean zero given the preceding information. These differences are the increments whose boundedness determines Azuma's deviation scale.
Randomized algorithm: An algorithm whose execution uses random choices as part of its computation. Azuma bounds deviations in quantities exposed step by step during randomized computation.
Freedman's inequality: A martingale tail inequality that uses both bounded increments and conditional variance information. Its variance-sensitive bound can improve on Azuma when conditional variances are small.
Filtration (probability theory): An increasing sequence of information sets representing what is known over time. The filtration defines the past against which each martingale increment is bounded and centered.
Hoeffding's lemma: An exponential-moment bound for a bounded random variable in terms of its range. Applying it conditionally to each increment yields Azuma's exponential tail estimate.
Random walk: A process that moves through a state space by successive random steps. A random walk with bounded step changes supplies a basic setting for martingale deviation bounds.

Linked from 3 pages

Doob's martingale inequalityCompared with: It adds increment assumptions to obtain sharper exponential tail estimates than general maximal bounds.