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

Font Size:  Small  Medium  Large

The Bernoulli sieve: an overview

Alexander Gnedin, Alexander Iksanov, Alexander Marynych

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.

Full Text: PostScript PDF

Valid XHTML 1.0 Transitional