Abstract We apply the splitting method to three well-known counting problems, namely 3-SAT, random graphs with prescribed degrees, and binary contingency tables. We present an enhanced version of the splitting method based on the capture-recapture technique, and show by experiments the superiority of this technique for SAT problems in terms of variance of the associated estimators, and speed of the algorithms.

arXiv: [arXiv:1103.6096]
SSRN [ssrn.com/abstract=1804807]
TI: [Tinbergen Institute Discussion Paper TI 2011-062/4].

Abstract An overview of variance reduction techniques is given, notably common random numbers, antithetic variates, control variates, conditioning, stratified sampling, importance sampling, splitting techniques, and quasi-Mont Carlo sampling.

CentER [Discussion Paper 2010-117]
SSRN [ssrn.com/abstract=1715474]

Abstract We present a method to obtain state- and time-dependent importance sampling estimators by repeatedly solving a minimum cross-entropy (MCE) program as the simulation progresses. This MCE-based approach lends a foundation to the natural notion to stop changing the measure when it is no longer needed. We use this method to obtain a state- and time-dependent estimator for the one-tailed probability of a light-tailed i.i.d. sum that is logarithmically efficient in general and strongly efficient when the jumps are Gaussian. We go on to construct an estimator for the two-tailed problem which is shown to be similarly efficient. We consider minor variants of the algorithm obtained via MCE, and present some numerical comparisons between our algorithms and others from the literature.

DOI: [10.1007/s10479-009-0611-7]

Abstract A sequence of real numbers (x_n) is Benford if the significands, i.e. the fraction parts in the floating-point representation of (x_n) are distributed logarithmically. Similarly, a discrete-time irreducible and aperiodic finite-state Markov chain with probability transition matrix P and limiting matrix P^* is Benford if every component of both sequences of matrices (Pⁿ - P^*) and (Pⁿ⁺¹-Pⁿ) is Benford or eventually zero. Using recent tools that established Benford behavior both for Newton's method and for finite-dimensional linear maps, via the classical theories of uniform distribution modulo 1 and Perron-Frobenius, this paper derives a simple sufficient condition (nonresonant) guaranteeing that P, or the Markov chain associated with it, is Benford. This result in turn is used to show that almost all Markov chains are Benford, in the sense that if the transition probabilities are chosen independently and continuously, then the resulting Markov chain is Benford with probability one. Concrete examples illustrate the various cases that arise, and the theory is complemented with several simulations and potential applications.

arXiv: [arXiv:1003.0562]
DOI: [10.1137/100789890]

Abstract A version of the classical secretary problem is studied, in which one is interested in selecting one of the b best out of a group of n differently ranked persons who are presented one by one in a random order. It is assumed that b≥1 is a preassigned number. It is known, already for a long time, that for the optimal policy one needs to compute b position thresholds, for instance via backwards induction. In this paper we study approximate policies, that use just a single or a double position threshold, albeit in conjunction with a level rank. We give exact and asymptotic (as n→∞) results, which show that the double-level policy is an extremely accurate approximation.

arXiv: [arXiv:1009.0626]
DOI: [10.1017/S026996481000032X]

Abstract The correspondence between the cross-entropy method and the zero-variance approximation to simulate a rare event problem in Markov chains is shown. This leads to a sufficient condition that the cross-entropy estimator is asymptotically optimal.

arXiv: [arXiv:1003.1950]
DOI: [10.1016/j.procs.2010.04.176]

Abstract There are various importance sampling schemes to estimate rare event probabilities in Markovian systems such as Markovian reliability models and Jackson networks. In this work, we present a general state dependent importance sampling method which partitions the state space and applies the cross-entropy method to each partition. We investigate two versions of our algorithm and apply them to several examples of reliability and queueing models. In all these examples we compare our method with other importance sampling schemes. The performance of the importance sampling schemes is measured by the relative error of the estimator and by the efficiency of the algorithm. The results from experiments show considerable improvements both in running time of the algorithm and the variance of the estimator.

DOI: [10.1016/j.ejor.2010.07.002]

Abstract In this paper we consider a rare-event problem in the fork-join queue for which we develop an efficient importance sampling algorithm.

Download the paper [full (PDF)].

Abstract This paper applies importance sampling simulation for estimating rare-event probabilities of the first passage time in the infinite server queue with renewal arrivals and general service time distributions. We consider importance sampling algorithms which are based on large deviations results of the infinite server queue, and we consider an algorithm based on the cross-entropy method, where we allow light-tailed and heavy-tailed distributions for the interarrival times and the service times. Efficiency of the algorithms is discussed by simulation experiments.

DOI: [10.1016/j.ejor.2008.10.028]

Proceedings versions in
Proceedings 7th International Workshop on Rare Event Simulation", INRIA, Rennes, France, September 2008.
Proceedings 2-nd Korea-Netherlands Joint Conference on Queueing Theory and its Applications to Telecommunication Systems Amsterdam, October 2006.

Abstract In this paper we apply the minimum cross-entropy method (MinxEnt) for estimating rare-event probabilities for the sum of i.i.d. random variables. MinxEnt is an analogy of the Maximum Entropy Principle in the sense that the objective is to minimize a relative (or cross) entropy of a target density h$from an unknown density f under suitable constraints. The main idea is to use the solution to this optimization program as the simulation density in importance sampling. We shall see that some existing importance sampling methods can be cast in a MinxEnt program, such as the large deviations approach for light tails and the hazard rate twisting for heavy tails. As an extension we shall consider a correlated version of this hazard rate twisted solution which give better simulation results. The sample generation is based on a Gibbs sampler algorithm.

DOI: [10.1177/0037549707087713]

Proceedings version in
Proceedings Korea-Netherlands Joint Conference on Queueing Theory and its Applications to Telecommunication Systems Seoul, June 2005.

Abstract We develop a methodology for studying ``large deviations type" questions. Our approach does not require that the large deviations principle holds, and is thus applicable to a larg class of systems. We study a system of queues with exponential servers, which share an arrival stream. Arrivals are routed to the (weighted) shortest queue. It is not known whether the large deviations principle holds for this system. Using the tools developed here we derive large deviations type estimates for the most likely behavior, the most likely path to overflow and the probability of overflow. The analysis applies to any finite number of queues. We show via a counterexample that this sytem may exhibit unexpected behavior.

DOI: [10.1007/s00186-005-0037-1]

An extended version is published as Tinbergen Institute Discussion Paper TI 2005-016/4.

Abstract This paper reports simulation experiments, applying the cross entropy method such as the importance sampling algorithm for efficient estimation of rare event probabilities in Markovian reliability systems. The method is compared to various failure biasing schemes that have been proved to give estimators with bounded relative errors. The results from the experiments indicate a considerable improvement of the performance of the importance sampling estimators, where performance is measured by the relative error of the estimate, by the relative error of the estimator, and by the gain of the importance sampling simulation to the normal simulation.

DOI: [10.1007/s10479-005-5727-9]

Abstract A fluid approximation gives the main term in the asymptotic expression of the value function for a controllable stochastic network. The policies which have the same asymptotic of their value functions as the value function of the optimal policy, are called asymptotically optimal policies. We consider a problem of finding from this set of asymptotically optimal policies a best one in the sense that the next term of its asymptotic expression is minimal. The analysis of this problem is closely connected with large deviation problems for a random walk.

DOI: [10.1214/aoap/1069786504]
JSTOR: [1193181].

Abstract This paper analyzes the transient buffer content distribution of a queue fed by a large number of Markov fluid sources. We characterize the probability of overflow at time t, given the current buffer level and the number of sources in the on-state.

After scaling buffer and bandwidth resources by the number of sources n, we can apply large deviations techniques. The transient overflow probability decays exponentially in n. In case of exponential on/off sources we derive an expression for the decay rate of the rare event probability under consideration. For general Markov fluid sources we present a plausible conjecture. We also provide the `most likely path' from the initial state to overflow (at time t).

Knowledge of the decay rate and the most likely path to overflow leads to (i) approximations of the transient overflow probability, and (ii) efficient simulation methods of the rare event of buffer overflow. The simulation methods, based on importance sampling, give a huge speed-up compared to straightforward simulations. The approximations are of low computational complexity, and accurate, as verified by means of simulation experiments.

DOI: [10.1145/511442.511443].

Proceedings version in
Proceedings 2nd International Workshop on Rare Event Simulation, Twente, March 1999.

Abstract This paper deals with the transient behavior of the Erlang loss model. After scaling both arrival rate and number of trunks, an asymptotic analysis of the blocking probability is given. Apart from that, the most likely path to blocking is given. Compared to results of Shwartz and Weiss, more explicit expressions are obtained by using probabilistic arguments. The computation method is applied to the problem of (real-time) dimensioning of virtual paths in ATM networks, and to the problem of integrating scheduled and switched connections in a single network.

DOI: [10.1016/S0166-5316(00)00050-X].

Abstract This paper describes a discrete-time retrial queue and shows how importance sampling simulations can be applied for estimating the probability of large orbit content and the overflow fraction of primary calls.

Download the paper: [full (PDF)].

Abstract In this paper we describe a decision support system developed to help in assessing the need for various type of prison cells. In particular we predict the probability that a criminal has to be sent home because of a shortage of cells. The problem is modelled through a queueing network with blocking after service. The main objective of our study is to describe our analytical method and an approximate algorithm to solve this network. Through simulation studies we evaluate our method. Both the analytic and the simulation tool are elements of the decision support system.

DOI: [10.1057/palgrave.jors.2601021]

This paper received the Goodeve Medal (2001)i for being the best paper published in any of the Operational Research Society's journals in 2000.

Abstract We analyse the deviant behavior of a queue fed by a large number of traffic streams, which models an ATM switch. In particular, we explicitly give the most likely trajectory (or optimal path) to buffer overflow, by applying large deviations techniques. This is done for a broad class of sources, consisting of Markov fluid sources and periodic sources. Apart from a number of ramifications of this result, we present guidelines for the numerical evaluation of the optimal path.

DOI: [10.1023/A:1019154129708].

Abstract Intuition may lead to the hypothesis that in stochastic inventory systems a higher demand variability results in larger variances and in an increase of total expected system costs. In a recent paper, Song (1994) formally proved this assertion to hold for a certain class of inventory models (including the Newsboy Problem), given a particular definition of variability. Here we use stochastic dominance relations in the Newsboy Problem to characterize demand distributions for which the opposite effect may occur, i.e., higher demand variability may result in larger variances and lower costs. In addition, we provide necessary and sufficient conditions under which larger demand variances and lower costs occur simultaneously.

DOI: [10.1287/opre.46.6.934]
JSTOR: [222946].
An extended version is published as Management Report Series 265 Erasmus University Rotterdam, 1996.

Abstract In this paper we consider a slotted queueing model with finite buffers and correlated input. Arrivals are generated by different sources and offered in batches at the end of each slot. The batch sizes depend on the states of the sources which change their states according to Markov schemes. In case that the buffer reaches its limits, the excess of the buffer is lost. At the end of a slot a random batch is removed from the buffer. We prove a large deviations result for the loss probability in this model, and apply importance sampling for estimation of this probability.

Download the paper: [full (PS)].

Abstract In this paper we analyse an (s, Q) inventory model in which used products can be remanufactured to new ones. We develop two approximations for the average costs and compare their performance with that of an approximation suggested by Muckstadt and Isaac. Next we extend the model with the option to dispose returned products and present a heuristic optimisation procedure which is checked with full enumeration.

DOI: [10.1016/0925-5273(95)00020-8].

Proceedings version in
Proceedings 8th International Working Seminar on Production Economics , Vol. 3, p. 19-23, 1994.

Abstract In deze studie behandelen we twee eenvoudige voorbeelden die illustratief zijn voor kwaliteitsgarantie van communicatiesystemen, namelijk een kleine kans op verminking van verzonden berichten en een kleine kans op verlies van delen van berichten. Deze kansen kunnen geschat worden door bijvoorbeeld het uitvoeren van simulaties. Omdat we hier typisch spreken over kansen van de orde 10^{-6} en kleiner, is het wenselijk variantiereductietechnieken toe te passen. Wij zullen in de voorbeelden laten zien hoe importance sampling de simulaties versnelt. Om een optimale nieuwe kansmaat te vinden worden limietresultaten uit de theorie van grote afwijkingen gebruikt.

Abstract In this paper we study continuous flow finite buffer systems with input rates modulated by Markov chains. Discrete event simulations are applied for estimating loss probabilities. The simulations are executed under a twisted version of the original probability measure (importance sampling). We present a simple rule for determining a new measure, then show that the new measure matches the `most likely' empirical measure that we expect from large deviations arguments, and finally prove optimality of the new measure.

JSTOR: [3215359].

Proceedings version in
Proceedings B-ISDN teletraffic modelling Symposium, Antwerpen, February 1995.

Abstract In this paper we study weak stochastic ordering on multidimensional lattices. The main objective of our study is to derive comparison of multidimensional marginal distributions of two Markov chains. We are able to prove this when the matrices of transition probabilities satisfy monotonicity and comparability properties.

DOI: [10.1016/0167-6377(95)00045-3].

Abstract This paper addresses characteristics of finite-buffer Markov-modulated fluid processes, particularly those related to their deviant behavior. Our aim in this paper is to find rough asymptotics for the probability of a loss cycle. Apart from that, we derive some properties of the fluid process in case of the buffer contents reaching a high level (a process we call the conjugate of the original process). Our main goal is to obtain practicable methods to find the rate matrix of this conjugate process. For this purpose we use large deviations techniques, but we consider the governing eigensystem, as well, and we discuss the relation between these two approaches. We extend the analysis to the multiple source case. Finally, we use the obtained results in simulation. We examine variance reduction by importance sampling in a multiple source example. The new statistical law of the fluid process is based on the conjugate rate matrices.

DOI: [10.1017/S0269964800003879].

Abstract Addresses the issue of call acceptance and routing in ATM networks. The goal is to design an algorithm that guarantees bounds on the fraction of cells lost by a call. The method proposed for call acceptance and routing does not require models describing the traffic. Each switch estimates the additional fraction of cells that would be lost if new calls were routed through the switch. The routing algorithm uses these estimates. The estimates are obtained by monitoring the switch operations and extrapolating to the situation where more calls are routed through the switch. The extrapolation is justified by a scaling property. To reduce the variance of the estimates, the switches calculate the cell loss that would occur with virtual buffers. A way to choose the sizes of the virtual buffers in order to minimize the variance is discussed. Thus, the switches constantly estimate their spare capacity. Simulations were performed using Markov fluid sources to test the validity of the approach.

DOI: [10.1109/26.380228].

Preprint available.

Abstract Markov modulated fluid models are studied in this paper. When the inputof the fluid model is represented by one Markov chain, two approaches are given that result in asymptotic expressions for the overflow probability. Both approaches are based on large deviations theories. The equivalence of the expressions is proved. When the input is represented by N similar Markov chains, a reduction property is derived.

DOI: [10.1017/S0269964800002722].

Abstract A separable closed queueing network is decomposed into two subnetworks. The rates of the servers in one of the subnetworks are controllable in order to maximize the throughput of the other one. This problem of optimal flow control is transformed to a linear programming problem. The optimal solution of the linear program yields the structure of the optimal control. Conditions for the network are given to guarantee the applicability of this approach.

DOI: [10.1109/9.21103].

Abstract A general method is developed to compute easy bounds of the weighted stationary probabilities for networks of queues which do not satisfy the standard product form. The bounds are obtained by constructing approximating reversible Markov chains. Thus, the bounds are insensitive with respectto service-time distributions. A special representation, called the tree-form solution, of the stationary distribution is used to derive the bounds. The results are applied to an overflow model.

JSTOR: [3214229].

Abstract In this paper we define functional monotonicity and functional dominance for nonnegative matrices and apply these properties to the blocks of a partitioned stochastic matrix. In this way we obtain stochastic ordering of conditional steady-state distributions of a Markov chain. The method will be applied to an overflow queueing model for showing that an upper bound of the blocking probabilities is valid for general service time distributions at one of the facilities.

DOI: [10.1080/15326348808807085].

Abstract A general method to obtain insensitive upper and lower bounds for the stationary distribution of queueing networks is sketched. It is applied to an overflow model. The bounds are shown to be valid for service distributions with decreasing failure rate. A characterization of phase-type distributions with decreasing failure rate is given. A approximationmethod is proposed. The methods are illustrated with numerical results.

JSTOR: [3214100].