logo

European Institute for Statistics, Probability, Stochastic Operations Research
and their Applications

About | Research | Events | People | Reports | Alumni | ContactHome


 

March 29 - April 1, 2016

 

"Simulation of rare events"

 

(part of SAM "Probability and Analysis")

 

 

SUMMARY REGISTRATION SPEAKERS

PROGRAMME

ABSTRACTS

SUMMARY

11th International Workshop on Rare Event Simulation (RESIM 2016)

RESIM 2016 will be the 11th workshop in a series of successful events held on the topic of rare event simulation since 1997.
It covers all aspects of rare event simulation, ranging from purely theoretical developments to practical applications. The objective is to provide a forum for researchers and practitioners working in different locations, using different methods and on different applications, to present recent results, exchange ideas, and discuss open problems and new directions.

The 2016 event will be organized as part of the Eurandom Stochastic Activity Month "Probability and Analysis", and partially funded by the research programme NETWORKS.
This will allow us to invite many speakers, selected both from among experts in rare-event simulation, and from among experts in a variety of (potential) application areas. Thus, we hope to stimulate interaction between the simulation and the application experts.
Besides the invited talks, there will also be two tutorial talks, and room for talks contributed after this call for papers.

 

ORGANISERS

Pieter-Tjerk de Boer University of Twente
Daan Crommelin University of Amsterdam / CWI
Michel Mandjes University of Amsterdam
Adrian Muntean Karlstad University



RESIM2016 solicits contributions on rare-event simulation methodologies and applications, including the following:
 

Methodologies:

Importance sampling
RESTART/Splitting
Averaging techniques
Cross-Entropy method
Large deviations theory
Interacting particles
Hybrid analytic/simulation techniques
Other novel approaches


Applications and models:

Queueing models
Reliability models
Financial and insurance risk models
Computer and telecommunication networks
Traffic/pedestrian flows
Air traffic safety
Power grids
Climate research
Materials science at low spatial scales
Computational chemistry
Computational biology and genetics
Other relevant areas
 



SUBMISSIONS

Indicate your interest in presenting a paper by submitting a title and a 1-page abstract by January 17, 2016 by email to Mrs. Patty Koorn (koorn@eurandom.tue.nl).

Authors will be notified of the acceptance / rejection of their paper by February 1, 2016.
At least one author of each accepted paper is expected to participate in the workshop. A workshop compendium will be prepared ahead of the workshop.

All materials that should be included in the compendium (short or full paper, or abstract supplemented by viewgraphs; maximum 12 pages) are due by February 29, 2016.

 

TUTORIAL SPEAKERS

Pierre L'Ecuyer Universit de Montral
Paul Dupuis Brown University

 

INVITED SPEAKERS

Sren Asmussen Aarhus University
Zdravko Botev University of Sidney
Peter Bolhuis University Of Amsterdam
Fredrique Cerou INRIA
Matteo Colangeli Gran Sasso Science Institute L’Aquilla
Jason Frank Utrecht University
Carsten Hartmann Freie Universitt Berlin
Henrik Hult KTH Stockholm
Peter Imkeller Humboldt-Universitat Berlin
Konstantinos Spiliopoulos Boston University
Bruno Tuffin INRIA
Jonathan Weare University of Chicago
Pieter Rein ten Wolde AMOLF / VU Amsterdam

PROGRAMME  (tentative)

Tuesday March 29

09.00 - 09.30 Welcome and opening Remco van der Hofstad (Eurandom)
09.30 - 10.10 Pierre L'Ecuyer tutorial

Introduction to Rare-Event Simulation

10.10 - 10.50 Sren Asmussen invited speaker Rare event problems and simulation in the lognormal left tail
10.50 - 11.20 Break    
11.20 - 11.40 Ewan Cahen contributed talk Rare event analysis and efficient simulation for a multi-dimensional ruin problem
11.40 - 12.00 Oleg Lukashenko contributed talk On estimation of some rare event probabilities related to Gaussian queues
12.00 - 12.20 Anne Buijsrogge contributed talk Analysis of a state-independent change of measure for the G|G|1 tandem queue
12.20 - 12.40 Manuel Villen Altamirano contributed talk Optimal importance function for RESTART simulation of a two-queue tandem Jackson network
13.00 - 14.00 Lunch    
14.00 - 14.40 Peter Bolhuis invited speaker Biased sampling of unbiased dynamical trajectories in complex molecular systems
14.40 - 15.20 Carsten Hartmann invited speaker Cross-entropy minimization and importance sampling of rare events
15.20 - 15.50 Break    
15.50 - 16.10 Josh Berryman contributed talk Forward Flux Sampling with Incomplete Progress Coordinate Information
16.10 - 16.30 Francois Le Gland contributed talk Marginalization for Rare Event Simulation in Switching Diffusions
16.30 - 17.10 Frederique Cerou invited speaker On the convergence of Adaptive Multilevel Splitting

Wednesday March 30

09.30 - 10.10 Pierre L'Ecuyer tutorial

Introduction to Rare-Event Simulation

10.10 - 10.50 Bruno Tuffin invited speaker Permutation Monte Carlo: applications, analysis and extension
10.50 - 11.30 Break    
11.30 - 11.50 Gang Liu contributed talk Rare event simulation related to financial risks: efficient estimation and sensitivity analysis
11.50 - 12.10 Anand Vidyashankar contributed talk Rare event simulation for age-dependent branching processes and applications
12.10 - 12.30 Krzysztof Bisewski contributed talk Rare event simulation for a spiralling Ornstein-Uhlenbeck process
12.30 - 14.00 Lunch    
14.00 - 14.40 Paul Dupuis tutorial

Subsolutions for the design and analysis of rare event simulation schemes

14.40 - 15.20 Henrik Hult invited speaker Efficient importance sampling for computing credit value adjustment of interest rate portfolios
15.20 - 15.50 Break    
15.50 - 16.10 Dane Johnson contributed talk Splitting for Rare Event Estimation for Problems with Rest Points
16.10 - 16.30 Bohan Chen contributed talk Importance sampling of heavy-tailed stochastic perpetuities
16.30 - 17.10 Konstantinos Spiliopoulos invited speaker Irreversible Langevin Samplers and Variance Reduction: A Large Deviations Approach and Diffusion on Graphs
18.30 - Conference dinner Restaurant "Sopranos"  

Thursday March 31

09.30 - 10.10 Peter Imkeller invited speaker Model selection for paleo-climatic time series: stable and fractional noise
10.10 - 10.50 Jason Frank invited speaker Dynamical sampling methods with applications
10.50 - 11.20 Break    
11.20 - 12.00 Jonathan Weare invited speaker Understanding umbrella sampling approaches to rare event simulation
12.00 - 12.40 Pieter Rein Ten Wolde invited speaker

Simulating rare events in cellular systems

12.40 - 14.00 Lunch    
14.00 - 14.20 Armin Zimmerman contributed talk Numerical Results for the Automated Rare Event Simulation of Stochastic Petri Nets
14.20 - 14.40 Charles-Edouard Brehier contributed talk Generalized Adaptive Multilevel Splitting:unbiasedness and applications
14.40 - 15.00 Clement Walter contributed talk Rare event simulation and splitting: a Point Process interpretation with application for discontinuous random variables
15.00 - 15.30 Break    
15.30 - 16.10 Paul Dupuis tutorial Subsolutions for the design and analysis of rare event simulation schemes
16.10 - 16.50 Mateo Colangeli invited speaker Latent heat and the Fourier law

 

Friday April 1

09.30 - 09.50 Debarati Bhaumik contributed talk Estimating power spill probabilities in energy systems with wind generation and storage
09.50 - 10.10 Ad Ridder contributed talk Sequential Importance Sampling for Counting Hamiltonian Cycles on Random Graphs
10.10 - 10.50 Zdravko Botev invited speaker How exponential tilting facilitates posterior simulation in the Bayesian Lasso model
10.50 - 11.20 Break    
11.20 - 11.40 Jose Villen Altamirano contributed talk Restart vs Splitting: A Comparative Study
11.40 - 12.20      
12.20 - 13.30 Lunch    

 

ABSTRACTS


Sren Asmussen

Rare event problems and simulation in the lognormal left tail

Sum of lognormal distributions come up in a number of problems in say insurance, finance and wireless communication. The distribution of such sums is not explicitly available so one has to resort to approximations and/or numerical methods. We look at such problems with emphasis on the tails and simulation. The starting point for the right tail is i.i.d. subexponential theory/algorithms but we also sketch the extension to dependence. The left tail is of particular importance in finance when considering portfolios with long positions and light-tailed theory suggests to use saddlepoint
methods. This involves the problem that not even the Laplace transform is explicit and leads to associated simulation problems also involving xponentially tilted lognormals.


Josh Berryman

Forward Flux Sampling with Incomplete Progress Coordinate Information

It has been observed that adequate statistics for calculations using the Forward Flux Sampling (FFS) splitting method are difficult to achieve when studying nucleation phenomena, due to the presence of hidden variables not captured by the typically used progress coordinates. We demonstrate that the Rosenbluth variant of FFS ameliorates these problems, giving examples from a study of the hard sphere fluid-to-crystal nucleation process. We discuss updates to the open source freshs.org rare event harness system.


Debarati Bhaumik

Estimating power spill probabilities in energy systems with wind generation and storage

The intermittent nature of the wind energy makes its integration to the energy system a highly challenging task. However, the challenges can be alleviated by incorporating energy storage devices into the system. Our study focuses on minimizing large power spilled by a stand-alone energy system. For this, we assessed a single domestic energy system incorporated with a wind turbine and a battery. The aim is to find the best operation mode of the battery such that the occurrence of large power spills is minimal.


Peter Bolhuis

Biased sampling of unbiased dynamical trajectories in complex molecular systems

The transition path sampling (TPS) methodology has enabled the sampling of rare events in complex systems using unbiased dynamical trajectories.  The method works by restricting the trajectory space to paths that visit specific stable states. In the last decade the TPS framework has been extended in various ways. On the one hand by the transition interface approach (TIS) (related to the forward flux method) to sample kinetic properties more efficiently. On the other hand by allowing transitions between the multiple (meta) stable states that often are present in complex systems. Multiple state TIS can be recast into a single replica exchange method, that, in principle, is able to explore the entire trajectory space starting from a single stable minimum. In this presentation, I will give an overview of the TPS methodology, discuss the link with splitting methods, and illustrate the application of path sampling  to rare events in molecular systems, such as protein folding, aggregation and association. 


Zdravko Botev

How exponential tilting facilitates posterior simulation in the Bayesian Lasso model

In this talk we propose a perfect simulation method to sample from the posterior density of the Bayesian Lasso Model.
The method exploits features of the problem to construct a sequential importance sampling density, which is then combined with exponential tilting.
The exponential tilting not only helps with the simulation, but suggests a simple and fast method for selecting the Lasso regularization parameter.
We give an numerical example with the well-known diabetes dataset of Efron.
(joint works with P.L’Ecuyer)


Charles-Edouard Brehier

Generalized Adaptive Multilevel Splitting: unbiasedness and applications

The Adaptive Multilevel Splitting (AMS) algorithm is a versatile and very effcient approach to simulate rare events, such as transitions between metastable states of stochastic processes. The main ingredient is as follows: n replicas interact (mutation-selection) through the definition of a sequence of (random) levels, computed adaptively using a reaction coordinate mapping. Obtaining reliable quantitative (e.g. reaction rates) and qualitative (e.g. reactive trajectories) information requires rigorous mathematical results. I would like to present the Generalized Adaptive Multilevel Splitting framework recently introduced in a preprint, which encompasses the AMS algorithm for simulating path of Markov chains; this framework also suggests several natural algorithmic new variants, and motivates new applications.


Anne Buijsrogge

Analysis of a state-independent change of measure for the G|G|1 tandem queue

In (Parekh and Walrand, 1989) a method is introduced to efficiently estimate the probability of a rare event in a single queue or network of queueus. The event they consider is that the total number of customers in the system reaches some level N in a busy cycle. Parekh and Walrand introduce a simple change of measure, which is state-independent, in order to estimate this probability efficiently using simulation. However, they do not provide any proofs of some kind of efficiency of their method. For the single queue (with mutiple servers) it has been shown in (Sadowsky, 1991) that the change of measure as proposed by Parekh and Walrand is asymptotically efficient under some mild conditions.

In this work we study the state-independent change of measure of the G|G|1 tandem queue, along the lines of Parekh and Walrand, and we provide necessary conditions for asymptotic efficiency. To the best of our knowledge, no results on asymptotic effciency for the G|G|1 tandem queue had been obtained previously. Looking at the results of the M|M|1 tandem queue, it is expected that this state-independent change of measure is the only state-independent change of measure for the G|G|1 tandem queue that can possibly be asymptotically effcient. We show that, under some conditions, it is indeed the only exponential state-independent change of measure that can be asymptotically effcient. However, we have also identified conditions for the two node G|G|1 tandem queue under which the Parekh and Walrand change of measure is still not asymptotically effcient.


Ewan Cahen

Rare event analysis and efficient simulation for a multi-dimensional ruin problem

We look at large deviations of multivariate stochastic processes in continuous time, in particular, we consider the event that both components of a bivariate stochastic process ((At, Bt))t≥0 ever simultaneously exceed some large level; a leading example is that of two Markov fluid queues driven by the same background process ever reaching some large level u. Exact analysis being prohibitive, we resort to asymptotic techniques and efficient simulation.


Frederique Cerou

On the convergence of Adaptive Multilevel Splitting

Adaptive Multilevel Splitting (AMS) is a simple algorithm to sample rare paths from a Markov process, typically a diffusion. This algorithm is now well known and used in the Molecular Dynamics community, and this talk will present recent results about its convergence, which are related to a Fleming-Viot type of interacting particles, build upon a special stochastic process known in the literature as the stochastic wave.


Bohan Chen

Importance sampling of heavy-tailed stochastic perpetuities

 


Mateo Colangeli

Latent heat and the Fourier law

We present  computer simulations run with a  stochastic  cellular automaton which describes 1D particle systems connected to reservoirs which keep two different densities at the endpoints.  We fix the parameters so that there is a phase transition (of the van der Waals type) and observe that if the densities at the boundaries are metastable then, after a transient, the system reaches an apparently stationary regime where the current flows from the reservoir with smaller density to the one with larger density.


Paul Dupuis

Subsolutions for the design and analysis of rare event simulation schemes

The two main methods used to estimate probabilities of rare events or to approximate expected values that are largely determined by rare events are importance sampling and splitting.  Each of the two methods can be associated with a function.  In the case of splitting the function determines the splitting thresholds, and in the case of importance sampling it determines a state-dependent change of measure.  In the light-tailed setting, good qualitative behavior (e.g., sub-exponential growth in the number particles for splitting) can be shown to hold if and only if the function is a subsolution for an associated partial differential equation (a Hamilton-Jacobi-Bellman equation).  Moreover when the subsolution property holds, the performance of the associated numerical method can be characterized in terms of the value of the subsolution at a certain point.
Much of this talk will be a review, revisiting some of the pitfalls of rare event Monte Carlo and how designs based on subsolutions avoid them.  Somewhat more refined statements of theorems than those available previously will be presented.  A point of emphasis will be to contrast the qualitative properties required of subsolutions for the two methods, and how these differences are reflected in qualitative differences between splitting and importance sampling.


Pierre L'Ecuyer

Introduction to Rare-Event Simulation

In this tutorial talk, we first give a brief overview of the difficulties encountered in rare-event simulation, then summarize the main ideas and methods that can substantially reduce the computing effort required to obtain reliable estimators.
The most popular methods are based primarily on importance sampling, splitting, and conditional expectation.
We explain them and give examples to provide insight.
We examine in particular the idea of approximate zero-variance importance sampling and how it can be implemented.
We discuss the splitting methodology, look at different types of splitting algorithms, and give examples.
We also recall and explain asymptotic robustness properties of estimators in rare-event simulation, such as logarithmic efficiency, bounded relative error (and relative moments), and vanishing relative error.
We discuss how such properties can be proved and give examples.
This tutorial is split in two 40-minute talks.


Jason Frank

Dynamical sampling methods with applications


Carsten Hartmann

Cross-entropy minimization and importance sampling of rare events

Cross-entropy (CE) minimization is a versatile Monte Carlo method for combinatorial optimization and sampling of rare events, going back to work by Reuven Rubinstein and co-workers. I will report on recent algorithmic extensions of the CE method to diffusions that can be used to design efficient importance sampling strategies for computing the rare events statistics of equilibrated systems. The approach is based on a Legendre-type duality between path functionals of diffusion processes associated with certain sampling and control problems that can be reformulated in terms of CE minimization. The method will be illustrated with several numerical examples and discussed along with algorithmic issues and possible extensions of the method to high-dimensional multiscale systems.
(joint work with Wei Zhang and Christof Schtte)


 Henrik Hult

Efficient importance sampling for computing credit value adjustment of interest rate portfolios

Prior to the financial crises in 2008, the credit risk in derivatives was not appropriately accounted for. Since then there has been an influx of value adjustments to derivative pricing collected under the name of XVA. The counterparty credit risk is this: A bank B trading derivatives with a counterparty C, is subject to the default risk of C. If C defaults at time T and the value of the derivative at that time is V(T) > 0 for the bank, then most likely B will not collect the full value of the derivative. The loss is called Lost Given Default LGD. On the other hand if the value is negative then the defaulting C will terminate the contract and use the money in the default. Therefore, at default, there is a asymmetry in the value, and the loss is LGD*max(V(T),0).
The credit value adjustment (CVA) is the expected loss of the counterparty defaulting before maturity, taking into account netting effects. In this talk I will show how to construct efficient importance sampling algorithms for computing the CVA for a portfolio of interest rate derivatives, when the short-rate follows a simple one-factor Hull-White model.


Peter Imkeller

Model selection for paleo-climatic time series: stable and fractional noise

Dynamical systems of the reaction-diffsion type with small noise have been instrumental to explain basic features of the dynamics of paleo-climate data. For instance, a spectral analysis of Greenland ice time series performed at the end of the 1990s representing average temperatures during the last ice age suggest an α−stable noise component with an α ~1.75. On the other hand, strong memory effects in the dynamics of global average temperatures are attributed to the global cryosphere. We model the time series as a dynamical system perturbed by α-stable and fractional Gaussian noise, and develop an effcient testing method for the best fitting α resp. Hurst coefficient. The method is based on the observed power variations of the residuals of the time series. Their asymptotic behavior in case of α-stable noise is described by α-stable processes, while in the fractional Gaussian case normal asymptotic behavior is observed for suitably renormalized approximations of the quadratic variation.


Dane Johnson

Splitting for Rare Event Estimation for Problems with Rest Points


The accelerated Monte Carlo algorithms most commonly used for rare event estimation are importance sampling and splitting. Implementing an importance sampling scheme requires choosing a change of measure and implementing a splitting scheme require choosing an importance function. These choices determine the effectiveness of the algorithms, and a good choice requires a careful understanding of the problem of interest. When considering problems with a rest point for the noiseless dynamics in the domain of interest and metastability issues (e.g., transition probabilities between rest points), the design issue can be especially challenging.1 Two important parameters in these problems are T , where the rare event has to occur on [0, T ], and E, which is a parameter indicating the magnitude of the noise.

One approach to the problem of algorithm design is based on large deviation theory and subsolutions to the Hamilton-Jacobi-Bellman partial differential equation. Such subsolutions induce schemes, i.e., the change of measure for importance sampling and the importance function for splitting. For time dependent problems such as those we consider, one is tempted to exploit the possibility of using subsolutions that are independent of time when T is large, and in particular to base the construction of the subsolution on the Freidlin-Wentsell quasipotential. It is known that this is not be appropriate when one considers importance sampling. However, as we discuss for splitting scheme it appears that one can in fact use this approach. We review the analysis which indicates the problems that importance sampling encounters, and then describe why splitting does not encounter the same difficulties, at least when the RESTART form of splitting is used for implementation. We also present several numerical examples which illustrate the usefulness of splitting in this context.


Francois Le Gland

Marginalization for Rare Event Simulation in Switching Diffusions

The problem addressed here is estimating the small probability that the continuous component X(t) of a switching diffusion (a special class of a Markov process (X(t), θ(t)) with a hybrid continuous/discrete state space) hits a critical region before some terminal time. In full generality, splitting methods provide alternative to importance sampling, with the interesting feature that trajectories are simulated under the original model, so that not only the probability of the rare but critical event can be estimated, but also typical critical trajectories are exhibited. Special issues are addressed here, which are specific to the hybrid nature of the state space.


Gang Liu

Rare event simulation related to financial risks: efficient estimation and sensitivity analysis

In this paper, we develop our previously proposed reversible shaking transformation methods to estimate the rare event statistics arising in different financial risk settings which are embedded within a unified framework of isonormal Gaussian process. Namely, we combine splitting methods with both Interacting Particle System (IPS) technique and ergodic transformations using Parallel-One-Path (POP) estimatiors. We also propose an adaptive version for the POP method and prove its convergence. We demonstrate the application of our methods in various examples which cover usual semi-martingale stochastic models (not necessarily Markovian) driven by Brownian motion and, also, models driven by fractional Brownian motion (non semi-martingale) to addrss various financial risks. Interestingly, owing to the Gaussian process framework, our methods are also able to efficiently handle the important problem of sensitivities of rare event statistics with respect to the model parameters.


Oleg Lukashenko

On estimation of some rare event probabilities related to Gaussian queues

We consider the probability that the normalized cumulative workload grows at least as the length T of the considered interval in case of Gaussian input traffic. Such probability is, in general, not available in closed
form, but can be estimated through simulation, although for high values of T rare events are involved. To cope with this problem, we make use of the BMC (Bridge Monte Carlo) approach, a special case of conditional Monte Carlo estimator. BMC approach exploits the Gaussian nature of the input process (independence is equivalent to uncorrelatedness) and relies on the properties of so-called bridge processes. The estimation algorithm can be applied to any Gaussian process with a non decreasing variance function.
We will present the results of several simulation experiments with Fractional Brownian Motion traces in order to study the properties of the proposed estimator for different values of the relevant parameters
(duration of the interval, value of the Hurst parameter, effect of the discretization step and choice of the conditioning point)


Ad Ridder

Sequential Importance Sampling for Counting Hamiltonian Cycles on Random Graphs

In this paper we consider counting the number of Hamiltonian cycles in random graphs. For fixed graphs such a problem is commonly known as a #P-complete counting problem as it extends its associated NP-complete decision problem. Clearly, randomized approximation schemes can produce accurate estimates. Then it is more interesting to obtain these good estimates in fast running times. In this way we encounter similar concepts as in the rare-event simulation literature, namely polynomial running times of the algorithms to obtain a certain performance guarantee. In our paper we propose a sequential importance sampling algorithm that is based on a simple one-step-look-ahead approach (OSLA). In this method, nodes are one-by-one randomly added to the uncomplete cycle until either a complete Hamiltonian cycle comes out, or the procedure gets stuck. Also we consider an enhanced extension by calling an oracle who knows after each iteration how to continue for obtaining a feasible solution. We call this the n-step-look-ahead method (nSLA). We apply our algorithms to both directed and undirected random graphs.


Konstantinos Spiliopoulos

Irreversible Langevin Samplers and Variance Reduction: A Large Deviations Approach and Diffusion on Graphs

Monte Carlo methods are very popular methods to sample from high-dimensional target distributions, which very often are of Gibbs type. Markov processes that have the target distribution as their invariant measure are used to approximate the equilibrium dynamics. In this talk, we explore performance criteria based on the related large deviations theory for random measures and we focus on the diffusion setting. We find that large deviations theory can not only adequately characterize the efficiency of the approximations, but it can also be used as a vehicle to design Markov processes, whose time average optimally (in the sense of variance reduction) approximates the quantities of interest. We quantify the effect that added irreversibility has in the speed of convergence to a target Gibbs measure and to the asymptotic variance of
the resulting estimator. One of our main finding is that adding irreversibility reduces the asymptotic variance of generic observables and we give an explicit characterization of when observables do not see their variances reduced in terms of a nonlinear Poisson equation. Connections to averaging problems for Hamiltonian systems and diffusion graphs will be given. Theoretical results are supplemented by simulations. (joint work with Luc Rey-Bellet)


Bruno Tuffin

Permutation Monte Carlo: applications, analysis and extension

Permutation Monte Carlo (PMC) is a conditional Monte Carlo method developed in the 90s to compute the probability u that a set of nodes become disconnected in a graph with independent failing links. It makes use of latent variables representing the repair times of links and looks at the order in which the links are repaired. The probability u can be computed conditional on this order. The turnip method is a variant removing from consideration at each step the failures that did not occur yet and do not have any impact on the system failure. It has been shown that these methods have been proved to give estimators with bounded relative error (BRE), which means that their standard deviation divided by the mean u remains bounded, when the link unreliabilities and u
converge to 0 while the network is fixed.

During this talk, we are going to review our published results and current research on those methods. More precisely, after an introduction to the technique, we will present:
- an extension to the case where failures of links are dependent;
- an extension to the case where links have random capacities and in which a certain target amount of flow must be carried from some source nodes to some destination nodes;
- Finally a more general extension to the more general computation of the hitting time of a given set of states by a continuous-time Markov chain. We show in this context how it can be used to estimate the cumulative distribution function, or the density, or some moment of the hitting time.

In each case we will describe if and when BRE is satisfied, provide numerical results, and compare with other methods, when relevant.
(joint work with Z. Botev, P. L'Ecuyer)


Pieter ten Wolde

Simulating rare events in cellular systems

Rare events play a central role in cellular systems. Cell differentiation during, e.g., embryonic development is driven by a sequence of rare switching events, and also the response of cellular systems to changes in their environment often involve rare switching events. Yet, simulating these events is a major computational challenge, because in conventional techniques most of the CPU time is wasted on the uneventful waiting time. In the past years, we have developed a new class of techniques, called Forward Flux Sampling (FFS), which makes it possible to simulate efficiently rare events in both equilibrium and non-equilibrium systems. More recently, we have extended these techniques so that they can also handle rare events in non-stationary (NS) systems. This NS-FFS technique can be used to study how sensitively systems respond to to transient fluctuations, or how efficiently they can be switched under the influence of an external signal, e.g. during cell differentiation. We apply NS-FFS to study the flipping of the phage lambda switch by an external signal. We show that there exists an optimal pulse that maximizes the switching efficiency.


Jose Villen Altamirano

Restart vs Splitting: A Comparative Study

In this paper the comparative study is made for both transient and steady-state simulation. Both original methods and also their truncation versions with different depths of truncation are compared. The models used for the study include several Jackson and non-Jackson networks and also a general model of reliability with different types of components. The main conclusion of the study is that RESTART behaves always significantly better than Splitting. Also, a small additional gain is achieved with RESTART with truncation in models where many thresholds can be set.


Manuel Villen Altamirano

Optimal importance function for RESTART simulation of a two-queue tandem Jackson network

RESTART is a widely applicable accelerated simulation technique that allows the evaluation of extremely low probabilities. In this method, a number of simulation retrials are performed when the process enters importance regions, i.e. regions of the state space where the chance of occurrence of a rare event of interest is higher. In previous papers the importance of a state, which is a measure of the chance of occurrence of the rare event when the state occurs, was defined. The importance regions should be defined by means of the importance of the states but, due to the difficulty of knowing them, they are defined by means of another function of the states called the importance function. The choice by the user of an importance function which reflects the importance of the states is crucial for the effective application of RESTART. The paper presents exact formulas of the importance of the states in a two-queue tandem Jackson network. It allows using the optimal importance function in this network and to gain insight on how to choose
an appropriate importance function in other queuing networks.


Clement Walter

Rare event simulation and splitting: a Point Process interpretation with application for discontinuous random variables

We introduce here a new approach to the Splitting methods with a Poisson process framework. Indeed for every real-valued random variable Y with continuous cdf (the output of a complex numerical code with random input for instance: Y = g(X)), we show that one can build a sequence of simulations whose distribution is related to a Poisson Process with intensity measure -log(P[Y > y]). On the one hand the number of samples (ie. simulations) required to get a realisation of Y above a given threshold q then follows a Poisson law with parameter -log(P[Y > q]) ; this is to be compared with the usual geometric law with parameter p obtained with naive Monte-Carlo. On the other hand simulating several processes in parallel allows to derive a Minimal Variance Unbiased Estimator (MVUE) for the probability p of exceeding the threshold q (it is also possible to build a quantile estimator given the probability p). Furthermore this framework allows us to handle possible discontinuities in the cdf of Y and to derive corrected MVUE to handle this case without knowing in advance if Y is actually discontinuous or not.


Jonathan Weare

Understanding umbrella sampling approaches to rare event simulation

I will discuss an ensemble sampling scheme based on a decomposition of the target average of interest into subproblems that are each individually easier to solve and can be solved in parallel. The most basic version of the scheme computes averages with respect to a given density and is a generalization of the Umbrella Sampling method for the calculation of free energies. We have developed a careful understanding of the accuracy of the scheme that is sufficiently detailed to explain the success of umbrella sampling in practice and to suggest improvements including adaptivity. For equilibrium versions of the scheme we have developed error bounds that reveal that the existing understanding of umbrella sampling is incomplete and leads to a number of erroneous conclusions about the scheme. Our bounds are motivated by new perturbation bounds for Markov Chains that we recently established and that are substantially more detailed than existing perturbation bounds for Markov chains. They demonstrate, for example, that equilibrium umbrella sampling is robust in the sense that in limits in which the straightforward approach to sampling from a density becomes exponentially expensive, the cost to achieve a fixed accuracy with umbrella sampling can increase only polynomially. I will also discuss extensions of the stratification philosophy to the calculation of dynamic averages with respect a given Markov process. The scheme is capable of computing very general dynamic averages and offers a natural way to parallelize in both time and space.


Armin Zimmermann

Numerical Results for the Automated Rare Event Simulation of Stochastic Petri Nets

Rare-event simulation is an efficient method to estimate measures of interest that depend on hitting or visiting a rare set of states of a discrete-event system. It is especially useful when state-level numerical methods are infeasible because numerical restrictions inhibit the use of (semi-)Markovian analytical techniques, e.g., due to the state space being too large to store completely. If the system can instead be expressed using a high-level description language such as stochastic Petri nets, then (rare-event) simulation can be performed on the higher level. Rare-event simulation methods based on multilevel splitting or importance sampling have been presented in the literature and software tool implementations are available for some of them. However, they require the specification of paths to the rare set, the distance, or importance function.
This paper presents the recent implementation of the ideas from [2] in the software tool TimeNET. We furthermore aim to compare the two methods and their results using examples, to better understand advantages and disadvantages. The overall goal is a technique (and software tool implementation) for fully automated rare-event simulation that does not require deeper knowledge of the underlying methods.


PRACTICAL INFORMATION

      Venue

Eurandom, Mathematics and Computer Science Dept, TU Eindhoven,

Den Dolech 2, 5612 AZ  EINDHOVEN,  The Netherlands

Eurandom is located on the campus of Eindhoven University of Technology, in the Metaforum building (4th floor) (about the building). The university is located at 10 minutes walking distance from Eindhoven main railway station (take the exit north side and walk towards the tall building on the right with the sign TU/e).
Accessibility TU/e campus and map.

 

 

      Registration

Registration is closed.

 

 

      Accommodation

For invited participants, we will take care of accommodation. Other attendees will have to make their own arrangements.

We have a preferred hotel, which can be booked at special rates. Please email Patty Koorn for instructions on how to make use of this special offer.

For other hotels around the university, please see: Hotels (please note: prices listed are "best available"). 

More hotel options can be found on the webpages of the Tourist Information Eindhoven, Postbus 7, 5600 AA Eindhoven.

 

      Travel

For those arriving by plane, there is a convenient direct train connection between Amsterdam Schiphol airport and Eindhoven. This trip will take about one and a half hour. For more detailed information, please consult the NS travel information pages or see Eurandom web page location.

Many low cost carriers also fly to Eindhoven Airport. There is a bus connection to the Eindhoven central railway station from the airport. (Bus route number 401) For details on departure times consult http://www.9292ov.nl

The University  can be reached easily by car from the highways leading to Eindhoven (for details, see our route descriptions).

 

      Conference facilities : Conference room, Metaforum Building  MF11&12

The meeting-room is equipped with a data projector, an overhead projector, a projection screen and a blackboard. Please note that speakers and participants making an oral presentation are kindly requested to bring their own laptop or their presentation on a memory stick.

 

      Conference Secretariat

Upon arrival, participants should register with the workshop officer, and collect their name badges. The workshop officer will be present for the duration of the conference, taking care of the administrative aspects and the day-to-day running of the conference: registration, issuing certificates and receipts, etc.

 

      Cancellation

Should you need to cancel your participation, please contact Patty Koorn, the Workshop Officer.

There is no registration fee, but should you need to cancel your participation after January 2, 2014, we will be obliged to charge a no-show fee of 30 euro.

 

      Contact

Mrs. Patty Koorn, Workshop Officer, Eurandom/TU Eindhoven, koorn@eurandom.tue.nl

 

SPONSORS

The organisers acknowledge the financial support/sponsorship of:

 

ERC???

 


 

 

        

        

Last updated 26-03-16,
by PK

 P.O. Box 513, 5600 MB Eindhoven, The Netherlands
tel. +31 40 2478100  
  e-mail: info@eurandom.tue.nl