Limit theorems in the generalized birthday problem

Authors

  • Andrii Ilienko National Technical University of Ukraine "Igor Sikorsky Kiev Polytechnic Institute"
  • Viktoriia Stamatiieva National Technical University of Ukraine "Igor Sikorsky Kiev Polytechnic Institute" https://orcid.org/0000-0003-2721-8985

DOI:

https://doi.org/10.17721/1812-5409.2024/2.3

Keywords:

generalized birthday problem, random point measures, vague convergence, poissonization, Poisson point processes

Abstract

In the authors' previous papers (Ilienko, 2019) and (Ilienko & Stamatiieva, 2021), a novel approach to the classical coupon collector's and birthday problems was introduced, based on the theory of random point measures and their vague convergence. In this paper, we further develop this approach using the birthday problem as a case study, and apply it to establish new limit theorems for a range of nontrivial characteristics of the model. More specifically, we define a point process on a metric space consisting of a countable number of copies of the real line. The atoms of this process correspond to the arrival times of new objects. Owing to the structure of the constructed process, each atom is naturally associated with an integer that indicates the number of times an object of that class has arrived. We demonstrate that, as the number of classes tends to infinity, these processes converge vaguely to a certain Poisson point process on the same space. The application of the continuous mapping theorem to the proven convergence further yields distributional limit theorems for various characteristics of the model. The essentially infinite-dimensional nature of the involved point processes leads to corresponding infinite-dimensional limit theorems for these characteristics, fully revealing their asymptotic structure.

 

Pages of the article in the issue: 14 - 19

Language of the article: Ukrainian English

References

Flajolet, P., Grabner, P. J., Kirschenhofer, P., & Prodinger, H. (1995). On ramanujan’s q-function. Journal of Computational and Applied Mathematics, 58(1), 103–116. Retrieved from https://doi.org/10.1016/0377-0427(93)E0258-N

Ilienko, A. (2019). Convergence of point processes associated with coupon collector’s and dixie cup problems. Electronic Communications in Probability, 24, Paper No. 51, 9. Retrieved from https://doi.org/10.1214/19-ecp263

Ilienko, A., & Stamatiieva, V. (2021). A limit theorem for point processes associated with the generalized birthday problem. Scientific Bulletin of Uzhhorod University; Series of Mathematics and Informatics, 39(2), 38–46. Retrieved from http://dx.doi.org/10.24144/2616-7700.2021.39(2).38-46

Johnson, N. L., & Kotz, S. (1977). Urn models and their application. John Wiley & Sons, New York-London-Sydney. (An approach to modern discrete probability theory)

Kallenberg, O. (2017). Random measures, theory and applications (Vol. 77). Springer, Cham. Retrieved from https://doi.org/10.1007/978-3-319-41598-7

Kolchin, V. F., Sevast’yanov, B. A., & Chistyakov, V. P. (1978). Random allocations (A. V. Balakrishnan, Ed.). V. H. Winston & Sons, Washington, DC; Halsted Press [John Wiley & Sons], New York-Toronto-London.

Last, G., & Penrose, M. (2018). Lectures on the poisson process (Vol. 7). Cambridge University Press, Cambridge.

Stamatiieva, V. (2023). Generalization of the asymptotic expansion of Ramanujan – Watson – Knuth. Scientific Bulletin of Uzhhorod University. Series of Mathematics and Informatics, 43(2), 52–61. Retrieved from http://dx.doi.org/10.24144/2616-7700.2023.43(2).52-61.

Downloads

Published

2025-01-29

How to Cite

Ilienko, A., & Stamatiieva, V. (2025). Limit theorems in the generalized birthday problem. Bulletin of Taras Shevchenko National University of Kyiv. Physical and Mathematical Sciences, 79(2), 14–19. https://doi.org/10.17721/1812-5409.2024/2.3

Issue

Section

Algebra, Geometry and Probability Theory