Parking on the infinite binary tree

• 成果类型: Article
• 署名作者: Aldous, David; Contat, Alice; Curien, Nicolas; Henard, Olivier
• 署名单位: University of California System; University of California Berkeley; Universite Paris Saclay
• 刊物名称: PROBABILITY THEORY AND RELATED FIELDS
• ISSN/ISSBN: 0178-8051
• DOI: 10.1007/s00440-023-01189-6
• 发表日期: 2023
• 页码: 481-504

摘要

Let (A(u) : u is an element of B) be i.i.d. non-negative integers that we interpret as car arrivals on the vertices of the full binary tree B. Each car tries to park on its arrival node, but if it is already occupied, it drives towards the root and parks on the first available spot. It is known (Bahl et al. in Parking on supercritical Galton-Watson trees, arXiv:1912.13062, 2019; Goldschmidt and Przykucki in Comb Probab Comput 28:23-45, 2019) that the parking process on B exhibits a phase transition in the sense that either a finite number of cars do not manage to park in expectation (subcritical regime) or all vertices of the tree contain a car and infinitely many cars do not manage to park (supercritical regime). We characterize those regimes in terms of the law of A in an explicit way. We also study in detail the critical regime as well as the phase transition which turns out to be discontinuous.