Hostname: page-component-848d4c4894-wzw2p Total loading time: 0 Render date: 2024-05-19T15:24:14.043Z Has data issue: false hasContentIssue false
  • English
  • Français

Queues, stores, and tableaux

Part of: Combinatorial probability Special processes Equilibrium statistical mechanics

Published online by Cambridge University Press:  14 July 2016

Moez Draief ,
Jean Mairesse  and
Neil O'Connell
Moez Draief*
Affiliation:
Université Paris 7
Jean Mairesse*
Affiliation:
Université Paris 7
Neil O'Connell*
Affiliation:
The University of Warwick
*
∗Postal address: LIAFA, Université Paris 7, case 7014, 2 place Jussieu, 75251 Paris Cedex 05, France.
∗Postal address: LIAFA, Université Paris 7, case 7014, 2 place Jussieu, 75251 Paris Cedex 05, France.
∗∗∗∗Postal address: Mathematics Institute, The University of Warwick, Coventry CV4 7AL, UK. Email address: noc@maths.warwick.ac.uk
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Consider the single-server queue with an infinite buffer and a first-in–first-out discipline, either of type M/M/1 or Geom/Geom/1. Denote by 𝒜 the arrival process and by s the services. Assume the stability condition to be satisfied. Denote by 𝒟 the departure process in equilibrium and by r the time spent by the customers at the very back of the queue. We prove that (𝒟, r) has the same law as (𝒜, s), which is an extension of the classical Burke theorem. In fact, r can be viewed as the sequence of departures from a dual storage model. This duality between the two models also appears when studying the transient behaviour of a tandem by means of the Robinson–Schensted–Knuth algorithm: the first and last rows of the resulting semistandard Young tableau are respectively the last instant of departure from the queue and the total number of departures from the store.

Keywords

Single-server queuestorage modelBurke's theoremnoncolliding random walktandem of queuesRobinson–Schensted–Knuth algorithm

MSC classification

Primary: 60K25: Queueing theory 60K35: Interacting random processes; statistical mechanics type models; percolation theory
Secondary: 60C05: Combinatorial probability 82B41: Random walks, random surfaces, lattice animals, etc.
Type
Research Papers
Information
Journal of Applied Probability , Volume 42 , Issue 4 , December 2005 , pp. 1145 - 1167
Copyright
© Applied Probability Trust 2005 

References

Anantharam, V. (1987). Probabilistic proof of the interchangeability of ·/ M/1 queues in series. Queueing Systems Theory Appl. 2, 387–392.CrossRefGoogle Scholar
Baccelli, F., Borovkov, A. and Mairesse, J. (2000). Asymptotic results on infinite tandem queueing networks. Prob. Theory Relat. Fields 118, 365–405.CrossRefGoogle Scholar
Baryshnikov, Yu. (2001). GUEs and queues. Prob. Theory Relat. Fields 119, 256–274.Google Scholar
Bedekar, A. S. and Azizoglu, M. (1998). The information-theoretic capacity of discrete-time queues. IEEE Trans. Inf. Theory 44, 446–461.Google Scholar
Brémaud, P. (1981). Point Processes and Queues. Martingale Dynamics. Springer, Berlin.Google Scholar
Bruneel, H. and Kim, B. G. (1993). Discrete-Time Models for Communication Systems Including ATM. Kluwer, Boston, MA.Google Scholar
Burke, P. (1956). The output of a queueing system. Operat. Res. 4, 699–704.Google Scholar
Chang, C. S. (1994). On the input–output map of a G/G/1 queue. J. Appl. Prob. 31, 1128–1133.CrossRefGoogle Scholar
Daley, D. J. and Vere-Jones, D. (1988). An Introduction to the Theory of Point Processes. Springer, New York.Google Scholar
Draief, M., Mairesse, J. and O'Connell, N. (2003). Joint Burke's theorem and RSK representation for a queue and a store. In Discrete Random Walks (Paris, 2003), eds Banderier, C. and Krattenthaler, C., Association of Discrete Mathematics and Theoretical Computer Science, Nancy, pp. 69–82.Google Scholar
Glynn, P. W. and Whitt, W. (1991). Departures from many queues in series. Ann. Appl. Prob. 1, 546–572.Google Scholar
Hambly, B., Martin, J. and O'Connell, N. (2001). Pitman's 2M-X theorem for skip-free random walks with Markovian increments. Electron. Commun. Prob. 6, 73–77.CrossRefGoogle Scholar
Harrison, J. and Williams, R. (1990). On the quasireversibility of a multiclass Brownian service station. Ann. Prob. 18, 1249–1268.Google Scholar
Hsu, J. and Burke, P. (1976). Behavior of tandem buffers with geometric input and Markovian output. IEEE Trans. Commun. 24, 358–361.CrossRefGoogle Scholar
Kelly, F. (1979). Reversibility and Stochastic Networks. John Wiley, New York.Google Scholar
Kipnis, C. and Landim, C. (1999). Scaling Limits of Interacting Particle Systems. Springer, Berlin.Google Scholar
Knuth, D. (1970). Permutations, matrices, and generalized Young tableaux. Pacific J. Math. 34, 709–727.Google Scholar
König, W., O'Connell, N. and Roch, S. (2002). Non-colliding random walks, tandem queues, and discrete orthogonal polynomial ensembles. Electron. J. Prob. 7, 1–24.CrossRefGoogle Scholar
Liggett, T. M. (1999). Stochastic Interacting Systems: Contact, Voter and Exclusion Processes. Springer, Berlin.CrossRefGoogle Scholar
Mairesse, J. and Prabhakar, B. (2003). The existence of fixed points for the ·/GI/1 queue. Ann. Prob. 31, 2216–2236.Google Scholar
Muth, E. (1979). The reversibility property of production lines. Manag. Sci. 25, 152–158.Google Scholar
O'Connell, N. (2003). A path-transformation for random walks and the Robinson–Schensted correspondence. Trans. Amer. Math. Soc. 355, 3669–3697.Google Scholar
O'Connell, N. (2003). Conditioned random walks and the RSK correspondence. J. Phys. A 36, 3049–3066.Google Scholar
O'Connell, N. and Yor, M. (2001). Brownian analogues of Burke's theorem. Stoch. Process. Appl. 96, 285–304.Google Scholar
O'Connell, N. and Yor, M. (2002). A representation for non-colliding random walks. Electron. Commun. Prob. 7, 1–12.Google Scholar
Prabhakar, B. (2003). The attractiveness of the fixed points of a ·/GI/1 queue. Ann. Prob. 31, 2237–2269.Google Scholar
Prabhakar, B. and Gallager, R. (2003). Entropy and the timing capacity of discrete queues. IEEE Trans. Inf. Theory 49, 357–370.Google Scholar
Rajewsky, N., Santen, L., Schadschneider, A. and Schreckenberg, M. (1998). The asymmetric exclusion process: comparison of update procedures. J. Statist. Phys. 92, 151–194.Google Scholar
Ratnarajah, T., Vaillancourt, R. and Alvo, M. (2005). Eigenvalues and condition numbers of complex random matrices. SIAM J. Matrix Anal. Appl. 26, 441–456.Google Scholar
Reich, E. (1957). Waiting times when queues are in tandem. Ann. Math. Statist. 28, 768–773.Google Scholar
Robert, P. (2003). Stochastic Networks and Queues (Appl. Math. 52). Springer, Berlin.Google Scholar
Sagan, B. (2001). The Symmetric Group. Representations, Combinatorial Algorithms, and Symmetric Functions (Graduate Texts Math. 203), 2nd edn. Springer, Berlin.Google Scholar
Seppäläinen, T. (2000). A variational coupling for a totally asymmetric exclusion process with long Jumps but no passing. In Hydrodynamic Limits and Related Topics (Fields Inst. Commun. 27; Toronto, ON, 1998), American Mathematical Society, Providence, RI, pp. 117–130.Google Scholar
Stanley, R. (1999). Enumerative Combinatorics (Camb. Studies Adv. Math. 62), Vol. 2. Cambridge University Press.CrossRefGoogle Scholar
Szczotka, W. and Kelly, F. (1990). Asymptotic stationarity of queues in series and the heavy traffic approximation. Ann. Prob. 18, 1232–1248.Google Scholar
Takagi, H. (1993). Queueing Analysis: A Foundation of Performance Evaluation, Vol. 3, Discrete-Time Systems. North-Holland, Amsterdam.Google Scholar
Tembe, S. and Wolff, R. (1974). The optimal order of service in tandem queues. Operat. Res. 24, 824–832.Google Scholar
Weber, R. (1979). The interchangeability of ·/ M/1 queues in series. J. Appl. Prob. 16, 690–695.Google Scholar