The lower tail: Poisson approximation revisited
2016 (English)In: Random structures & algorithms (Print), ISSN 1042-9832, E-ISSN 1098-2418, Vol. 48, no 2, 219-246 p.Article in journal (Refereed) PublishedText
The well-known Janson's inequality gives Poisson-like upper bounds for the lower tail probability P(X(1-epsilon)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 epsilon=1) of Janson, uczak and Ruciski.
Place, publisher, year, edition, pages
2016. Vol. 48, no 2, 219-246 p.
Janson's inequality, concentration inequality, large deviations, lower tail, subgraph counts
IdentifiersURN: urn:nbn:se:uu:diva-275525DOI: 10.1002/rsa.20590ISI: 000367624300001OAI: oai:DiVA.org:uu-275525DiVA: diva2:901727
FunderKnut and Alice Wallenberg Foundation