Asymptotics in Knuth’s parking problem for caravans. (English) Zbl 1102.60006

A generalized version of Knuth’s parking problem is considered, in which instead of cars drops of paint are distributed at random on the unit circle. More precisely, let \(s_1,s_2,\dots,s_m\) be \(m\) locations on the unit circle (selected according to some probabilistic procedure described in the paper) and let \(p_1,\dots,p_m\) be the (random) sizes of \(m\) drops of paint of total mass 1. These drops fall successively at the respective locations. Each time a drop of paint falls we brush it clockwise in such a way that the resulting painted portion of the circle is covered by a unit density of paint (i.e., no piece of circle is brushed twice). In this setting drops of paint may be viewed as a continuous version of \(m\) car caravans of total size \(n\) arriving at random on a circle with \(n\) parking spots.
Extending a recent paper of P. Chassaing and G. Louchard [Random Struct. Algorithms 21, No. 1, 76–119 (2002; Zbl 1032.60003)] the authors relate the asymptotics of the sizes of blocks formed by the painted pieces of the circle with the dynamics of the additive coalescence described by D. J. Aldous and J. Pitman [Ann. Probab. 26, No. 4, 1703–1726 (1998; Zbl 0936.60064)] and, imposing different assumptions on the tail distribution of the drops’ size, characterize several qualitatively different versions of the eternal additive coalescence.


60C05 Combinatorial probability
Full Text: DOI arXiv HAL


[1] Aldous, Ann Probab 26 pp 1703– (1998)
[2] Aldous, Random Struct Algor 15 pp 176– (1999)
[3] Aldous, Probab Theory Relat Fields 118 pp 455– (2000)
[4] Bertoin, Probab Theory Relat Fields 117 pp 289– (2000)
[5] Bertoin, Ann Probab 29 pp 344– (2001)
[6] Bertoin, Random Struct Algor 25 pp 277– (2004)
[7] Camarri, Electron J Probab 5 pp 18– (2000)
[8] Chassaing, Random Struct Algor 21 pp 76– (2002)
[9] Dvoretzky, Magyar Tud Akad Mat Kutató Int Közl 9 pp 209– (1964)
[10] Evans, Ann Inst Henri Poincare Probab Stat 34 pp 339– (1998)
[11] Kallenberg, Gebiete 27 pp 23– (1973)
[12] Le Gall, Basel (1999)
[13] Miermont, Electron J Probab 6 pp 33– (2002)
[14] Pitman, Ann Probab 25 pp 855– (1997)
[15] Rényi, Magyar Tud Akad Mat Kutató Int Közl 3 pp 109– (1958)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.