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
- NSF-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
-
-
more » « less
Abstract We study nonparametric maximum likelihood estimation for two classes of multivariate distributions that imply strong forms of positive dependence; namely log‐supermodular (
MTP 2) distributions andlog ‐L ♮ ‐concave (LLC ) distributions. In both cases we also assume log‐concavity in order to ensure boundedness of the likelihood function. Givenn independent and identically distributed random vectors from one of our distributions, the maximum likelihood estimator (MLE) exists a.s. and is unique a.e. with probability one whenn ≥3. This holds independently of the ambient dimensiond . We conjecture that the MLE is always the exponential of a tent function. We prove this result for samples in {0,1}d or in under MTP2, and for samples in under LLC. Finally, we provide a conditional gradient algorithm for computing the maximum likelihood estimate. -
more » « less
Abstract An $n \times n$ matrix with $\pm 1$ entries that acts on ${\mathbb {R}}^{n}$ as a scaled isometry is called Hadamard. Such matrices exist in some, but not all dimensions. Combining number-theoretic and probabilistic tools, we construct matrices with $\pm 1$ entries that act as approximate scaled isometries in ${\mathbb {R}}^{n}$ for all $n \in {\mathbb {N}}$. More precisely, the matrices we construct have condition numbers bounded by a constant independent of $n$.
Using this construction, we establish a phase transition for the probability that a random frame contains a Riesz basis. Namely, we show that a random frame in ${\mathbb {R}}^{n}$ formed by $N$ vectors with independent identically distributed coordinate having a nondegenerate symmetric distribution contains many Riesz bases with high probability provided that $N \ge \exp (Cn)$. On the other hand, we prove that if the entries are sub-Gaussian, then a random frame fails to contain a Riesz basis with probability close to $1$ whenever $N \le \exp (cn)$, where $c<C$ are constants depending on the distribution of the entries.
-
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
-
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
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1002/rsa.21001
