Stationary Solution Approximation using a Memory-Efficient Perfect Sampling Technique

The analytical solution of large Markovian models is one of the major challenges in performance evaluation. Structured formalisms provide a modular description to tackle state space explosion by presenting memory-efficient solutions based on tensor algebra and specific software tools implement such solutions using iterative methods. However, even these numerical methods become unsuitable when massively large models are considered, i.e., models with more than 100 million states. To deal with such classes of models is possible to find approximations of the stationary solution using simulation of long-run trajectories with perfect sampling methods. The use of these methods prevents usual simulation problems such as initial state setup and burn-in time. Unfortunately, the number of produced samples to establish statistically significant solution remains an open problem. This paper analyzes the sampling process in its extent, proposing a memory-efficient stopping criteria based on a numerical tolerance of the measures of interest. Moreover, we present some memory cost estimations for a classical Markovian model in order to demonstrate the gains of the proposed method.