Concentration Inequalities

Chebyshev’s inequality bounds a tail probability using the variance. Exponential bounds require more information about the distribution, but they can give much stronger control of rare fluctuations. We first derive such bounds for sums, then ask how much survives for a nonlinear function of independent observations.

Let \(X_1,\ldots,X_n\) be i.i.d. with law \(P\). For a function \(f\), write \(Pf=\mathbb{E} f(X_1)\), \(P_nf=n^{-1}\sum_{i=1}^n f(X_i)\), and \(\mathbb G_nf=\sqrt n(P_n-P)f\). Rademacher variables are independent random signs, independent of the observations. See the empirical-process setup for measurability conventions.

Tensorization tells us we can investigate the variance of a random function, in which the data are independent. In particular, we know that this variance is small if \(f\) has “small” gradient. Given this understanding, we can then ask ourselves what can we understand about the distribution of these fluctuations. The tools that are most useful for understanding the distribution of fluctuations are called concentration inequalities.

The simplest form of a concentration inequality is Markov’s inequality (and, by extension, Chebyshev’s inequality). Let’s look at what Chebyshev’s inequality predicts for the sum of \(n\) i.i.d. random variables with finite positive variance \(\sigma^2\). Denote \(S_n = \sum_{1 \leq i \leq n} X_i\). An application of Chebyshev’s inequality tells us

\[\begin{aligned} \mathbf P\,\,\!\!(|S_n - \mathbb{E} S_n| \geq \varepsilon) \leq \frac{n\sigma^2}{\varepsilon^2} ~. \end{aligned}\]

With a \(\sqrt{n}\)-rescaling, we have

\[\begin{aligned} \mathbf P\,\,\!\!(|S_n - \mathbb{E} S_n| \geq \sqrt{n}\varepsilon) \leq \frac{\sigma^2}{\varepsilon^2} ~. \end{aligned}\]

Compare this with the prediction of the central limit theorem, which tells us

\[\begin{aligned} \mathbf P\,\,\!\!(S_n - \mathbb{E} S_n \geq \sqrt{n}\varepsilon) \xrightarrow{n\to\infty} 1 - \Phi \left( \frac{\varepsilon}{\sigma} \right) \leq \frac{\sigma}{\sqrt{2\pi} \varepsilon} \exp \left( - \frac{\varepsilon^2}{2\sigma^2} \right) ~. \end{aligned}\]

Chebyshev gives fluctuations of order \(\sqrt n\) in probability. The central limit theorem describes the limit at each fixed \(\varepsilon>0\); it does not by itself give a finite-sample exponential tail bound, or a bound uniform over growing thresholds. Such concentration bounds need additional hypotheses, such as boundedness or control of exponential moments.

It turns out we can improve on the bound offered by Chebyshev’s inequality. Apply Markov’s inequality to the exponential of the centered sum. The free parameter lets us balance the threshold against the growth of the moment generating function. For any \(\lambda > 0\),

\[\begin{aligned}\mathbf P\,\,\!\!(S_n - \mathbb{E} S_n \geq \varepsilon) = \mathbf P\,\,\!\!( e^{\lambda(S_n - \mathbb{E} S_n)} \geq e^{\lambda\varepsilon}) &\leq \frac{\mathbb{E} e^{\lambda(S_n - \mathbb{E} S_n)}}{ e^{\lambda\varepsilon}} ~, \end{aligned}\]

which follows from Markov’s inequality. Because \(S_n\) is the sum of \(n\) i.i.d. random variables, the rightmost expression becomes

\[\begin{aligned}&= \frac{1}{e^{\lambda\varepsilon}} \prod_{1 \leq i \leq n} \mathbb{E} e^{\lambda(X_i-\mathbb{E}X_i)} ~.\end{aligned}\]

So, supposing that the function \(\mathbb{E} e^{\lambda(S_n - \mathbb{E} S_n)}\) is well-defined (exists and finite), it remains to derive a bound for \(\mathbb{E} e^{\lambda(X_i-\mathbb{E}X_i)}\).

Lemma 1. Let \(X\) be a random variable with \(\mathbb{E} X = 0\), and suppose \(X \in [a,b]\) almost surely. Then, for any \(\lambda > 0\),

\[\begin{aligned} \mathbb{E} e^{\lambda X} \leq e^{\frac{\lambda^2(b-a)^2}{8}} ~. \end{aligned}\tag{1}\]

Proof. Boundedness makes \(g(\lambda)=\log\mathbb{E}e^{\lambda X}\) twice differentiable for every real \(\lambda\). Under the probability measure with density \(e^{\lambda X}/\mathbb{E}e^{\lambda X}\), differentiation gives \(g^{\prime\prime}(\lambda)=\operatorname{Var}_\lambda(X)\). This measure is still supported on \([a,b]\). With \(m=(a+b)/2\),

\[0\leq g^{\prime\prime}(\lambda)=\operatorname{Var}_\lambda(X)\leq\mathbb{E}_\lambda[(X-m)^2]\leq\frac{(b-a)^2}{4}.\]

Since \(g(0)=0\) and \(g^\prime(0)=\mathbb{E}X=0\), integrating this bound twice yields, for every \(\lambda>0\),

\[g(\lambda)=\int_0^\lambda(\lambda-s)g^{\prime\prime}(s)\,ds\leq\frac{\lambda^2(b-a)^2}{8}.\]

Exponentiating proves (1). If \(a=b\), the mean-zero assumption makes \(X=0\), and the same inequality holds with equality. The bound is global in \(\lambda\), which is what the subsequent optimization requires. ◻

Theorem 2 (Hoeffding). Let \(X_1, \dots, X_n\) be independent bounded random variables, such that \(X_i \in [a_i, b_i]\) almost surely. For every \(\varepsilon>0\), if \(\sum_i(b_i-a_i)^2>0\), we have

\[\begin{aligned} \mathbf P\,\,\!\!(S_n - \mathbb{E} S_n \geq \varepsilon) &\leq \exp \left( -\frac{2\varepsilon^2}{\sum_{1 \leq i \leq n} (b_i - a_i)^2} \right) ~, \\ \mathbf P\,\,\!\!(S_n - \mathbb{E} S_n \leq -\varepsilon) &\leq \exp \left( -\frac{2\varepsilon^2}{\sum_{1 \leq i \leq n} (b_i - a_i)^2} \right) ~. \end{aligned}\]

If all interval widths are zero, the centered sum is zero almost surely, so both tail probabilities are zero instead.

Proof. Write \(V=\sum_{i=1}^n(b_i-a_i)^2\). If \(V=0\), the centered sum vanishes, and both tail probabilities are zero for \(\varepsilon>0\). Otherwise, apply Lemma 1 to each centered variable \(X_i-\mathbb{E}X_i\). Independence preserves the product of their centered exponential moments:

\[\begin{aligned} \mathbf P\,\,\!\!(S_n - \mathbb{E} S_n \geq \varepsilon) &= \mathbf P\,\,\!\!( e^{\lambda(S_n - \mathbb{E} S_n)} \geq e^{\lambda\varepsilon}) \leq \frac{\mathbb{E} e^{\lambda(S_n - \mathbb{E} S_n)}}{ e^{\lambda\varepsilon}} \\ &= \frac{1}{e^{\lambda\varepsilon}} \prod_{1 \leq i \leq n} \mathbb{E} e^{\lambda(X_i-\mathbb{E}X_i)} \\ &\leq \frac{1}{e^{\lambda\varepsilon}} e^{\sum_{1 \leq i \leq n} \frac{\lambda^2(b_i - a_i)^2}{8}} \\ &= \exp \left( -\lambda \varepsilon + \frac{\lambda^2}{8} \sum_{1 \leq i \leq n} (b_i - a_i)^2 \right) ~. \end{aligned}\]

It remains to find the minimum of the function \(g(\lambda) = -\lambda \varepsilon + \frac{\lambda^2}{8} \sum_{1 \leq i \leq n} (b_i - a_i)^2\). Since this is a quadratic function, it follows that the minimum occurs at

\[\begin{aligned} \lambda = \frac{4\varepsilon}{\sum_{1 \leq i \leq n} (b_i - a_i)^2} ~. \end{aligned}\]

Therefore, the inequality above reduces to

\[\begin{aligned} \mathbf P\,\,\!\!(S_n - \mathbb{E} S_n \geq \varepsilon) &\leq \exp \left( -\lambda \varepsilon + \frac{\lambda^2}{8} \sum_{1 \leq i \leq n} (b_i - a_i)^2 \right) \\ &\leq \exp \left( \frac{-4\varepsilon^2 + 2 \varepsilon^2}{\sum_{1 \leq i \leq n} (b_i - a_i)^2 } \right) = \exp \left( \frac{-2 \varepsilon^2}{\sum_{1 \leq i \leq n} (b_i - a_i)^2 } \right) ~, \end{aligned}\]

as desired. Apply the same upper-tail argument to \(-X_1,\ldots,-X_n\) to obtain the lower-tail bound, with threshold \(-\varepsilon\). ◻

Corollary 3. Let \((a_1, \dots, a_n) \in \mathbb R^n\) be constants, and \((\varepsilon_1, \dots, \varepsilon_n)\) be independent Rademacher random variables. Then, for every positive threshold and nonzero coefficient vector,

\[\begin{aligned} \mathbf P\,\,\!\!\left( \left| \sum_{1 \leq i \leq n} a_i \varepsilon_i \right| \geq t \right) \leq 2 e^{-\frac{t^2}{2 \lVert a \rVert^2}} ~, \end{aligned}\]

where \(\lVert \cdot \rVert\) denotes the Euclidean norm.

Proof. The variable \(a_i\varepsilon_i\) has mean zero and range \([-|a_i|,|a_i|]\). Thus the sum of squared range widths in Hoeffding's inequality is \(4\sum_i a_i^2=4\|a\|^2\). Add its two one-sided bounds. If \(a=0\), the sum is zero and its tail probability is zero for every \(t>0\). ◻

Hoeffding's bound uses only the ranges of the variables. Boundedness guarantees the exponential moments used in its proof; for unbounded variables this requires a separate hypothesis. For i.i.d. variables in \([a,b]\), with \(a<b\), and \(\alpha\in(0,1)\), it gives

\[\begin{aligned} \mathbb P\!\left\{S_n - \mathbb{E} S_n \geq \sqrt{\log \left( \frac{1}{\alpha} \right) \frac{n(b-a)^2}{2}}\right\}\leq\alpha ~. \end{aligned}\]

So, we can construct the following conservative confidence interval at level \(1-\alpha\) for the population mean:

\[\begin{aligned} \left[ \overline X_n \pm \frac{b-a}{\sqrt{2n}} \sqrt{\log \left( \frac{2}{\alpha} \right)} \right] ~, \end{aligned}\]

where \(\overline X_n\) denotes the sample mean. Finally, note that we have not used any information about the variance of \(X_i\) in constructing this inequality.

A real random variable \(X\) is subgaussian if there are constants \(C,\nu>0\) such that \(\mathbb P(|X|>t)\leq C e^{-\nu t^2}\) for every \(t>0\). This is equivalent to each of the following conditions, with constants allowed to change:

(i) \(\mathbb E e^{MX^2}<\infty\) for some \(M>0\). (ii) \(\mathbb E e^{\lambda(X-\mathbb EX)}\leq L e^{\ell\lambda^2}\) for every \(\lambda\in\mathbb R\), for some \(\ell>0\) and finite \(L\geq1\). (iii) \(\mathbb E|X|^p\leq K^p p^{p/2}\) for all real \(p\geq1\), for some \(K>0\).

Proof of the equivalences. From the tail bound, choose \(0<M<\nu\). The tail-integral formula gives

\[\mathbb E e^{MX^2}=1+\int_1^\infty\mathbb P\{|X|>\sqrt{\log u/M}\}\,du\leq1+C\int_1^\infty u^{-\nu/M}\,du<\infty.\]

Conversely, writing \(A=\mathbb E e^{MX^2}\), Markov gives \(\mathbb P(|X|>t)\leq A e^{-Mt^2}\). Also \(\sup_{x\geq0}x^p e^{-Mx^2}=(p/(2eM))^{p/2}\), so \(\mathbb E|X|^p\leq A(p/(2eM))^{p/2}\), which has the form (iii) since \(A\leq\max(1,A)^p\). In the reverse direction, (iii) and Markov with \(p=t^2/(e^2K^2)\geq1\) give \(\mathbb P(|X|>t)\leq e^{-p}\); increasing the prefactor covers \(t<eK\).

For (i) implies (ii), let \(\mu=\mathbb EX\), finite by (i), and choose \(a=M/2\). The inequality \((X-\mu)^2\leq2X^2+2\mu^2\) implies \(B=\mathbb E e^{a(X-\mu)^2}<\infty\). Since \(\lambda y\leq ay^2+\lambda^2/(4a)\), we obtain (ii) with \(L=B\), \(\ell=1/(4a)\). Finally (ii), optimized at \(\lambda=\pm t/(2\ell)\), gives \(\mathbb P(|X-\mu|>t)\leq2L e^{-t^2/(4\ell)}\). For \(t>2|\mu|\), use \(|X|>t\Rightarrow|X-\mu|>t/2\), and enlarge the constant to cover smaller \(t\). This returns the original tail condition. ◻

An example of a subgaussian process is the Rademacher process, as described in Corollary 3. A much more powerful result is true, and is an example of a maximal inequality.

Proposition 4 (Maximal inequality: subgaussian). Suppose \(Y_1, \dots, Y_n\) are subgaussian random variables, with constants

\[\begin{aligned} \mathbb{E} e^{\lambda Y_i} \leq e^{\frac{\lambda^2 \sigma^2}{2}} ~~\text{for all }\lambda\in\mathbb R,\quad 1 \leq i \leq n ~. \end{aligned}\]

Then,

\[\begin{aligned} \mathbb{E} \sup_{1 \leq i \leq n} Y_i \leq \sigma \sqrt{2 \log n} ~. \end{aligned}\]

Proof. This follows from Jensen’s inequality and the assumption in the statement:

\[\begin{aligned} e^{\lambda \mathbb{E} \sup_{1 \leq i \leq n} Y_i} &\leq \mathbb{E} e^{\lambda \sup_{1 \leq i \leq n} Y_i} \\ &\leq \sum_{1 \leq i \leq n} \mathbb{E} e^{\lambda Y_i} \leq \sum_{1 \leq i \leq n} e^{\frac{\lambda^2 \sigma^2}{2}} = n e^{\frac{\lambda^2 \sigma^2}{2}} ~. \end{aligned}\]

Therefore, taking the logarithm of both sides gives

\[\begin{aligned} \mathbb{E} \sup_{1 \leq i \leq n} Y_i \leq \frac{\log n}{\lambda} + \frac{\lambda \sigma^2}{2} ~. \end{aligned}\]

For \(n>1\) and \(\sigma>0\), the minimum of the right-hand side occurs at \(\lambda = \sqrt{\frac{2\log n}{\sigma^2}}\), so the inequality above reduces to

\[\begin{aligned} \mathbb{E} \sup_{1 \leq i \leq n} Y_i \leq \sigma \sqrt{2 \log n} ~, \end{aligned}\]

as desired. ◻

For \(n=1\), let \(\lambda\downarrow0\) in the bound above. If \(\sigma=0\), let \(\lambda\to\infty\). Both cases give the stated zero upper bound. The two-sided moment assumption also implies \(\mathbb EY_i=0\), by differentiating at zero. Independence of the \(Y_i\) is not needed.

Proposition 5. Let \(f\) be a continuous, strictly increasing, convex function from \([0,\infty)\) to \([0,\infty)\). Take finite constants \(c_i>0\). Suppose \(\xi_1, \dots, \xi_n\) are random variables such that

\[\begin{aligned} \mathbb{E} f\left( \frac{|\xi_i|}{c_i} \right) \leq L \end{aligned}\]

for some finite constant \(L\), and the inequality above holds for all \(1 \leq i \leq n\). Then,

\[\begin{aligned} \mathbb{E} \sup_{1 \leq i \leq n} |\xi_i| \leq f^{-1} (Ln) \sup_{1 \leq i \leq n} c_i ~. \end{aligned}\]

Proof. Since \(f\) is strictly increasing, convex, and nonnegative, we have (by Jensen’s inequality applied in the following calculations)

\[\begin{aligned} f \left( \frac{\mathbb{E} \sup_{1 \leq i \leq n} |\xi_i|}{\sup_{1 \leq i \leq n} c_i} \right) &\leq f \left( \mathbb{E} \sup_{1 \leq i \leq n} \frac{|\xi_i|}{c_i} \right) \\ &\leq \mathbb{E} f \left( \sup_{1 \leq i \leq n} \frac{|\xi_i|}{c_i} \right) \leq \sum_{1 \leq i \leq n} \mathbb{E} f \left( \frac{|\xi_i|}{c_i} \right) \leq Ln ~. \end{aligned}\]

Since \(f\) is invertible by our assumptions, apply \(f^{-1}\) to both sides to conclude. ◻

The inverse in Proposition 5 is defined at \(Ln\): an increasing convex function that is not constant is unbounded, and \(Ln\geq f(0)\). Such a function also has a positive linear lower bound for large arguments, so the moment assumptions ensure the integrability needed for Jensen's inequality.

Example 6. Let \(\varepsilon_1,\ldots,\varepsilon_n\) be independent Rademacher signs, let \(a^{(1)},\ldots,a^{(n)}\in\mathbb R^n\), and put \(\xi_i=\sum_{k=1}^n a_k^{(i)}\varepsilon_k\). The variables \(\xi_i\) may be dependent, since they use the same signs. Independence of the signs gives, for every \(\lambda\in\mathbb R\),

\[\mathbb{E}e^{\lambda\xi_i}=\prod_{k=1}^n\cosh(\lambda a_k^{(i)})\leq\exp\!\left(\frac{\lambda^2\|a^{(i)}\|_2^2}{2}\right).\]

The last inequality follows by differentiating \(h(u)=\log\cosh u\): \(h(0)=h^\prime(0)=0\) and \(0\leq h^{\prime\prime}(u)=1/\cosh^2u\leq1\), so \(h(u)\leq u^2/2\). Exponential Markov bounds applied with both signs of \(\lambda\), and optimized at \(|\lambda|=s/\|a^{(i)}\|_2^2\), yield

\[\mathbb P\{|\xi_i|\geq s\}\leq2\exp\!\left(-\frac{s^2}{2\|a^{(i)}\|_2^2}\right),\qquad s>0.\]

If \(a^{(i)}=0\), then \(\xi_i=0\) and no normalization is needed. Otherwise this also proves the squared-exponential moment bound used in maximal inequalities. With \(Y=\exp(\xi_i^2/(6\|a^{(i)}\|_2^2))\), the tail-integral identity gives

\[\mathbb{E}Y=1+\int_1^\infty\mathbb P\{Y>s\}\,ds\leq1+2\int_1^\infty s^{-3}\,ds=2.\]

For the maximum, write \(v=\max_{1\leq i\leq n}\|a^{(i)}\|_2\). For \(\lambda>0\), Jensen’s inequality and the sum bound give

\[\lambda\,\mathbb{E}\max_{1\leq i\leq n}|\xi_i|\leq\log\mathbb{E}e^{\lambda\max_i|\xi_i|}\leq\log\sum_{i=1}^n\bigl(\mathbb{E}e^{\lambda\xi_i}+\mathbb{E}e^{-\lambda\xi_i}\bigr)\leq\log(2n)+\frac{\lambda^2v^2}{2}.\]

When \(v>0\), minimize the right side after division by \(\lambda\), taking \(\lambda=\sqrt{2\log(2n)}/v\). Thus

\[\mathbb{E}\max_{1\leq i\leq n}|\xi_i|\leq v\sqrt{2\log(2n)}.\]

For \(v=0\), both sides vanish. The factor \(\log(2n)\) includes the case \(n=1\); a bound using \(\log n\) alone would incorrectly give zero there. The argument needs no independence between the linear combinations. ◻

The same optimization can be carried out for a general log moment generating function. The resulting bound is called the Chernoff bound.

Lemma 7 (Chernoff). For an integrable random variable \(X\), write

\[\begin{aligned} \psi (\lambda) = \log \mathbb{E} e^{\lambda(X - \mathbb{E} X)} ~~\text{and}~~ \psi^* (t) = \sup_{\lambda \geq 0} \lambda t - \psi(\lambda) \end{aligned}\]

to denote the log moment generating function and its Legendre transform, respectively. Then, \(\mathbf P\,\,\!\!(X - \mathbb{E} X \geq t) \leq e^{-\psi^*(t)}\) for all \(t \geq 0\).

Proof. For every \(\lambda>0\), exponential Markov gives \(\mathbb P(X-\mathbb EX\geq t)\leq\exp\{\psi(\lambda)-\lambda t\}\). We allow \(\psi(\lambda)=+\infty\); such a parameter gives no useful bound. The choice \(\lambda=0\) gives the bound one. Taking the infimum over all \(\lambda\geq0\) yields \(\exp\{-\sup_{\lambda\geq0}(\lambda t-\psi(\lambda))\}=e^{-\psi^*(t)}\). No attainment of the infimum is needed. ◻

A direct consequence of the Chernoff bound is a powerful concentration inequality, called Bernstein’s inequality.

Proposition 8 (Bernstein). Let \(X_1, X_2, \dots\) be independent random variables with bounded ranges \([-M,M]\) and zero means. Take \(M>0\) and \(v>0\). Then, for \(t>0\),

\[\begin{aligned} \mathbf P\,\,\!\!\left( \left| \sum_{1 \leq i \leq n} X_i \right| > t \right) \leq 2 e^{-\frac{t^2}{2(v + Mt/3)}} ~, \end{aligned}\tag{2}\]

for \(v \geq \sum_{1 \leq i \leq n} \mathop{\mathrm{Var}}(X_i)\).

Proof, using Proposition 9 below. For \(u\geq0\), expand the exponential and use \(\mathbb EX_i=0\), \(|X_i|^k\leq M^{k-2}X_i^2\) for \(k\geq2\):

\[\mathbb E e^{uX_i/M}\leq1+\frac{\mathbb EX_i^2}{M^2}(e^u-1-u)\leq\exp\!\left\{\frac{\mathbb EX_i^2}{M^2}(e^u-1-u)\right\}.\]

The series and expectation can be interchanged because \(X_i\) is bounded. Independence and multiplication show that \(Z=M^{-1}\sum_iX_i\) satisfies Proposition 9 with parameter \(v/M^2\). Applying its third bound at \(t/M\) gives the upper tail in (2). Repeat for \(-X_i\) and add the bounds. If all variances vanish, each centered variable is zero almost surely and the positive-threshold tail is zero; thus no division by a zero variance is needed. ◻

We deduce Bernstein’s inequality from the following result (in the abstract).

Proposition 9. Let \(Z\) be a random variable whose moment-generating function, for some \(v > 0\), satisfies

\[\begin{aligned} \mathbb{E} e^{\lambda Z} \leq \exp (v(e^\lambda - 1 - \lambda)) \quad \text{for } \lambda > 0 ~. \end{aligned}\tag{3}\]

Then, for all \(t \geq 0\),

\[\begin{aligned}\mathbf P\,\,\!\!(Z \geq t) \leq \exp \left( -v h_1 \left( \frac{t}{v} \right) \right) &\leq \exp \left( -\frac{3t}{4} \log \left( 1 + \frac{2t}{3v} \right) \right) \leq \exp \left( -\frac{t^2}{2(v + t/3)} \right) ~.\end{aligned}\]

Furthermore,

\[\begin{aligned}\mathbf P\,\,\!\!\left( Z \geq \sqrt{2vx} + \frac{x}{3} \right) &\leq e^{-x} \quad \text{for } x \geq 0 ~.\end{aligned}\]

Proof. For \(t>0\), Markov and (3) give

\[\mathbb P(Z\geq t)\leq\inf_{\lambda>0}\exp\{v(e^\lambda-1-\lambda)-\lambda t\}.\]

The exponent has derivative \(v(e^\lambda-1)-t\) and positive second derivative, so its minimum occurs at \(\lambda=\log(1+t/v)\). Substitution gives \(-v h_1(t/v)\), where \(h_1(u)=(1+u)\log(1+u)-u\). At \(t=0\) the claim follows from the bound one.

To justify both comparisons explicitly, put \(k(u)=h_1(u)-(3u/4)\log(1+2u/3)\). Then \(k(0)=k'(0)=0\) and

\[k''(u)=\frac{u^2}{9(1+u)(1+2u/3)^2}\geq0.\]

Hence \(k(u)\geq0\). Moreover \(\log(1+w)\geq2w/(2+w)\) for \(w\geq0\), since their difference vanishes at zero and has derivative \(w^2/[(1+w)(2+w)^2]\). With \(w=2u/3\), this proves

\[h_1(u)\geq\frac{3u}{4}\log(1+2u/3)\geq\frac{u^2}{2(1+u/3)}.\]

For the final tail estimate, the elementary inequality \(k!\geq2\cdot3^{k-2}\), \(k\geq2\), gives

\[e^\lambda-1-\lambda\leq\frac{\lambda^2}{2(1-\lambda/3)},\qquad0\leq\lambda<3.\]

Thus \(\log\mathbb Ee^{\lambda Z}\leq v\lambda^2/[2(1-\lambda/3)]\). For \(x>0\), set \(s=\sqrt{2x/v}\), \(\lambda=s/(1+s/3)\), and \(t=\sqrt{2vx}+x/3=vs+vs^2/6\). Direct substitution yields

\[-\lambda t+\frac{v\lambda^2}{2(1-\lambda/3)}=-\frac{vs^2}{2}=-x.\]

Markov now gives the desired \(e^{-x}\) bound. For \(x=0\), it is again the bound one. ◻

Independent subgaussian variables have subgaussian sums, by multiplying their moment generating functions. For a nonlinear function of independent inputs, however, unconditional bounds on individual pieces need not control its martingale differences. The useful hypothesis is a conditional exponential-moment bound. Entropy tensorization and log-Sobolev inequalities provide another route to such concentration.

Lemma 10 (Azuma). Let \(X_1, \dots, X_n\) be independent random variables defined on \(\mathscr X\). Let \(\Delta_k\) be a martingale difference array with respect to \(X_1, \dots, X_k\), defined as

\[\begin{aligned} \Delta_k = \mathbb{E} [f(X_1, \dots, X_n) \mid X_1, \dots, X_k] - \mathbb{E} [f(X_1, \dots, X_n) \mid X_1, \dots, X_{k-1}] ~, \end{aligned}\]

where \(f(X_1,\ldots,X_n)\) is integrable. Let \(\sigma_k^2\geq0\) be deterministic constants (variance proxies, not necessarily the actual variances). Suppose, for every \(\lambda\in\mathbb R\), the following conditional subgaussian property holds:

\[\begin{aligned} \mathbb{E} [e^{\lambda \Delta_k} \mid X_1, \dots, X_{k-1}] \leq e^{\frac{\lambda^2 \sigma_k^2}{2}} ~~ \rm a.s. \end{aligned}\]

Then, the sum \(\sum_{1 \leq k \leq n} \Delta_k\) is subgaussian.

Proof. Write \(\mathcal F_k=\sigma(X_1,\ldots,X_k)\) and \(S_k=\sum_{i=1}^k\Delta_i\), with \(S_0=0\). Since \(S_{k-1}\) is \(\mathcal F_{k-1}\)-measurable, the tower property and the conditional hypothesis give

\[\mathbb Ee^{\lambda S_k}=\mathbb E\!\left[e^{\lambda S_{k-1}}\mathbb E(e^{\lambda\Delta_k}\mid\mathcal F_{k-1})\right]\leq e^{\lambda^2\sigma_k^2/2}\mathbb Ee^{\lambda S_{k-1}}.\]

Iteration yields \(\mathbb Ee^{\lambda S_n}\leq\exp\{\lambda^2\sum_k\sigma_k^2/2\}\) for all real \(\lambda\). The tower step is valid initially for nonnegative extended expectations, and the bound proves finiteness inductively. If \(V=\sum_k\sigma_k^2>0\), optimizing at \(\lambda=\pm t/V\) gives \(\mathbb P(|S_n|\geq t)\leq2e^{-t^2/(2V)}\). If \(V=0\), taking \(\lambda\to\infty\) in the one-sided Markov bounds shows \(S_n=0\) almost surely. The same proof works for any filtration and integrable martingale differences satisfying the displayed conditional bounds. ◻

Here is a classical bound for the sum of bounded martingale difference array.

Lemma 11 (Azuma-Hoeffding). With the setup of Lemma 10, suppose \(|\Delta_i| \leq c_i\) for some constants \(c_i\) for all \(1 \leq i \leq n\). Then, the sum \(\sum_{1 \leq k \leq n} \Delta_k\) is subgaussian.

Proof. Conditional on \(\mathcal F_{i-1}\), the variable \(\Delta_i\) has mean zero and lies in \([-c_i,c_i]\). The conditional version of Lemma 1 therefore gives

\[\mathbb E(e^{\lambda\Delta_i}\mid\mathcal F_{i-1})\leq\exp\{\lambda^2(2c_i)^2/8\}=\exp\{\lambda^2c_i^2/2\}.\]

For negative \(\lambda\), apply that lemma to \(-\Delta_i\). Lemma 10, with \(\sigma_i^2=c_i^2\), now yields \(\mathbb Ee^{\lambda\sum_i\Delta_i}\leq e^{\lambda^2\sum_i c_i^2/2}\) and \(\mathbb P(|\sum_i\Delta_i|\geq t)\leq2e^{-t^2/(2\sum_i c_i^2)}\) for \(t>0\) when the denominator is positive. If every \(c_i=0\), the sum is zero. ◻

From these results, we can deduce the simplest subgaussian concentration inequality. Again, we cannot naïvely apply the tensorization arguments to subgaussian random variables; we can, however, apply a tensorization principle to a martingale difference array, as above. We only require that the functions we consider obey the bounded difference property: a function \(f : \mathscr X^n \to \mathbb R\) satisfies the bounded difference property if there exists some nonnegative constants \(d_1, \dots, d_n\) such that

\[\begin{aligned} \sup_{x_1, \dots, x_n; x'_i \in \mathscr X} | f(x_1, \dots, x_n) - f(x_1, \dots, x_{i-1}, x'_i, x_{i+1}, \dots, x_n) | \leq d_i \end{aligned}\tag{4}\]

holds for all \(1 \leq i \leq n\).

Lemma 12 (McDiarmid). Suppose \(X_1, \dots, X_n\) are independent random variables defined on \(\mathscr X\), and \(f\) is a measurable function satisfying the bounded difference property (4). Then,

\[\begin{aligned} \mathbf P\,\,\!\!(|f(X_1, \dots, X_n) - \mathbb{E} f(X_1, \dots, X_n)| > t) \leq 2 e^{-\frac{2t^2}{\sum_{1 \leq i \leq n} d_i^2}} ~. \end{aligned}\]

Proof. Fix the past \(x_1,\ldots,x_{i-1}\), and average only over the independent future coordinates:

\[g_i(x)=\mathbb E f(x_1,\ldots,x_{i-1},x,X_{i+1},\ldots,X_n).\]

For any \(x,y\), the bounded difference assumption and the same future realization give \(|g_i(x)-g_i(y)|\leq d_i\). Thus, conditional on the past, \(g_i(X_i)\) lies in an interval of width at most \(d_i\). The martingale difference is \(\Delta_i=g_i(X_i)-\mathbb E[g_i(X_i)\mid\mathcal F_{i-1}]\); subtracting the mean preserves that interval width. Conditional Hoeffding therefore gives

\[\mathbb E(e^{\lambda\Delta_i}\mid\mathcal F_{i-1})\leq e^{\lambda^2d_i^2/8}.\]

Iterating as in Lemma 10 and using \(\sum_i\Delta_i=f(X)-\mathbb Ef(X)\), we get \(\mathbb E e^{\lambda(f(X)-\mathbb Ef(X))}\leq e^{\lambda^2D/8}\), where \(D=\sum_i d_i^2\). For \(D>0\), optimize the upper-tail bound at \(\lambda=4t/D\), repeat with \(-f\), and add to obtain \(2e^{-2t^2/D}\). If \(D=0\), changing coordinates one at a time shows that \(f\) is constant and the positive-threshold tail vanishes. In particular, the sharp constant uses the conditional range width \(d_i\); the weaker fact \(|\Delta_i|\leq d_i\) alone would lose a factor four in the exponent. ◻

An application of these tools is detailed in Remark 6 of the note on symmetrization, bracketing, and covering numbers.

The modified log-Sobolev inequality gives another way to combine the coordinate contributions: tensorize the entropy and then apply the Herbst argument. Namely, we can show the following bounded difference inequality in terms of entropy. Let

\[\begin{aligned} D_i^+ f(x) &\triangleq \sup_w f(x_1, \dots, x_{i-1}, w, x_{i+1}, \dots, x_n) - f(x_1, \dots, x_n) ~, \\ D_i^- f(x) &\triangleq f(x_1, \dots, x_n) - \inf_w f(x_1, \dots, x_{i-1}, w, x_{i+1}, \dots, x_n) ~, \end{aligned}\]

where \(f: \mathscr X^n \to \mathbb R\) is some function.

Theorem 13 (Bounded difference inequality). Suppose \(X_1, \dots, X_n\) are independent random variables. Assume \(f(X)\) is integrable, the coordinate suprema below are measurable, and the indicated squared-derivative norms are finite and positive. Then, for all \(t \geq 0\),

\[\begin{aligned} \mathbf P\,\,\!\!( f(X_1, \dots, X_n) \geq \mathbb{E} f(X_1, \dots, X_n) + t) &\leq e^{-\frac{t^2}{4 \lVert \sum_{1 \leq i \leq n} |D_i^- f|^2 \rVert_{\infty}}} \\ \mathbf P\,\,\!\!( f(X_1, \dots, X_n) \leq \mathbb{E} f(X_1, \dots, X_n) - t) &\leq e^{-\frac{t^2}{4 \lVert \sum_{1 \leq i \leq n} |D_i^+ f|^2 \rVert_{\infty}}} \end{aligned}\]

Proof. First suppose \(f\) is bounded. Fix all coordinates except \(i\), and let \(g=f(X)\), \(g'\) its value after replacing coordinate \(i\) by an independent copy. Jensen's inequality gives \(\operatorname{Ent}_i(e^g)\leq\operatorname{Cov}_i(g,e^g)\). Symmetrizing this covariance and interchanging the two copies gives

\[\operatorname{Ent}_i(e^g)\leq\frac12\mathbb E_i[(g-g')(e^g-e^{g'})]=\mathbb E_i[(g-g')(e^g-e^{g'})\mathbf1_{g>g'}].\]

On \(g>g'\), use \(1-e^{-(g-g')}\leq g-g'\) and \(g-g'\leq D_i^-f(X)\). Therefore

\[\operatorname{Ent}_i(e^f)\leq\mathbb E_i[(D_i^-f)^2e^f].\]

Apply this to \(\lambda f\), \(\lambda\geq0\), and tensorize entropy. With \(V_- =\|\sum_i(D_i^-f)^2\|_\infty\),

\[\operatorname{Ent}(e^{\lambda f})\leq\lambda^2\mathbb E\!\left[e^{\lambda f}\sum_i(D_i^-f)^2\right]\leq\lambda^2V_-\mathbb Ee^{\lambda f}.\]

The Herbst argument, with variance proxy \(2V_-\), yields \(\log\mathbb Ee^{\lambda(f-\mathbb Ef)}\leq\lambda^2V_-\). Exponential Markov optimized at \(\lambda=t/(2V_-)\) proves the upper-tail bound. For the lower tail apply this argument to \(-f\), using the exact identity \(D_i^-(-f)=D_i^+f\).

For integrable, possibly unbounded \(f\), set \(f_m=\max(-m,\min(f,m))\). Monotonicity and the contraction property of clipping imply \(D_i^-f_m\leq D_i^-f\) and \(D_i^+f_m\leq D_i^+f\). Also \(f_m\to f\) almost surely and in \(L^1\). Fatou applied to \(e^{\lambda(f_m-\mathbb Ef_m)}\) passes each exponential-moment bound to \(f\), after which the same Markov optimization applies. If a norm is zero, replace it by any positive \(\eta\) and let \(\eta\downarrow0\); the corresponding tail is zero for \(t>0\). At \(t=0\), use the bound one. ◻