Martingale exposure and Azuma’s inequality

Let F be an integrable real statistic determined by finitely many independent random choices. After revealing the first i choices, let M_i be the conditional expectation of F given that information. The tower property says the expected next prediction, conditional on the present, is the present prediction. Thus M is a martingale starting at the unconditional mean and ending at F. Its increments need not be independent and are usually functions of the information already exposed.

To bound one increment, freeze the previous revelations and compare two possible values of the next choice. Couple the remaining random choices identically in the two completions. If changing that one exposed choice changes F by at most c in every such paired completion, the conditional expectations range across an interval of length at most c. In particular, the actual prediction differs from their conditional average by at most c. This supplies a valid, sometimes conservative, absolute increment bound for Azuma.

If martingale increments have deterministic almost-sure bounds c_i with a positive sum of squares, Azuma controls a one-sided deviation t by an exponential involving that sum. If the sum is zero the martingale is constant, so positive deviations have probability zero and need no division formula. Applying the same theorem to minus M gives the lower tail, and summing gives a two-sided bound. A bound valid only on typical configurations is not automatically an Azuma hypothesis: exceptional increments must be handled by a stopping argument or a theorem explicitly allowing them. Nor can a bound on the final statistic’s variance simply replace the increment bounds.

Exposure order changes both the number and size of the increments. For graph coloring, reveal the independent blocks consisting of each vertex’s edges to earlier vertices. Changing one block modifies only edges incident to one vertex. Removing that vertex leaves exactly the same induced graph in both completions. Each chromatic number lies between the chromatic number of the common graph and one more, so the two values differ by at most one. There are n blocks instead of approximately n squared edge revelations.

A tail theorem around the expectation may be powerful even when the expectation has no explicit formula. It says repeated draws are usually close to a common center, but another argument is needed to locate that center. For chromatic number, deterministic graph bounds, first moments, or a more refined random-graph analysis may estimate it. The concentration calculation itself does not claim a numerical coloring algorithm, an efficiently computable expectation, or a sharp description of the distribution.

Stopping-time care is especially important in random graph processes whose sensitivities grow near a boundary. A proof can stop the process before the bad region, bound the stopped increments, and separately estimate the probability of reaching that region. The filtration must still describe everything known so far, and the stopped process must be defined consistently. This discipline carries over to dynamic concentration and the differential equation method, where a martingale controls accumulated random fluctuations while a deterministic equation describes the expected drift.