Maxima of Sub-Gaussian Variables

For the upper tail, for any \(\lambda>0\), Markov’s inequality and the MGF condition give $$ P(X-\mu\geq t) \leq e^{-\lambda t}E[e^{\lambda(X-\mu)}] \leq \exp\!\left(-\lambda t+\frac{\sigma^2\lambda^2}{2}\right). $$ The exponent is minimized at \(\lambda=t/\sigma^2\), giving the stated upper-tail bound. Apply the same argument to \(-(X-\mu)\) for the lower tail. If \(\sigma=0\), the MGF condition forces \(X=\mu\) almost surely, so the positive-deviation probabilities are zero.

These individual bounds are the input for a maximum bound. In particular, the scales and means need not be the same across variables.

Tail Bounds for a Finite Maximum

Proof. The event that the maximum exceeds \(t\) is the union of the individual exceedance events: $$ \left\{\max_i(X_i-\mu_i)\geq t\right\} =\bigcup_{i=1}^{m}\{X_i-\mu_i\geq t\}. $$ The union bound and the individual sub-Gaussian tail bounds therefore give $$ P\!\left(\max_i(X_i-\mu_i)\geq t\right) \leq \sum_{i=1}^{m}P(X_i-\mu_i\geq t) \leq \sum_{i=1}^{m}\exp\!\left(-\frac{t^2}{2\sigma_i^2}\right). $$ If \(\sigma_i\leq\sigma\), then each exponential is at most \(\exp(-t^2/(2\sigma^2))\), yielding the common-scale bound. The argument uses no joint distribution calculation, so dependence does not affect its validity. \(\square\)

For a common upper bound \(\sigma>0\), choose a desired error probability \(\delta\in(0,1)\). Solving \(m\exp(-t^2/(2\sigma^2))=\delta\) gives the threshold $$ t=\sigma\sqrt{2\log(m/\delta)}. $$ Consequently, $$ P\!\left(\max_i(X_i-\mu_i)\geq \sigma\sqrt{2\log(m/\delta)}\right)\leq\delta. $$ The dependence on the number of variables is through \(\sqrt{\log m}\), rather than a factor proportional to \(m\) in the threshold. The factor \(m\) appears in the tail probability and becomes a logarithm when the bound is inverted.

Unequal Scales and Unequal Means

If the centered variables have different parameters, retaining each \(\sigma_i\) can improve on replacing them all by their largest scale. The theorem already supplies this heterogeneous bound. If the quantities of interest are the uncentered \(X_i\), their means must also be taken into account. For any real \(x\), the event \(\{\max_i X_i\geq x\}\) is the union of \(\{X_i\geq x\}\). For indices with \(x>\mu_i\), apply the individual tail bound; indices with \(x\leq\mu_i\) can only be bounded trivially by 1. Thus $$ P(\max_i X_i\geq x) \leq \sum_{i:x>\mu_i}\exp\!\left(-\frac{(x-\mu_i)^2}{2\sigma_i^2}\right) +\#\{i:x\leq\mu_i\}. $$ This form is useful when means differ, though it may be uninformative if the threshold is below several means.

An Expected-Maximum Bound

The tail bound controls exceedance probabilities at a chosen threshold. A related argument gives a direct bound on the expected maximum. It also shows why the logarithm of the number of variables appears.

Proof. Each \(Z_i\) has finite exponential moments by its MGF bound and is integrable. For any \(\lambda>0\), the pointwise inequality $$ \max_i Z_i\leq\frac{1}{\lambda}\log\!\left(\sum_{i=1}^{m}e^{\lambda Z_i}\right) $$ holds because the sum includes \(e^{\lambda \max_i Z_i}\). The random variable on the right is integrable: it is bounded above by \(\lambda^{-1}\log m+\max_i Z_i\), and the finite maximum of integrable variables is integrable. Jensen’s inequality for the concave logarithm, followed by the MGF bounds, yields $$ E[\max_i Z_i] \leq\frac{1}{\lambda}\log\!\left(\sum_{i=1}^{m}E[e^{\lambda Z_i}]\right) \leq\frac{\log m}{\lambda}+\frac{\lambda\sigma^2}{2}. $$ For \(m>1\), minimize the last expression over \(\lambda>0\). Its derivative is \(-\log(m)/\lambda^2+\sigma^2/2\), so the minimizing value is \(\lambda=\sqrt{2\log(m)}/\sigma\). Substituting gives \(\sigma\sqrt{2\log m}\). For \(m=1\), the expected maximum is \(E[Z_1]=0\). \(\square\)

For variables with means \(\mu_i\) and individual parameters \(\sigma_i\), the same proof gives a more detailed form. For every \(\lambda>0\), $$ E[\max_i X_i] \leq\frac{1}{\lambda}\log\!\left( \sum_{i=1}^{m}\exp\!\left(\lambda\mu_i+\frac{\lambda^2\sigma_i^2}{2}\right) \right). $$ Indeed, apply the pointwise log-sum inequality to \(X_i\), take expectations using Jensen’s inequality, and use \(E[e^{\lambda X_i}]\leq\exp(\lambda\mu_i+\lambda^2\sigma_i^2/2)\). Taking the infimum over \(\lambda>0\) can yield a sharper bound when the means or scales differ.

Absolute Maxima and Common Pitfalls

A bound for the largest positive deviation is not automatically a bound for the largest absolute deviation. For each \(i\), sub-Gaussianity bounds both \(P(Z_i\geq t)\) and \(P(Z_i\leq-t)\). Applying the union bound to all \(2m\) events gives $$ P\!\left(\max_i|X_i-\mu_i|\geq t\right) \leq 2\sum_{i=1}^{m}\exp\!\left(-\frac{t^2}{2\sigma_i^2}\right) \leq 2m\exp\!\left(-\frac{t^2}{2\sigma^2}\right), $$ when every \(\sigma_i\leq\sigma\). The corresponding common-scale threshold for probability at most \(\delta\) is \(\sigma\sqrt{2\log(2m/\delta)}\).

• Mistake: requiring independence. The union bound is valid for dependent events. Independence is unnecessary for the maximum bounds derived here.
• Mistake: omitting the number of variables. Bounding one tail by \(\exp(-t^2/(2\sigma^2))\) does not by itself bound the chance that any of \(m\) variables exceeds \(t\). The union bound contributes the factor \(m\).
• Mistake: ignoring different means. A bound on \(\max_i(X_i-\mu_i)\) is not the same as a bound on \(\max_iX_i\) when the means differ. Center each variable or account for its mean in the threshold.
• Mistake: confusing one-sided and absolute maxima. The event \(\max_i Z_i\geq t\) only concerns positive deviations. For \(\max_i|Z_i|\), include lower-tail events too, producing the factor \(2\).

These results are useful whenever a statistic is selected as the largest among many candidates: the number of candidates affects the guarantee even if each candidate individually has a strong tail bound. The union-bound approach is simple and robust, while the expected-maximum argument supplies a complementary bound on average size. Both remain valid under dependence; any gains from a more detailed dependence structure require additional assumptions and analysis.