An asymptotically optimal bound for the concentration function of a sum of independent integer random variables

This paper proves an asymptotically optimal bound for the concentration function of a sum of independent integer random variables, confirming that the sum's maximum point probability is bounded by that of a corresponding sum of minimal-variance variables when the total variance is sufficiently large, thereby extending the result to separable Hilbert spaces.

The Gist

Imagine you are running a massive lottery where thousands of people are buying tickets. Each person has a specific "luckiness" limit: they can't be too lucky (they can't win the jackpot every time), but they have a certain maximum probability of winning a small prize.

Now, imagine you add up all the winnings from these thousands of people. The big question this paper answers is: What is the absolute worst-case scenario for the total sum? In other words, what is the highest possible chance that the total sum of all winnings lands on one specific number (like exactly $1,000,000)?

The author, Valentas Kurauskas, proves a mathematical rule that tells us exactly how "clumped" or "concentrated" this total sum can be.

Here is the breakdown using simple analogies:

1. The "Clumping" Problem (Concentration)

Think of a random variable as a bag of marbles. Some numbers have many marbles (high probability), and some have few.

• The Goal: We want to know the maximum number of marbles that can pile up on a single number in the final bag after mixing everyone's bags together.
• The Constraint: We know that for every individual person (random variable), their bag can't have more than, say, 10% of the marbles on any single number.

2. The "Perfectly Balanced" Counter-Example

The paper asks: How do we arrange the individual bags to make the final pile as "clumpy" as possible?

The author proves that to get the maximum clumpiness, you shouldn't use complicated, weird distributions. Instead, you should use the simplest, most "spread out" distributions possible that still respect the 10% limit.

• The Analogy: Imagine you have a bucket of water (probability mass) and a cup with a hole (the limit). To make the water pile up as high as possible in the final bucket, you shouldn't pour it in a fancy spiral. You should pour it in the most uniform, flat way possible (like a uniform distribution) or a simple two-step distribution.
• The "Minimum Variance" Trick: The paper shows that the "worst-case" scenario happens when each individual bag is arranged to have the smallest possible spread (variance) while still obeying the rules. It's like trying to make a stack of coins wobble as little as possible; the most stable (least wobbly) stack is the one that ends up being the tallest.

3. The "Asymptotically Optimal" Discovery

The title mentions "asymptotically optimal." This is a fancy way of saying: "It works perfectly when the numbers get huge."

• The Small Scale: If you only have 5 people, the math is messy. The "perfect" arrangement might depend on weird details.
• The Large Scale: If you have 1,000,000 people, the messy details wash away. The paper proves that if the total "spread" (variance) of the system is large enough, the clumpiness of the real-world sum will be almost identical (within a tiny error margin) to the clumpiness of our "perfectly balanced" theoretical model.

Think of it like a crowd of people walking in a field. If there are only 3 people, they might walk in a weird zig-zag. But if there are 10,000 people, they will naturally form a smooth, predictable bell curve. This paper calculates exactly how "smooth" that curve can get before it hits a wall.

4. The "Magic" of Rearrangement

The paper uses a concept called rearrangement.

• The Metaphor: Imagine you have a pile of sand. You can move the grains around. The paper proves that if you want to make the pile as tall as possible at the peak, you should move the sand so that it forms a perfect, symmetrical pyramid (or a specific "staircase" shape) rather than a jagged, uneven rock.
• The author proves that no matter how messy the individual inputs are, you can always "rearrange" them into this perfect shape to find the maximum possible height.

5. The "Hilbert Space" Twist

The paper also mentions "separable Hilbert spaces."

• The Analogy: Usually, we think of numbers on a line (1D). But what if the numbers are points in a 3D room, or even a 100-dimensional room?
• The paper shows that the same rules apply! Whether you are adding up numbers on a line or adding up vectors in a complex, multi-dimensional universe, the "clumping" behavior follows the same logic. The dimension of the room doesn't change the fundamental rule; it just changes the shape of the "pyramid."

The Big Takeaway

Before this paper, mathematicians had good guesses and partial answers, but they weren't sure if the "simplest" arrangement was truly the worst-case scenario for large numbers.

This paper confirms:
If you have a huge sum of independent random events, the maximum chance of hitting a specific number is determined by the simplest, most "compact" versions of those events. If the total variance is large enough, the real-world answer is almost exactly the same as the theoretical best-case scenario.

It's like saying: "If you mix enough ingredients, the recipe for the 'most concentrated' flavor is always the one where the ingredients are arranged in the most orderly, least chaotic way possible."

Technical Summary

Here is a detailed technical summary of the paper "An asymptotically optimal bound for the concentration function of a sum of independent integer random variables" by Valentas Kurauskas.

1. Problem Statement and Context

The Core Problem:
The paper addresses the concentration function problem for sums of independent random variables. For a random variable $X$, the concentration function at a point is defined as $Q(X) = \sup_{x \in \mathbb{R}} P(X=x)$. The central question is: given independent integer random variables $X_1, \dots, X_n$ with constraints $Q(X_i) \le \alpha_i$ (where $\alpha_i \in (0, 1]$), what is the maximum possible value of $Q(S_n)$ where $S_n = \sum X_i$?

The Conjecture:
The paper focuses on a conjecture proposed by Juškevičius (2023). The conjecture posits that the maximum concentration is achieved when the summands are "extremal" distributions that minimize variance. Specifically, if $Y_i$ are independent random variables such that $Q(Y_i) = \alpha_i$ and $Y_i$ has the minimum possible variance among all distributions satisfying this constraint (denoted as $\nu_{\alpha_i}$), then:
$$Q\left(\sum_{i=1}^n X_i\right) \le Q\left(\sum_{i=1}^n \epsilon_i Y_i\right)$$
where $\epsilon_i \in \{-1, 1\}$ are signs chosen to maximize the concentration of the sum of the $Y_i$'s.

The Gap:
While exact results exist for specific cases (e.g., uniform distributions or specific intervals), a general proof for arbitrary sequences $\alpha_i$ had remained open. Previous bounds were often suboptimal by a constant factor.

2. Main Result

The author proves the conjecture asymptotically.

Theorem 1.1:
For any $\delta > 0$, there exists a threshold variance $V_0(\delta)$ such that if the variance of the sum of the extremal variables $Y = \sum Y_i$ satisfies $\text{Var}(Y) \ge V_0(\delta)$, then:
$$Q\left(\sum_{i=1}^n X_i\right) \le (1 + \delta) Q\left(\sum_{i=1}^n \epsilon_i Y_i\right)$$
for some choice of signs $\epsilon_i \in \{-1, 1\}$.

Corollary:
This result extends to random elements in a separable Hilbert space, implying that the asymptotically optimal bound holds regardless of the dimension of the space, provided the variance of the sum is sufficiently large.

3. Methodology and Technical Approach

The proof is divided into two parts: Part I (Main Proof Structure) and Part II (The Core Technical Lemma). The methodology relies on a sophisticated combination of probability theory, combinatorics, and approximation theory.

A. Reduction to Extremal and Balanced Sequences

• Extremal Measures: The author defines $\nu_\alpha$ as the distribution with mass $\alpha$ on $\lfloor \alpha^{-1} \rfloor$ points and the remainder on one point. This distribution minimizes variance for a fixed concentration bound.
• Balanced Sequences: The proof utilizes the concept of "balanced" sequences where the summands can be paired such that their distributions are symmetric (e.g., $X \sim -X'$).
• Rearrangement Inequalities: The paper employs the Hardy-Littlewood-Pólya (HLP) rearrangement inequality and its generalizations (Theorem 2.16) to show that symmetrizing and rearranging distributions generally increases concentration.

B. Approximation by Discretized Gaussian

A crucial step involves approximating the sum of independent lattice random vectors by a discretized multivariate Gaussian distribution.

• Theorem 3.1: The paper utilizes a recent result by Barbour, Luczak, and Xia (based on Stein's method) to bound the Total Variation (TV) distance between the sum of independent lattice vectors and a rounded Gaussian vector.
• Condition: This approximation is valid only if the summands are not "too concentrated" on a proper sublattice. The proof involves grouping variables to ensure the summands generate the full lattice $\mathbb{Z}^d$.

C. Inverse Littlewood–Offord Theory

To handle the structure of the summands, the paper applies the Inverse Littlewood–Offord theorem (Nguyen and Vu).

• Lemma 3.5: If the concentration of the sum is high, the support of the individual random variables must be contained within a Symmetric Generalized Arithmetic Progression (GAP) of low rank and bounded volume.
• This allows the author to reduce the general problem to a setting where the random variables have bounded support and specific structural properties.

D. Local Limit Theorems and Log-Concavity

• Log-Concavity: The extremal distributions $\nu_\alpha$ are log-concave. The paper leverages properties of log-concave measures (strong unimodality) to bound the concentration function using the variance (Lemma 2.7).
• Odlyzko-Richmond Theorem: The proof uses a theorem regarding the log-concavity of $n$-fold convolutions (Theorem 3.7) to establish that the distribution of the sum becomes unimodal and "flat" near the mode for large $n$.
• Berry-Esseen Theorem: Used to approximate the discrete distribution of the sum by a normal distribution, providing error bounds for the concentration function.

E. The "Gap" Argument (Lemma 2.26)

The core of the technical difficulty lies in Lemma 2.26, which establishes that for "strongly balanced" sequences with quantized parameters, the concentration of any sum $S$ is dominated by the concentration of the extremal sum $S'$.

• The proof constructs a coupling between the arbitrary sum and the extremal sum.
• It uses a "probabilistic method" to show that if the variance is large, the difference in concentration is negligible ($\epsilon$-domination).
• It handles the case where the summands might lie on a sublattice by grouping them into blocks to ensure the sum generates the full lattice, allowing the application of the multivariate local limit theorem.

4. Key Contributions

1. Asymptotic Proof of Juškevičius's Conjecture: The paper provides the first proof that the conjecture holds asymptotically as the variance of the sum grows.
2. Optimality up to $(1+\delta)$: It establishes that the bound is tight up to an arbitrarily small factor $(1+\delta)$, improving upon previous results that had constant factors (e.g., up to $2\sqrt{6}/3$).
3. Generalization to Hilbert Spaces: The result is shown to hold for random variables in infinite-dimensional separable Hilbert spaces, a significant generalization of previous integer-only results.
4. Synthesis of Advanced Tools: The work successfully integrates:
   • Inverse Littlewood–Offord theory (structural constraints).
   • Multivariate Local Limit Theorems (Gaussian approximation).
   • Rearrangement inequalities (symmetrization).
   • Log-concavity properties (unimodality).

5. Significance

• Theoretical Impact: This resolves a long-standing open problem in the theory of concentration of measure. It clarifies the relationship between the variance of summands and the maximum concentration of their sum.
• Methodological Advance: The paper demonstrates a powerful framework for handling "non-symmetric" extremal problems by reducing them to "balanced" cases via rearrangement and grouping techniques.
• Limitations and Future Work: The constant $V_0(\delta)$ derived in the proof is huge and non-explicit. The author notes that proving the exact conjecture (without the $1+\delta$ factor) likely requires methods beyond the current scope. However, the asymptotic result is sufficient for many applications in high-dimensional probability and combinatorics.

In summary, Kurauskas provides a rigorous, albeit technically dense, proof that the "worst-case" concentration of a sum of independent integer variables is asymptotically achieved when the variables are distributed to minimize their variance, confirming a major conjecture in the field.