On the method of typical bounded differences

DOI10.1017/S0963548315000103MaRDI QIDQ5366890zbMATH OpenOpenAlexFDO

Authors Lutz Warnke

Publication date 10 October 2017

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1212.5796

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Inequalities; stochastic orderings (60E15)

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 Gamma that holds with very high probability, we essentially relax the Lipschitz condition (L) to situations where Gamma 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'as and ErdH{o}s.

Recommendations

• When Janson meets McDiarmid: Bounded difference inequalities under graph-dependence
• scientific article; zbMATH DE number 1195776
• scientific article; zbMATH DE number 4170917
• An inequality for tail probabilities of martingales with bounded differences
• Concentration for self-bounding functions and an inequality of Talagrand

Cites work

• A Best Possible Kolmogoroff-Type Inequality for Martingales and a Characteristic Property
• A Large Deviation Inequality for Functions of Independent, Multi-Way Choices
• A new look at independence
• An old approach to the giant component problem
• Asymptotic packing via a branching process
• Asymptotic theory of finite dimensional normed spaces. With an appendix by M. Gromov: Isoperimetric inequalities in Riemannian manifolds
• Concentration and moment inequalities for polynomials of independent random variables
• Concentration Inequalities and Martingale Inequalities: A Survey
• Concentration of Measure for the Analysis of Randomized Algorithms
• Concentration of multivariate polynomials and its applications
• Concentration of non‐Lipschitz functions and applications
• Counting extensions
• Degree sequences of random digraphs and bipartite graphs
• Divide and conquer martingales and the number of triangles in a random graph
• Handbook of large-scale random networks
• scientific article; zbMATH DE number 4170917 (Why is no real title available?)
• scientific article; zbMATH DE number 1246230 (Why is no real title available?)
• scientific article; zbMATH DE number 1342092 (Why is no real title available?)
• scientific article; zbMATH DE number 1158743 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 903456 (Why is no real title available?)
• scientific article; zbMATH DE number 3198427 (Why is no real title available?)
• Longest cycles in sparse random digraphs
• Nearly perfect matchings in regular simple hypergraphs
• On Brooks' Theorem for Sparse Graphs
• On tail probabilities for martingales
• On the concentration of multivariate polynomials with small expectation
• On the size of a random maximal graph
• On the size of a random sphere of influence graph
• Phase diagram for the constrained integer partitioning problem
• Poisson approximation for large deviations
• Probabilistic analysis of power assignments
• Probability Inequalities for Sums of Bounded Random Variables
• Random maximalH-free graphs
• Random triangle removal
• Setting 2 variables at a time yields a new lower bound for random 3-SAT (extended abstract)
• Sharp concentration of the chromatic number on random graphs \(G_{n,p}\)
• The C_ℓ‐free process
• The chromatic number of random graphs
• The condensation phase transition in random graph coloring
• The deletion method for upper tail estimates
• The early evolution of the \(H\)-free process
• The evolution of subcritical Achlioptas processes
• The height of a random partial order: Concentration of measure
• The Janson inequalities for general up-sets
• The lower tail: Poisson approximation revisited
• The reverse \(H\)-free process for strictly 2-balanced graphs
• The Sharp Threshold for Maximum-Size Sum-Free Subsets in Even-Order Abelian Groups
• The triangle-free process
• Weighted sums of certain dependent random variables
• When does the \(K_{4}\)-free process stop?

Cited in

(49)

• Bounding one-way differences
• Upper tails for arithmetic progressions in random subsets
• Cutoff for random walk on dynamical Erdős-Rényi graph
• A sharp threshold for bootstrap percolation in a random hypergraph
• Loose cores and cycles in random hypergraphs
• Concentration inequalities for non-causal random fields
• Covering the edges of a random hypergraph by cliques
• Packing nearly optimal Ramsey R(3,t) graphs
• The \(Q_2\)-free process in the hypercube
• On the missing log in upper tail estimates
• Upper tail bounds for stars
• A gentle introduction to the differential equation method and dynamic concentration
• Moderate deviations of subgraph counts in the Erdős-Rényi random graphs \(G(n,m)\) and \(G(n,p)\)
• Short proofs of some extremal results. III
• scientific article; zbMATH DE number 1195776 (Why is no real title available?)
• A stronger bound for the strong chromatic index
• Large triangle packings and Tuza's conjecture in sparse random graphs
• Almost all Steiner triple systems are almost resolvable
• Closing the random graph gap in Tuza's conjecture through the online triangle packing process
• Large girth approximate Steiner triple systems
• The Sharp Threshold for Maximum-Size Sum-Free Subsets in Even-Order Abelian Groups
• On Induced Paths, Holes, and Trees in Random Graphs
• Probabilistic properties of highly connected random geometric graphs
• The condensation phase transition in random graph coloring
• A note on long cycles in sparse random graphs
• The impact of heterogeneity and geometry on the proof complexity of random satisfiability
• On the efficacy of higher-order spectral clustering under weighted stochastic block models
• A randomized construction of high girth regular graphs
• Counting extensions revisited
• The jump of the clique chromatic number of random graphs
• Site percolation on pseudo‐random graphs
• The number of n-queens configurations
• Hamilton completion and the path cover number of sparse random graphs
• Large monochromatic components in 3‐edge‐colored Steiner triple systems
• On the concentration of the chromatic number of random graphs
• Deviation probabilities for arithmetic progressions and other regular discrete structures
• Probability-of-failure-based optimization for random PDEs through concentration-of-measure inequalities
• The bright side of simple heuristics for the TSP
• Cover and hitting times of hyperbolic random graphs
• The degree-restricted random process is far from uniform
• Average distance in a general class of scale-free networks
• On edge collapse of random simplicial complexes
• Giant rainbow trees in sparse random graphs
• Average-case and smoothed analysis of graph isomorphism
• The completion numbers of Hamiltonicity and pancyclicity in random graphs
• Local convergence of random graph colorings
• Loose paths in random ordered hypergraphs
• Sharp phase transitions for the overlap gap property
• Sharp thresholds for the overlap gap property: Ising p-spin Glass and random k-SAT

This page was built for publication: On the method of typical bounded differences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5366890)