From Independent Inputs to a Martingale
A function of many independent random inputs can be difficult to analyze directly: changing one input may alter the function, but the final value also depends on all the others. Reveal the inputs one at a time and take conditional expectations of the final function. These conditional expectations form a martingale, and the effect of changing a single coordinate controls one step of that martingale. The Azuma–Hoeffding inequality then turns those stepwise bounds into a tail bound for the function itself.
Let \((\Omega,\mathcal{F},\mathbb{P})\) be a probability space, and let \(X_1,\dots,X_n\) be independent random variables taking values in finite or countable state spaces \(S_1,\dots,S_n\). Write \(S=S_1\times\cdots\times S_n\), and let \(f:S\to\mathbb{R}\) be a function such that \(f(X_1,\dots,X_n)\) is integrable. The real-valued process below is indexed by discrete time \(i=0,\dots,n\), with filtration \(\mathcal{F}_i=\sigma(X_1,\dots,X_i)\) and \(\mathcal{F}_0=\{\varnothing,\Omega\}\).
Independence makes the construction especially useful: after the first \(i\) coordinates are revealed, the unrevealed coordinates retain their original joint distribution. Suppose there are constants \(c_1,\dots,c_n\ge0\) such that, for every \(i\), changing only coordinate \(i\) changes the function by at most \(c_i\):
This condition is required for all choices of the other coordinates and the two possible values of coordinate \(i\). It is a bound on the range of influence of one input, not a bound on the size of \(f\) itself.
Proof. Each \(M_i\) is integrable because it is a conditional expectation of an integrable random variable, and \(M_i\) is \(\mathcal{F}_i\)-measurable by definition. The tower property gives \(\mathbb{E}[M_i\mid\mathcal{F}_{i-1}]=\mathbb{E}[f(X_1,\dots,X_n)\mid\mathcal{F}_{i-1}]=M_{i-1}\); hence this is a martingale and \(\mathbb{E}[D_i\mid\mathcal{F}_{i-1}]=0\).
To bound the increment, fix a revealed prefix \((x_1,\dots,x_{i-1})\). Average \(f(x_1,\dots,x_{i-1},x_i,X_{i+1},\dots,X_n)\) over the unrevealed coordinates, and call the resulting function of \(x_i\) \(g_i(x_i)\). Independence ensures that the distribution used for this average is the same for every possible \(x_i\). For any \(x_i,x_i'\), the coordinatewise assumption holds for each fixed choice of the future coordinates. Averaging that inequality gives \(|g_i(x_i)-g_i(x_i')|\le c_i\). Given the prefix, \(M_i\) is \(g_i(X_i)\), while \(M_{i-1}\) is its conditional mean over \(X_i\). Thus \(D_i\) is a value of \(g_i(X_i)\) minus a mean of its possible values. All those values lie in an interval of length at most \(c_i\); their mean lies in the same interval, so \(D_i\) lies in an interval of length at most \(c_i\) and has conditional mean zero. The argument applies almost surely to every prefix of positive probability, proving the claim. \(\square\)
The Bounded-Differences Inequality
The Azuma–Hoeffding inequality from conditional moment bounds states that if a discrete-time martingale has increments with conditional mean zero and, given the past, each increment lies in an interval of deterministic length \(c_i\), then for \(t>0\), its upper tail after \(n\) steps is at most \(\exp(-2t^2/\sum_{i=1}^n c_i^2)\). This is the standard Azuma–Hoeffding result established in the earlier material on martingale inequalities. Its interval-length hypothesis matters: an interval of length \(c_i\) gives the constant \(2\) in the exponent below.
Proof. The exposure-increment result shows that \(M_i=\mathbb{E}[f\mid\mathcal{F}_i]\) is a martingale and that its \(i\)th increment has conditional mean zero and conditional interval length at most \(c_i\). Apply the stated Azuma–Hoeffding inequality to \(M_n-M_0\). Since \(M_n=f(X_1,\dots,X_n)\) almost surely and \(M_0=\mathbb{E}f(X_1,\dots,X_n)\), this gives the upper-tail bound. Apply the same result to the martingale \((-M_i)_{i=0}^n\) to obtain the lower-tail bound. The two events \(\{f-\mathbb{E}f\ge t\}\) and \(\{\mathbb{E}f-f\ge t\}\) have union \(\{|f-\mathbb{E}f|\ge t\}\); adding their probability bounds gives the two-sided inequality. If \(\sum_i c_i^2=0\), every \(c_i=0\), so the increment result gives \(D_i=0\) almost surely for every \(i\). Then \(f=M_n=M_0=\mathbb{E}f\) almost surely, and all positive-deviation probabilities are zero. \(\square\)
The two-sided result uses a union bound, so its prefactor is \(2\). The bound is useful even when the exact distribution of \(f\) is complicated: one need only control the effect of changing each input. Its strength depends on the sum of squared coordinate bounds, not on the number of inputs alone.
Worked Example: A Sum of Unequal Bernoulli Variables
Let \(X_1,X_2,X_3\) be independent Bernoulli variables with success probabilities \(\tfrac14,\tfrac34,\tfrac12\), respectively, and take \(f=X_1+X_2+X_3\). The probability space carries these independent variables, and the filtration is \(\mathcal{F}_i=\sigma(X_1,\dots,X_i)\). Changing any one coordinate changes the sum by at most \(1\), so \(c_1=c_2=c_3=1\).
The mean is \(\mathbb{E}f=\tfrac14+\tfrac34+\tfrac12=\tfrac32\). For a realized first coordinate \(x_1\), the conditional expectation is \(M_1=x_1+\tfrac34+\tfrac12=x_1+\tfrac54\). For a realized prefix \((x_1,x_2)\), \(M_2=x_1+x_2+\tfrac12\), and \(M_3=x_1+x_2+x_3\).
For the particular outcome \((X_1,X_2,X_3)=(1,0,1)\), the full calculation is \(M_0=\tfrac32\), \(M_1=1+\tfrac54=\tfrac94\), \(M_2=1+0+\tfrac12=\tfrac32\), and \(M_3=1+0+1=2\). The increments are \(D_1=\tfrac94-\tfrac32=\tfrac34\), \(D_2=\tfrac32-\tfrac94=-\tfrac34\), and \(D_3=2-\tfrac32=\tfrac12\). Each increment has absolute value at most \(1\), consistent with the conditional interval-length result.
Check: The increments sum to \(\tfrac34-\tfrac34+\tfrac12=\tfrac12\), which equals \(M_3-M_0=2-\tfrac32=\tfrac12\). For any \(t>0\), the two-sided bound is \(2\exp(-2t^2/3)\), since \(c_1^2+c_2^2+c_3^2=1+1+1=3\).
Worked Example: The Event That the Maximum Is Two
Let \(X_1,X_2\) be independent and uniform on \(\{0,1,2\}\), and define \(f(X_1,X_2)=\mathbf{1}_{\{\max(X_1,X_2)=2\}}\). The filtration reveals \(X_1\) and then \(X_2\). Changing either coordinate can change this indicator by at most \(1\), so \(c_1=c_2=1\).
There are nine equally likely ordered pairs. The event occurs for exactly \((0,2),(1,2),(2,0),(2,1),(2,2)\), so \(\mathbb{E}f=\mathbb{P}(f=1)=\tfrac59\). Before any coordinate is revealed, \(M_0=\tfrac59\). If \(X_1=0\) or \(X_1=1\), the event occurs precisely when \(X_2=2\), so \(M_1=\tfrac13\). If \(X_1=2\), the event has already occurred, so \(M_1=1\). Finally, \(M_2=f\).
For the realized pair \((X_1,X_2)=(2,1)\), the conditional expectations are \(M_0=\tfrac59\), \(M_1=1\), and \(M_2=1\). Thus \(D_1=1-\tfrac59=\tfrac49\) and \(D_2=0\), and their sum is \(\tfrac49=M_2-M_0\). The concentration bound for any \(t>0\) is \(2\exp(-2t^2/2)=2\exp(-t^2)\).
Check: The five listed pairs give probability \(\tfrac59\). Equivalently, the complement consists of the four pairs whose coordinates both lie in \(\{0,1\}\), so the event probability is \(1-\tfrac49=\tfrac59\) as well.
Worked Example: Adjacent Disagreements in a Bit String
Let \(X_1,X_2,X_3,X_4\) be independent fair bits, each uniform on \(\{0,1\}\), and let \(f=\mathbf{1}_{\{X_1\ne X_2\}}+\mathbf{1}_{\{X_2\ne X_3\}}+\mathbf{1}_{\{X_3\ne X_4\}}\). Changing an endpoint bit affects at most one summand, and changing either interior bit affects at most two. Therefore \(c_1=c_4=1\), \(c_2=c_3=2\), and \(\sum_i c_i^2=1+4+4+1=10\).
Each adjacent pair disagrees with probability \(\tfrac12\), so \(M_0=\mathbb{E}f=3\cdot\tfrac12=\tfrac32\). Consider the realized string \((0,1,1,0)\). After revealing \(X_1=0\), the three edges each have conditional disagreement probability \(\tfrac12\), giving \(M_1=\tfrac32\). After revealing \((0,1)\), the first edge is a known disagreement, while the two remaining edges each have conditional expectation \(\tfrac12\), giving \(M_2=1+\tfrac12+\tfrac12=2\). After revealing \((0,1,1)\), the first two edges contribute \(1+0\), and the last has expectation \(\tfrac12\), giving \(M_3=\tfrac32\). All four bits reveal the value \(f=1+0+1=2\), so \(M_4=2\).
The increments on this outcome are \(0,\tfrac12,-\tfrac12,\tfrac12\), and their sum is \(\tfrac12=M_4-M_0=2-\tfrac32\). For any \(t>0\), the two-sided inequality gives \(\mathbb{P}(|f-\tfrac32|\ge t)\le2\exp(-2t^2/10)=2\exp(-t^2/5)\).
Check: The realized string has exactly two disagreements, matching \(M_4=2\); and the four coordinate bounds contribute \(1+4+4+1=10\) to the denominator, as used in the concentration calculation.
Interpreting the Bound and Avoiding a Counting Error
Coordinate bounds need not be equally sharp. For example, in the adjacent-disagreement function, an endpoint can change only one edge, whereas an interior coordinate can change two. Using the sharper bounds \(1,2,2,1\) yields denominator \(10\); assigning the crude bound \(2\) to all four coordinates would yield denominator \(16\), a valid but weaker estimate. When bounding an input's influence, count only the terms that can actually change.
A common mistake in the maximum example is to claim that six of the nine ordered pairs have maximum \(2\), and hence assign probability \(\tfrac69\). That count is wrong: the pairs with maximum exactly \(2\) are \((0,2),(1,2),(2,0),(2,1),(2,2)\), five pairs. The four pairs \((0,0),(0,1),(1,0),(1,1)\) have maximum less than \(2\). The corrected probability is therefore \(\tfrac59\), which also agrees with the complement calculation.
Finally, coordinatewise bounded changes do not mean that \(f\) itself is bounded by \(c_i\), nor do they imply independence of the martingale increments. The method requires independence of the inputs to preserve the same distribution for unrevealed coordinates when comparing possible values of the current coordinate. The martingale increments are conditionally centered, and their conditional ranges are controlled; these are the features needed by Azuma–Hoeffding.
Check Your Understanding
For each question, identify the filtration and verify any coordinate bounds before applying concentration.
- For independent Bernoulli variables \(X_1,\dots,X_n\), what coordinate bounds apply to \(f=\sum_{i=1}^n X_i\), and what is the resulting two-sided bound?
- Why does independence ensure that the conditional expectation over unrevealed coordinates uses the same distribution for two possible values of the coordinate being exposed?
- For the maximum example on \(\{0,1,2\}^2\), compute \(M_1\) when \(X_1=1\), and then compute \(D_1\).
- For a sum of adjacent disagreements on five fair bits, state a valid bound for each coordinate by counting the affected edges.
- Why is the sum of squared coordinate bounds \(10\), rather than \(16\), for the four-bit adjacent-disagreement example?