Sharp lower bounds for tiny upward deviations

Sharp lower bounds for tiny upward deviations

Introduction

If you’ve ever tried to answer a “small risk” question—like “how unlikely is it that a bunch of independent things add up to noticeably more than expected?”—you’ve bumped into small-deviation inequalities. The new research in this arXiv paper tackles exactly that, but in a particularly delicate setting: sums of independent nonnegative random variables under only first-moment (mean) constraints.

More concretely, the paper studies independent nonnegative random variables (X1,\dots,Xn) with the condition (\mathbb{E}Xi \le 1) for each (i). Let
[
S=\sum{i=1}^n X_i.
]
The authors prove a sharp lower bound on the probability that (S) stays below a slightly increased level (\mathbb{E}S+\delta). Here “slightly” means (\delta>0), and the result behaves differently depending on whether (\delta\ge 1) or not.

What makes this feel “fresh” is that it settles a sharp form of a long-standing conjecture originally due to Feige (and closely related conjectures), at least throughout the regime (\delta \ge 1). The proof also uses two modern ideas that feel very current: a recent calibration result for a mean-constrained hypothesis test (solving Gaffke’s conjecture) plus a convex-geometry tool (Grünbaum’s centroid theorem).

Why This Matters

This kind of inequality matters right now because lots of modern decision systems—especially in AI-adjacent optimization—operate in regimes where you only trust first-moment information. Think: you can bound expected cost, expected loss, expected load, or expected slack, but you may have no reliable handle on higher moments like variance or tails. Yet you still want “small deviation” guarantees: How confidently can I say the total won’t overshoot by a moderate amount?

A practical scenario: imagine a resource scheduler that assigns multiple independent tasks to servers. Each task consumes a random amount of compute/memory, with nonnegative loads, and you have an upper bound on each task’s expected load (say, (\mathbb{E}X_i \le 1) after normalization). You might care about the probability that the total load (S) exceeds (\mathbb{E}S+\delta) by a modest (\delta\ge 1). The paper’s result gives a distribution-free handle on that probability, which is exactly what you need when you can’t assume nice distributions.

And where does this build compared to previous AI research? In the ML world, a lot of “probability of bad events” work assumes sub-Gaussian behavior, log-concavity, or specific distribution families. This paper instead goes in the opposite direction: it starts from just independence + nonnegativity + mean constraints, then derives sharp probability bounds. That’s philosophically aligned with the broader push in AI for robust, distribution-free guarantees—except here the authors go further by proving sharpness (optimal bounds), not just correctness.

Main Result: The sharp two-branch probability lower bound for (S)

The core object is the event that the sum stays below a shifted threshold:
[
S < \mathbb{E}S + \delta.
]
Under the assumptions of the theorem in the paper (independent, nonnegative, and (\mathbb{E}X_i \le 1)), the authors prove a tight (optimal) lower bound on the probability of that event.

While the statement in the excerpt you provided is partially formatted, the logic is clear: the bound splits into two regimes—one branch for (\delta \in (0,1)) and another for (\delta\ge 1)—and the paper establishes that for (\delta\ge 1) the bound matches the best conjectured form. In fact, the authors emphasize:
- For every (n) and every (\delta\ge 1), the bound is optimal.
- They connect this directly to Feige’s conjectured sharp universal bound.

Comparing what’s conjectured vs. proved (and where)

The paper discusses Feige’s conjecture, and the improvement/precision achieved depends on the size of (\delta). In the excerpt, the paper notes their theorem proves the conjecture throughout (\delta \ge 1), and for (0<\delta<1) they obtain a weaker constant compared to Feige’s conjectured expression.

Here’s the comparison in the form the paper describes:

This “two-branch” phenomenon isn’t just cosmetic—it corresponds to what kinds of extremal configurations (the worst-case distributions) can produce the largest deviation.

The intuition behind the (\delta\ge 1) “(e^{-1})” behavior

A neat conceptual clue appears in the paper’s discussion of an extremal example. When the mean of each (X_i) is exactly 1, the paper notes that the event
[
S < \mathbb{E}S + \delta \quad \text{(in a certain exact boundary setting)}
]
behaves in a way that forces extremality: essentially, for the threshold to be violated in the “most adversarial” case, the random variables must “turn on” simultaneously in a way that clashes with the mean constraint unless the variables are trivial.

The upshot: in the regime (\delta\ge 1), the optimal universal bound lands on a familiar constant—(e^{-1})—and the paper explains that at (\delta=1) the geometry of a simplex and its centroid aligns perfectly with the threshold hyperplane.

So, why should (e^{-1}) even show up in probability bounds for sums? Because the proof machinery routes the probabilistic problem through geometry of convex sets, and in that route the function that controls “how much volume lies on one side of a hyperplane” naturally yields terms like ((n/(n+1))^n), which converge to (e^{-1}) and remain sharp for finite (n).

In short: the sharp constant is forced by convex-geometric volume ratios, not by distribution-specific tail behavior.

How the proof works (without turning your brain into toast)

The proof strategy is a high-level “pipeline”:

1. Reduce the probabilistic problem to bounding a certain geometric quantity that looks like a normalized volume of a polytope slice.
2. Use a modern calibration result (from Vlassis and Thomas) that gives the best possible inequality for independent nonnegative variables under mean constraints.
3. Upper-bound the geometric volume using a centroid theorem and a generalized Grünbaum inequality.
4. Combine everything, take complements, and convert back into the probability statement for (S).

Let’s unpack the two key ingredients that do most of the heavy lifting.

Ingredient A: Vlassis–Thomas calibration using a Dirichlet simplex

The paper uses a theorem from Vlassis and Thomas (actually referenced as [VT26] in the excerpt) that transforms mean-constrained independent nonnegative variables into a statement about a random point on a simplex.

They define a random vector (D=(D0,\dots,Dn)) uniformly on the standard simplex (\Delta_n). In the excerpt’s notation, (D) is distributed as (\mathrm{Dir}(1,\dots,1)), the Dirichlet distribution with all parameters 1 (i.e., uniform over the simplex).

Then they consider a function (Kn(x)) that corresponds to the normalized volume of a region carved out by inequalities involving (\sum xi Di). The Vlassis–Thomas theorem says: roughly speaking,
- the probability that (\sum Xi) exceeds a mean-shifted threshold is controlled by (K_n) evaluated at a scaled vector built from the means.

In the paper’s flow, once you set (\mui = \mathbb{E}Xi) and normalize with (Yi = Xi/\mui) (when needed), the event ({S \ge \mathbb{E}S + \delta}) implies a condition like
[
\sum{i=1}^n \text{(something built from } Y_i\text{)} \ge n+\delta.
]
That “(n+\delta)” is the trigger that forces the geometry to land in the right region.

Ingredient B: Grünbaum’s centroid theorem (and a modern generalization)

Now for the geometry. Grünbaum’s centroid theorem is a classic result in convex geometry: it tells you, for a convex body with centroid at the origin, how much volume must lie in any halfspace that “cuts” through in a particular way.

The paper uses Grünbaum’s theorem in a generalized form by Letwin and Yaskin [LY24]. In the excerpt, the generalized Grünbaum inequality is applied to a shifted simplex so that its centroid sits at the origin, which makes the theorem directly usable.

There’s a particularly clean moment at (\delta=1). In that case, the hyperplane cut passes through the centroid exactly, so Grünbaum’s inequality becomes tight and yields an expression of the form
[
1 - \left(\frac{n}{n+1}\right)^n \le 1-e^{-1}.
]
For larger (\delta), the generalized inequality adjusts the constant, and after algebra and the Vlassis–Thomas calibration, this produces the claimed sharp probability bound.

Putting it together

After bounding (Kn(Y)) by something like (1-b{n,\delta}), they use the Vlassis–Thomas theorem to upper-bound
[
\mathbb{P}(S \ge \mathbb{E}S + \delta)
]
by (1 - b_{n,\delta}). Then they take complements to get a lower bound for
[
\mathbb{P}(S < \mathbb{E}S + \delta).
]

So the “moral” is:
mean constraints → simplex calibration → centroid/volume bound → sharp small-deviation inequality.

Extremality and optimality: why the bound can’t be improved for (\delta\ge 1)

The paper not only proves the inequality—it also argues sharpness: for (\delta\ge 1), the bound is optimal, meaning you can’t hope for a better universal constant that works for all independent nonnegative random variables with the given mean constraint.

The excerpt hints at why that’s believable: there are configurations where the inequality becomes an equality-like situation, tied to how the simplex slice aligns with the centroid at (\delta=1), and more generally to how the generalized Grünbaum inequality becomes tight for the relevant slice geometry.

This is an important distinction. Many inequalities in probability are “correct but not tight.” Here, the authors work hard to match the conjectured extremal behavior, and they tie it back to sharp convex geometry.

About “AI use” and formal verification (yes, it’s relevant)

The paper includes a statement about AI assistance: the initial proof was found by ChatGPT 5.6 Pro, and then the authors checked, revised, and rewrote the argument themselves.

Also, the paper mentions an accompanying Lean formalization (available via GitHub: https://github.com/pengzhang91/Feige) that provides an end-to-end formal proof of Feige’s conjecture for the relevant range. That matters for credibility in a research area like this, because the proof is a careful chain of nontrivial results from both probability and convex geometry—formal proof is a strong “no gaps” signal.

Key Takeaways

• Sharp small-deviation bounds: For independent nonnegative (Xi) with only first-moment constraints ((\mathbb{E}Xi\le 1)), the paper proves a sharp lower bound on (\mathbb{P}(S < \mathbb{E}S+\delta)).
• The regime (\delta\ge 1) is fully optimal: The result matches the sharp form predicted by Feige’s conjecture throughout (\delta\ge 1), with the universal constant behavior connecting to the (e^{-1}) branch.
• The proof is probability + geometry: The core method routes the deviation problem through simplex volume functions (K_n(x)), using:
  • the Vlassis–Thomas theorem (a calibration result related to Gaffke’s conjecture), and
  • Grünbaum’s centroid theorem plus a generalized Grünbaum inequality.
• Practical “robustness” value: In real systems where you only trust means (not tail assumptions), and where variables are nonnegative and independent, this gives a distribution-free way to bound the chance of a moderate overshoot.
• Stronger than “just a bound”: The paper doesn’t settle for approximations—at least for (\delta\ge 1), it pins down the best possible universal constant, and the authors also report Lean formalization of the key proof chain.

If you want, I can also rewrite the main theorem statement in a clean, fully readable formula form (it got garbled in the excerpt formatting) and illustrate with a couple toy examples of distributions that approach the bound.