Large deviations and Berry-Esseen bounds for hashing with linear probing
Thierry Klein, Agnès Lagnoux, P. Petit · arXiv (Cornell University) · 2014
We study the asymptotic behavior of a sum of independent and identically distributed random variables conditioned by a sum of independent and identically distributed integer-valued random variables. First, we prove a large deviations result in the context of hashing with linear probing. By the way, we establish a large deviations result for triangular arrays when the Laplace transform is not defined in a neighborhood of 0. Second, we prove a Berry-Esseen bound in a general setting.