Joint Burke's Theorem and RSK Representation for a Queue and a Store
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 b...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2003-01-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/3339/pdf |
| _version_ | 1827324131169796096 |
|---|---|
| author | Moez Draief Jean Mairesse Neil O'Connell |
| author_facet | Moez Draief Jean Mairesse Neil O'Connell |
| author_sort | Moez Draief |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-25T02:07:08Z |
| format | Article |
| id | doaj.art-469f4436a78749c6a411bca8dfddad79 |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T02:07:08Z |
| publishDate | 2003-01-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-469f4436a78749c6a411bca8dfddad792024-03-07T14:29:56ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502003-01-01DMTCS Proceedings vol. AC,...Proceedings10.46298/dmtcs.33393339Joint Burke's Theorem and RSK Representation for a Queue and a StoreMoez Draief0Jean Mairesse1Neil O'Connell2Laboratoire d'informatique Algorithmique : Fondements et ApplicationsLaboratoire d'informatique Algorithmique : Fondements et ApplicationsWarwick Mathematics InstituteConsider 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.https://dmtcs.episciences.org/3339/pdfrobinson-schensted-knuth algorithmtandem of queuesnon-colliding random walkssingle server queuestorage modelburke'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] |
| spellingShingle | Moez Draief Jean Mairesse Neil O'Connell Joint Burke's Theorem and RSK Representation for a Queue and a Store Discrete Mathematics & Theoretical Computer Science 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] |
| title | Joint Burke's Theorem and RSK Representation for a Queue and a Store |
| title_full | Joint Burke's Theorem and RSK Representation for a Queue and a Store |
| title_fullStr | Joint Burke's Theorem and RSK Representation for a Queue and a Store |
| title_full_unstemmed | Joint Burke's Theorem and RSK Representation for a Queue and a Store |
| title_short | Joint Burke's Theorem and RSK Representation for a Queue and a Store |
| title_sort | joint burke s theorem and rsk representation for a queue and a store |
| topic | 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] |
| url | https://dmtcs.episciences.org/3339/pdf |
| work_keys_str_mv | AT moezdraief jointburkestheoremandrskrepresentationforaqueueandastore AT jeanmairesse jointburkestheoremandrskrepresentationforaqueueandastore AT neiloconnell jointburkestheoremandrskrepresentationforaqueueandastore |