Deviation results for sparse tables in hashing with linear probing

DOI10.1007/S00440-021-01100-1zbMATH Open1493.60055arXiv1603.02235OpenAlexW3124151833MaRDI QIDQ2159253FDOQ2159253

Pierre Petit, Thierry Klein, Agnès Lagnoux

Publication date: 28 July 2022

Published in: Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete (Search for Journal in Brave)

Abstract: We consider the model of hashing with linear probing and we establish the moderate and large deviations for the total displacement in sparse tables. In this context, Weibull-like-tailed random variables appear. Deviations for sums of such heavy-tailed random variables are studied in cite{Nagaev69-1,Nagaev69-2}. Here we adapt the proofs therein to deal with conditioned sums of such variables and solve the open question in cite{TFC12}. By the way, we establish the deviations of the total displacement in full tables, which can be derived from the deviations of empirical processes of i.i.d. random variables established in cite{Wu94}..

Full work available at URL: https://arxiv.org/abs/1603.02235

zbMATH Keywords

large deviationsBrownian motionempirical processesparking problemAiry distribution[https://portal.mardi4nfdi.de/w/index.php?title=+Special%3ASearch&search=%EF%BF%BD%EF%BF%BDukasiewicz+random+walk&go=Go ��ukasiewicz random walk]conditioned sums of i.i.d. random variableshashing with linear probingtriangular arrays and Weibull-like distribution

Mathematics Subject Classification ID

Large deviations (60F10) Analysis of algorithms (68W40) Sums of independent random variables; random walks (60G50) Combinatorial probability (60C05)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Asymptotic Statistics
• Functional Analysis, Calculus of Variations and Optimal Control
• Large deviations of heavy-tailed sums with applications in insurance
• On the analysis of linear probing hashing
• Asymptotic distribution for the cost of linear probing hashing
• Individual displacements for linear probing hashing with different insertion policies
• Large deviations of sums of independent random variables
• Phase transition for Parking blocks, Brownian excursion and coalescence
• 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. II
• A simple proof of Sanov's theorem
• Integral Limit Theorems Taking Large Deviations into Account when Cramér’s Condition Does Not Hold. I
• Moment convergence in conditional limit theorems
• A theorem about probabilities of large deviations with an application to queuing theory
• Large deviations, moderate deviations and LIL for empirical processes
• Computer Science and Its Relation to Mathematics
• A conditional Berry–Esseen inequality
• Parking functions, empirical processes, and the width of rooted labeled trees
• Conditional large and moderate deviations for sums of discrete random variables. Combinatoric applications
• Parking with density

Cited In (1)

• Title not available (Why is that?)

This page was built for publication: Deviation results for sparse tables in hashing with linear probing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2159253)