Premium
Asymptotics in Knuth's parking problem for caravans
Author(s) -
Bertoin Jean,
Miermont Grégory
Publication year - 2006
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20092
Subject(s) - struct , coalescent theory , mathematics , space (punctuation) , distribution (mathematics) , combinatorics , discrete mathematics , computer science , mathematical analysis , biochemistry , chemistry , operating system , gene , programming language , phylogenetic tree
We consider a generalized version of Knuth's parking problem, in which caravans consisting of a random number of cars arrive at random on the unit circle. Then each car turns clockwise until it finds a free space to park. Extending a recent work by Chassaing and Louchard Random Struct Algor 21(1) (2002), 76–119, we relate the asymptotics for the sizes of blocks formed by occupied spots with the dynamics of the additive coalescent. According to the behavior of the caravans' size tail distribution, several qualitatively different versions of the eternal additive coalescent are involved. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006