# 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.

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.

## Citations

3 citations in Web of Science®
4 citations in Scopus®

## Altmetrics

Detailed statistics

Item Type: Journal Article, refereed, original work 07 Faculty of Science > Institute of Mathematics 510 Mathematics English 2011 24 Apr 2013 11:39 05 Apr 2016 16:43 Springer 0010-3616 Publisher DOI. An embargo period may apply. https://doi.org/10.1007/s00220-011-1288-8
Permanent URL: https://doi.org/10.5167/uzh-77147

 Preview
Content: Presentation
Language: English
Filetype: PDF
Size: 916kB
View at publisher

## TrendTerms

TrendTerms displays relevant terms of the abstract of this publication and related documents on a map. The terms and their relations were extracted from ZORA using word statistics. Their timelines are taken from ZORA as well. The bubble size of a term is proportional to the number of documents where the term occurs. Red, orange, yellow and green colors are used for terms that occur in the current document; red indicates high interlinkedness of a term with other terms, orange, yellow and green decreasing interlinkedness. Blue is used for terms that have a relation with the terms in this document, but occur in other documents.
You can navigate and zoom the map. Mouse-hovering a term displays its timeline, clicking it yields the associated documents.