Joint Burke's Theorem and RSK Representation for a Queue and a Store

Abstract : 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.
Type de document :
Communication dans un congrès
Cyril Banderier and Christian Krattenthaler. Discrete Random Walks, DRW'03, 2003, Paris, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AC, Discrete Random Walks (DRW'03), pp.69-82, 2003, DMTCS Proceedings
Liste complète des métadonnées

Littérature citée [24 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01183934
Contributeur : Coordination Episciences Iam <>
Soumis le : mercredi 12 août 2015 - 09:07:45
Dernière modification le : jeudi 11 janvier 2018 - 06:17:42
Document(s) archivé(s) le : vendredi 13 novembre 2015 - 11:37:56

Fichier

dmAC0107.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01183934, version 1

Collections

Citation

Moez Draief, Jean Mairesse, Neil O'Connell. Joint Burke's Theorem and RSK Representation for a Queue and a Store. Cyril Banderier and Christian Krattenthaler. Discrete Random Walks, DRW'03, 2003, Paris, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AC, Discrete Random Walks (DRW'03), pp.69-82, 2003, DMTCS Proceedings. 〈hal-01183934〉

Partager

Métriques

Consultations de la notice

159

Téléchargements de fichiers

179