Concentration Inequalities for Negatively Dependent Random Variables

This direction is merged into another direction: dependent variable concentration. Its last version stays readable and citable here.

Version 1 of 136 papers54 conceptsfrozen 2026-10-04

In probability theory, we often assume that random variables are independent to make math tractable. However, in many real-world systems—from load balancing in distributed networks to sampling without replacement in surveys—variables are inherently dependent.

The breakthrough in this field is the realization that a specific type of "friendly" dependence, known as Negative Association (NA), actually makes systems more predictable than if they were independent. When variables exhibit mutual repulsion—where one being "high" makes others likely to be "low"—their sum concentrates around the mean even more tightly than a sum of independent variables.

The Intuition of Mutual Repulsion

The classic mental model for this is the "balls and bins" experiment. If you throw $n$ balls into $m$ bins, the number of balls in bin A and the number in bin B are not independent; if bin A is overfilled, there are fewer balls available for bin B.

As Devdatt Dubhashi and Desh Ranjan formalize in Balls and Bins: A Study in Negative Dependence, these occupancy variables are negatively associated. This "competitive" relationship prevents the variables from clustering together at extreme values. In Simple Proofs of Occupancy Tail Bounds, Dubhashi demonstrates that this property allows us to treat these dependent variables as if they were independent when calculating tail bounds.

Why Negative Dependence Works

The power of independence lies in the Chernoff-Hoeffding bounds, which provide sharp exponential guarantees that a sum won't deviate far from its expectation. Usually, these bounds require the joint distribution to factorize.

However, Devdatt Dubhashi, Volker Priebe, and Desh Ranjan showed in Negative Dependence Through the FKG Inequality that negative association is a sufficient condition to apply these same bounds. Mathematically, this works because the moment generating function of a sum of negatively associated variables is bounded by the product of their individual moment generating functions.

Essentially, negative dependence acts as a stabilizer. Because the variables "fight" each other for magnitude, the total sum is less likely to experience the "perfect storm" of all variables being large simultaneously. This is why Aryeh Kontorovich notes in Decoupling Maximal Inequalities that even simple negative pairwise covariance is often enough to keep the expected maximum of a system within a factor of 2 of the independent case.

Applications in Optimization and Sampling

This theoretical framework has profound implications for algorithm design, particularly in randomized rounding. When solving complex optimization problems like the knapsack problem, we often relax integer constraints to probabilities.

In Dependent randomized rounding for clustering and partition systems with knapsack constraints, David G. Harris and Aravind Srinivasan use negative association to ensure that while individual items are picked randomly, the total weight of the items stays strictly within the budget. Because the rounding process is designed to be negatively dependent, the probability of violating a constraint is exponentially small.

Similarly, in survey statistics, Patrice Bertail and Guillaume Papa show in Learning from Survey Training Samples that sampling without replacement creates a negatively associated dataset. This allows machine learning models trained on survey data to have rigorous generalization bounds, despite the data points not being "identically and independently distributed" (i.i.d.).

Relaxing the Conditions

Recent research has focused on making these tools more versatile by weakening the requirements for negative dependence.

By moving from the strict requirement of independence to the broader umbrella of negative dependence, researchers like Daniel Berend and Aryeh Kontorovich have been able to solve long-standing problems, such as proving the Concentration of the Missing Mass. They show that the "missing mass" (the probability of outcomes not yet seen in a sample) concentrates because the indicators for whether an outcome has been seen are negatively associated.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_concentration_inequalities_for_negativel_4b2e9de2,
  title = {Concentration Inequalities for Negatively Dependent Random Variables},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/concentration-inequalities-for-negatively-dependent-random-variables/rdr_4b2e9de2a17a4b758655c2516349b497},
  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_concentration_inequalities_for_negativel_4b2e9de2_v1,
  title = {Concentration Inequalities for Negatively Dependent Random Variables},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/concentration-inequalities-for-negatively-dependent-random-variables/rdr_4b2e9de2a17a4b758655c2516349b497/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}