Deviation results for sparse tables in hashing with linear probing

1. Chassaing, P., Flajolet, P.: Hachage, arbres, chemins & graphes. Gaz. Math. 95, 29–49 (2003)

   MathSciNet  MATH  Google Scholar 

2. Chassaing, P., Louchard, G.: Phase transition for parking blocks, Brownian excursion and coalescence. Random Struct. Algorithms 21(1), 76–119 (2002)

   Article  MathSciNet  Google Scholar 

3. Chassaing, P., Marckert, J.-F.: Parking functions, empirical processes, and the width of rooted labeled trees. Electron. J. Combin. 8(1), Research Paper 14, 19 (2001)

4. Clarke, F.: Functional Analysis, Calculus of Variations and Control, vol. 264 of Graduate Texts in Mathematics. Springer, London (2013)

5. Csiszár, I.: A simple proof of Sanov’s theorem. Bull. Braz. Math. Soc. (N.S.) 37(4), 453–459 (2006)

   Article  MathSciNet  Google Scholar 

6. de Acosta, A.: Projective systems in large deviation theory II: some applications. In: Hoffmann-Jørgensen, J., Kuelbs, J., Marcus, M.B. (eds.) Probability in Banach Spaces, 9, pp. 241–250. Birkhäuser Boston, Boston (1994)

7. Flajolet, P., Poblete, P., Viola, A.: On the analysis of linear probing hashing. Algorithmica 22(4), 490–515 (1998)

   Article  MathSciNet  Google Scholar 

8. Flajolet, P., Sedgewick, R.: Analytic Combinatorics, 1st edn. Cambridge University Press, New York (2009)

   Book  Google Scholar 

9. Gamboa, F., Klein, T., Prieur, C.: Conditional large and moderate deviations for sums of discrete random variables. Combinatoric applications. Bernoulli 18(4), 1341–1360 (2012)

   Article  MathSciNet  Google Scholar 

10. Janson, S.: Asymptotic distribution for the cost of linear probing hashing. Random Struct. Algorithms 19(3–4), 438–471 (2001)

    Article  MathSciNet  Google Scholar 

11. Janson, S.: Moment convergence in conditional limit theorems. J. Appl. Probab. 38(2), 421–437 (2001)

    Article  MathSciNet  Google Scholar 

12. Janson, S.: Individual displacements for linear probing hashing with different insertion policies. ACM Trans. Algorithms 1(2), 177–213 (2005)

    Article  MathSciNet  Google Scholar 

13. Klein, T., Lagnoux, A., Petit, P.: A conditional Berry–Esseen inequality. J. Appl. Probab. 56(1), 76–90 (2019)

    Article  MathSciNet  Google Scholar 

14. Klein, T., Lagnoux, A., Petit, P.: Large deviation results for triangular arrays of semiexponential random variables. Preprint (2020)

15. Knuth, D.E.: Notes on “open” addressing (1963)

16. Knuth, D.E.: Computer science and its relation to mathematics. Am. Math. Monthly 81, 323–343 (1974)

    Article  MathSciNet  Google Scholar 

17. Knuth, D.E.: The Art of Computer Programming. Vol. 3. Addison-Wesley, Reading, MA (1998). Sorting and searching, Second edition [of MR0445948]

18. Linnik, J.V.: On the probability of large deviations for the sums of independent variables. In: Proceedings of the Fourth Berkeley Symposium on Mathematical Statistics and Probability, Volume 2: Contributions to Probability Theory, Vol. II, pp 289–306. Univ. California Press, Berkeley (1961)

19. Marckert, J.-F.: Parking with density. Random Struct. Algorithms 18(4), 364–380 (2001)

    Article  MathSciNet  Google Scholar 

20. Mikosch, T., Nagaev, A.V.: Large deviations of heavy-tailed sums with applications in insurance. Extremes 1(1), 81–110 (1998)

    Article  MathSciNet  Google Scholar 

21. Nagaev, A.V.: Integral limit theorems taking large deviations into account when Cramér’s condition does not hold. I. Theory Probab. Appl. 14(1), 51–64 (1969)

22. Nagaev, A.V.: Integral limit theorems taking large deviations into account when Cramér’s condition does not hold. II. Theory Probab. Appl. 14(2), 193–208 (1969)

    Article  Google Scholar 

23. Nagaev, S.V.: Large deviations of sums of independent random variables. Ann. Probab. 7(5), 745–789 (1979)

    Article  MathSciNet  Google Scholar 

24. Perchet, V., Vigeral, G.: A minmax theorem for concave-convex mappings with no regularity assumptions. J. Convex Anal. 22(2), 537–540 (2015). (4 pages)

    MathSciNet  MATH  Google Scholar 

25. Petrov, V. V.: Generalization of Cramér’s limit theorem. Uspehi Matem. Nauk (N.S.) 9(4(62)), 195–202 (1954)

26. Plachky, D., Steinebach, J.: A theorem about probabilities of large deviations with an application to queuing theory. Period. Math. Hungar. 6(4), 343–345 (1975)

    Article  MathSciNet  Google Scholar 

27. Rockafellar, R.T.: Convex Analysis, vol. 28. Princeton University Press, Princeton (1970)

    Book  Google Scholar 

28. van der Vaart, A.W.: Asymptotic Statistics. Cambridge Series in Statistical and Probabilistic Mathematics, vol. 3. Cambridge University Press, Cambridge (1998)

29. Wu, L.M.: Large deviations, moderate deviations and LIL for empirical processes. Ann. Probab. 22(1), 17–27 (1994)

    Article  MathSciNet  Google Scholar 

Download references