Premium
The infamous upper tail
Author(s) -
Janson Svante,
Ruciński Andrzej
Publication year - 2002
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.10031
Subject(s) - mathematics , combinatorics , upper and lower bounds , binomial (polynomial) , random graph , discrete mathematics , random variable , integer (computer science) , graph , struct , statistics , mathematical analysis , computer science , programming language
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 = ( p i : 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 K 4 or C 4 in a random graph G ( n , p ), for certain ranges of p . © 2002 Wiley Periodicals, Inc. Random Struct. Alg., 20:317–342 2002