Search Results

Documents authored by Mörters, Peter

Document
DOI: 10.4230/LIPIcs.AofA.2024.14
Early Typical Vertices in Subcritical Random Graphs of Preferential Attachment Type

Authors: Peter Mörters and Nick Schleicher

Published in: LIPIcs, Volume 302, 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)

Abstract
We study the size of the connected component of early typical vertices in a subcritical inhomogeneous random graph with a kernel of preferential attachment type. The principal tools in our analysis are, first, a coupling of the neighbourhood of a typical vertex in the graph to a killed branching random walk and, second, an asymptotic result for the number of particles absorbed at the killing barrier in this branching random walk.
Cite as

Peter Mörters and Nick Schleicher. Early Typical Vertices in Subcritical Random Graphs of Preferential Attachment Type. In 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 302, pp. 14:1-14:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{morters_et_al:LIPIcs.AofA.2024.14,
  author =	{M\"{o}rters, Peter and Schleicher, Nick},
  title =	{{Early Typical Vertices in Subcritical Random Graphs of Preferential Attachment Type}},
  booktitle =	{35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)},
  pages =	{14:1--14:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-329-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{302},
  editor =	{Mailler, C\'{e}cile and Wild, Sebastian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2024.14},
  URN =		{urn:nbn:de:0030-drops-204493},
  doi =		{10.4230/LIPIcs.AofA.2024.14},
  annote =	{Keywords: Inhomogeneous random graphs, preferential attachment, networks, subcritical behaviour, size of components, connectivity, coupling, branching random walk, random tree}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2022.28
A Sublinear Local Access Implementation for the Chinese Restaurant Process

Authors: Peter Mörters, Christian Sohler, and Stefan Walzer

Published in: LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)

Abstract
The Chinese restaurant process is a stochastic process closely related to the Dirichlet process that groups sequentially arriving objects into a variable number of classes, such that within each class objects are cyclically ordered. A popular description involves a restaurant, where customers arrive one by one and either sit down next to a randomly chosen customer at one of the existing tables or open a new table. The full state of the process after n steps is given by a permutation of the n objects and cannot be represented in sublinear space. In particular, if we only need specific information about a few objects or classes it would be preferable to obtain the answers without simulating the process completely. A recent line of research [Oded Goldreich et al., 2010; Moni Naor and Asaf Nussboim, 2007; Amartya Shankha Biswas et al., 2020; Guy Even et al., 2021] attempts to provide access to huge random objects without fully instantiating them. Such local access implementations provide answers to a sequence of queries about the random object, following the same distribution as if the object was fully generated. In this paper, we provide a local access implementation for a generalization of the Chinese restaurant process described above. Our implementation can be used to answer any sequence of adaptive queries about class affiliation of objects, number and sizes of classes at any time, position of elements within a class, or founding time of a class. The running time per query is polylogarithmic in the total size of the object, with high probability. Our approach relies on some ideas from the recent local access implementation for preferential attachment trees by Even et al. [Guy Even et al., 2021]. Such trees are related to the Chinese restaurant process in the sense that both involve a "rich-get-richer" phenomenon. A novel ingredient in our implementation is to embed the process in continuous time, in which the evolution of the different classes becomes stochastically independent [Joyce and Tavaré, 1987]. This independence is used to keep the probabilistic structure manageable even if many queries have already been answered. As similar embeddings are available for a wide range of urn processes [Krishna B. Athreya and Samuel Karlin, 1968], we believe that our approach may be applicable more generally. Moreover, local access implementations for birth and death processes that we encounter along the way may be of independent interest.
Cite as

Peter Mörters, Christian Sohler, and Stefan Walzer. A Sublinear Local Access Implementation for the Chinese Restaurant Process. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 28:1-28:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{morters_et_al:LIPIcs.APPROX/RANDOM.2022.28,
  author =	{M\"{o}rters, Peter and Sohler, Christian and Walzer, Stefan},
  title =	{{A Sublinear Local Access Implementation for the Chinese Restaurant Process}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)},
  pages =	{28:1--28:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-249-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{245},
  editor =	{Chakrabarti, Amit and Swamy, Chaitanya},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.28},
  URN =		{urn:nbn:de:0030-drops-171500},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2022.28},
  annote =	{Keywords: Chinese restaurant process, Dirichlet process, sublinear time algorithm, random recursive tree, random permutation, random partition, Ewens distribution, simulation, local access implementation, continuous time embedding}
}
Document
DOI: 10.4230/LIPIcs.AofA.2020.21
The Disordered Chinese Restaurant and Other Competing Growth Processes

Authors: Cécile Mailler, Peter Mörters, and Anna Senkevich

Published in: LIPIcs, Volume 159, 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)

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.
Cite as

Cécile Mailler, Peter Mörters, and Anna Senkevich. The Disordered Chinese Restaurant and Other Competing Growth Processes. In 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 159, pp. 21:1-21:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{mailler_et_al:LIPIcs.AofA.2020.21,
  author =	{Mailler, C\'{e}cile and M\"{o}rters, Peter and Senkevich, Anna},
  title =	{{The Disordered Chinese Restaurant and Other Competing Growth Processes}},
  booktitle =	{31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)},
  pages =	{21:1--21:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-147-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{159},
  editor =	{Drmota, Michael and Heuberger, Clemens},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2020.21},
  URN =		{urn:nbn:de:0030-drops-120511},
  doi =		{10.4230/LIPIcs.AofA.2020.21},
  annote =	{Keywords: Chinese restaurant process, competing growth processes, reinforced branching processes, preferential attachment tree with fitness, Poisson processes}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact