PreprintarXiv licencearXiv
Sharp Tail Bounds Beyond Twice the Mean
Abstract
Consider n independent, non-negative, mean at most one random variables, X1,X2,…. We show the following bound on the probability of their sum exceeding a threshold t: ℙ[∑i=1n Xi≥ t] ≤ 1−(1−1/t)n for all t≥ 2n+1 . To prove this, we consider a relaxed optimization problem over a set of sequences of ordered, but non-independent random variables. This allows us to reformulate it recursively as dynamic programming problem. The bound becomes an equality for the binary i.i.d.~random variables satisfying ℙ[Xi=0]= 1−1/t and ℙ[Xi=t]=1/t, which remains the maximizer in the relaxed problem.
Related
- Sharp Harmonic-Mean Bounds for Neumann Eigenvalues on Riemannian Surfaces and Counterexamples to Geodesic Ball Optimality on Higher-Dimensional Spheres
- Sharp mean-width and Jacobian bounds for Euclidean and hyperbolic harmonic maps
- The asymptotic in Waring's problem over function fields beyond twice the degree
- A Proof of the Erdős Matching Conjecture for Large Matchings via Sharp Tail Probability for Sums of i.i.d. Nonnegative Random Variables
- Sums of two dependent uniform random variables: a characterization by joint tail bounds
BibTeX
@misc{strack2026sharp,
title = {{Sharp Tail Bounds Beyond Twice the Mean}},
author = {Philipp Strack and Jannik M. Westermann},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2608.06317},
eprint = {2608.06317},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.06317},
}
RIS
TY - UNPB
TI - Sharp Tail Bounds Beyond Twice the Mean
AU - Philipp Strack
AU - Jannik M. Westermann
PY - 2026
DA - 2026/09/18
PB - arXiv
DO - 10.48550/arxiv.2608.06317
UR - https://arxiv.org/abs/2608.06317
AB - Consider n independent, non-negative, mean at most one random variables, X_1,X_2,…. We show the following bound on the probability of their sum exceeding a threshold t: ℙ[∑_i=1^n X_i≥ t] ≤ 1−(1−1/t)^n for all t≥ 2n+1 . To prove this, we consider a relaxed optimization problem over a set of sequences of ordered, but non-independent random variables. This allows us to reformulate it recursively as dynamic programming problem. The bound becomes an equality for the binary i.i.d.~random variables satisfying ℙ[X_i=0]= 1−1/t and ℙ[X_i=t]=1/t, which remains the maximizer in the relaxed problem.
ER -