Last few years have seen rapid developments in the mathematical tools for studying mixing times of Markov chains. However, most of the focus has been on finite-state Markov chains. Several engineering problems involve study of countable state Markov chains. Most popular examples are queueing systems that are used to model various resource allocation problems in networks, data centers, ride-hailing etc. In this work, we focus on the Erlang-C system (also known as M/M/n queue), and bound the Chi-square distance between the finite time queue length distribution and the stationary distribution for a finite number of servers. We then use these bounds to study the behavior in the many-server heavy-traffic asymptotic regimes. The Erlang-C model exhibits a phase transition at the so-called Halfin-Whitt regime. We show that our mixing rate matches the limiting behavior in the Super-Halfin-Whitt regime, and matches up to a constant factor in the Sub-Halfin-Whitt regime.
We obtain these results using the Lyapunov-Poincaré approach, where we first carefully design a Lyapunov function to obtain a negative drift outside a finite set. Within the finite set, we develop different strategies depending on the properties of the finite set to get a handle on the mixing behavior via a local Poincaré inequality. A key aspect of our methodological contribution is in obtaining tight guarantees in these two regions, which when combined give us tight mixing time bounds. We believe that this approach is of independent interest for studying mixing in reversible countable-state Markov chains more generally, and will serve as a stepping stone towards understanding the transient behavior of more general queueing systems.
Short Bio:
Siva Theja Maguluri is Fouts Family Early Career Professor and an Associate Professor in the H. Milton Stewart School of Industrial and Systems Engineering at Georgia Tech. He obtained his Ph.D. and MS in ECE as well as MS in Applied Math from UIUC, and B.Tech in Electrical Engineering from IIT Madras. His research interests span the areas of Control, Optimization, Algorithms and Applied Probability. In particular, he works on Reinforcement Learning theory, scheduling, resource allocation and revenue optimization problems that arise in a variety of systems. His research and teaching are recognized through several awards including the “Best Publication in Applied Probability award, NSF CAREER award, second place award at INFORMS JFIG best paper competition, Student best paper award at IFIP Performance, CTL/BP Junior Faculty Teaching Excellence Award, and “Student Recognition of Excellence in Teaching: Class of 1934 CIOS Award.
