The lower tail: Poisson approximation revisited1. Issue 2 (25th July 2015)

• Record Type: Journal Article
• Authors: Janson, Svante; Warnke, Lutz
• Is Part Of: Random structures & algorithms. Volume 48:Issue 2(2016)
• Page Start: 219
• Page End: 246
• Publication Date: 2015-07-25
• Subjects: Janson's inequality -- concentration inequality -- large deviations -- lower tail -- subgraph counts; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20590
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: The well‐known "Janson's inequality" gives Poisson‐like upper bounds for the lower tail probability ℙ ( X ⩽ ( 1 − ε ) E X ) 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