Lagmental Vicfred

Chernoff Bounds Optimize an Exponential Moment by Vicfred

tags: mathematics, concentration inequalities, tail bounds, martingales

Exponentiating a tail event introduces a free parameter that can be minimized. I will separate the object being defined from the consequence being claimed.

The data

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.

$$ \lambda>0,\qquad M_X(\lambda)=\mathbf E[e^{\lambda X}] $$

The typography mirrors the proof: first declare \(\mathsf D\), then state \(\mathsf C\). The symbol \(\Longrightarrow\) below is a logical dependency, not extra mathematical structure.

$$ \mathbf P(X\ge t)\le\inf_{\lambda>0}e^{-\lambda t}M_X(\lambda) $$

Derivation

This is the algebraic core of the note. Once this line is correct, the surrounding interpretation has something solid to refer to.

$$ \mathbf P(X\ge t)=\mathbf P(e^{\lambda X}\ge e^{\lambda t})\le e^{-\lambda t}\mathbf E[e^{\lambda X}] $$

Invariant content

The formula is reusable precisely because it says which pieces are structural and which belong only to the worked example.

$$ \begin{aligned} \mathsf{D}\;&:\quad \lambda>0,\qquad M_X(\lambda)=\mathbf E[e^{\lambda X}],\\[5pt] \mathsf{C}\;&:\quad \mathbf P(X\ge t)\le\inf_{\lambda>0}e^{-\lambda t}M_X(\lambda). \end{aligned} $$

Scope

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(X\ge t)\le\inf_{\lambda>0}e^{-\lambda t}M_X(\lambda) \end{gathered}} $$

The notation is dense, but it is doing honest work: every delimiter records scope and every index records dependence. Removing one should require a mathematical reason.

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