Deviation results for sparse tables in hashing with linear probing
DOI10.1007/s00440-021-01100-1zbMath1493.60055arXiv1603.02235OpenAlexW3124151833MaRDI QIDQ2159253
Pierre Petit, Thierry Klein, Agnès Lagnoux
Publication date: 28 July 2022
Published in: Probability Theory and Related Fields (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1603.02235
Brownian motionempirical processeshashing with linear probinglarge deviationsparking problemAiry distributionconditioned sums of i.i.d. random variablesŁukasiewicz random walktriangular arrays and Weibull-like distribution
Analysis of algorithms (68W40) Sums of independent random variables; random walks (60G50) Combinatorial probability (60C05) Large deviations (60F10)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A simple proof of Sanov's theorem
- On the analysis of linear probing hashing
- Large deviations of heavy-tailed sums with applications in insurance
- Large deviations, moderate deviations and LIL for empirical processes
- A theorem about probabilities of large deviations with an application to queuing theory
- Conditional large and moderate deviations for sums of discrete random variables. Combinatoric applications
- Parking with density
- Moment convergence in conditional limit theorems
- Asymptotic distribution for the cost of linear probing hashing
- Individual displacements for linear probing hashing with different insertion policies
- Functional Analysis, Calculus of Variations and Optimal Control
- Phase transition for Parking blocks, Brownian excursion and coalescence
- Asymptotic Statistics
- Computer Science and Its Relation to Mathematics
- A conditional Berry–Esseen inequality
- Large-deviation results for triangular arrays of semiexponential random variables
- Integral Limit Theorems Taking Large Deviations into Account when Cramér’s Condition Does Not Hold. I
- Integral Limit Theorems Taking Large Deviations Into Account When Cramér’s Condition Does Not Hold. II
- Large deviations of sums of independent random variables
- Parking functions, empirical processes, and the width of rooted labeled trees
This page was built for publication: Deviation results for sparse tables in hashing with linear probing
