The lower tail: Poisson approximation revisited

Abstract

The well-known "Janson's inequality" gives Poisson-like upper bounds for the lower tail probability \Pr(X \le (1-\eps)\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 \eps=1) of Janson, Luczak and Rucinski.

21 pages

References in corpus (2)

• Upper Tails for Cliques
• The Janson inequalities for general up-sets

Cited by in corpus (8)

• Upper tails for arithmetic progressions in random subsets
• On the lower tail variational problem for random graphs
• A counterexample to the DeMarco-Kahn Upper Tail Conjecture
• On the missing log in upper tail estimates
• Upper tail bounds for Stars
• Local limit theorems for subgraph counts
• Counting extensions revisited
• Moderate Deviations of Triangle Counts in the Erdős-Rényi Random Graph $G(n,m)$: The Lower Tail