In probability theory and theoretical computer science, McDiarmid's inequality (named after Colin McDiarmid ) is a concentration inequality which bounds the deviation between the sampled value and the expected value of certain functions when they are evaluated on independent random variables. McDiarmid's inequality applies to functions that satisfy a bounded differences property, meaning that replacing a single argument to the function while leaving all other arguments unchanged cannot cause too large of a change in the value of the function.
Statement A function f : X 1 × X 2 × ⋯ × X n → R {\displaystyle f:{\mathcal {X}}_{1}\times {\mathcal {X}}_{2}\times \cdots \times {\mathcal {X}}_{n}\rightarrow \mathbb {R} } satisfies the bounded differences property if substituting the value of the i {\displaystyle i} th coordinate x i {\displaystyle x_{i}} changes the value of f {\displaystyle f} by at most c i {\displaystyle c_{i}} . More formally, if there are constants c 1 , c 2 , … , c n {\displaystyle c_{1},c_{2},\dots ,c_{n}} such that for all i ∈ [ n ] {\displaystyle i\in [n]} , and all x 1 ∈ X 1 , x 2 ∈ X 2 , … , x n ∈ X n {\displaystyle x_{1}\in {\mathcal {X}}_{1},\,x_{2}\in {\mathcal {X}}_{2},\,\ldots ,\,x_{n}\in {\mathcal {X}}_{n}} ,
sup x i ′ ∈ X i | f ( x 1 , … , x i − 1 , x i , x i + 1 , … , x n ) − f ( x 1 , … , x i − 1 , x i ′ , x i + 1 , … , x n ) | ≤ c i . {\displaystyle \sup _{x_{i}'\in {\mathcal {X}}_{i}}\left|f(x_{1},\dots ,x_{i-1},x_{i},x_{i+1},\ldots ,x_{n})-f(x_{1},\dots ,x_{i-1},x_{i}',x_{i+1},\ldots ,x_{n})\right|\leq c_{i}.}
Extensions
Unbalanced distributions A stronger bound may be given when the arguments to the function are sampled from unbalanced distributions, such that resampling a single argument rarely causes a large change to the function value.
This may be used to characterize, for example, the value of a function on graphs when evaluated on sparse random graphs and hypergraphs, since in a sparse random graph, it is much more likely for any particular edge to be missing than to be present.
Differences bounded with high probability McDiarmid's inequality may be extended to the case where the function being analyzed does not strictly satisfy the bounded differences property, but large differences remain very rare.
There exist stronger refinements to this analysis in some distribution-dependent scenarios, such as those that arise in learning theory.
Sub-Gaussian and sub-exponential norms Let the k {\displaystyle k} th centered conditional version of a function f {\displaystyle f} be
… excerpt ends here. Continue reading the full article.
