Moez Draief ; Jean Mairesse ; Neil O'Connell - Joint Burke's Theorem and RSK Representation for a Queue and a Store

dmtcs:3339 - Discrete Mathematics & Theoretical Computer Science, January 1, 2003, DMTCS Proceedings vol. AC, Discrete Random Walks (DRW'03) -
Joint Burke's Theorem and RSK Representation for a Queue and a Store

Authors: Moez Draief 1; Jean Mairesse 1; Neil O'Connell 2

  • 1 Laboratoire d'informatique Algorithmique : Fondements et Applications
  • 2 Warwick Mathematics Institute

Consider the single server queue with an infinite buffer and a FIFO discipline, either of type M/M/1 or Geom/Geom/1. Denote by $\mathcal{A}$ the arrival process and by $s$ the services. Assume the stability condition to be satisfied. Denote by $\mathcal{D}$ the departure process in equilibrium and by $r$ the time spent by the customers at the very back of the queue. We prove that $(\mathcal{D},r)$ has the same law as $(\mathcal{A},s)$ which is an extension of the classical Burke Theorem. In fact, $r$ can be viewed as the departures from a dual storage model. This duality between the two models also appears when studying the transient behavior of a tandem by means of the RSK algorithm: the first and last row of the resulting semi-standard Young tableau are respectively the last instant of departure in the queue and the total number of departures in the store.

Volume: DMTCS Proceedings vol. AC, Discrete Random Walks (DRW'03)
Section: Proceedings
Published on: January 1, 2003
Imported on: May 10, 2017
Keywords: Robinson-Schensted-Knuth algorithm,tandem of queues,non-colliding random walks,Single server queue,storage model,Burke's theorem,[INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS],[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO],[INFO.INFO-CG] Computer Science [cs]/Computational Geometry [cs.CG]

2 Documents citing this article

Consultation statistics

This page has been seen 211 times.
This article's PDF has been downloaded 155 times.