We develop an endcient importance sampling algorithm for estimating the tail distribution of heavy-tailed compound sums, i.e. random variables of the form SM = Z1 + :::: + ZM where the Zi's are i.i.d. random variables in R and M is a non-negative, integer-valued random variable independent of the Zi's. We construct the rst estimator that can be rigorously shown to be strongly endcient only under the assumption that the Zi's are subexponential and M is lighttailed. Our estimator is based on state-dependent importance sampling and we use Lyapunovtype inequalities to control its second moment. The performance of our estimator is empirically illustrated in various instances involving popular heavy-tailed models.

We consider the problem of the exact simulation of random variables Z that satisfy the distributional identity Z ~ VY + (1 V)Z, where V in [0, 1] and Y are independent, and ~ denotes equality in distribution. Equivalently, Z is the limit of a Markov chain driven by that map. We give an algorithm that can be automated under the condition that we have a source capable of generating independent copies of Y, and that V has a density that can be evaluated in a black box format. The method uses a doubling trick for inducing coalescence in coupling from the past. Applications include exact samplers for many Dirichlet means, some two-parameter Poisson Dirichlet means, and a host of other distributions related to occupation times of Bessel bridges that can be described by stochastic ûxed point equations.

Most popular simulation and emulation tools use high-level models of forwarding behavior in switches and routers, and give little guidance on setting model parameters such as buffer sizes. Thus, a myriad of papers report results that are highly sensitive to the forwarding model or buffer size used. Incorrect conclusions are often drawn from these results about transport or application protocol performance, service provisioning, or vulnerability to attacks. In this paper, we argue that measurement-based models for routers and other forwarding devices are necessary. We devise such a model and validate it with measurements from three types of Cisco routers and one Juniper router, under varying traffic conditions. The structure of our model is device-independent, but the model uses device-specific parameters. The compactness of the parameters and simplicity of the model make it versatile for high-fidelity simulations that preserve simulation scalability. We construct a profiler to infer the parameters within a few hours. Our results indicate that our model approximates different types of routers significantly better than the default ns-2 simulator models. The results also indicate that queue characteristics vary dramatically among the devices we measure, and that backplane contention can be a factor.

Importance splitting is a simulation technique to estimate very small entrance probabilities for Markov processes by splitting sample paths at various stages before reaching the set of interest. This can be done in many ways, yielding diㄦent variants of the method. In this context, we propose a new one, called xed number of successes. We prove unbiasedness for the new and some known variants, because in many papers, the proof is based on an incorrect argument. Further, we analyze its behavior in a simplied setting in terms of endciency and asymptotics in comparison to the standard variant. The main diㄦence is that it controls the precision of the estimator rather than the computational eろt. Our analysis and simulation examples show that it is rather robust in terms of parameter choice and we present a two stage procedure which also yields condence intervals.

The expected duration of multi-hop paths can be incorporated at diㄦent layers in the protocol stack to improve the performance of mobile ad hoc networks. This article presents two discretetime and discrete-space Markov chain based methods, DTMC-CA and DTMC-MFT, to estimate the duration of multi-hop road-based paths in vehicular ad hoc networks (VANET). The duration of such paths does not depend on individual nodes because packets can be forwarded by any vehicle located along the roads forming the path. DTMC-CA derives probabilistic measures based only on vehicle density for a trac mobility model, which in this article is the microscopic Cellular Automaton (CA) freeway trac model. DTMC-MFT generalizes the approach used by DTMC-CA to any vehicular mobility model by focusing on the macroscopic information of vehicles rather than their microscopic characteristics. The proposed analytical models produce performance-measure values comparable to simulation estimates from the validated CA trac model. Furthermore, this article demonstrates the benets of incorporating expected path durations into a VANET routing protocol. Simulation results show that the network overhead associated with route maintenance can be reduced to less than half by using the expected path durations.

The simultaneous optimization of multiple responses in a dynamic system is challenging. When a response has a known gradient, it is often easily improved along the path of steepest ascent. On the contrary, a stochastic approximation technique may be used when the gradient is unknown or costly to obtain. We consider the problem of optimizing multiple responses in which the gradient is known for only one response. We propose a hybrid approach for this problem called simultaneous perturbation stochastic approximation steepest ascent, SPSA-SA or SP(SA)2 for short. SP(SA)2 is an SPSA technique that leverages information about the known gradient to constrain the perturbations used to approximate the others. We apply SP(SA)2 to the cross-layer optimization of throughput, packet loss, and end-to-end delay in a mobile ad hoc network (MANET), a self- organizing wireless network. The results show that SP(SA)2 achieves higher throughput and lower packet loss and end-to-end delay than the steepest ascent, SPSA, and the Nelder-Mead stochastic approximation approaches. It also reduces the cost in the number of iterations to perform the optimization.

We present an analytic model and a methodology to determine the optimal packet scheduling policy in a High Speed Downlink Packet Access (HSDPA) system. The optimal policy is the one that maximizes cell throughput while maintaining a level of fairness between the users in the cell. A discrete stochastic dynamic programming model for the HSDPA downlink scheduler is presented. Value iteration is then used to solve for the optimal scheduling policy. We use a FSMC (Finite State Markov Channel) to model the HSDPA downlink channel. A near optimal heuristic scheduling policy is developed. Simulation is used to study the performance of the resulted heuristic policy and compare it to the computed optimal policy. The results show that the performance of the heuristic policy is very close to that of the optimal policy. The heuristic policy has much less computational complexity which makes it easy to deploy, with only slight reduction in performance compared to the optimal policy.

We consider the problem of throughput-optimal cross-layer design of wireless networks. We propose a joint congestion control and scheduling algorithm that achieves a fraction 1/dI (G) of the capacity region, where dI (G) depends on certain structural properties of the underlying connectivity graph G of the wireless network, and also on the type of interference constraints. For a wide Range of wireless networks, dI (G) can be upper bounded by a constant, independent of the number of nodes in the network. The scheduling element of our algorithm is the maximal scheduling policy. Although this scheduling policy has been considered in several previous works, the challenges underlying its practical implementation in a fully distributed manner while accounting for necessary message exchanges have not been addressed in the literature. In this paper, we propose two algorithms for the distributed implementation of the maximal scheduling policy accounting for message exchanges, and analytically show that they still can achieve the performance guarantee under the 1-hop and 2-hop interference models. We also evaluate the performance of our cross-layer solutions in more realistic network settings with imperfect synchronization under the signal-to-interference-plus-noise ratio (SINR) interference model, and compare with the standard layered approaches such as TCP over IEEE 802.11b DCF networks.

Cross-layer design has become one of the most e®ective and e±cient methods to provide quality of service (QoS) over various communication networks, especially over wireless multimedia net- works. However, current research on cross-layer design has been carried out in various piecemeal approaches, and lacks a methodological foundation to gain in-depth understanding of complex cross-layer behaviors such as multiscale temporal-spatial behavior, leading to a design paradox and/or unmanageable design problems. In this paper, we propose a theoretical framework for quantitative interaction measures, which is further extended to sensitivity analysis by quantifying the contribution made by each design variable and by the interactions among them on the design objective. Thus, the proposed framework can signi¯cantly enhance our capability for cross-layer behavior characterization and provide design insights for future design. Furthermore, a case study on cross-layer optimized wireless multimedia communications has been adopted to illustrate major cross-layer design tradeo®s and validate the proposed framework. Both analytical and experimen- tal results show the correctness and e®ectiveness of the proposed framework.

We propose a new framework for worst case performance evaluation of MAC protocols for wireless ad hoc networks. Given a protocol, its performance metrics and a network topology, our framework first generates MAC scenarios which achieve poor performance at MAC-level. In order to evaluate the impact of these MAC scenarios on the end performance, we model the interactions between MAC interface and the MAC layer using a state transition graph and generate high level scenarios using enumeration techniques. These high level scenarios can be simulated and compared with heuristics developed by others to identify high level scenarios that are expected to lead to the worst case end performance.

In order to demonstrate its usefulness, we use our framework to evaluate the worst case performance of IEEE 802.11 DCF protocol by generating a library of MAC and high level scenarios. We simulate the high level scenarios to demonstrate that the scenarios we generate exhibit the worst performance among all the scenarios, including those generated by using heuristics recently proposed by other researchers.

Ultra-wideband (UWB) communications has emerged as a promising technology for high data rate wireless personal area networks (WPANs). In this paper, we address two key issues that impact the performance of a multi-hop UWB-based WPAN: throughput and transmission range. Arbitrary selection of routes in such a network may result in reserving an unnecessarily long channel time, and hence low network throughput and high blocking rate for prospective reservations. To remedy this situation, we propose a novel cross-layer resource allocation design. At the core of this design is a routing technique (called RTERU) that uses the allocated channel time as a routing metric. RTERU exploits the dependence of this metric on the multiple-rate capability of an UWB system. We show that selecting the route that consumes the minimum channel time while satisfying a target packet delivery probability over the selected route is an NP-hard problem. Accordingly, RTERU resorts to approximate path selection algorithms (implemented proactively and reactively) to find near-optimal solutions at reasonable computational/communication overhead. We further enhance the performance of RTERU by integrating into its design a packet overhearing capability. Simulations are used to demonstrate the performance of our proposed solutions.

We present a numerical inversion method for generating random variates from continuous distributions when only the density function is given. The algorithm is based on polynomial interpolation of the inverse CDF and Gauss-Lobatto integration. The user can select the required precision which may be close to machine precision for smooth, bounded densities; the necessary tables have moderate size. Our computational experiments with the classical standard distributions (normal, beta, gamma, t-distributions) and with the noncentral chi-square, hyperbolic, generalized hyperbolic and stable distributions showed that our algorithm always reaches the required precision. The setup time is moderate and the marginal execution time is very fast and nearly the same for all distributions. Thus for the case that large samples with xed parameters are required the proposed algorithm is the fastest inversion method known. Speed-up factors up to 1000 are obtained when compared to inversion algorithms developed for the specic distributions. This makes our algorithm especially attractive for the simulation of copulas and for quasi-Monte Carlo applications.

Scheduling and resource management play an important role in building complex distributed systems, such as grids. In this paper we study the impact on performance of job service demand variability in a two-level grid architecture, given that the grid and local schedulers are unaware of each job’s service demand. We examine two scheduling policies at grid level, which utilize site load information and three policies at local level. A simulation model is used to evaluate performance. Results show that service demand variability degrades performance, and thus a suitable local resource allocation policy is needed to reduce its impact.

Lindley’s recursion is an explicit recursive equation that describes the recursive relationship between consecutive waiting times in a single-stage single-server queue. In this paper, we develop explicit recursive representations for multi-server tandem queues with blocking. We demonstrate the application of these recursive representations with simulations of large-scale tandem queueing networks. We compare the computational efficiency of these representations with two other popular discrete-event simulation approaches, namely, event scheduling and process interaction. Experimental results show that these representations are seven (or more) times faster than their counterparts based on the event-scheduling and process-interaction approaches.

The design, visualization, manipulation, and implementation of models for computer simulation are key parts of the discipline. Models are constructed as a means to understand physical phenomena as state changes occur over time. One issue that arises is the need to correlate models and their components with the phenomena being modeled. For example, a part of an automotive engine needs to be placed into cognitive context with the diagrammatic icon that represents that part's function. A typical solution to this problem is to display a dynamic model of the engine in one window and the engine's CAD model in another. Users are expected to, on their own, mentally blend the dynamic model and the physical phenomenon into the same context. However, this contextualization is not trivial in many applications.

Our approach expands upon this form of user interaction by specifying two ways in which dynamic models and the corresponding physical phenomena may be viewed, and experimented with, within the same human interaction space. We present a methodology and implementation of contextualization for diagram-based dynamic models using an anesthesia machine, and then follow up with a human study of its effects on spatial cognition.

An integrated Belief-Desire-Intention (BDI) modeling framework is proposed for human decision making and planning for evacuation scenarios, whose submodules are based on a Bayesian belief network (BBN), Decision- Field-Theory (DFT), and a probabilistic depth first search (PDFS) technique. A key novelty of the proposed model is its ability to represent both the human decision-making and decision-planning functions in a unified framework. To mimic realistic human behaviors, attributes of the BDI framework are reverse-engineered from human-in-the-loop experiments conducted in the Cave Automatic Virtual Environment (CAVE). The proposed modeling framework is demonstrated for a human’s evacuation behaviors in response to a terrorist bomb attack. The simulated environment and agents (models of humans) conforming to the proposed BDI framework are implemented in AnyLogic® agent-based simulation software, where each agent calls external Netica BBN software to perform its perceptual processing function and Soar software to perform its real-time planning and decision-execution functions. The constructed simulation has been used to test the impact of several factors (e.g., demographics, number of police officers, information sharing via speakers) on evacuation performance (e.g., average evacuation time, percentage of casualties).

We extend and analyze a new class of estimators for the variance parameter of a steady-state simulation output process. These estimators are based on “folded” versions of the standardized time series (STS) of the process, and are analogous to the area and Cram´er–von Mises estimators calculated from the original STS. In fact, one can apply the folding mechanism more than once to produce an entire class of estimators, all of which re-use the same underlying data stream. We show that these folded estimators share many of the same properties as their non-folded counterparts, with the added bonus that they are often nearly independent of the non-folded versions. In particular, we derive the asymptotic distributional properties of the various estimators as the run length increases, as well as their bias, variance, and mean squared error. We also study linear combinations of these estimators, and we show that such combinations yield estimators with lower variance than their constituents. Finally, we consider the consequences of batching, and we see that the batched versions of the new estimators compare favorably to benchmark estimators such as the nonoverlapping batch means estimator.

In this paper, we develop a stochastic approximation method to solve a monotone estimation prob- lem and use this method to enhance the empirical performance of the Q-learning algorithm when applied to Markov decision problems with monotone value functions. We begin by considering a monotone estimation problem where we want to estimate the expectation of a random vector η. We assume that the components of E{η} are known to be in increasing order. The stochastic approximation method that we propose is designed to exploit this information by projecting its iterates onto the set of vectors with increasing components. The novel aspect of the method is that it uses projections with respect to the max norm. We show the almost sure convergence of the stochastic approximation method. After this result, we consider the Q-learning algorithm when applied to Markov decision problems with monotone value functions. We study a variant of the Q-learning algorithm that uses projections to ensure that the value function approximation that is obtained at each iteration is also monotone. Computational results indicate that the performance of the Q-learning algorithm can be improved signi¯cantly by exploiting the monotonicity property of the value functions.

We consider the problem of finding a set of feasible or near-feasible systems among a finite number of simulated systems in the presence of constraints on secondary performance measures. We first present a generic procedure that detects the feasibility of one system in the presence of one constraint and extend it to the case of two or more systems and constraints. To accelerate the elimination of infeasible systems, a method that re-uses collected observations and its varianceupdating version are discussed. Experimental results are presented to compare the performance of the proposed procedures.

Agent-based business process simulation has grown in popularity, in part, because of its analysis capabilities. The analyses depend on the kinds of simulations that can be built, adapted, and extended, which in turn, depend on the underlying simulation framework. We report the results of our analysis of 19 agent-based process simulation tools and their simulation frameworks. We conclude that a growing number of simulation tools are using component-based software techniques. Nevertheless, most simulation tools do not directly support requirements models, their transformation into executable simulations, or the management of model variants over time. Such practices are becoming more widely applied in software engineering, under the term software product line engineering (SPLE). Based on our analysis, agent-based process simulation tools may improve their customization capacity by: (1) supporting object modeling more completely and (2) supporting software product line engineering issues.

This paper considers importance sampling as a tool for rare-event simulation. The focus is on estimating the probability of overflow in the downstream queue of a Jacksonian two-node tandem queue -- it is known that in this setting ‘traditional’ state-independent importance-sampling distributions perform poorly. We therefore concentrate on developing a state-dependent change of measure, that we prove to be asymptotically efficient.

More specific contributions are the following. (i)We concentrate on the probability of the second queue exceeding a certain predefined threshold before the system empties. Importantly, we identify an asymptotically efficient importance-sampling distribution for any initial state of the system. (ii) The choice of the importance-sampling distribution is backed up by appealing heuristics that are rooted in large-deviations theory. (iii) The method for proving asymptotic efficiency relies on probabilistic arguments only. The paper is concluded by simulation experiments that show a considerable speed up.

The field of Game Theory has proved to be of great importance in modeling interactions between self-interested parties in a variety of settings. Traditionally, game theoretic analysis relied on highly stylized models to provide interesting insights about problems at hand. The shortcoming of such models is that they often do not capture vital detail. On the other hand, many real strategic settings, such as sponsored search auctions and supply-chains, can be modeled in high resolution using simulations. Recently, a number of approaches have been introduced to perform analysis of game-theoretic scenarios via simulation-based models. The first contribution of this work is the asymptotic analysis of Nash equilibria obtained from simulation-based models. The second contribution is to derive expressions for probabilistic bounds on the quality of Nash equilibrium solutions obtained using simulation data. In this vein, we derive very general distribution-free bounds, as well as bounds which rely on the standard normality assumptions, and extend the bounds to infinite games via Lipschitz continuity. Finally, we introduce a new maximum-a-posteriori estimator of Nash equilibria based on game-theoretic simulation data and show that it is consistent and almost surely unique.

Computer networks often display nonlinear behaviour when examined over a wide range of oper- ating conditions. There are few strategies available for modelling such behaviour and optimizing such systems as they run. Prole-driven regression is developed and applied to modelling and run-time optimization of throughput in a mobile ad hoc network, a self-organizing collection of mobile wireless nodes without any xed infrastructure. The intermediate models generated in prole-driven regression are used to t an overall model of throughput, and are also used to op- timize controllable factors at run-time. Unlike others, the throughput model accounts for node speed. The resulting optimization is very ective; locally optimizing the network factors at run- time results in throughput as much as six times higher than that achieved with the factors at their default levels.

A setwise Gibbs sampler (SGS) method is developed to simulate stationary distributions and performance measures of network occupancy of Baskett-Chandy-Muntz-Palacios (BCMP) telecommunication models. It overcomes the simulation difficulty encountered in applying the standard Gibbs sampler to closed BCMP networks with constant occupancy constraints. We show Markov chains induced by SGS converge to the target stationary distributions. This paper also investigates the filtered Gibbs sampler (FGS) as an efficient method for estimating various network performance measures. It shows that FGS’s efficiency is considerable but may be improperly overestimated. A more conservative performance estimator is then presented.

When planning simulations of large-scale systems, it is important to anticipate what information is required to model the system and obtain desired output. This can be done without tying the study to a specific simulation package or language. It is valuable to do so to avoid unnecessarily long development and execution times. In this paper, we offer a simulation information model (SIM) designed to help organize system information in the early stages of a project. (It can also be used to analyze existing models.) The SIM allows complexity analysis of the system to be performed, and may lead to a better selection of simulation language. The SIM is illustrated using two examples, and its relationship to current formalisms is discussed.

To enhance efficiency in Monte Carlo simulations, we develop an adaptive stratified sampling algorithm for allocation of sampling effort within each stratum, in which an adaptive variance reduction technique is applied. Given the number of replications in each batch, our algorithm updates allocation fractions to minimize the work-normalized variance of the stratified estimator of the mean. We establish the asymptotic normality of the stratified estimator of the mean as the number of batches tends to infinity. Although implementation of the proposed algorithm requires a small amount of initial work, the algorithm has the potential to yield substantial improvements in estimator efficiency. Equally important is that the adaptive framework avoids the need for frequent recalibration of the parameters of the variance reduction methods applied within each stratum when changes occur in the experimental conditions governing system performance. To illustrate the applicability and effectiveness of our algorithm, we provide numerical results for a Black-Scholes option pricing, where we stratify the underlying Brownian motion with respect to its terminal value and apply an importance sampling method to normal random variables filling in the Brownian path. Relative to the estimator variance with proportional allocation, the proposed algorithm achieved a fourfold reduction in estimator variance with a negligible increase in computing time.

Content Distribution Networks (CDNs) have gained considerable attention in the past few years. As such, there is need for developing frameworks for carrying out CDN simulations. In this pa- per, we present a modeling and simulation framework for CDNs, called CDNsim. CDNsim has been designated to provide a realistic simulation for CDNs, simulating the surrogate servers, the TCP/IP protocol and the main CDN functions. The main advantages of this tool are its high per- formance, its extensibility and its user interface which is used to configure its parameters. CDNsim provides an automated environment for conducting experiments and extracting client, server and network statistics. The purpose of CDNsim is to be used as a testbed for CDN evaluation and experimentation. This is quite useful both for the research community (to experiment with new CDN data management techniques) and for CDN developers (to evaluate profits on prior certain CDN installations).

This article explores possibilities for designing and executing simulation models with specific analysis goals in mind, and shows that a tight coupling of the modeling and analysis phases in a simulation project can lead to dramatic improvements in the study results. Suggestions are made for how simulation analysis, considered in the explicit context of discrete-event simulation models, can create new opportunities for meaningful research and more efficient modeling. Modeling decisions can play a significant role in the performance of analytical procedures. How a simulation model is designed can enable, inhibit, or even invalidate analytical procedures and methodology research results.

Industrial Strength COMPASS (ISC) is a particular implementation of a general framework for optimizing the expected value of a performance measure of a stochastic simulation with respect to integer-ordered decision variables in a finite (but typically large) feasible region defined by linear-integer constraints. The framework consists of a global-search phase, followed by a local-search phase, and ending with a “clean-up” (selection of the best) phase. Each phase provides a probability 1 convergence guarantee as the simulation effort increases without bound: Convergence to a globally optimal solution in the global-search phase; convergence to a locally optimal solution in the local-search phase; and convergence to the best of a small number of good solutions in the clean-up phase. In practice, ISC stops short of such convergence by applying an improvement-based transition rule from the global phase to the local phase; a statistical test of convergence from the local phase to the clean-up phase; and a ranking-and-selection procedure to terminate the clean-up phase. Small-sample validity of the statistical test and ranking-and-selection procedure is proven for normally distributed data. ISC is compared to the commercial optimization via simulation package OptQuest on five test problems that range from 2 to 20 decision variables and on the order of 10⁴ to 10²⁰ feasible solutions. These test cases represent response-surface models with known properties and realistic system simulation problems.

We propose to improve the efficiency of simulation optimization by integrating the notion of optimal computing budget allocation into the Cross-Entropy (CE) method, which is a global optimization search approach that iteratively updates a parameterized distribution from which candidate solutions are generated. This article focuses on continuous optimization problems. In the stochastic simulation setting where replications are expensive but noise in the objective function estimate could mislead the search process, the allocation of simulation replications can make a significant difference in the performance of such global optimization search algorithms. A new allocation scheme is developed based on the notion of optimal computing budget allocation. The proposed approach improves the updating of the sampling distribution by carrying out this computing budget allocation in an efficient manner, by minimizing the expected mean-squared error of the CE weight function. Numerical experiments indicate that the computational efficiency of the CE method can be substantially improved if the ideas of computing budget allocation are applied.

In simulation of complex stochastic systems, such as Discrete-Event Systems (DES), statistical distributions are used to model the underlying randomness in the system. A sensitivity analysis of the simulation output with respect to parameters of the input distributions, such as the mean and the variance, is therefore of great value. The focus of this article is to provide a practical guide for robust sensitivity, respectively, gradient estimation that can be easily implemented along the simulation of a DES. We study the Measure-Valued Differentiation (MVD) approach to sensitivity estimation. Specifically, we will exploit the “modular” structure of the MVD approach, by firstly providing measure-valued derivatives for input distributions that are of importance in practice, and subsequently, by showing that if an input distribution possesses a measure-valued derivative, then so does the overall Markov kernel modeling the system transitions. This simplifies the complexity of applying MVD drastically: one only has to study the measure-valued derivative of the input distribution, a measure-valued derivative of the associated Markov kernel is then given through a simple formula in canonical form. The derivative representations of the underlying simple distributions derived in this article can be stored in a computer library. Combined with the generic MVD estimator, this yields an automated gradient estimation procedure. The challenge in automating MVD so that it can be included into a simulation package is the verification of the integrability condition to guarantee that the estimators are unbiased. The key contribution of the article is that we establish a general condition for unbiasedness which is easily checked in applications. Gradient estimators obtained by MVD are typically phantom estimators and we discuss the numerical efficiency of phantom estimators with the example of waiting times in the G/G/1 queue.

The asymptotic robustness of estimators as a function of a rarity parameter, in the context of rare-event simulation, is often qualified by properties such as bounded relative error (BRE) and logarithmic efficiency (LE), also called asymptotic optimality. However, these properties do not suffice to ensure that moments of order higher than one are well estimated. For example, they do not guarantee that the variance of the empirical variance remains under control as a function of the rarity parameter. We study generalizations of the BRE and LE properties that take care of this limitation. They are named bounded relative moment of order k (BRM-k) and logarithmic efficiency of order k (LE-k), where k ≥ 1 is an arbitrary real number. We also introduce and examine a stronger notion called vanishing relative centered moment of order k, and exhibit examples where it holds. These properties are of interest for various estimators, including the empirical mean and the empirical variance. We develop (sufficient) Lyapunov-type conditions for these properties in a setting where state-dependent importance sampling (IS) is used to estimate first-passage time probabilities. We show how these conditions can guide us in the design of good IS schemes, that enjoy convenient asymptotic robustness properties, in the context of random walks with light-tailed and heavy-tailed increments. As another illustration, we study the hierarchy between these robustness properties (and a few others) for a model of highly reliable Markovian system (HRMS) where the goal is to estimate the failure probability of the system. In this setting, for a popular class of IS schemes, we show that BRM-k and LE-k are equivalent and that these properties become strictly stronger when k increases. We also obtain a necessary and sufficient condition for BRM-k in terms of quantities that can be readily computed from the parameters of the model.

The British National Health Service (NHS) has a performance management framework that aims to guarantee short waiting times for patients by including mandatory targets for hospitals. DGHPSim is a suite of four components that simulates the activities of an NHS general hospital to show the effect of different policies on waiting times in these hospitals. DGHPSim has a generic structure that is used to simulate a particular hospital by employing data appropriate to that hospital from available data sets. Two of the components of DGHPSim, the accident and emergency simulator and the outpatient simulator, may be used independently as stand-alone simulators of these hospital functions. The DGHPSim suite incorporates a novel way of simulating the multitasking behavior of clinicians and uses transition matrices, extracted from standard datasets, to represent the states through which patients pass and the wards in which they may be treated. As a whole, the DGHPSim suite may be used to investigate improvement options before their implementation or to investigate how a hospital has improved its performance. We show how DGHPSim is used to investigate reported performance improvements in an English general hospital.

Human immunodeficiency virus (HIV) increases the risks of developing tuberculosis (TB) disease following infection, and speeds up disease progression. This has had a devastating effect on TB epidemics in sub-Saharan Africa, where incidence rates have more than trebled in the past twenty years. Current control methods for TB disease have failed to keep pace with this growth in TB, and there is an urgent need to find TB control strategies that are effective in high-HIV prevalent settings. This paper describes a discrete-event simulation model of endemic TB that includes the effects of HIV and of household structure on the transmission dynamics of TB. Incorporating a social structure allows us to compare the effectiveness of contact-tracing interventions with targeted case-finding at high risk groups. We describe the modeling of the household structure in some detail, as this has applications to the modeling of other infectious diseases.