Stretched exponential decay for subcritical parking times on

Michael Damron, Hanbaek Lyu, David SivakoffRandom Struct. Algorithms 2021 · OpenReview

TL;DR

This paper analyzes the "parking model" on a grid, where cars randomly move and occupy the first empty spot they find. The authors prove that in the "subcritical" regime (where cars are less numerous than spots), the time it takes for a car to park decays exponentially with a stretched exponent, specifically $e^{-Ct^{d/(d+2)}}$. This reveals a surprising asymmetry compared to the "supercritical" regime and offers a new understanding of how these systems evolve.

What Problem Does This Paper Address?

The parking model, introduced in prior work, is a fascinating system where cars (particles) perform random walks on a grid ($\mathbb{Z}^d$) and occupy the first vacant spot they encounter. Once a spot is occupied, it remains so. This model has a critical point at $p=1/2$, where $p$ is the initial density of cars. Below this point (subcritical, $p < 1/2$), cars are expected to eventually park. Above this point (supercritical, $p > 1/2$), cars are more likely to wander indefinitely.

While previous work established that cars eventually park in the subcritical phase, the precise rate at which this happens (i.e., the tail distribution of the parking time) remained an open question. This paper aims to precisely characterize this decay rate for the parking time of a car starting at the origin, particularly in the subcritical phase and for small initial car densities. Understanding this decay is crucial for comprehending the long-term behavior and dynamics of such interacting particle systems.

Methods

The authors employ a combination of probabilistic techniques and spectral graph theory.

  • Lower Bound: To establish a lower bound on the parking time's decay, they consider a large box around the origin. They force this box to be initially filled with cars and then analyze the probability that the car starting at the origin remains within this box for a long time. This involves analyzing the survival probability of a random walk within a bounded region.
  • Upper Bound: The upper bound proof is more intricate and builds upon the "busy subgraph" method from previous work. A key innovation is the use of a spectral isoperimetric bound from Levine-Peres. This allows them to control the exit time of a random walk from various subgraphs of the grid. They combine this with an analysis of how many cars are needed to "occupy" a subgraph (the busy subgraph condition) to bound the probability that the origin's parking spot remains vacant.
  • Spectral Graph Theory: Proposition 2.3, a central technical lemma, uses spectral properties of random walks on subgraphs. It bounds the probability that a random walk stays within a subgraph for a long time using the operator norm of the transition matrix of the random walk restricted to that subgraph.

Datasets

Not discussed in the paper. The paper deals with a theoretical model on $\mathbb{Z}^d$ and does not involve empirical datasets.

Key Insights and Ideas

  • Stretched Exponential Decay: The most striking finding is the stretched exponential decay $e^{-Ct^{d/(d+2)}}$ for the parking time in the subcritical phase. This exponent is dimension-dependent and reveals a slower decay than a simple exponential.
  • Asymmetry Between Phases: The paper highlights a significant asymmetry between the subcritical ($p < 1/2$) and supercritical ($p > 1/2$) phases. In the subcritical phase, the parking time decays as $e^{-Ct^{d/(d+2)}}$, while in the supercritical phase (for $d=1$), the parking time of a spot decays like $e^{-c\sqrt{t}}$. This difference suggests distinct underlying mechanisms governing the system's evolution in each phase.
  • Dimension Dependence: The exponent $d/(d+2)$ clearly shows how the dimensionality of the grid influences the rate of decay. Higher dimensions lead to a slower decay (a larger exponent, closer to 1).
  • Improved Critical Density: The paper provides an improved bound for the critical density $p_0$ below which the expected total number of visits to the origin by cars is finite. Their bound $p_0 \sim d^{-2}$ is better than previous results.

Key Results

  • For $p > 0$ sufficiently small, the tail probability of the parking time $T$ of the car at the origin satisfies $P_p(\tau > t) \sim e^{-C_1 t^{d/(d+2)}}$.
  • For $d=1$ and $p \in [0, 1/2)$, the same bound holds.
  • For $p \in [0, p_0)$, where $p_0 \sim d^{-2}$, the tail probability is bounded by $P_p(\tau > t) \leq p e^{-c_2 t^{d/(d+2)}}$.
  • For $d=1$ and $p > 1/2$, the parking time of the spot at the origin decays as $e^{-c\sqrt{t}}$.
  • The expected total number of visits to the origin by cars for small $p$ is $E_p V = p + O(p^2 (\log p^{-1})^{(d+2)/d})$.

Limitations and Future Work

  • Subcritical Phase Focus: The primary result focuses on the subcritical phase ($p < 1/2$). While the paper contrasts this with the supercritical phase, a complete characterization of the supercritical phase's parking time decay for cars is not provided.
  • Continuous Time: The paper primarily deals with discrete-time random walks. Extending these results to continuous-time models (like diffusion-limited annihilating systems) is mentioned as a potential future direction, though it might require new technical tools.
  • General Graphs: The results are for $\mathbb{Z}^d$. Extending them to more general graphs, particularly infinite transitive unimodular graphs, is a natural next step, as hinted by the reference to previous work on such graphs.
  • Moving Spots: The paper contrasts its results with scenarios involving moving spots. Investigating the parking model with moving spots would be an interesting extension.

Summary updated

BibTeX
@inproceedings{damron2021stretched,
  author = {Michael Damron and Hanbaek Lyu and David Sivakoff},
  title = {{Stretched exponential decay for subcritical parking times on}},
  booktitle = {Random Struct. Algorithms},
  year = {2021},
  url = {https://openreview.net/forum?id=uMB3axOG6U},
}

Loading related content...

Figure