The standard performance evaluation methods for stochastic discrete-event models are numerical analysis of the stochastic process and simulation. Both methods have characteristic advantages and disadvantages depending on the size of the reachability graph and type of process and performance measure: numerical evaluation requires to generate the reachability graph followed by a numerical solution of equations, thus restricting the allowed distributions and the state space size. Simulation avoids these problems, but leads to unacceptably long run times if states of interest are only rarely hit, i.e., the variance of the simulation converges only very slowly with the number of simulated events. This is not a problem for numerical methods, on the other hand.

The paper reports on a recently proposed hybrid performance evaluation algorithm for the steady-state solution of models such as stochastic Petri nets and Markov chains [1] that integrates elements of both methods. As such, the algorithm unifies simulation and numerical analysis in a joint framework. It automatically adapts its behavior depending on the available size of main memory and number of model states. The algorithm is proved to result in an unbiased estimator whose variance tends to zero with increasing simulation time, using a measure-based formulation [2].

The new measure-based approach provides much freedom to tailor the simulation to the problem at hand, e.g. when considering rare events. In fact, it can be seen as bridging the gap between two extreme special cases: simulating a single run (or multiple runs) of a Markov chain as well as a deterministic, numerical approach which is often infeasible as it requires unbounded memory. Simulations of concrete examples demonstrate the superiority of the measure-based approach over these extremes as well as its versatility.

The algorithm extends the idea of splitting simulation methods [3] such as RESTART [4] with concurrent multiple particles / trajectories. This presentation will show its applicability to rare-event problems; first experiments have shown significant possible speedups [1,5]. We expect that the algorithm will simplify the configuration effort of splitting simulations, while still using a heuristic similar to the importance function [4].

References
[1] A. Zimmermann and T. Hotz, Integrating simulation and numerical analysis in the evaluation of generalized stochastic Petri nets, ACM Transactions on Modeling and Computer Simulation (TOMACS), vol. 29, no. 4, 2019.
[2] T. Hotz and A. Zimmermann, Analysing Markov chains using random measures, in 32nd European Meeting of Statisticians (EMS2019), Palermo, 2019.
[3] P. Glasserman, P. Heidelberger, P. Shahabuddin, and T. Zajic, Multilevel splitting for estimating rare event probabilities, Operations Research, vol. 47, pp. 585-600, 1999.
[4] M. Villen-Altamirano and J. Villen-Altamirano, On the effciency of RESTART for multidimensional systems, ACM Transactions on Modeling and Computer Simulation, vol. 16, no. 3, pp. 251-279, Jul. 2006.
[5] A. Zimmermann, T. Hotz, V. Hädicke, and M. Friebe, Analysis of safety-critical cloud architectures with multi-trajectory simulation, in 68th Annual Reliability and Maintainability Symposium (RAMS 2022), Jan. 2022,
(accepted for publication).
[6] M. J. Garvels, J.-K. C. Van Ommeren, and D. P. Kroese, On the importance function in splitting simulation, European Transactions on Telecommunications, vol. 13, no. 4, pp. 363-371, 2002.