Burning cars in a parking lot

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.