On the method of typical bounded differences

Abstract

Concentration inequalities are fundamental tools in probabilistic combinatorics and theoretical computer science for proving that random functions are near their means. Of particular importance is the case where f(X) is a function of independent random variables X=(X_1, ..., X_n). Here the well known bounded differences inequality (also called McDiarmid's or Hoeffding-Azuma inequality) establishes sharp concentration if the function f does not depend too much on any of the variables. One attractive feature is that it relies on a very simple Lipschitz condition (L): it suffices to show that |f(X)-f(X')| \leq c_k whenever X,X' differ only in X_k. While this is easy to check, the main disadvantage is that it considers worst-case changes c_k, which often makes the resulting bounds too weak to be useful. In this paper we prove a variant of the bounded differences inequality which can be used to establish concentration of functions f(X) where (i) the typical changes are small although (ii) the worst case changes might be very large. One key aspect of this inequality is that it relies on a simple condition that (a) is easy to check and (b) coincides with heuristic considerations why concentration should hold. Indeed, given an event Γthat holds with very high probability, we essentially relax the Lipschitz condition (L) to situations where Γoccurs. The point is that the resulting typical changes c_k are often much smaller than the worst case ones. To illustrate its application we consider the reverse H-free process, where H is 2-balanced. We prove that the final number of edges in this process is concentrated, and also determine its likely value up to constant factors. This answers a question of Bollobás and Erdős.

25 pages

References in corpus (7)

• An old approach to the giant component problem
• The condensation phase transition in random graph coloring
• When does the K_4-free process stop?
• The C_\ell-free process
• The Janson inequalities for general up-sets
• The evolution of subcritical Achlioptas processes
• The sharp threshold for maximum-size sum-free subsets in even-order abelian groups

Cited by in corpus (16)

• Provable Tensor Ring Completion
• Parameter Setting in Quantum Approximate Optimization of Weighted Problems
• Upper tails for arithmetic progressions in random subsets
• Almost all Steiner triple systems have perfect matchings
• Large girth approximate Steiner triple systems
• Packing nearly optimal Ramsey R(3,t) graphs
• Almost all Steiner triple systems are almost resolvable
• On the missing log in upper tail estimates
• Cutoff for Random Walk on Dynamical Erdős--Rényi Graph
• Upper tail bounds for Stars
• Prague dimension of random graphs
• Counting extensions revisited
• The jump of the clique chromatic number of random graphs
• On the concentration of the chromatic number of random graphs
• Cover and Hitting Times of Hyperbolic Random Graphs
• Efficiently Approximating Vertex Cover on Scale-Free Networks with Underlying Hyperbolic Geometry