A New Finite Approximation Method for Evaluating Steady-State Performance of a Continuous-State Markov Chain with an Application to Queues with Customer Abandonment
提出一种新方法，通过构造有限状态代理马尔可夫链来近似计算连续状态马尔可夫链的稳态分布，并给出误差界。应用于GI/GI/1+GI排队系统，数值实验表明该方法在过载或平衡负载的中小到达强度下优于仿真、相位型近似、扩散近似和流体近似。
This paper develops a new method for computing the stationary distribution and steady-state performance measures of stochastic systems that can be described as a continuous-state Markov chain supported on [Formula: see text]. The balance equations are solved by constructing a proxy Markov chain with finite states. We show the consistency of an approximate solution and provide deterministic nonasymptotic error bounds under the supremum norm. Our method is near optimal among all approximation methods using discrete distributions. We apply the developed method to compute the stationary distribution of virtual waiting time and associated performance measures for a GI/GI/1+GI queue in which the large market assumption may not hold and the patience time may follow any bounded distribution. Numerical experiments show that our method outperforms steady-state simulation, phase-type approximation, diffusion approximation, and fluid approximation, particularly for medium or small arrival intensities in overloaded or balanced loaded queues. Funding: S. Li and S. Mehrotra were supported by the National Science Foundation grant CMMI-1763035.