Large deviations and Berry-Esseen bounds for hashing with linear probing
Authors:
- T KleinTKT Klein
- A LagnouxALA Lagnoux
- P PetitPPP Petit
Preprint
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.Keywords
All Related Versions
This publication has 14 references indexed in Scilit:
- Individual Displacements in Hashing with Coalesced ChainsCombinatorics, Probability and Computing, 2008
- Individual displacements for linear probing hashing with different insertion policiesACM Transactions on Algorithms, 2005
- Random trees and applicationsProbability Surveys, 2005
- Phase transition for Parking blocks, Brownian excursion and coalescenceRandom Structures & Algorithms, 2002
- A Vervaat-like path transformation for the reflected brownian bridge conditioned on its local time at 0The Annals of Probability, 2001
- On the Analysis of Linear Probing HashingAlgorithmica, 1998
- On Approximating Probabilities for Small and Large Deviations in $\mathbb{R}^d$The Annals of Probability, 1990
- Sanov Property, Generalized $I$-Projection and a Conditional Limit TheoremThe Annals of Probability, 1984
- A Berry-Esseen Bound for an Occupancy ProblemThe Annals of Probability, 1982
- Maximum entropy and conditional probabilityIEEE Transactions on Information Theory, 1981