The Disordered Chinese Restaurant and Other Competing Growth Processes

Cecile Mailler, Peter Morters, Anna Senkevich

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

The disordered Chinese restaurant process is a partition-valued stochastic process where the elements of the partitioned set are seen as customers sitting at different tables (the sets of the partition) in a restaurant. Each table is assigned a positive number called its attractiveness.

At every step a customer enters the restaurant and either joins a table with a probability proportional to the product of its attractiveness and the number of customers sitting at the table, or occupies a previously unoccupied table, which is then assigned an attractiveness drawn from a bounded distribution independently of everything else. When all attractivenesses are equal to the upper bound this process is the classical Chinese restaurant process; we show that the introduction of disorder can drastically change the behaviour of the system.

Our main results are distributional limit theorems for the scaled number of customers at the busiest table, and for the ratio of occupants at the busiest and second busiest table.

The limiting distributions are universal, i.e.\ they do not depend on the distribution of the attractiveness. They follow from two general Poisson limit theorems for a broad class of processes consisting of families growing with different rates from different birth times, which have further applications, for example to preferential attachment networks.
Original languageEnglish
Title of host publication31st International Meeting on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)
EditorsM. Drmota , C. Heuberger
DOIs
Publication statusPublished - 10 Jun 2020
Event31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms, A of A 2020 - Klagenfurt, Austria
Duration: 16 Jun 202019 Jun 2020

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume159

Conference

Conference31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms, A of A 2020
CountryAustria
CityKlagenfurt
Period16/06/2019/06/20

Cite this