Abstract | ||
---|---|---|
The well-known \"Janson's inequality\" gives Poisson-like upper bounds for the lower tail probability ﾿X≤1-εEX when X is the sum of dependent indicator random variables of a special form. We show that, for large deviations, this inequality is optimal whenever X is approximately Poisson, i.e., when the dependencies are weak. We also present correlation-based approaches that, in certain symmetric applications, yield related conclusions when X is no longer close to Poisson. As an illustration we, e.g., consider subgraph counts in random graphs, and obtain new lower tail estimates, extending earlier work for the special case ε=1 of Janson, Łuczak and Ruciński. © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 48, 219-246, 2016 |
Year | DOI | Venue |
---|---|---|
2016 | 10.1002/rsa.20590 | Random Structures & Algorithms |
Keywords | Field | DocType |
large deviations | Janson,Discrete mathematics,Combinatorics,Random variable,Random graph,Large deviations theory,Concentration inequality,Poisson distribution,Mathematics,Special case | Journal |
Volume | Issue | ISSN |
48 | 2 | 1042-9832 |
Citations | PageRank | References |
0 | 0.34 | 13 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Svante Janson | 1 | 1009 | 149.67 |
Lutz Warnke | 2 | 19 | 6.13 |