Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2411.10296 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912120557273088 |
|---|---|
| author | Serunjogi, Semu |
| author_facet | Serunjogi, Semu |
| contents | In this paper, we investigate the parking process on a uniform random rooted binary tree with $n$ vertices. Viewing each vertex as a single parking space, a random number of cars independently arrive at and attempt to park on each vertex one at a time. If a car attempts to park on an occupied vertex, it traverses the unique path on the tree towards the root, parking at the first empty vertex it encounters. If this is not possible, the car exits the tree at the root.
We shall investigate the limit of the probability of the event that all cars can park when $\lfloor αn \rfloor$ cars arrive, with $α> 0$. We find that there is a phase transition at $α_c = 2 - \sqrt{2}$, with this event having positive limiting probability when $α< α_c$, and the probability tending to 0 as $n \rightarrow \infty$ for $α> α_c$.
This is analogous to the work done by Goldschmidt and Przykucki (arXiv:1610.08786) and Goldschmidt and Chen (arXiv:1911.03816), while agreeing with the general result proven by Curien and Hénard (arXiv:2205.15932). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_10296 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Parking on a random rooted binary tree Serunjogi, Semu Probability In this paper, we investigate the parking process on a uniform random rooted binary tree with $n$ vertices. Viewing each vertex as a single parking space, a random number of cars independently arrive at and attempt to park on each vertex one at a time. If a car attempts to park on an occupied vertex, it traverses the unique path on the tree towards the root, parking at the first empty vertex it encounters. If this is not possible, the car exits the tree at the root. We shall investigate the limit of the probability of the event that all cars can park when $\lfloor αn \rfloor$ cars arrive, with $α> 0$. We find that there is a phase transition at $α_c = 2 - \sqrt{2}$, with this event having positive limiting probability when $α< α_c$, and the probability tending to 0 as $n \rightarrow \infty$ for $α> α_c$. This is analogous to the work done by Goldschmidt and Przykucki (arXiv:1610.08786) and Goldschmidt and Chen (arXiv:1911.03816), while agreeing with the general result proven by Curien and Hénard (arXiv:2205.15932). |
| title | Parking on a random rooted binary tree |
| topic | Probability |
| url | https://arxiv.org/abs/2411.10296 |