The infamous upper tail

Authors:
Publisher website
Google Scholar
Abstract
Let Γ be a finite index set and k ≥ 1 a given integer. Let further 𝒮 ⊆ [Γ]≤k be an arbitrary family of k element subsets of Γ. Consider a (binomial) random subset Γp of Γ, where p = (pi : i ∈ Γ) and a random variable X counting the elements of 𝒮 that are contained in this random subset. In this paper we survey techniques of obtaining upper bounds on the upper tail probabilities ℙ(X ≥ λ + t) for t > 0. Seven techniques, ranging from Azuma's inequality to the purely combinatorial deletion method, are described, illustrated, and compared against each other for a couple of typical applications. As one application, we obtain essentially optimal bounds for the upper tails for the numbers of subgraphs isomorphic to K4 or C4 in a random graph G(n, p), for certain ranges of p. © 2002 Wiley Periodicals, Inc. Random Struct. Alg., 20:317–342 2002

This publication has 14 references indexed in Scilit: