Phase transition for Parking blocks, Brownian excursion and coalescence

Publisher Website
Google Scholar
Abstract
In this paper, we consider hashing with linear probing for a hashing table with m places, n items (n < m), and ℓ = m − n empty places. For a noncomputer science‐minded reader, we shall use the metaphore of n cars parking on m places: each car ci chooses a place pi at random, and if pi is occupied, ci tries successively pi + 1, pi + 2, until it finds an empty place. Pittel [42] proves that when ℓ/m goes to some positive limit β < 1, the size B of the largest block of consecutive cars satisfies 2(β − 1 − log β)B = 2 log m − 3 log log m + Ξm, where Ξm converges weakly to an extreme‐value distribution. In this paper we examine at which level for n a phase transition occurs between B = o(m) and m − B = o(m). The intermediate case reveals an interesting behavior of sizes of blocks, related to the standard additive coalescent in the same way as the sizes of connected components of the random graph are related to the multiplicative coalescent. © 2002 Wiley Periodicals, Inc. Random Struct. Alg., 21: 76–119, 2002

This publication has 39 references indexed in Scilit: