The infamous upper tail. (English) Zbl 0996.60023

Janson, Svante; Ruciński, Andrzej

Random Struct. Algorithms 20, No. 3, 317-342 (2002).

Authors’ summary: Let \(\Gamma\) be a finite index set and \(k\geq 1\) a given integer. Let further \({\mathcal S}\subseteq [\Gamma]^{\leq k}\) be an arbitrary family of \(k\) element subsets of \(\Gamma\). Consider a (binomial) random subset \(\Gamma_{{\mathbf p}}\) of \(\Gamma\), where \({\mathbf p}= (p_i:i\in \Gamma)\), and a random variable \(X\) counting the elements of \({\mathcal S}\) that are contained in this random subset. We survey techniques of obtaining upper bounds on the upper tail probabilities \(\mathbb{P} (X\geq \lambda+ 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\).

Reviewer: Lars Holst (Stockholm)

MSC:

60E15	Inequalities; stochastic orderings
60C05	Combinatorial probability

Keywords:

random graphs; tail probabilities

References:

[1]	Bennett, J Am Stat Assoc 57 pp 33– (1962)
[2]	Boucheron, Random Struct Alg 16 pp 277– (2000) · Zbl 0954.60008
[3]	Erd?s, Publ Math Inst Hung Acad Sci 5 pp 17– (1960)
[4]	and Sharp thresholds for Ramsey properties, in preparation.
[5]	and Ramsey games against one-armed bandit, in preparation.
[6]	and Proof of a conjecture of Erd?s, Combinatorial theory and its applications, Vol. II, and (Editors), Colloq. Math. Soc. J?nos Bolyai 4, North-Holland, Amsterdam, 1970, pp. 601-623.
[7]	Hoeffding, J Am Stat Assoc 58 pp 13– (1963)
[8]	Janson, Random Struct Alg 1 pp 221– (1990) · Zbl 0747.05079
[9]	and Random graphs, Wiley, New York, 2000.
[10]	and The deletion method for upper tail estimates, Technical Report U.U.D.M. 2000: 28, Uppsala University, Uppsala, Sweden. · Zbl 1074.60006
[11]	Kim, Combinatorica 20 pp 417– (2000) · Zbl 0969.60013
[12]	On the method of bounded differences, Surveys in combinatorics (Proceedings, Norwich 1989), London Math. Soc. Lecture Note Ser. 141, Cambridge University Press, Cambridge, 1989, pp. 148-188.
[13]	Concentration, Probabilistic methods for algorithmic discrete mathematics, and (Editors), Springer-Verlag, Berlin, 1998, pp. 195-248.
[14]	R?dl, Random Struct Alg 5 pp 253– (1994) · Zbl 0790.05079
[15]	R?dl, J Am Math Soc 8 pp 917– (1995)
[16]	Spencer, J Combin Theor A 55 pp 247– (1990) · Zbl 0721.05033
[17]	Talagrand, Inst Hautes ?tudes Sci Publ Math 81 pp 73– (1995) · Zbl 0864.60013
[18]	Vu, Random Struct Alg 16(4) pp 344– (2000) · Zbl 0958.60028
[19]	Vu, Random Struct Alg 17 pp 29– (2000) · Zbl 0953.05056
[20]	Vu, Combin Probab Comput
[21]	Vu, Random Struct Alg