document: Phase transition for parking blocks , Brownian excursion and coalescence In this paper , we consider hashing with linear probing for a hashing table with m places , n items -LRB- n < m -RRB- , and l = m-n empty places . For a noncomputer science-minded reader , we shall use the metaphore of n cars parking on m places : each car c/sub i / chooses a place p/sub i / at random , and if p/sub i / is occupied , c/sub i / tries successively p/sub i / +1 , p/sub i / +2 , until it finds an empty place . Pittel -LSB- 42 -RSB- proves that when l/m goes to some positive limit beta < 1 , the size B/sub 1 / / sup m , l / of the largest block of consecutive cars satisfies 2 -LRB- beta -1 - log beta -RRB- B/sub 1 / / sup m , l / = 2 log m-3 log log m + Xi / sub m / , where Xi / sub m / converges weakly to an extreme-value distribution . In this paper we examine at which level for n a phase transition occurs between B/sub 1 / / sup m , l / = o -LRB- m -RRB- and m-B/sub 1 / / sup m , l / = o -LRB- m -RRB- . 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
doc_bio_tags: O O O B I O B I O B O O O O O O B O B I O O B O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O