Stationary Solution Approximation using a Memory-Efficient Perfect Sampling Technique

Ricardo M. Czekster, P. Fernandes, A. Sales, Thais Webber

Research output: Chapter in Book/Published conference outputConference publication

Abstract

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.
Original languageEnglish
Title of host publication44TH ANNUAL SIMULATION SYMPOSIUM 2011 (ANSS 2011) - 2011 SPRING SIMULATION MULTICONFERENCE - BK 2 OF 8
Pages119–126
Publication statusPublished - 1 Apr 2011
Event44TH ANNUAL SIMULATION SYMPOSIUM 2011 (ANSS 2011) - 2011 SPRING SIMULATION MULTICONFERENCE - Boston, United States
Duration: 3 Apr 20117 Apr 2011

Conference

Conference44TH ANNUAL SIMULATION SYMPOSIUM 2011 (ANSS 2011) - 2011 SPRING SIMULATION MULTICONFERENCE
Country/TerritoryUnited States
CityBoston
Period3/04/117/04/11

Fingerprint

Dive into the research topics of 'Stationary Solution Approximation using a Memory-Efficient Perfect Sampling Technique'. Together they form a unique fingerprint.

Cite this