Title: Finite-Time Behavior of Erlang-C Model: Mixing Time, Mean Queue Length and Tail Bounds Show Chinese title

Title: Erlang-C模型的有限时间行为：混合时间、平均队列长度和尾部界

Abstract: Service systems like data centers and ride-hailing are popularly modeled as queueing systems in the literature. Such systems are primarily studied in the steady state due to their analytical tractability. However, almost all applications in real life do not operate in a steady state, so there is a clear discrepancy in translating theoretical queueing results to practical applications. To this end, we provide a finite-time convergence for Erlang-C systems (also known as $M/M/n$ queues), providing a stepping stone towards understanding the transient behavior of more general queueing systems. We obtain a bound on 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. To prove such a result, we employ the Lyapunov-Poincar\'e 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\'e 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. Show Chinese abstract

Abstract: 像数据中心和网约车服务这样的系统在文献中通常被建模为排队系统。由于其分析上的可处理性，这类系统主要在稳态下进行研究。然而，现实生活中几乎所有的应用都不在稳态下运行，因此在将理论排队结果转化为实际应用时存在明显的偏差。为此，我们为Erlang-C系统（也称为 $M/M/n$ 排队系统）提供了有限时间收敛性，这为理解更一般的排队系统的瞬态行为提供了一个垫脚石。我们得到了有限数量的服务器下，有限时间队列长度分布与平稳分布之间的卡方距离的界。然后我们利用这些界来研究许多服务器重负载渐近区域中的行为。Erlang-C模型在所谓的Halfin-Whitt区域表现出相变。我们证明了我们的混合速率与Super-Halfin-Whitt区域的极限行为匹配，并且在Sub-Halfin-Whitt区域中与一个常数因子匹配。为了证明这样一个结果，我们采用了李雅普诺夫-庞加莱方法，在这种方法中，我们首先精心设计一个李雅普诺夫函数以在外围有限集合外获得负漂移。在有限集合内部，我们根据有限集合的性质发展不同的策略，通过局部庞加莱不等式来控制混合行为。我们方法论贡献的一个关键方面是在这两个区域中获得紧致保证，当它们结合在一起时，为我们提供了紧致混合时间界。我们认为，这种方法对于研究可逆计数状态马尔可夫链的混合行为具有独立的兴趣。