Lagmental Vicfred

Hoeffding Gives Subgaussian Tails for Bounded Sums by Vicfred

tags: mathematics, concentration inequalities, tail bounds, martingales

Independent bounded summands concentrate around their expected sum. The example is deliberately concrete; it is a test of the statement, not a substitute for it.

Objects and notation

Tail bounds convert information about the moment-generating function \(M_X(\lambda)=\mathbf E[e^{\lambda X}]\) into estimates for \(\mathbf P(X\ge t)\). Stronger assumptions produce exponentially sharper bounds.

$$ X_i\in[a_i,b_i]\ \text{independent},\qquad S_n=\sum_iX_i $$

The first display fixes the mathematical data. I label it \(\mathsf{data}\) mentally, while the next is the \(\mathsf{claim}\); the bridge between them is the displayed \(\Longrightarrow\), not an automatic implication.

$$ \mathbf P(S_n-\mathbf E S_n\ge t)\le\exp\!\left(-\frac{2t^2}{\sum_i(b_i-a_i)^2}\right) $$

Push the symbols

An explicit case prevents the notation from becoming ceremonial. Every subscript and superscript in the display contributes to the value.

$$ X_i\in[0,1]\Longrightarrow\mathbf P\!\left(\left|\frac1n\sum_iX_i-\mathbf E X_1\right|\ge\varepsilon\right)\le2e^{-2n\varepsilon^2} $$

Structural reading

The compact alignment is a local map of the argument: assumptions on the first row, consequence on the second. Any generalisation must preserve that dependency.

$$ \begin{aligned} \mathsf{D}\;&:\quad X_i\in[a_i,b_i]\ \text{independent},\qquad S_n=\sum_iX_i,\\[5pt] \mathsf{C}\;&:\quad \mathbf P(S_n-\mathbf E S_n\ge t)\le\exp\!\left(-\frac{2t^2}{\sum_i(b_i-a_i)^2}\right). \end{aligned} $$

A hypothesis worth keeping

The parameter must be optimized only over values where the moment-generating function exists. Independence and boundedness hypotheses are not interchangeable.

$$ \boxed{\begin{gathered} \text{compact conclusion}\\[-2pt] \mathbf P(S_n-\mathbf E S_n\ge t)\le\exp\!\left(-\frac{2t^2}{\sum_i(b_i-a_i)^2}\right) \end{gathered}} $$

This is enough machinery for one note: an exact object, a worked case, a structural law, and a clearly marked boundary. Each layer can now be tested independently.

This article was posted on Wed 31 January 2024. Facts and circumstances may have changed since publication.
Please contact me before jumping to conclusions if something seems wrong or unclear.