Rare event simulation methods for stochastic models of computer and communication systems

Instructor: Dr. Werner Sandmann

Affiliation: Otto-Friedrich-University, Bamberg, Germany, Department of Information Systems and Applied Computer Science

Duration: 20 hours

Period: May 17 - 25, 2005

Place: Dipartimento di Ingegneria dell'Informazione: Elettronica, Informatica, Telecomunicazioni, via G. Caruso, meeting room, ground floor

Credits: 5

Final test: yes

Contacts: Prof. Michele Pagano

Prerequisites

• Basics of probability, statistics and Markov chains
• Basics of queueing models
• Basics of simulation output data analysis

Contents

• Rare Events
• Introduction and Motivation
• Characterization: A Taste of Large Deviations
• The Problem of Rare Event Simulation
• Approaches to Simulation Speed-up
• Importance Sampling
• General Basics
• Efficiency Criteria
• Classical Change of Measure
• Applications and Examples
• Importance Sampling for Markovian Models
• Brief Review of Markov Chains
• Formal Basis of Importance Sampling for Markov Chains
• Application to Higher-Level Model Descriptions
• Heuristics for Markovian Reliability Models
• Attractor-Rare-Set-Framework and Cyclic Approach
• Optimal Importance Sampling for Markovian Models
• Adaptive Importance Sampling
• Notes on Stochastic Optimization
• Unified Parametrization
• Direct Variance Minimization
• The Cross-Entropy-Method
• Introduction to RESTART