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 overviewConference paper

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: [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], [en] the occupancy problem, random partitions

Bibliographic References

12 Documents citing this article

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, 2020, Statistics Related with Ewens Sampling Formula, SpringerBriefs in statistics, pp. 49-72, 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;Jean-Jil Duchamps;Jim Pitman;et al., 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, 2016, Application to the Bernoulli Sieve, Probability and its applications, pp. 191-208, 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, Journal of Theoretical Probability, 28, 1, pp. 1-40, 10.1007/s10959-012-0475-7.

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 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 Iksanov, 2012, On the number of empty boxes in the Bernoulli sieve II, Stochastic Processes and their Applications, 122, 7, pp. 2701-2729, 10.1016/j.spa.2012.04.010.

Sources : OpenCitations, OpenAlex & Crossref

Share and export

Consultation statistics

This page has been seen 696 times.

This article's PDF has been downloaded 486 times.