A Probabilistic Parking Process and Labeled IDLA

Pamela E. Harris, Thiago Holleben, J. Carlos Martínez Mori, Amanda Priestley, Keith Sullivan, Per Wagenius · 2025

Read A Probabilistic Parking Process and Labeled IDLA by Pamela E. Harris, Thiago Holleben, J. Carlos Martínez Mori, Amanda Priestley, Keith Sullivan, Per Wagenius (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-11718.txt.

Introduction

Pamela Harris and co-authors add chance to a classic parking puzzle. In the 1966 protocol of Konheim and Weiss, cars arrive with preferred spots and drive on when their choice is taken. The outcomes, called parking functions, became a favorite topic in counting mathematics. The new variant makes the process probabilistic and links it to internal diffusion limited aggregation, a growth model from 1991.

The authors compute the long-run distribution of the process for a class of starting preferences that includes weakly increasing parking functions. They also work out how long the protocol takes to finish when all cars park. In some cases they prove the process is negatively correlated. They then study random weakly increasing parking functions directly: the spread of the last entry, the chance a given set of cars is lucky, and the expected number of lucky cars.

Catalog record

CREATORPamela E. Harris, Thiago Holleben, J. Carlos Martínez Mori, Amanda Priestley, Keith Sullivan, Per Wagenius
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE83 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-11718

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A Probabilistic Parking Process and Labeled IDLA Pamela E. Harris, Thiago Holleben, J. Carlos Martínez Mori, Amanda Priestley, Keith Sullivan, Per Wagenius Abstract . In 1966, Konheim and Weiss [ 33 ] introduced a now classical parking protocol. The deterministic process and its resultant objects, known as parking functions , have since become a favorite object of study in enumerative combinatorics. In our work, we introduce and study a probabilistic variant of the classical parking protocol, which is closely related to Internal Diffusion Limited Aggregation, or IDLA, introduced in 1991 by Diaconis and Fulton [ 19 ] . In particular, we compute the stationary distribution of this process when initiated with a particular class of initial preferences, of which weakly increasing parking functions are a subset. Furthermore, we compute the expected time it takes for the protocol to complete assuming all of the cars park, and prove that, in some cases, the parking process is negatively correlated. In addition, we study statistics of uniformly random weakly increasing parking functions such as the distribution of the last entry, the probability that a specific set of cars is lucky, and the expected number of lucky cars. \usdate 2020 Mathematics Subject Classification Primary: 60C05; Secondary: 60K35, 60J05 1. Introduction In 1966 Konheim and Weiss [ 33 ] introduced a now classical parking problem which is defined as follows. Fix n\in\mathbb{N}=\{1,2,3,\ldots\} and consider a sequence of n cars, each given labels in [n]\coloneqq\{1,2,\dots,n\} , attempting to park on the sites of the line segment [n] according to the following protocol. Initially, each car records its preferred parking spot in the preference list \alpha\coloneqq(\alpha_{1},\alpha_{2},\dots,\alpha_{n})\in[n]^{n} , with \alpha_{i} being the preference of car i . The cars then enter the street from left to right, and attempt to park in increasing order of their labels. If their preferred parking spot is unoccupied, they are able to immediately park in their desired spot. Otherwise, each car continues to drive to the next available spot to the right and parks there. If there is no such parking spot available, the car exits the street and is unable to park. The set of preference lists \alpha such that all cars can park under the aforementioned protocol are called parking functions , and the set of all parking functions with n cars is denoted by \mathsf{PF}_{n} . To give a few simple but illustrative examples, the preference list (1,1,1,\dots,1) is a parking function, as is any permutation of [n] . We let S_{n} denote the set of permutations of [n] , and we write permutations in one-line notation. However, the preference list (n,n,n,\dots,n) is not a parking function, as the second car already fails to park. Konheim and Weiss, interested in studying hash functions, initiated the study of these combinatorial objects by proving that |\mathsf{PF}_{n}|=(n+1)^{n-1} . Since then, classical parking functions and several new variants [ 7 , 8 , 24 ] have been of great interest to the enumerative combinatorics community. In addition, parking functions, along with their restrictions and generalizations, have connections to a vast range of mathematical fields. Past work connects parking functions to computing volumes of polytopes, hyperplane arrangements, representation theory, sorting algorithms, enumerating Boolean intervals in the weak Bruhat order of the symmetric group, facet structure of the permutahedron, and even to the continued fraction expansion of \sqrt{2} and to the Tower of Hanoi game [ 1 , 21 , 30 , 40 , 26 , 24 , 23 , 50 , 32 , 28 ] . For a brief introduction to parking functions and some of their properties, we recommend [ 38 ] . For a detailed overview of known results about parking functions, we point the reader to Yan [ 55 ] , and for many open problems involving parking functions we recommend [ 5 ] . In this work, we will be interested in discussing the behavior of a probabilistic parking protocol when initiated with a preference vector which is a parking function (in the classical sense) having a specific outcome permutation , where the outcome permutation is the final order of the parked cars at the end of the classical parking process. In particular, we will consider parking functions whose outcome is the identity permutation, a set which we denote \mathrm{PF}_{n}(\mathrm{id}) . For example, (1,2,1)\in\mathsf{PF}_{3}(\mathrm{id}) , but (2,1,3)\notin\mathsf{PF}_{3}(\mathrm{id}) since the cars do not park in the order of the identity permutation. We will also discuss statistics of weakly increasing parking functions, which are parking functions whose entries are weakly increasing. More formally, we have the following definition. Definition 1.1 (Weakly Increasing Parking Function) . A weakly increasing parking function of length n\geq 1 is a preference list \alpha=(\alpha_{1},\alpha_{2},\ldots,\alpha_{n})\in[n]^{n} such that \alpha_{i}\leq i for all i\in[n] and \alpha_{1}\leq\alpha_{2}\leq\cdots\leq\alpha_{n} . We denote the set of weakly increasing parking functions of length n\geq 1 by \mathsf{PF}^{\uparrow}_{n} . Weakly increasing parking functions are known Catalan objects (i.e., combinatorial objects enumerated by the Catalan numbers, for more on Catalan objects see [ 51 ] ). Moreover, the outcome of any weakly increasing parking function is the identity permutation (i.e., \mathsf{PF}^{\uparrow}_{n}\subseteq\mathrm{PF}_{n}(\mathrm{id}) ). However, note that the converse is not true: for example, (1,2,1)\in\mathsf{PF}_{3} parks in the order 123 , but is not weakly increasing. The classical parking process, and resultant parking functions, have steadily increased in popularity as objects of study in the probability community. Recently there have been several works studying phase transitions in the parking process on random graphs such as random trees [ 2 , 12 , 13 , 9 , 11 , 15 , 27 ] , and Frozen Erős-Rényi graphs [ 10 ] . Diaconis and Hicks [ 20 ] , on the other hand, considered the question “What does a random parking function look like?” . They gave probabilistic interpretations of some known generating functions, and used these results to derive statistics about parking functions. However, there are relatively few works which introduce randomness into the parking protocol itself. Durmić, Han, Harris, Ribeiro, and Yin [ 22 ] give one such model. In their parking protocol, whenever a car attempting to park finds its preferred parking spot occupied, with probability p the car proceeds as in the classical parking protocol, and parks in the first empty spot it finds to the right. With probability q\coloneqq 1-p the car reverses the classical parking protocol, and searches backwards in an attempt to park in the first open spot it finds to the left. Remarkably, the probability of obtaining a parking function is shown to be independent of the forward probability p . They also provided some combinatorial consequences of the probabilistic parking protocol, which gave interpretations of the triangular arrays produced by a generating polynomial related to the study of duplicial algebras and Lagrange inversion [ 22 , Theorem 8] . Motivated by the results of Diaconis and Hicks [ 20 ] and Durmić et al. [ 22 ] , we study statistics of a model of stochastic parking when it is started with an initial preference list which is a parking function whose outcome is the identity permutation. Note, that there are n! parking functions with outcome the identity permutation, namely those preferences \alpha\coloneqq(\alpha_{1},\alpha_{2},\ldots,\alpha_{n}) satisfying a_{i}\leq i for all i\in[n] . For

Read the complete text