Hostname: page-component-74656f9884-npj9w Total loading time: 0 Render date: 2026-11-08T00:43:26.017Z Has data issue: false hasContentIssue false

Parking on a Random Tree

Published online by Cambridge University Press:  23 October 2018

CHRISTINA GOLDSCHMIDT
Affiliation:
Department of Statistics, University of Oxford, 24–29 St Giles', Oxford OX1 3LB, UK Lady Margaret Hall, Norham Gardens, Oxford OX2 6QA, UK (e-mail: goldschm@stats.ox.ac.uk)
MICHAŁ PRZYKUCKI
Affiliation:
School of Mathematics, University of Birmingham, Edgbaston, Birmingham B15 2TT, UK (e-mail: m.j.przykucki@bham.ac.uk)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

Consider a uniform random rooted labelled tree on n vertices. We imagine that each node of the tree has space for a single car to park. A number m ≤ n of cars arrive one by one, each at a node chosen independently and uniformly at random. If a car arrives at a space which is already occupied, it follows the unique path towards the root until it encounters an empty space, in which case it parks there; if there is no empty space, it leaves the tree. Consider m = ⌊α n⌋ and let An,α denote the event that all ⌊α n⌋ cars find spaces in the tree. Lackner and Panholzer proved (via analytic combinatorics methods) that there is a phase transition in this model. Then if α ≤ 1/2, we have $\mathbb{P}({A_{n,\alpha}}) \to {\sqrt{1-2\alpha}}/{(1-\alpha})$, whereas if α > 1/2 we have $\mathbb{P}({A_{n,\alpha}}) \to 0$. We give a probabilistic explanation for this phenomenon, and an alternative proof via the objective method. Along the way, we consider the following variant of the problem: take the tree to be the family tree of a Galton–Watson branching process with Poisson(1) offspring distribution, and let an independent Poisson(α) number of cars arrive at each vertex. Let X be the number of cars which visit the root of the tree. We show that $\mathbb{E}{[X]}$ undergoes a discontinuous phase transition, which turns out to be a generic phenomenon for arbitrary offspring distributions of mean at least 1 for the tree and arbitrary arrival distributions.

Information

Type
Paper
Copyright
Copyright © Cambridge University Press 2018