Perfect simulation of monotone systems for rare event probability estimation

This paper deals with the estimation of rare event probabilities in finite capacity queuing networks. The traditional product form property of Markovian queueing networks usually vanishes when capacity of queues are finite and clients are blocked or rejected. A new efficient simulation method, derived from Propp & Wilson (Propp 1996), perfect simulation, is applied in the finite capacity queue context. An algorithm directly samples states of the network according to the stationary distribution. This method is adapted for simulation of rare events, typically when events are described by an increasing subset of the state space. Provided that events of the network are monotone, monotonicity techniques are used to reduce the sampling time. Moreover, a stopping mechanism has been developed to interrupt the simulation when an increasing set has been reached. Then, for the estimation of a monotonous reward function, the simulation time could be reduced drastically as in (Vincent and Marchand 2004).