Concentration Bounds Under Negative Dependence

108 concepts64 papers2 proposals

When analyzing randomized algorithms or statistical models, we frequently rely on concentration inequalities—such as the Chernoff, Hoeffding, or Bernstein bounds—to prove that a sum of random variables stays close to its expected value. Traditionally, these powerful tools require the underlying variables to be strictly independent. But in many real-world systems, variables are inherently entangled.

Consider the classic "balls and bins" experiment. If we throw $n$ balls into $m$ bins, the occupancy states of the bins are not independent: if one set of bins is overfilled, the remaining disjoint set of bins is more likely to be underfilled. This is an intuitive form of negative dependence.

Remarkably, this kind of dependence does not destroy concentration; it enhances it. Because the variables experience a form of mutual repulsion, they are prevented from clustering together in extreme configurations. As a result, their sum concentrates around the mean at least as strongly as if they were independent, allowing researchers to safely apply standard independent tail bounds to deeply dependent systems.

Formalizing the Repulsion: Negative Association

To transform this physical intuition into a rigorous mathematical framework, Devdatt Dubhashi et al. formalized the concept of Negative Association (NA) in Balls and Bins: A Study in Negative Dependence.

A collection of random variables $X_1, X_2, \dots, X_n$ is said to be negatively associated if, for any two disjoint subsets of variables $A$ and $B$, and any two coordinate-wise non-decreasing functions $f$ and $g$, the covariance is non-positive:

$$\text{Cov}(f(X_A), g(X_B)) \le 0$$

This definition captures the idea that increasing the variables in subset $A$ forces the variables in subset $B$ to decrease. In Negative Dependence Through the FKG Inequality, Devdatt Dubhashi et al. demonstrated that for binary indicator variables, this condition simplifies significantly: negative association is mathematically equivalent to simple negative correlation between pairs, allowing researchers to establish strong joint dependence properties through basic pairwise covariance checks.

Why It Works: Moment-Generating Function Domination

The core reason why negatively associated variables satisfy independent tail bounds lies in the behavior of their joint moment-generating function (MGF).

For a set of independent variables, the MGF of their sum factors exactly into the product of their individual MGFs due to independence:

$$\mathbb{E}\left[e^{t \sum X_i}\right] = \prod \mathbb{E}\left[e^{t X_i}\right]$$

When variables are negatively associated, their mutual repulsion ensures that they cannot simultaneously take large values. Mathematically, this forces the joint expectation of their exponential functions to be bounded above by the product of their individual expectations:

$$\mathbb{E}\left[e^{t \sum_{i=1}^n X_i}\right] \le \prod_{i=1}^n \mathbb{E}\left[e^{t X_i}\right]$$

As highlighted by Devdatt Dubhashi in Simple Proofs of Occupancy Tail Bounds, this product-domination property means that when you apply the standard Chernoff bounding trick, the dependent joint distribution behaves even more tightly than an independent one. This provides a clean, calculation-free justification for treating dependent indicators as independent when computing upper tail bounds.

Broadening the Taxonomy of Dependence

While Negative Association elegantly covers occupancy models and permutations, many stochastic processes exhibit negative correlations that do not fit strictly within its algebraic constraints. This has motivated the development of a broader hierarchy of negative dependence structures:

High-Dimensional Extensions and Matrix Concentration

The frontier of this research direction extends these scalar concepts to matrix-valued random variables, which are critical for analyzing graphs and high-dimensional data. This is often studied via Strongly Rayleigh distributions—the strongest mathematical formulation of negative dependence, which remains stable under marginalization and conditioning (e.g., the distribution of edges chosen in a random spanning tree).

In A Matrix Chernoff Bound for Strongly Rayleigh Distributions and Spectral Sparsifiers from a few Random Spanning Trees, Rasmus Kyng et al. successfully extended matrix concentration inequalities to Strongly Rayleigh environments. They proved that a sum of random matrices drawn from these distributions concentrates around its expected matrix.

However, the authors noted a fascinating efficiency tradeoff: the resulting bounds carry an additional logarithmic factor in the exponent compared to purely independent matrix sums. This suggests that while negative dependence physically prevents the clustering of eigenvalues, current high-dimensional mathematical tools are still evolving to fully capture its complete efficiency relative to independent sampling.

Applications Across Computer Science

Understanding concentration under negative dependence has unlocked solutions to several long-standing algorithmic and statistical challenges:

  • Randomized Rounding in Optimization: When rounding fractional solutions of linear programs to integers, maintaining global resource constraints is notoriously difficult. In Random Walks in Polytopes and Negative Dependence, Yuval Peres et al. designed Gaussian random walks over matroid polytopes that inherently output negatively associated distributions. This ensures that the rounded integer solutions inherit the desirable properties of the fractional solution with high probability. This mechanism underpins modern breakthroughs in online matching and edge coloring, such as those developed by Amin Saberi et al. in The Greedy Algorithm Is not Optimal for On-Line Edge Coloring.
  • Streaming Algorithms: Data stream sketch structures suffer from complex counter correlations due to shared update rules. In A Formal Analysis of the Count-Min Sketch with Conservative Updates, Younes Ben Mazziane et al. applied negative association to model these conditional updates, proving that counter values vary in opposite directions and yielding significantly tighter error bounds for tracking heavy hitters.
  • Statistical Generalization: In vocabulary estimation and language modeling, the "missing mass" (the total probability of unseen items in a sample) is a sum of highly dependent indicators. David A. McAllester et al. in Concentration Inequalities for the Missing Mass and for Histogram Rule Error utilized negative association to establish distribution-free concentration bounds for the missing mass, proving it converges to its expectation far more tightly than traditional independent models would predict.

Key Foundational Work

Balls and Bins: A Study in Negative Dependence (1996) — contributed 5 concept elements to this direction.
Simple Proofs of Occupancy Tail Bounds (1995) — contributed 4 concept elements to this direction.
Negative Dependence Through the FKG Inequality (1996) — contributed 4 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_dependent_variable_concentration_069ab937,
  title = {dependent variable concentration},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/dependent-variable-concentration/rdr_069ab9374eca4950ac7e81b2d64a036b},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 1, frozen text):

@misc{lacuna_dependent_variable_concentration_069ab937_v1,
  title = {dependent variable concentration},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/dependent-variable-concentration/rdr_069ab9374eca4950ac7e81b2d64a036b/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake