Markov Chain Simulation with Fewer Random Samples
Markov Chain Simulation with Fewer Random Samples
复制标题
DOI：
10.1016/j.entcs.2013.07.012
复制
发表时间：
2013-08
期刊：
影响因子：
--
通讯作者：
Dimitrios Milios;S. Gilmore
中科院分区：
文献类型：
--
作者：
Dimitrios Milios;S. Gilmore
我们提出了一种加速 CTMC 模拟方法，该方法在产生所有涉及的转换的意义上是精确的。我们将我们的方法称为轨迹采样模拟，因为它从状态序列的分布和给定某些特定序列的时间分布中进行采样。从轨迹空间而不是过渡空间采样意味着我们需要生成更少的随机数，这是一个通常计算成本很高的操作。从时间分布中采样涉及用几何分布来近似控制停留时间的指数分布。适当选择近似参数可以确保模拟的随机过程与原始马尔可夫链的模拟几乎相同。我们的方法不依赖于系统的属性，当这些方法不适用时，它可以用作更有效方法的替代方法。
We propose an accelerated CTMC simulation method that is exact in the sense that it produces all of the transitions involved. We call our methodTrajectory Sampling Simulationas it samples from the distribution of state sequences and the distribution of time given some particular sequence. Sampling from the trajectory space rather than the transition space means that we need to generate fewer random numbers, which is an operation that is typically computationally expensive. Sampling from the time distribution involves approximating the exponential distributions that govern the sojourn times with a geometric distribution. A proper selection for the approximation parameters can ensure that the stochastic process simulated is almost identical to the simulation of the original Markov chain. Our approach does not depend on the properties of the system and it can be used as an alternative to more efficient approaches when those are not applicable.