Deviation results for sparse tables in hashing with linear probing

• 成果类型: Article
• 署名作者: Klein, Thierry; Lagnoux, Agnes; Petit, Pierre
• 署名单位: Universite de Toulouse; Universite Toulouse III - Paul Sabatier; Universite Federale Toulouse Midi-Pyrenees (ComUE); Institut National des Sciences Appliquees de Toulouse; Centre National de la Recherche Scientifique (CNRS); CNRS - National Institute for Mathematical Sciences (INSMI); Universite de Toulouse; Universite de Toulouse; Universite de Toulouse - Jean Jaures; Centre National de la Recherche Scientifique (CNRS); Centre National de la Recherche Scientifique (CNRS); Universite de Toulouse; Universite Toulouse III - Paul Sabatier
• 刊物名称: PROBABILITY THEORY AND RELATED FIELDS
• ISSN/ISSBN: 0178-8051
• DOI: 10.1007/s00440-021-01100-1
• 发表日期: 2022
• 页码: 871-908
• 关键词: moderate deviations; parking; sums

摘要

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 Nagaev (Theory Probab Appl 14(1):51-64, 1969; Theory Probab Appl 14(2):193-208, 1969). Here we adapt the proofs therein to deal with conditioned sums of such variables and solve the open question in Gamboa et al. (Bernoulli 18(4):1341-1360, 2012). 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 Wu (Ann Probab 22(1):17-27, 1994).