Large deviations and Berry-Esseen bounds for hashing with linear probing

Authors:
  • TKT Klein
    T Klein
  • ALA Lagnoux
    A Lagnoux
  • PPP Petit
    P Petit

Abstract
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.

This publication has 14 references indexed in Scilit: