Premium
On the concentration of multivariate polynomials with small expectation
Author(s) -
Vu Van H.
Publication year - 2000
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/1098-2418(200007)16:4<344::aid-rsa4>3.0.co;2-5
Subject(s) - struct , multivariate statistics , mathematics , random variable , combinatorics , order (exchange) , discrete mathematics , statistics , computer science , programming language , finance , economics
Let t 1 ,…, t n be independent, but not necessarily identical, {0, 1} random variables. We prove a general large deviation bound for multivariate polynomials (in t 1 ,…, t n ) with small expectation [order O (polylog( n ))]. Few applications in random graphs and combinatorial number theory will be discussed. Our result is closely related to a classical result of Janson [Random Struct Algorithms 1 (1990), 221–230]. Both of them can be applied in similar situations. On the other hand, our result is symmetric, while Janson's inequality only deals with the lower tail probability. © 2000 John Wiley & Sons, Inc. Random Struct. Alg., 16: 344–363, 2000