The Bernoulli sieve: an overview

Alexander Gnedin; Alexander Iksanov; Alexander Marynych

doi:10.46298/dmtcs.2770

Alexander Gnedin ; Alexander Iksanov ; Alexander Marynych - The Bernoulli sieve: an overview

dmtcs:2770 - Discrete Mathematics & Theoretical Computer Science, January 1, 2010, DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10) - https://doi.org/10.46298/dmtcs.2770

The Bernoulli sieve: an overviewArticle

Authors: Alexander Gnedin ¹; Alexander Iksanov ²; Alexander Marynych ²

1 Mathematical Institute
2 Faculty of Cybernetics [Kyiv]

The Bernoulli sieve is a version of the classical balls-in-boxes occupancy scheme, in which random frequencies of infinitely many boxes are produced by a multiplicative random walk, also known as the residual allocation model or stick-breaking. We give an overview of the limit theorems concerning the number of boxes occupied by some balls out of the first $n$ balls thrown, and present some new results concerning the number of empty boxes within the occupancy range.

https://doi.org/10.46298/dmtcs.2770

Source: HAL:hal-01185568v1

Volume: DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10)

Section: Proceedings

Published on: January 1, 2010

Imported on: January 31, 2017

Keywords: the occupancy problem,random partitions,[INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS],[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO],[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[INFO.INFO-CG] Computer Science [cs]/Computational Geometry [cs.CG]

Bibliographic References

14 Documents citing this article

Alexander Iksanov;Bastien Mallein, 2021, Late levels of nested occupancy scheme in random environment, 38, 1, pp. 130-166, 10.1080/15326349.2021.1984948, https://hal.science/hal-03354403.

Alexander Gnedin;Alexander Iksanov, 2020, On nested infinite occupancy scheme in random environment, Probability Theory and Related Fields, 177, 3-4, pp. 855-890, 10.1007/s00440-020-00963-0, https://doi.org/10.1007/s00440-020-00963-0.

Dariusz Buraczewski;Bohdan Dovgay;Alexander Iksanov, 2020, On intermediate levels of nested occupancy scheme in random environment generated by stick-breaking I, Electronic Journal of Probability, 25, none, 10.1214/20-ejp534, https://doi.org/10.1214/20-ejp534.

Hajime Yamato, SpringerBriefs in statistics, Statistics Related with Ewens Sampling Formula, pp. 49-72, 2020, 10.1007/978-981-15-6975-3_4.

Jim Pitman;Wenpin Tang, 2019, Regenerative random permutations of integers, The Annals of Probability, 47, 3, 10.1214/18-aop1286, https://doi.org/10.1214/18-aop1286.

Jim Pitman;Yuri Yakubovich, 2019, Gaps and interleaving of point processes in sampling from a residual allocation model, Bernoulli, 25, 4B, 10.3150/19-bej1104, https://doi.org/10.3150/19-bej1104.

Jean-Jil Duchamps;Jim Pitman;Wenpin Tang, 2018, Renewal sequences and record chains related to multiple zeta sums, Transactions of the American Mathematical Society, 371, 8, pp. 5731-5755, 10.1090/tran/7516, https://doi.org/10.1090/tran/7516.

Jim Pitman;Yuri Yakubovich, 2017, Extremes and gaps in sampling from a GEM random discrete distribution, Electronic Journal of Probability, 22, none, 10.1214/17-ejp59, https://doi.org/10.1214/17-ejp59.

Alexander Iksanov, Probability and its applications, Application to the Bernoulli Sieve, pp. 191-208, 2016, 10.1007/978-3-319-49113-4_5.

Noa Slater;Yoram Louzoun;Loren Gragert;Martin Maiers;Ansu Chatterjee;et al., 2015, Power Laws for Heavy-Tailed Distributions: Modeling Allele and Haplotype Diversity for the National Marrow Donor Program, PLoS Computational Biology, 11, 4, pp. e1004204, 10.1371/journal.pcbi.1004204, https://doi.org/10.1371/journal.pcbi.1004204.

Gerold Alsmeyer;Alexander Iksanov;Matthias Meiners, 2013, Power and Exponential Moments of the Number of Visits and Related Quantities for Perturbed Random Walks, arXiv (Cornell University), 28, 1, pp. 1-40, 10.1007/s10959-012-0475-7, https://arxiv.org/abs/1111.4159.

Alexander Gnedin;Alexander Iksanov, 2012, Regenerative compositions in the case of slow variation: A renewal theory approach, Electronic Journal of Probability, 17, none, 10.1214/ejp.v17-2002, https://doi.org/10.1214/ejp.v17-2002.

Alexander Gnedin;Alexander Iksanov;Alexander Marynych, 2012, A Generalization of the Erdős–Turán Law for the Order of Random Permutation, Combinatorics Probability Computing, 21, 5, pp. 715-733, 10.1017/s0963548312000247.

Alexander Iksanov, 2012, On the number of empty boxes in the Bernoulli sieve II, arXiv (Cornell University), 122, 7, pp. 2701-2729, 10.1016/j.spa.2012.04.010, https://arxiv.org/abs/1110.3713.

Sources : OpenCitations, OpenAlex & Crossref

Share and export

Consultation statistics

This page has been seen 499 times.

This article's PDF has been downloaded 273 times.