Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. The Bernoulli sieve: ...
Conference paper

The Bernoulli sieve: an overview

Alexander Gnedin (1), Alexander Iksanov (2), Alexander Marynych (2)
(1) Mathematical Institute
(2) Faculty of Cybernetics [Kyiv]
Download article
Open on HAL
Imported on
January 31, 2017
Published on
December 31, 2009
Last modified on
March 31, 2025
Volume
DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10)
Proceedings
DOI
10.46298/dmtcs.2770
License
https://about.hal.science/hal-authorisation-v1
Indicators
1027
Views
687
Downloads

The Bernoulli sieve: an overview

Alexander Gnedin (1), Alexander Iksanov (2), Alexander Marynych (2)
(1) Mathematical Institute
(2) Faculty of Cybernetics [Kyiv]
Abstract
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.
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]
  • the occupancy problem
  • random partitions
Cited by

Source: OpenCitations

  • Gaps and interleaving of point processes in sampling from a residual allocation model

    Bernoulli

    Authors : Jim Pitman ORCID, Yuri Yakubovich ORCID

    Journal reference : Volume 25, 2019, pp.

    DOI : 10.3150/19-bej1104

  • Statistics Related with Ewens Sampling Formula

    SpringerBriefs in statistics

    Authors : Hajime Yamato ORCID

    Journal reference : Volume , 2020, pp. 49-72

    DOI : 10.1007/978-981-15-6975-3_4

  • Regenerative compositions in the case of slow variation: A renewal theory approach

    Electronic Journal of Probability

    Authors : Alexander Gnedin, Alexander Iksanov ORCID

    Journal reference : Volume 17, 2012, pp.

    DOI : 10.1214/ejp.v17-2002

  • On nested infinite occupancy scheme in random environment

    Probability Theory and Related Fields

    Authors : Alexander Gnedin, Alexander Iksanov ORCID

    Journal reference : Volume 177, 2020, pp. 855-890

    DOI : 10.1007/s00440-020-00963-0

  • A Generalization of the Erdős–Turán Law for the Order of Random Permutation

    Combinatorics Probability Computing

    Authors : ALEXANDER GNEDIN, ALEXANDER IKSANOV ORCID, ALEXANDER MARYNYCH ORCID

    Journal reference : Volume 21, 2012, pp. 715-733

    DOI : 10.1017/s0963548312000247

  • Power Laws for Heavy-Tailed Distributions: Modeling Allele and Haplotype Diversity for the National Marrow Donor Program

    PLoS Computational Biology

    Authors : Noa Slater, Yoram Louzoun ORCID, Loren Gragert ORCID, Martin Maiers ORCID, Ansu Chatterjee ORCID, Mark Albrecht

    Journal reference : Volume 11, 2015, pp. e1004204

    DOI : 10.1371/journal.pcbi.1004204

  • On the number of empty boxes in the Bernoulli sieve II

    Stochastic Processes and their Applications

    Authors : Alexander Iksanov ORCID

    Journal reference : Volume 122, 2012, pp. 2701-2729

    DOI : 10.1016/j.spa.2012.04.010

  • Renewal sequences and record chains related to multiple zeta sums

    arXiv (Cornell University)

    Authors : Jean-Jil Duchamps, Jim Pitman, Wenpin Tang

    Journal reference : Volume 371, 2018, pp. 5731-5755

    DOI : 10.1090/tran/7516

  • Application to the Bernoulli Sieve

    Probability and its applications

    Authors : Alexander Iksanov ORCID

    Journal reference : Volume , 2016, pp. 191-208

    DOI : 10.1007/978-3-319-49113-4_5

  • Extremes and gaps in sampling from a GEM random discrete distribution

    Electronic Journal of Probability

    Authors : Jim Pitman ORCID, Yuri Yakubovich ORCID

    Journal reference : Volume 22, 2017, pp.

    DOI : 10.1214/17-ejp59

  • Regenerative random permutations of integers

    The Annals of Probability

    Authors : Jim Pitman, Wenpin Tang

    Journal reference : Volume 47, 2019, pp.

    DOI : 10.1214/18-aop1286

  • Late levels of nested occupancy scheme in random environment

    arXiv (Cornell University)

    Authors : Alexander Iksanov ORCID, Bastien Mallein ORCID

    Journal reference : Volume 38, 2021, pp. 130-166

    DOI : 10.1080/15326349.2021.1984948

  • On intermediate levels of nested occupancy scheme in random environment generated by stick-breaking I

    Electronic Journal of Probability

    Authors : Dariusz Buraczewski ORCID, Bohdan Dovgay, Alexander Iksanov ORCID

    Journal reference : Volume 25, 2020, pp.

    DOI : 10.1214/20-ejp534

  • Power and Exponential Moments of the Number of Visits and Related Quantities for Perturbed Random Walks

    Journal of Theoretical Probability

    Authors : Gerold Alsmeyer ORCID, Alexander Iksanov ORCID, Matthias Meiners ORCID

    Journal reference : Volume 28, 2013, pp. 1-40

    DOI : 10.1007/s10959-012-0475-7
Preview
Loading PDF preview...