Perfect simulation and non-monotone Markovian systems
Perfect simulation and non-monotone Markovian systems
复制标题
完美模拟和非单调马尔可夫系统
DOI：
10.4108/icst.valuetools2008.4404
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
J. Vincent
中科院分区：
文献类型：
--
作者：
A. Bušić;B. Gaujal;J. Vincent
完美模拟或过去耦合是对单调离散时间马尔可夫链的稳态进行采样的有效技术。事实上，我们只需考虑与系统中最小和最大状态相对应的两条轨迹。我们在此证明，即使是非单调系统，也只需计算两个轨迹：下极包络和上极包络。由于在每个时间步取下极值（或上极值）得到的状态序列并不对应于系统的可行轨迹，因此包络可能不会耦合，或者耦合时间可能会更长。我们的研究表明，包络法对于某些类别的非单调排队网络是有效的，例如批量到达的排队网络、具有分叉和加入节点的排队网络和/或具有负客户的排队网络。
Perfect simulation, or coupling from the past, is an efficient technique for sampling the steady state of monotone discrete time Markov chains. Indeed, one only needs to consider two trajectories corresponding to minimal and maximal state in the system. We show here that even for non-monotone systems one only needs to compute two trajectories: an infimum and supremum envelope. Since the sequence of states obtained by taking infimum (resp. supremum) at each time step does not correspond to a feasible trajectory of the system, the envelopes might not couple or the coupling time might be larger. We show that the envelope approach is efficient for some classes of non-monotone queuing networks, such as networks of queues with batch arrivals, queues with fork and join nodes and/or with negative customers.