Weighted Dyck paths and nonstationary queues. Issue 2 (26th April 2022)

• Record Type: Journal Article
• Authors: Bet, Gianmarco; Selen, Jori; Zocca, Alessandro
• Is Part Of: Stochastic models. Volume 38:Issue 2(2022)
• Page Start: 268
• Page End: 287
• Publication Date: 2022-04-26
• Subjects: Queueing theory -- time-inhomogeneous Markov chain -- Dyck paths -- continuous-time Markov chain; Stochastic processes -- Periodicals; Probabilities -- Periodicals; 519.2
• DOI: 10.1080/15326349.2021.2011748
• Languages: English
• ISSNs: 1532-6349

Abstract

Abstract: We consider a model for a queue in which only a fixed number N of customers can join. Each customer joins the queue independently at an exponentially distributed time. Assuming further that the service times are independent and follow an exponential distribution, this system can be described as a two-dimensional Markov chain on a finite triangular region S of the square lattice. We interpret the resulting random walk on S as a Dyck path that is weighted according to some state-dependent transition probabilities that are constant along one axis, but are rather general otherwise. We untangle the resulting intricate combinatorial structure by introducing appropriate generating functions that exploit the recursive structure of the model. This allows us to derive an explicit expression for the probability mass function of the number of customers served in any busy period (equivalently, of the length of any excursion of the Dyck path above the diagonal) as a weighted sum with alternating sign over a certain subclass of Dyck paths.