论文标题
与叛逆的随机匹配模型的完美采样
Perfect sampling of stochastic matching models with reneging
论文作者
论文摘要
在本文中，我们引入了肯德尔过去算法（DCFTP）的主导耦合的微小变化，以构成有限的马尔可夫链。它基于（通常是单调的）一个（通常是单调）的（通常是非单调的）随机递归的控制。我们表明，该算法特别适用于具有有界耐心的随机匹配模型，该模型是系统的稳态分布在封闭形式中通常未知。我们首先表明该模型的马尔可夫链可以通过无限服务队列轻松控制。然后，我们研究了耐心时间是确定性的特定情况，并且该控制论点可能失败。在这种情况下，我们诉诸于一种临时技术，该技术也可以被视为对照（这次，按到达序列）。然后，我们将此算法与经典的CFTP进行比较，并展示如何使用我们的完美模拟结果来估计和比较各种均衡中各种系统的损耗概率。
In this paper, we introduce a slight variation of the Dominated Coupling From the Past algorithm (DCFTP) of Kendall, for bounded Markov chains. It is based on the control of a (typically non-monotonic) stochastic recursion by a (typically monotonic) one. We show that this algorithm is particularly suitable for stochastic matching models with bounded patience, a class of models for which the steady state distribution of the system is in general unknown in closed form. We first show that the Markov chain of this model can be easily controlled by an infinite-server queue. We then investigate the particular case where patience times are deterministic, and this control argument may fail. in that case we resort to an ad-hoc technique that can also be seen as a control (this time, by the arrival sequence). We then compare this algorithm to the classical CFTP one, and show how our perfect simulation results can be used to estimate, and compare, the loss probabilities of various systems in equilibrium.
