Multiclass Hammersley–Aldous–Diaconis process and multiclass-customer queues

Pablo A. Ferrari; James B. Martin

Annales de l'I.H.P. Probabilités et statistiques (2009)

  • Volume: 45, Issue: 1, page 250-265
  • ISSN: 0246-0203

Abstract

top
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.

How to cite

top

Ferrari, Pablo A., and Martin, James B.. "Multiclass Hammersley–Aldous–Diaconis process and multiclass-customer queues." Annales de l'I.H.P. Probabilités et statistiques 45.1 (2009): 250-265. <http://eudml.org/doc/78019>.

@article{Ferrari2009,
abstract = {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 ρ&gt;λ. 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.},
author = {Ferrari, Pablo A., Martin, James B.},
journal = {Annales de l'I.H.P. Probabilités et statistiques},
keywords = {multi-class Hammersley–Aldous–Diaconis process; multiclass queuing system; invariant measures; multi-class Hammersley-Aldous-Diaconis process},
language = {eng},
number = {1},
pages = {250-265},
publisher = {Gauthier-Villars},
title = {Multiclass Hammersley–Aldous–Diaconis process and multiclass-customer queues},
url = {http://eudml.org/doc/78019},
volume = {45},
year = {2009},
}

TY - JOUR
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
PB - Gauthier-Villars
VL - 45
IS - 1
SP - 250
EP - 265
AB - 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 ρ&gt;λ. 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.
LA - eng
KW - multi-class Hammersley–Aldous–Diaconis process; multiclass queuing system; invariant measures; multi-class Hammersley-Aldous-Diaconis process
UR - http://eudml.org/doc/78019
ER -

References

top
  1. [1] D. Aldous and P. Diaconis. Hammersley’s interacting particle process and longest increasing subsequences. Probab. Theory Related Fields 103 (1995) 199–213. Zbl0836.60107MR1355056
  2. [2] O. Angel. The stationary measure of a 2-type totally asymmetric exclusion process. J. Combin. Theory Ser. A 113 (2006) 625–635. Zbl1087.60067MR2216456
  3. [3] F. Baccelli and P. Brémaud. Elements of Queueing Theory, 2nd edition. Springer, Berlin, 2003. Zbl1021.60001MR1957884
  4. [4] E. Cator and P. Groeneboom. Hammersley’s process with sources and sinks. Ann. Probab. 33 (2005) 879–903. Zbl1066.60011MR2135307
  5. [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. Zbl1102.60320MR1251221
  6. [6] E. Duchi and G. Schaeffer. A combinatorial approach to jumping particles. J. Combin. Theory Ser. A 110 (2005) 1–29. Zbl1059.05006MR2128962
  7. [7] M. Ekhaus and L. Gray. A strong law for the motion of interfaces in particle systems. Unpublished manuscript, 1993. 
  8. [8] P. A. Ferrari. Shock fluctuations in asymmetric simple exclusion. Probab. Theory Related Fields 91 (1992) 81–101. Zbl0744.60117MR1142763
  9. [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. Zbl0841.60085MR1298099
  10. [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. Zbl0725.60113MR1085334
  11. [11] P. A. Ferrari and J. B. Martin. Stationary distributions of multi-type totally asymmetric exclusion processes. Ann. Probab. 35 (2007) 807–832. Zbl1117.60089MR2319708
  12. [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. Zbl1155.60043MR2249632
  13. [13] P. L. Ferrari. Polynuclear growth on a flat substrate and edge scaling of GOE eigenvalues. Comm. Math. Phys. 252 (2004) 77–109. Zbl1124.82316MR2103905
  14. [14] J. E. Garcia. Processo de Hammersley. Ph.d. Thesis (Portuguese). University of São Paulo, 2000. Available at http://www.ime.usp.br/~pablo/students/jesus/garcia-tese.pdf. 
  15. [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. Zbl0236.00018MR405665
  16. [16] T. M. Liggett. Coupling the simple exclusion process. Ann. Probab. 4 (1976) 339–356. Zbl0339.60091MR418291
  17. [17] T. M. Liggett. Interacting Particle Systems. Springer, New York, 1985. Zbl0559.60078MR776231
  18. [18] T. M. Liggett. Stochastic Interacting Systems: Contact, Voter and Exclusion Processes. Springer, Berlin, 1999. Zbl0949.60006MR1717346
  19. [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. Zbl0826.60083MR1325044
  20. [20] M. Prähofer and H. Spohn. Scale invariance of the PNG droplet and the Airy process J. Stat. Phys. 108 (2002) 1071–1106. Zbl1025.82010MR1933446
  21. [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). Zbl0891.60093MR1386297
  22. [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. Zbl0872.60084
  23. [23] W. D. Wick. A dynamical phase transition in an infinite particle system. J. Statist. Phys. 38 (1985) 1015–1025. Zbl0625.76080MR802566

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.