An official website of the United States government
Classical parking functions are defined as the parking preferences for $$n$$ cars driving (from west to east) down a one-way street containing parking spaces labeled from $$1$$ to $$n$$ (from west to east). Cars drive down the street toward their preferred spot and park there if the spot is available. Otherwise, the car continues driving down the street and takes the first available parking space, if such a space exists. If all cars can park using this parking rule, we call the $$n$$-tuple containing the cars' parking preferences a parking function. In this paper, we introduce a generalization of the parking rule allowing cars whose preferred space is taken to first proceed up to $$k$$ spaces west of their preferred spot to park before proceeding east if all of those $$k$$ spaces are occupied. We call parking preferences which allow all cars to park under this new parking rule $$k$$-Naples parking functions of length $$n$$. This generalization gives a natural interpolation between classical parking functions, the case when $k=0$, and all $$n$$-tuples of positive integers $$1$$ to $$n$$, the case when $$k\geq n-1$$. Our main result provides a recursive formula for counting $$k$$-Naples parking functions of length $$n$$. We also give a characterization for the $k=1$ case by introducing a new function that maps $$1$$-Naples parking functions to classical parking functions, i.e. $$0$$-Naples parking functions. Lastly, we present a bijection between $$k$$-Naples parking functions of length $$n$$ whose entries are in weakly decreasing order and a family of signature Dyck paths.
more »
« less
Stretched exponential decay for subcritical parking times on
In the parking model on ℤd, each vertex is initially occupied by a car (with probability p) or by a vacant parking spot (with probability 1−p). Cars perform independent random walks and when they enter a vacant spot, they park there, thereby rendering the spot occupied. Cars visiting occupied spots simply keep driving (continuing their random walk). It is known that p=1/2 is a critical value in the sense that the origin is a.s. visited by finitely many distinct cars when p<1/2, and by infinitely many distinct cars when p≥1/2. Furthermore, any given car a.s. eventually parks for p≤1/2 and with positive probability does not park for p>1/2. We study the subcritical phase and prove that the tail of the parking time τ of the car initially at the origin obeys the bounds exp(−C1tdd+2)≤ℙp(τ>t)≤exp(−c2tdd+2) for p>0 sufficiently small. For d=1, we prove these inequalities for all p∈[0,1/2). This result presents an asymmetry with the supercritical phase (p>1/2), where methods of Bramson--Lebowitz imply that for d=1 the corresponding tail of the parking time of the parking spot of the origin decays like e−ct√. Our exponent d/(d+2) also differs from those previously obtained in the case of moving obstacles.
more »
« less
- PAR ID:
- 10220027
- Date Published:
- Journal Name:
- Random Structures & Algorithms
- ISSN:
- 1042-9832
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
null (Ed.)Spot-level parking availability information (the availability of each spot in a parking lot) is in great demand, as it can help reduce time and energy waste while searching for a parking spot. In this article, we propose a crowdsensing system called SpotE that can provide spot-level availability in a parking lot using drivers’ smartphone sensors. SpotE only requires the sensor data from drivers’ smartphones, which avoids the high cost of installing additional sensors and enables large-scale outdoor deployment. We propose a new model that can use the parking search trajectory and final destination (e.g., an exit of the parking lot) of a single driver in a parking lot to generate the probability profile that contains the probability of each spot being occupied in a parking lot. To deal with conflicting estimation results generated from different drivers, due to the variance in different drivers’ parking behaviors, a novel aggregation approach SpotE-TD is proposed. The proposed aggregation method is based on truth discovery techniques and can handle the variety in Quality of Information of different vehicles. We evaluate our proposed method through a real-life deployment study. Results show that SpotE-TD can efficiently provide spot-level parking availability information with a 20% higher accuracy than the state-of-the-art.more » « less
-
The smart parking industry continues to evolve as an increasing number of cities struggle with traffic congestion and inadequate parking availability. For urban dwellers, few things are more irritating than anxiously searching for a parking space. Research results show that as much as 30% of traffic is caused by drivers driving around looking for parking spaces in congested city areas. There has been considerable activity among researchers to develop smart technologies that can help drivers find a parking spot with greater ease, not only reducing traffic congestion but also the subsequent air pollution. Many existing solutions deploy sensors in every parking spot to address the automatic parking spot detection problems. However, the device and deployment costs are very high, especially for some large and old parking structures. A wide variety of other technological innovations are beginning to enable more adaptable systems-including license plate number detection, smart parking meter, and vision-based parking spot detection. In this paper, we propose to design a more adaptable and affordable smart parking system via distributed cameras, edge computing, data analytics, and advanced deep learning algorithms. Specifically, we deploy cameras with zoom-lens and motorized head to capture license plate numbers by tracking the vehicles when they enter or leave the parking lot; cameras with wide angle fish-eye lens will monitor the large parking lot via our custom designed deep neural network. We further optimize the algorithm and enable the real-time deep learning inference in an edge device. Through the intelligent algorithm, we can significantly reduce the cost of existing systems, while achieving a more adaptable solution. For example, our system can automatically detect when a car enters the parking space, the location of the parking spot, and precisely charge the parking fee and associate this with the license plate number.more » « less
-
Abstract Shalom and Tao showed that a polynomial upper bound on the size of a single, large enough ball in a Cayley graph implies that the underlying group has a nilpotent subgroup with index and degree of polynomial growth both bounded effectively.The third and fourth authors proved the optimal bound on the degree of polynomial growth of this subgroup, at the expense of making some other parts of the result ineffective.In the present paper, we prove the optimal bound on the degree of polynomial growth without making any losses elsewhere.As a consequence, we show that there exist explicit positive numbers ε d \varepsilon_{d} such that, in any group with growth at least a polynomial of degree 𝑑, the growth is at least ε d n d \varepsilon_{d}n^{d} .We indicate some applications in probability; in particular, we show that the gap at 1 for the critical probability for Bernoulli site percolation on a Cayley graph, recently proven to exist by Panagiotis and Severo, is at least exp { - exp { 17 exp { 100 ⋅ 8 100 } } } \exp\{-\exp\{17\exp\{100\cdot 8^{100}\}\}\} .more » « less
-
In the system we study, 1's and 0's represent occupied and vacant sites in the contact process with births at rate $$\lambda$$ and deaths at rate 1. $-1$'s are sterile individuals that do not reproduce but appear spontaneously on vacant sites at rate $$\alpha$$ and die at rate $$\theta\alpha$$. We show that the system (which is attractive but has no dual) dies out at the critical value and has a nontrivial stationary distribution when it is supercritical. Our most interesting results concern the asymptotics when $$\alpha\to 0$$. In this regime the process resembles the contact process in a random environment.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1002/rsa.21001
