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渐近情况下至多相差一个常数因子。 为了证明这样的结果，我们采用了Lyapunov-Poincaré方法，首先精心设计一个Lyapunov函数以在有限集合之外获得负漂移。 在有限集合内，我们根据有限集合的性质发展不同的策略，通过局部Poincaré不等式来掌握混合行为。 我们方法论贡献的一个关键方面是在这两个区域中获得紧密的保证，当结合在一起时，给我们提供了紧密的混合时间界限。 我们认为，这种方法对于研究可逆可数状态马尔可夫链的混合行为具有独立的兴趣。