Saturation in a Markovian parking process. (English) Zbl 1012.60087

Summary: We consider \(\mathbb{Z}\) as an infinite lattice street where cars of integer length \(m\geq 1\) can park. The parking process is described by a 0-1 interacting particle system such that a site \(z\in\mathbb{Z}\) is in state 1 whenever a car has its rear end at \(z\) and 0 otherwise. Cars attempt to park after exponential times with parameter \(\lambda\), leave after exponential times with parameter 1 and are not allowed to touch nor overlap. We define and study a jamming occupation density for this parking process, using the quasi-stationary distribution of a Markov chain related to the reversible measure of the particle system. An extension to a strip in \(\mathbb{Z}^2\) is also investigated.


60K35 Interacting random processes; statistical mechanics type models; percolation theory
60J27 Continuous-time Markov processes on discrete state spaces
60K30 Applications of queueing theory (congestion, allocation, storage, traffic, etc.)
Full Text: DOI


[1] Baram, A. and Kutasov, D. (1994). Random sequential adsorption on a 3 \times lattice: an exact solution. J. Phys. A 27 3683-3687.
[2] Bean, N. G., Gibbens, R. J. and Zachary, S. (1997). Dynamic and equilibrium behavior of controlled loss networks. Ann. Appl. Probab. 7 873-885. · Zbl 0890.60087
[3] Bertsimas, D. and Chryssikou, T. (1999). Bounds and policies for dynamic routing in loss networks. Oper. Res. 47 379-394. JSTOR: · Zbl 0979.90012
[4] Chen, M. F. (1992). From Markov Chains to Nonequilibrium Particle Systems. World Scientific, Singapore. · Zbl 0753.60055
[5] Coffman, E. G. Jr., Flatto, L. and Jelenković, P. (2000). Interval packing: the vacant interval distribution. Ann. Appl. Probab. 10 240-257. · Zbl 1161.60338
[6] Coffman, E. G. Jr., Flatto, L., Mitrani, I., Shepp, L. A. and Knessl, C. (1988). Stochastic models of queue storage. Probab. Engrg. Inform. Sci. 2 75-93. · Zbl 1134.60391
[7] Coffman, E. G. Jr., Kadota, T. T. and Shepp, L. A. (1985). A stochastic model of fragmentation in dynamic storage allocation. SIAM J. Comput. 14 416-425. · Zbl 0605.68021
[8] Coffman, E. G. Jr., Mallows, C. L. and Poonen, B. (1994). Parking arcs on the circle with applications to one-dimensional communication networks. Ann. Appl. Probab. 4 1098-1111. · Zbl 0812.60090
[9] Cooper, D. W. (1987). Parking problem (sequential packing) simulations in two and three dimensions. J. Colloid Interface Sci. 119 442-450.
[10] Darroch, J. N. and Seneta, E. (1965). On quasi-stationary distributions in absorbing discrete-time Markov chains. J. Appl. Probab. 2 88-100. JSTOR: · Zbl 0134.34704
[11] Downton, F. (1961). A note on vacancies on a line. J. Roy. Statist. Soc. Ser. B 23 364-374. JSTOR: · Zbl 0101.10902
[12] Durrett, R. (1988). Lecture Notes on Particle Systems and Percolation. Wadsworth, Belmont, CA. · Zbl 0659.60129
[13] Dvoretzky, A. and Robbins, H. (1964). On the ‘parking’ problem. Publ. Math. Inst. Hung. Acad. Sci. 9 209-225. · Zbl 0251.60023
[14] Gotoh, K., Jodrey, W. and Tory, E. M. (1978). Average nearest-neighbour spacing in a random dispersion of equal spheres. Powder Technol. 21 285-287.
[15] Itoh, Y. and Shepp, L. (1999). Parking cars with spin but no length. J. Statist. Phys. 97 209-231. · Zbl 0954.60098
[16] Itoh, Y. and Ueda, S. (1979). A random packing model for elections. Ann. Inst. Statist. Math. 31 157-167. JSTOR: · Zbl 0411.92015
[17] Kelly, F. P. (1987). One-dimensional circuit-switched networks. Ann. Probab. 15 1166- 1179. · Zbl 0626.60102
[18] Kelly, F. P. (1991). Loss networks. Ann. Appl. Probab. 1 319-378. · Zbl 0743.60099
[19] Liggett, T. M. (1985). Interacting Particle Systems. Springer, New York. · Zbl 0559.60078
[20] Mackenzie, J. K. (1962). Sequential filling of a line by intervals placed at random and its applications to linear adsorption. J. Chem. Phys. 37 723-728.
[21] Morrison, J. A., Ramakrishnan, K. G. and Mitra, D. (1999). Refined asymptotic approximations to loss probabilties and their sensitivities in shared unbuffered resources. SIAM J. Appl. Math. 59 494-513. · Zbl 0920.60074
[22] Mullooly, J. P. (1968). A one-dimensional space filling problem. J. Appl. Probab. 5 427-435. JSTOR: · Zbl 0174.21505
[23] Ney, P. E. (1962). A random interval filling problem. Ann. Math. Statist. 33 702-718. · Zbl 0211.49105
[24] Page, E. S. (1959). The distribution of vacancies on a line. J. Roy. Statist. Soc. Ser. B 21 364-374. JSTOR: · Zbl 0092.35402
[25] Pakes, A. G. (1976). Some limit theorems for Markov chains with applications to branching processes. In Studies in Probability and Statistics (E. J. Williams, ed.) 21-39. NorthHolland, Amsterdam. · Zbl 0341.60039
[26] Palásti, I. (1960). On some random space filling problems. Publ. Math. Inst. Hung. Acad. Sci. 5 353-360. · Zbl 0247.60011
[27] Rényi, A. (1958). On a one-dimensional problem concerning random space filling. Publ. Math. Inst. Hung. Acad. Sci. 3 109-127. · Zbl 0211.49601
[28] Rhee, W. T. (2000). Order of decay of the wasted space for a stochastic packing problem. Ann. Appl. Probab. 10 539-548. · Zbl 1051.60012
[29] Seneta, E. (1981). Nonnegative Matrices and Markov Chains. Springer, New York. · Zbl 0471.60001
[30] Suomela, P. (1976). Construction of nearest neighbours systems. Ann. Acad. Sci. Fenn. Ser. A I Math. Dissertationes 10. · Zbl 0358.60067
[31] Ycart, B. (1993). The philosopher’s process: an ergodic reversible nearest particle system. Ann. Appl. Probab. 3 356-363. · Zbl 0798.60086
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.