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

Bertoin, Jean; Miermont, Grégory

Random Struct. Algorithms 29, No. 1, 38-55 (2006).

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.

Reviewer: Vladimir Vatutin (Moskva)

MSC:

60C05

Combinatorial probability

Keywords:

additive coalescence; bridges with exchangeable increments

Citations:

Zbl 1032.60003; Zbl 0936.60064

References:

[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)