Simulation of Markovian models using the Bootstrap technique

• Dione Taschetto PUCRS
• Paulo Fernandes PUCRS
• Thais Webber PUCRS
• Afonso Sales PUCRS

Abstract

Simulation is an interesting alternative to solve Markovian models. However, when compared to analytical and numerical solutions it suffers from a lack of confidence in the accuracy of results due to the very nature of simulation, which is the choice of samples through pseudorandom generation. This paper proposes a different way to simulate Markovian models by using a Bootstrap-based statistical technique to minimize the effect of sample choices. The effectiveness of the proposed technique, called Bootstrap Simulation, is compared to the exact results of numerical solution for a set of examples described using Stochastic Automata Networks modeling formalism.

References

Aczel, A. D. (1998). Probability 1: The Book That Proves There is Life in Outer Space. Harvest Books, Orlando, Florida.

Arnoldi, W. E. (1951). The principle of minimized iterations in the solution of the matrix eigenvalue problem. Quarterly of Applied Mathematics, 9:17–29.

Bauer, E. and Kohavi, R. (1999). An Empirical Comparison of Voting Classification Algorithms: Bagging, Boosting, and Variants. Machine Learning, 36(1-2):105–139.

Bertolini, C., Brenner, L., Fernandes, P., Sales, A., and Zorzo, A. F. (2004). Structured StochasticModeling of Fault-Tolerant Systems. In 12th IEEE/ACM Internacional Symposium on Modelling, Analysis and Simulation on Computer and Telecommunication Systems (MASCOTS’04), pages 139–146, Volendam, The Netherlands. IEEE Press.

Brenner, L., Fernandes, P., Fourneau, J. M., and Plateau, B. (2009). Modelling Grid5000 point availability with SAN. Elect. Notes in Theoret. Computer Science (ENTCS), 232:165–178.

Brenner, L., Fernandes, P., Plateau, B., and Sbeity, I. (2007). PEPS2007 - Stochastic Automata Networks Software Tool. In Fourth Internat. Conf. on the Quantitative Evaluation of Systems (QEST’07), pages 163–164, Edinburgh, UK. IEEE Press.

Donatelli, S. (1993). Superposed stochastic automata: a class of stochastic Petri nets with parallel solution and distributed state space. Performance Evaluation, 18(1):21–36.

Dotti, F. L., Fernandes, P., Sales, A., and Santos, O. M. (2005). Modular Analytical Performance Models for Ad Hoc Wireless Networks. In 3rd International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOpt’05), pages 164–173, Trentino, Italy. IEEE Computer Society.

Efron, B. (1979). Bootstrap Methods: Another Look at the Jackknife. The Annals of Statistics, 7(1):1–26.

Fernandes, P., Plateau, B., and Stewart, W. J. (1998). Efficient descriptor-vector multiplication in Stochastic Automata Networks. Journal of the ACM, 45(3):381–414.

Häggström, O. (2002). Finite Markov Chains and Algorithmic Applications. Cambridge University Press. Based on lecture notes.

Hillston, J. (1996). A compositional approach to performance modelling. Cambridge University Press, New York, USA.

Manly, B. F. J. (1997). Randomization, Bootstrap and Monte Carlo Methods in Biology. Chapman & Hall/CRC, second edition.

Plateau, B. (1985). On the stochastic structure of parallelism and synchronization models for distributed algorithms. In Proc. of the 1985 ACM SIGMETRICS Conf. on Measurements and Modeling of Comp. Systems, pages 147–154, Austin, Texas. ACM Press.

Propp, J. G. and Wilson, D. B. (1996). Exact Sampling with Coupled Markov Chains and Applications to Statistical Mechanics. Random Structures and Algorithms, 9(1–2):223–252.

Ross, S. M. (2002). Simulation. Academic Press, Inc., Orlando, FL, USA.

Saad, Y. and Schultz, M. H. (1986). GMRES: A Generalized Minimal RESidual Algorithm for Solving Nonsymmetric Linear Systems. SIAM Journal on Scientific and Statistical Computing, 7(3):856–869.

Sales, A. and Plateau, B. (2009). Reachable state space generation for structured models which use functional transitions. In Proc. of the 6th Internat. Conf. on the Quantitative Evaluation of Systems (QEST’09), pages 269–278, Budapest, Hungary. IEEE Press.

Sayre, K. (1999). Improved techniques for software testing based on Markov chain usage models. PhD thesis, University of Tennessee, Knoxville, USA.

Shannon, R. E. (1998). Introduction to the art and science of simulation. In Proceedings of the 30th Conference on Winter Simulation (WSC’98), pages 7–14, Los Alamitos, CA, USA. IEEE Computer Society Press.

Stewart, W. J. (2009). Probability, Markov Chains, Queues, and Simulation. Princeton University Press, Princeton, NJ, USA.

Taschetto, D. (2010). Precisão de Simulações para Solução de Modelos Estocásticos. Master’s thesis, PUCRS-FACIN-PPGCC, Porto Alegre.