Limit theorems in the generalized birthday problem
DOI:
https://doi.org/10.17721/1812-5409.2024/2.3Keywords:
generalized birthday problem, random point measures, vague convergence, poissonization, Poisson point processesAbstract
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 EnglishReferences
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
How to Cite
Issue
Section
License
Copyright (c) 2024 Andrii Ilienko, Viktoriia Stamatiieva

This work is licensed under a Creative Commons Attribution 4.0 International License.
Authors who publish with this journal agree to the following terms:
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).