Header

UZH-Logo

Maintenance Infos

Burning cars in a parking lot


Bertoin, J (2011). Burning cars in a parking lot. Communications in Mathematical Physics, 306(1):261-290.

Abstract

Knuth’s parking scheme is a model in computer science for hashing with linear probing. One may imagine a circular parking lot with n sites; cars arrive at each site with unit rate. When a car arrives at a vacant site, it parks there; otherwise it turns clockwise and parks at the first vacant site which is found. We incorporate fires into this model by throwing Molotov cocktails on each site at a smaller rate n −α , where 0 < α < 1 is a fixed parameter. When a car is hit by a Molotov cocktail, it burns and the fire propagates to the entire occupied interval which turns vacant. We show that with high probability when n → ∞, the parking lot becomes saturated at a time close to 1 (i.e. as in the absence of fire) for α > 2/3, whereas for α < 2/3, the average occupation approaches 1 at time 1 but then quickly drops to 0 before the parking lot is ever saturated. Our study relies on asymptotics for the occupation of the parking lot without fires in certain regimes which may be of independent interest.

Abstract

Knuth’s parking scheme is a model in computer science for hashing with linear probing. One may imagine a circular parking lot with n sites; cars arrive at each site with unit rate. When a car arrives at a vacant site, it parks there; otherwise it turns clockwise and parks at the first vacant site which is found. We incorporate fires into this model by throwing Molotov cocktails on each site at a smaller rate n −α , where 0 < α < 1 is a fixed parameter. When a car is hit by a Molotov cocktail, it burns and the fire propagates to the entire occupied interval which turns vacant. We show that with high probability when n → ∞, the parking lot becomes saturated at a time close to 1 (i.e. as in the absence of fire) for α > 2/3, whereas for α < 2/3, the average occupation approaches 1 at time 1 but then quickly drops to 0 before the parking lot is ever saturated. Our study relies on asymptotics for the occupation of the parking lot without fires in certain regimes which may be of independent interest.

Statistics

Citations

3 citations in Web of Science®
5 citations in Scopus®
Google Scholar™

Altmetrics

Downloads

115 downloads since deposited on 24 Apr 2013
8 downloads since 12 months
Detailed statistics

Additional indexing

Item Type:Journal Article, refereed, original work
Communities & Collections:07 Faculty of Science > Institute of Mathematics
Dewey Decimal Classification:510 Mathematics
Language:English
Date:2011
Deposited On:24 Apr 2013 11:39
Last Modified:09 Jan 2018 19:49
Publisher:Springer
ISSN:0010-3616
Free access at:Publisher DOI. An embargo period may apply.
Publisher DOI:https://doi.org/10.1007/s00220-011-1288-8

Download

Download PDF  'Burning cars in a parking lot'.
Preview
Content: Presentation
Language: English
Filetype: PDF
Size: 916kB
View at publisher