A combined splitting—cross entropy method for rare-event probability estimation of queueing networks

We present a fast algorithm for the efficient estimation of rare-event (buffer overflow) probabilities in queueing networks. Our algorithm presents a combined version of two well known methods: the splitting and the cross-entropy (CE) method. We call the new method SPLITCE. In this method, the optimal change of measure (importance sampling) is determined adaptively by using the CE method. Simulation results for a single queue and queueing networks of the ATM-type are presented. Our numerical results demonstrate higher efficiency of the proposed method as compared to the original splitting and CE methods. In particular, for a single server queue example we demonstrate numerically that both the splitting and the SPLITCE methods can handle our buffer overflow example problems with both light and heavy tails efficiently. Further research must show the full potential of the proposed method.     

Markov chain Monte Carlo Using an Approximation

This article presents a method for generating samples from an unnormalized posterior distribution f(·) using Markov chain Monte Carlo (MCMC) in which the evaluation of f(·) is very difficult or computationally demanding. Commonly, a less computationally demanding, perhaps local, approximation to f(·) is available, say f^**_x(·). An algorithm is proposed to generate an MCMC that uses such an approximation to calculate acceptance probabilities at each step of a modified Metropolis–Hastings algorithm. Once a proposal is accepted using the approximation, f(·) is calculated with full precision ensuring convergence to the desired distribution. We give sufficient conditions for the algorithm to converge to f(·) and give both theoretical and practical justifications for its usage. Typical applications are in inverse problems using physical data models where computing time is dominated by complex model simulation. We outline Bayesian inference and computing for inverse problems. A stylized example is given of recovering resistor values in a network from electrical measurements made at the boundary. Although this inverse problem has appeared in studies of underground reservoirs, it has primarily been chosen for pedagogical value because model simulation has precisely the same computational structure as a finite element method solution of the complete electrode model used in conductivity imaging, or “electrical impedance tomography.” This example shows a dramatic decrease in CPU time, compared to a standard Metropolis–Hastings algorithm.     

The Transform Likelihood Ratio Method for Rare Event Simulation with Heavy Tails

We present a novel method, called the transform likelihood ratio (TLR) method, for estimation of rare event probabilities with heavy-tailed distributions. Via a simple transformation (change of variables) technique the TLR method reduces the original rare event probability estimation with heavy tail distributions to an equivalent one with light tail distributions. Once this transformation has been established we estimate the rare event probability via importance sampling, using the classical exponential change of measure or the standard likelihood ratio change of measure. In the latter case the importance sampling distribution is chosen from the same parametric family as the transformed distribution. We estimate the optimal parameter vector of the importance sampling distribution using the cross-entropy method. We prove the polynomial complexity of the TLR method for certain heavy-tailed models and demonstrate numerically its high efficiency for various heavy-tailed models previously thought to be intractable. We also show that the TLR method can be viewed as a universal tool in the sense that not only it provides a unified view for heavy-tailed simulation but also can be efficiently used in simulation with light-tailed distributions. We present extensive simulation results which support the efficiency of the TLR method.     

Statistical Multiplexing of Homogeneous Fractional Brownian Streams

In this paper, the statistical multiplexing of independent fractional Brownian traffic streams with the same Hurst value 0.5<H<1 is studied. The buffer overflow probabilities based on steady-state and transient queue length tail distributions are used respectively as the common performance criterion. Under general conditions, the minimal buffer allocation to the merged traffic is identified in either case so that strictly positive bandwidth savings are realized. Impact of the common H value on multiplexing gains is investigated. The analytical results are applicable in data network engineering problems, where ATM is deployed as the transport network carrying long-range dependent data traffic.     

Simulation and Analysis of a New Mobility Model for Mobile Communication Networks

The traffic generation models, which describe how the clients use the network services, as well as the mobility models, which describe how clients move within the service area covered by the network, are essential tools for QoS analysis in these environments. In this paper we present the simulation of a new mobility model implemented for the analysis of QoS parameters of a mobile network, such as channel occupation time, handoff and new call blocking probabilities.     

A loss network model with overflow for capacity planning of a neonatal unit

The main aim of this paper is to derive a solution to the capacity problem faced by many perinatal networks in the United Kingdom. We propose a queueing model to determine the number of cots at all care units for any desired overflow and rejection probability in a neonatal unit. The model formulation is developed, being motivated by overflow models in telecommunication systems. Exact expressions for the overflow and rejection probabilities are derived. The model is then applied to a neonatal unit of a perinatal network in the UK.     

Optimizing Bernoulli Routing Policies for Balancing Loads on Call Centers and Minimizing Transmission Costs

We address the problem of assigning probabilities at discrete time instants for routing toll-free calls to a given set of call centers to minimize a weighted sum of transmission costs and load variability at the call centers during the next time interval.We model the problem as a tripartite graph and decompose the finding of an optimal probability assignment in the graph into the following problems: (i) estimating the true arrival rates at the nodes for the last time period; (ii) computing routing probabilities assuming that the estimates are correct. We use a simple approach for arrival rate estimation and solve the routing probability assignment by formulating it as a convex quadratic program and using the affine scaling algorithm to obtain an optimal solution.We further address a practical variant of the problem that involves changing routing probabilities associated with k nodes in the graph, where k is a prespecified number, to minimize the objective function. This involves deciding which k nodes to select for changing probabilities and determining the optimal value of the probabilities. We solve this problem using a heuristic that ranks all subsets of k nodes using gradient information around a given probability assignment.The routing model and the heuristic are evaluated for speed of computation of optimal probabilities and load balancing performance using a Monte Carlo simulation. Empirical results for load balancing are presented for a tripartite graph with 99 nodes and 17 call center gates.     

A Generalization of the Hutchinson Measure

The Hutchinson measure is the invariant measure associated with an iterated function system with probabilities. Generalized iterated function systems (GIFS) are generalizations of iterated function systems which are obtained by considering contractions from X × X to X, rather than contractions from a metric space X to itself. Along the lines of this generalization we consider GIFS with probabilities. In this paper we prove the existence of an analogue of Hutchinson measure associated with a GIFS with probabilities and present some of its properties. The work was supported by CNCSIS grant 8A;1067/2006.     

Stability of join-the-shortest-queue networks

This paper investigates stability behavior in a variant of a generalized Jackson queueing network. In our network, some customers use a join-the-shortest-queue policy when entering the network or moving to the next station. Furthermore, we allow interarrival and service times to have general distributions. For networks with two stations we derive necessary and sufficient conditions for positive Harris recurrence of the network process. These conditions involve only the mean values of the network primitives. We also provide counterexamples showing that more information on distributions and tie-breaking probabilities is needed for networks with more than two stations, in order to characterize the stability of such systems. However, if the routing probabilities in the network satisfy a certain homogeneity condition, then we show that the stability behavior can be explicitly determined, again using the mean value parameters of the network. A byproduct of our analysis is a new method for using the fluid model of a queueing network to show non-positive recurrence of a process. In previous work, the fluid model was only used to show either positive Harris recurrence or transience of a network process. J.G. Dai’s research supported in part by National Science Foundation grants DMI-0300599, CMMI-0727400 and CNS-0718701, and by an IBM Faculty Award. J.J. Hasenbein’s research supported in part by National Science Foundation grant DMI-0132038. B. Kim’s research was supported by the MIC (Ministry of Information and Communication), Korea, under the ITRC (Information Technology Research Center) support program supervised by the IITA (Institute of Information Technology Assessment).     

Confidence sets and coverage probabilities based on preliminary estimators in logistic regression models

In this paper we present recentered confidence sets for the parameters of a logistic regression model based on preliminary minimum ?$?$-divergence estimators. Asymptotic coverage probabilities are given as well as a simulation study in order to analyze the coverage probabilities for small and moderate sample sizes.     

Success runs of lengthk in Markov dependent trials

The geometric type and inverse Polýa-Eggenberger type distributions of waiting time for success runs of lengthk in two-state Markov dependent trials are derived by using the probability generating function method and the combinatorial method. The second is related to the minimal sufficient partition of the sample space. The first two moments of the geometric type distribution are obtained. Generalizations to ballot type probabilities of which negative binomial probabilities are special cases are considered. Since the probabilities do not form a proper distribution, a modification is introduced and new distributions of orderk for Markov dependent trials are developed.     

Importance functions for restart simulation of general Jackson networks

RESTART is an 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 regions of the state space where the chance of occurrence of the rare event is higher. These regions are defined by means of a function of the system state called the importance function. Guidelines for obtaining suitable importance functions and formulas for the importance function of two-stage networks were provided in previous papers. In this paper, we obtain effective importance functions for RESTART simulation of Jackson networks where the rare set is defined as the number of customers in a particular (‘target’) node exceeding a predefined threshold. Although some rough approximations and assumptions are used to derive the formulas of the importance functions, they are good enough to estimate accurately very low probabilities for different network topologies within short computational time.     

A risk model with renewal shot-noise Cox process

In this paper we generalise the risk models beyond the ordinary framework of affine processes or Markov processes and study a risk process where the claim arrivals are driven by a Cox process with renewal shot-noise intensity. The upper bounds of the finite-horizon and infinite-horizon ruin probabilities are investigated and an efficient and exact Monte Carlo simulation algorithm for this new process is developed. A more efficient estimation method for the infinite-horizon ruin probability based on importance sampling via a suitable change of probability measure is also provided; illustrative numerical examples are also provided.     

Importance Sampling Simulations of Markovian Reliability Systems Using Cross-Entropy

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.     

System reliability analysis of slope stability using generalized Subset Simulation

Slope failure mechanisms (e.g., why and where slope failure occurs) are usually unknown prior to slope stability analysis. Several possible failure scenarios (e.g., slope sliding along different slip surfaces) can be assumed, leading to a number of scenario failure events of slope stability. How to account rationally for various scenario failure events in slope stability reliability analysis and how to identify key failure events that have significant contributions to slope failure are critical questions in slope engineering. In this study, these questions are resolved by developing an efficient computer-based simulation method for slope system reliability analysis. The proposed approach decomposes a slope system failure event into a series of scenario failure events representing possible failure scenarios and calculates their occurrence probabilities by a single run of an advanced Monte Carlo simulation (MCS) method, called generalized Subset Simulation (GSS). Using GSS results, representative failure events (RFEs) that are considered relatively independent are identified from scenario failure events using probabilistic network evaluation technique. Their relative contributions are assessed quantitatively, based on which key failure events are determined. The proposed approach is illustrated using a soil slope example and a rock slope example. It is shown that the proposed approach provides proper estimates of occurrence probabilities of slope system failure event and scenario failure events by a single GSS run, which avoids repeatedly performing simulations for each failure event. Compared with direct MCS, the proposed approach significantly improves computational efficiency, particularly for failure events with small failure probabilities. Key failure events of slope stability are determined among scenario failure events in a cost-effective manner. Such information is valuable in making slope design decisions and remedial measures.     

Tandem behavior of a telecommunication system with finite buffers and repeated calls

The tandem behavior of a telecommunication system with finite buffers and repeated calls is modeled by the performance of a finite capacityG/M/1 queueing system with general interarrival time distribution, exponentially distributed service time, the first-come-first-served queueing discipline and retrials. In this system a fraction of the units which on arrival at a node of the system find it busy, may retry to be processed, by merging with the incoming arrival units in that node, after a fixed delay time. The performance of this system in steady state is modeled by a queueing network and is approximated by a recursive algorithm based on the isolation method. The approximation outcomes are compared against those from a simulation study. Our numerical results indicate that in steady state the non-renewal superposition arrival process, the non-renewal overflow process, and the non-renewal departure process of the above system can be approximated with compatible renewal processes.     

Better Optimization of Nonlinear Uncertain Systems (BONUS): A New Algorithm for Stochastic Programming Using Reweighting through Kernel Density Estimation

Given a series-parallel queueing network topology with exponential servers of finite capacity, a systematic design methodology is presented that approximately solves the optimal routing and buffer space allocation problems within the network. The multi-objective stochastic nonlinear programming problem in integer variables is described and a two-stage iterative optimization procedure is presented which interconnects the routing and buffer space allocation problems. The algorithmic procedure couples the Expansion method, a decomposition method for computing performance measures in queueing networks with finite capacity, along with Powell's unconstrained optimization procedure which allocates the buffers and a multi-variable search procedure for determining the routing probabilities. The effectiveness and efficiency of the resulting two-stage design methodology is tested and evaluated in a series of experimental designs along with simulations of the network topologies.     

Using asymptotic results to obtain a confidence interval for the population median

Almost all introductory and intermediate level statistics textbooks include the topic of confidence interval for the population mean. Almost all these texts introduce the median as a robust measure of central tendency. Only a few of these books, however, cover inference on the population median and in particular confidence interval for the median. This may be due to the somewhat complex nature of the problem. This paper attempts to popularize a method that is conceptually and computationally simpler than the currently used methods in textbooks and has the promise of being more accessible to elementary/intermediate level statistics students. The method is conceptually simpler, because its development parallels that of obtaining a confidence interval for the mean and it involves concepts that are well-covered in elementary courses. It is computationally simple, because its major computational component is a smoothing method that is widely available in statistical software. For the latter reason, the proposed method is referred to as the Smoothing method. A simple R program is given that produces confidence intervals using the Smoothing method. Utilization of Minitab, SAS, and SPSS for this purpose is also discussed. A simulation study is performed to compare statistical properties of the proposed method to those of the two currently popular methods of Bootstrap and Binomial. Based on this limited simulation studies, it is observed that the Smoothing method is at least as good as, and in some respects is superior to, the Binomial and Bootstrap methods in samples of size as large or larger than 30.     

Link Prediction for Partially Observed Networks

Link prediction is one of the fundamental problems in network analysis. In many applications, notably in genetics, a partially observed network may not contain any negative examples, that is, edges known for certain to be absent, which creates a difficulty for existing supervised learning approaches. We develop a new method that treats the observed network as a sample of the true network with different sampling rates for positive (true edges) and negative (absent edges) examples. We obtain a relative ranking of potential links by their probabilities, using information on network topology as well as node covariates if available. The method relies on the intuitive assumption that if two pairs of nodes are similar, the probabilities of these pairs forming an edge are also similar. Empirically, the method performs well under many settings, including when the observed network is sparse. We apply the method to a protein–protein interaction network and a school friendship network.     

Using a Markov process model of an association football match to determine the optimal timing of substitution and tactical decisions

A football match is modelled as a four-state Markov process. A log-linear model, fed by real data, is used to estimate transition probabilities by means of the maximum likelihood method. This makes it possible to estimate the probability distributions of goals scored and the expected number of league points gained, from any position in a match, for any given set of transition probabilities and hence in principle for any match. This approach is developed in order to estimate the optimal time to change tactics using dynamic programming, either by making a substitution or by some other conscious change of plan. A simple example of this approach is included as an illustration.