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) Inequalities; stochastic orderings (60E15) Combinatorial probability (60C05)

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

• 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?)
• 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 Inequalities and Martingale Inequalities: A Survey
• Concentration and moment inequalities for polynomials of independent random variables
• 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
• 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 Janson inequalities for general up-sets
• The Sharp Threshold for Maximum-Size Sum-Free Subsets in Even-Order Abelian Groups
• 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 lower tail: Poisson approximation revisited
• The reverse \(H\)-free process for strictly 2-balanced graphs
• The triangle-free process
• Weighted sums of certain dependent random variables
• When does the \(K_{4}\)-free process stop?

Cited in

(47)

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

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)