uu.seUppsala University Publications
Change search
ReferencesLink to record
Permanent link

Direct link
The lower tail: Poisson approximation revisited
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics.
Univ Cambridge, Dept Pure Math & Math Stat, Cambridge CB3 0WB, England..
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
Abstract [en]

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.
Keyword [en]
Janson's inequality, concentration inequality, large deviations, lower tail, subgraph counts
National Category
URN: urn:nbn:se:uu:diva-275525DOI: 10.1002/rsa.20590ISI: 000367624300001OAI: oai:DiVA.org:uu-275525DiVA: diva2:901727
Knut and Alice Wallenberg Foundation
Available from: 2016-02-09 Created: 2016-02-04 Last updated: 2016-02-09Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Janson, Svante
By organisation
Department of Mathematics
In the same journal
Random structures & algorithms (Print)

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 105 hits
ReferencesLink to record
Permanent link

Direct link