Multiclass Hammersley-Aldous-Diaconis process and multiclass-customer queues
Annales de l'I.H.P. Probabilités et statistiques, Volume 45 (2009) no. 1, pp. 250-265.

In the Hammersley-Aldous-Diaconis process, infinitely many particles sit in ℝ and at most one particle is allowed at each position. A particle at x, whose nearest neighbor to the right is at y, jumps at rate y-x to a position uniformly distributed in the interval (x, y). The basic coupling between trajectories with different initial configuration induces a process with different classes of particles. We show that the invariant measures for the two-class process can be obtained as follows. First, a stationary M/M/1 queue is constructed as a function of two homogeneous Poisson processes, the arrivals with rate λ and the (attempted) services with rate ρ>λ. Then put first class particles at the instants of departures (effective services) and second class particles at the instants of unused services. The procedure is generalized for the n-class case by using n-1 queues in tandem with n-1 priority types of customers. A multi-line process is introduced; it consists of a coupling (different from Liggett's basic coupling), having as invariant measure the product of Poisson processes. The definition of the multi-line process involves the dual points of the space-time Poisson process used in the graphical construction of the reversed process. The coupled process is a transformation of the multi-line process and its invariant measure is the transformation described above of the product measure.

Dans un processus de Hammersley nous considérons une infinité de particules sur la droite réelle; et il ne peut pas y avoir plus d'une particule sur chaque position. Une particule située en x et ayant pour plus proche voisine (sur sa droite) une particule située en y, saute avec un taux y-x à une position aléatoire choisie uniformément dans l'interval (x, y). Le couplage basique entre des trajectoires ayant des configurations initiales différentes induit un processus avec des particules de classes différentes. Nous donnons une construction explicite de la mesure invariante pour le processus ayant n classes de particules. Pour démontrer que la mesure est invariante nous introduisons un autre processus appelé «multi-ligne». La mesure invariante pour ce processus est un produit de plusieurs processus de Poisson. La définition du processus multi-ligne met en jeu les «points duaux» (de l'espace-temps), qui apparaient naturellement dans la construction graphique du processus renversé par rapport au temps.

DOI: 10.1214/08-AIHP168
Classification: 60K35, 60K25, 90B22
Keywords: multi-class Hammersley-Aldous-Diaconis process, multiclass queuing system, invariant measures
     author = {Ferrari, Pablo A. and Martin, James B.},
     title = {Multiclass {Hammersley-Aldous-Diaconis} process and multiclass-customer queues},
     journal = {Annales de l'I.H.P. Probabilit\'es et statistiques},
     pages = {250--265},
     publisher = {Gauthier-Villars},
     volume = {45},
     number = {1},
     year = {2009},
     doi = {10.1214/08-AIHP168},
     mrnumber = {2500238},
     zbl = {1171.60383},
     language = {en},
     url = {}
AU  - Ferrari, Pablo A.
AU  - Martin, James B.
TI  - Multiclass Hammersley-Aldous-Diaconis process and multiclass-customer queues
JO  - Annales de l'I.H.P. Probabilités et statistiques
PY  - 2009
SP  - 250
EP  - 265
VL  - 45
IS  - 1
PB  - Gauthier-Villars
UR  -
DO  - 10.1214/08-AIHP168
LA  - en
ID  - AIHPB_2009__45_1_250_0
ER  - 
%0 Journal Article
%A Ferrari, Pablo A.
%A Martin, James B.
%T Multiclass Hammersley-Aldous-Diaconis process and multiclass-customer queues
%J Annales de l'I.H.P. Probabilités et statistiques
%D 2009
%P 250-265
%V 45
%N 1
%I Gauthier-Villars
%R 10.1214/08-AIHP168
%G en
%F AIHPB_2009__45_1_250_0
Ferrari, Pablo A.; Martin, James B. Multiclass Hammersley-Aldous-Diaconis process and multiclass-customer queues. Annales de l'I.H.P. Probabilités et statistiques, Volume 45 (2009) no. 1, pp. 250-265. doi : 10.1214/08-AIHP168.

[1] D. Aldous and P. Diaconis. Hammersley's interacting particle process and longest increasing subsequences. Probab. Theory Related Fields 103 (1995) 199-213. | MR | Zbl

[2] O. Angel. The stationary measure of a 2-type totally asymmetric exclusion process. J. Combin. Theory Ser. A 113 (2006) 625-635. | MR | Zbl

[3] F. Baccelli and P. Brémaud. Elements of Queueing Theory, 2nd edition. Springer, Berlin, 2003. | MR | Zbl

[4] E. Cator and P. Groeneboom. Hammersley's process with sources and sinks. Ann. Probab. 33 (2005) 879-903. | MR | Zbl

[5] B. Derrida, S. A. Janowsky, J. L. Lebowitz and E. R. Speer. Exact solution of the totally asymmetric simple exclusion process: shock profiles. J. Statist. Phys. 73 (1993) 813-842. | MR | Zbl

[6] E. Duchi and G. Schaeffer. A combinatorial approach to jumping particles. J. Combin. Theory Ser. A 110 (2005) 1-29. | MR | Zbl

[7] M. Ekhaus and L. Gray. A strong law for the motion of interfaces in particle systems. Unpublished manuscript, 1993.

[8] P. A. Ferrari. Shock fluctuations in asymmetric simple exclusion. Probab. Theory Related Fields 91 (1992) 81-101. | MR | Zbl

[9] P. A. Ferrari, L. R. G. Fontes and Y. Kohayakawa. Invariant measures for a two-species asymmetric process. J. Statist. Phys. 76 (1994) 1153-1177. | MR | Zbl

[10] P. A. Ferrari, C. Kipnis and E. Saada. Microscopic structure of travelling waves in the asymmetric simple exclusion process. Ann. Probab. 19 (1991) 226-244. | MR | Zbl

[11] P. A. Ferrari and J. B. Martin. Stationary distributions of multi-type totally asymmetric exclusion processes. Ann. Probab. 35 (2007) 807-832. | MR | Zbl

[12] P. A. Ferrari and J. B. Martin. Multiclass processes, dual points and M/M/1 queues. Markov Process. Related Fields 12 (2006) 273-299. | MR | Zbl

[13] P. L. Ferrari. Polynuclear growth on a flat substrate and edge scaling of GOE eigenvalues. Comm. Math. Phys. 252 (2004) 77-109. | MR | Zbl

[14] J. E. Garcia. Processo de Hammersley. Ph.d. Thesis (Portuguese). University of São Paulo, 2000. Available at

[15] J. M. Hammersley. A few seedlings of research. In Proceedings of the Sixth Berkeley Symposium on Mathematical Statistics and Probability (Univ. California, Berkeley, Calif., 1970/1971), Vol. I: Theory of statistics 345-394. Univ. California Press, Berkeley, Calif, 1972. | MR | Zbl

[16] T. M. Liggett. Coupling the simple exclusion process. Ann. Probab. 4 (1976) 339-356. | MR | Zbl

[17] T. M. Liggett. Interacting Particle Systems. Springer, New York, 1985. | MR | Zbl

[18] T. M. Liggett. Stochastic Interacting Systems: Contact, Voter and Exclusion Processes. Springer, Berlin, 1999. | MR | Zbl

[19] T. Mountford and B. Prabhakar. On the weak convergence of departures from an infinite series of /M/1 queues. Ann. Appl. Probab. 5 (1995) 121-127. | MR | Zbl

[20] M. Prähofer and H. Spohn. Scale invariance of the PNG droplet and the Airy process J. Stat. Phys. 108 (2002) 1071-1106. | MR | Zbl

[21] T. Sepäläinen. A microscopic model for the Burgers equation and longest increasing subsequences. Electron. J. Probab. 1 (1996) (approx.) 51 pp. (electronic). | EuDML | MR | Zbl

[22] E. R. Speer. The two species asymmetric simple exclusion process. In On Three Levels: Micro, Meso and Macroscopic Approaches in Physics 91-102. C. M. M. Fannes and A. Verbuere (Eds). Plenum, New York, 1994. | Zbl

[23] W. D. Wick. A dynamical phase transition in an infinite particle system. J. Statist. Phys. 38 (1985) 1015-1025. | MR | Zbl

Cited by Sources: