Abstract | ||
---|---|---|
In the late 1990s, Kim and Vu pioneered an inductive method for showing concentration of certain random variables X. Shortly afterwards, Janson and Ruciński developed an alternative inductive approach, which often gives comparable results for the upper tail P(X≥(1+ε)EX). In some cases, both methods yield upper tail estimates which are best possible up to a logarithmic factor in the exponent, but closing this narrow gap has remained a technical challenge. In this paper we present a BK-inequality based combinatorial sparsification idea that can recover this missing logarithmic term in the upper tail. |
Year | DOI | Venue |
---|---|---|
2020 | 10.1016/j.jctb.2019.05.003 | Journal of Combinatorial Theory, Series B |
Keywords | DocType | Volume |
Upper tail,Missing log,Concentration inequalities,Large deviations,Tail estimates | Journal | 140 |
ISSN | Citations | PageRank |
0095-8956 | 0 | 0.34 |
References | Authors | |
0 | 1 |
Name | Order | Citations | PageRank |
---|---|---|---|
Lutz Warnke | 1 | 19 | 6.13 |