bluuebunny/crossref_metadata_2025 huggingface dataset:
Estimating Derivatives Via Poisson's Equation
Authors: Fox Bennett L. , Glasserman Paul
Published: July 2009

Let x(j) be the expected reward accumulated up to hitting an absorbing set in a Markov chain, starting from state j. Suppose the transition probabilities and the one-step reward function depend on a parameter, and denote by y(j) the derivative of x(j) with respect to that parameter. We estimate y(0) starting from the respective Poisson equations that x = [x(0),x(l),…] and y = [y(0),y(l),…] satisfy. Relative to a likelihood-ratio-method (LRM) estimator, our estimator generally has (much) smaller variance; in a certain sense, it is a conditional expectation of that estimator given x. Unlike LRM, however, we have to estimate certain components of x. Our method has broader scope than LRM: we can estimate sensitivity to opening arcs.
Optimal Order for Servers in Series with No Queue Capacity
Authors: Ding Jie , Greenberg Betsy S.
Published: July 2009

In this paper we consider the problem of finding the optimal order for two servers in series when there is no queue capacity. We show that it is better for the faster server to be first. The strength of this conclusion will depend on the strength of the assumption made about the service distribution. We also find the optimal order for some systems where both servers have the same average service time and different service distributions.
Constrained Discounted Markov Decision Chains
Authors: Sennott Linn I.
Published: July 2009

A Markov decision chain with countable state space incurs two types of costs: an operating cost and a holding cost. The objective is to minimize the expected discounted operating cost, subject to a constraint on the expected discounted holding cost. The existence of an optimal randomized simple policy is proved. This is a policy that randomizes between two stationary policies, that differ in at most one state. Several examples from the control of discrete time queueing systems are discussed.
On Some Properties of the Multivariate Aging Classes
Authors: Mukherjee S. P. , Chatterjee A.
Published: July 2009

Two multivariate aging classes described by Johnson and Kotz [7] and Zahedi [11] and known as vector multivariate increasing/decreasing hazard rate (VMIHR/VMDHR) class and decreasing/increasing multivariate mean remaining life of type 2 (DMMRL/IMMRL-2) class, respectively, as well as componentwise NBUE/NWUE class, are considered. The chain of implications between these classes and some characterizing properties of them with regard to the equilibrium distribution corresponding to a multivariate distribution function and concave (convex) transformation of the residual random vector have been established. The “closure under mixture’ property of the first two classes are also studied.
On the Shortest Queue Policy for the Tandem Parallel Queue
Authors: Hordijk Arie , Koole Ger
Published: July 2009

We consider two nodes in tandem. At each node or service center, there are two exponential servers present with the same service rate μ and each with its own queue. Customers arrive at the first node according to a Poisson process with arrival rate λ. At their arrival, they have to be assigned to one of the servers, so they are routed to one of the queues at node 1. Customers leaving center 1 enter node 2 and are routed to one of the queues at node 2. In this paper, we consider the case with full information and the case with partial information.
A Note on External Uniformization for Finite Markov Chains in Continuous Time
Authors: Kijima Masaaki
Published: July 2009

An external uniformization technique was developed by Ross [4] to obtain approximations of transition probabilities of finite Markov chains in continuous time. Yoon and Shanthikumar [7] then reported through extensive numerical experiments that this technique performs quite well compared to other existing methods. In this paper, we show that external uniformization results from the strong law of large numbers whose underlying distributions are exponential. Based on this observation, some remarks regarding properties of the approximation are given.
Approximating the Student's t-Tail Probability and Its Inverse
Authors: Lin Jinn-Tyan
Published: July 2009

This paper proposes a logistic approximation to the upper tail of the t distribution and its inverse that is more convenient and more accurate than those of Shah and Allen [3], and Koehler [1] and Lin [2], when measured in terms of the number of keystrokes and absolute relative errors, respectively.
Generating Uniformly Distributed Random Numbers without Floating Point Operations
Authors: Kolonko M.
Published: July 2009

We present a fast algorithm for random numbers distributed uniformly on (0,1). In contrast to most other generators, it uses no floating point operations. Instead, the internal bit representation of the numbers is generated directly from a random bit source. It can easily be implemented in high-level languages like Modula-2 and shows good empirical behavior.
Product Form Solutions for Multiserver Centers with Hierarchical Concurrency Constraints
Authors: Krzesinski A. E. , Schassberger R.
Published: July 2009

We establish the quasireversibility of a certain exponential multiserver queue. The queuing discipline imposes restrictions on the numbers of customers of different classes and subclasses that can be served simultaneously. Customer loss is also allowed. Due to its quasireversibility the queue can be used as a node in a product form network. Our work generalizes work of Le Boudec, Krzesinski, and Crosby.
Loss Probability of a Burst Arrival Finite Queue with Synchronized Service
Authors: Miyazawa Masakiyo
Published: July 2009

We are concerned with a burst arrival single-server queue, where arrivals of cells in a burst are synchronized with a constant service time. The main concern is with the loss probability of cells for the queue with a finite buffer. We analyze an embedded Markov chain at departure instants of cells and get a kind of lumpability for its state space. Based on these results, this paper proposes a computation algorithm for its stationary distribution and the loss probability. Closed formulas are obtained for the first two moments of the numbers of cells and active bursts when the buffer size is infinite.
Gated, Exhaustive, Parallel Service
Authors: Browne Sid , CoffmanJR. E. G. , Gilbert E. N. , Wright Paul E.
Published: July 2009

We analyze gated, exhaustive service of an infinite-server system with vacations. Customers enter a queue in a Poisson stream. The servers, working in parallel, serve customers in stages. A stage begins with all customers transferred from the queue to the servers (the gate opens). The servers then begin serving these customers, all simultaneously. The stage ends when their services are completed. Service is exhaustive because the servers must again examine the queue to see if any new customers arrived during the last stage. If there are any, a new stage begins. If there are none, the servers move on to other work. The time spent away from the queue is called vacation time. The queue may represent a node or station in a data transmission network and the servers may be communication channels.

We analyze the equilibrium behavior of the number of requests served during a stage for general service and vacation time distributions. This analysis leads to the solution of a Fredholm integral equation of the second kind. We find conditions under which the system is stable and compute bounds on performance metrics of interest. Approximate techniques are introduced and tested. Finally, an extension to polling systems is studied.
On the Recurrent Solution of Renewal-Type Integral Equations
Authors: Banjević Dragan
Published: July 2009

In 1987, Sheldon M. Ross [4] gave an interesting recurrent relation method for approximations of important functions in renewal theory. Using his idea and Feller's technique for inverting Laplace transforms, we obtain a general method for recurrent approximations to the solutions of renewal-type integral equations.
Heuristics for Finite-Buffer Queues
Authors: Tijms Henk
Published: July 2009

The approximation of the loss probability in finite-buffer queues is a practical problem of considerable interest. A new heuristic is given. This heuristic is based on the equilibrium distribution of the corresponding infinite-buffer queue. Numerical results show an excellent performance of the heuristic.
The Waiting-Time Distribution for the GI/G/1 Queue under the D-Policy
Authors: Li Jingwen , Niu Shun-Chen
Published: July 2009

We study a generalization of the GI/G/l queue in which the server is turned off at the end of each busy period and is reactivated only when the sum of the service times of all waiting customers exceeds a given threshold of size D. Using the concept of a “randomly selected” arriving customer, we obtain as our main result a relation that expresses the waiting-time distribution of customers in this model in terms of characteristics associated with a corresponding standard GI/G/1 queue, obtained by setting D = 0. If either the arrival process is Poisson or the service times are exponentially distributed, then this representation of the waiting-time distribution can be specialized to yield explicit, transform-free formulas; we also derive, in both of these cases, the expected customer waiting times. Our results are potentially useful, for example, for studying optimization models in which the threshold D can be controlled.
Evaluating Best-Case and Worst-Case Coefficients of Variation when Bounds Are Available
Authors: Fishman George S. , Rubin David S.
Published: July 2009

This paper describes a procedure for computing tightest possible best-case and worst-case bounds on the coefficient of variation of a discrete, bounded random variable when lower and upper bounds are available for its unknown probability mass function. An example from the application of the Monte Carlo method to the estimation of network reliability illustrates the procedure and, in particular, reveals considerable tightening in the worst-case bound when compared to the trivial worst-case bound based exclusively on range.
The Application of Restricted Counter Schemes to Three Models of Linear Search
Authors: Hofri Micha , Shachnai Hadas
Published: July 2009

The mechanism of the Counter Scheme (CS) has been shown to be an effective statistical approach for the reorganization of linear lists, where the records in the list are referenced independently with a time homogeneous multinomial distribution. In this paper we show that derivative schemes can be used effectively in other contexts as well. Specifically, we consider (a) linear lists that are doubly linked, so that they may be accessed at both ends, (b) multilists, which result from dissecting a linear list into several pieces that are accessed independently and reside in WORM (write-once-read-many) store, and (c) reorganizing a disk, by copying its contents to another disk, so as to minimize the expected seek time required to access a record.
A Pocket-Calculator Approximation to the Inverse Normal Tail Probability Function
Authors: Lin Jinn-Tyan
Published: July 2009

Data analytic techniques are used in the construction of a simple approximation to the inverse normal tail probability function. The approximation is more accurate and more convenient than Hamaker's [2] over a wide range, when measured in terms of the number of keystrokes and absolute relative error.
An Error-Bound Theorem for Approximate Markov Chains
Authors: Dijk Nico M. Van
Published: July 2009

Recently an error-bound theorem was reported to conclude analytic error bounds for approximate Markov chains. The theorem required a uniform bound for marginal expectations of the approximate model. This note will relax this bound to steady state rather than marginal expectations as of practical interest

(i) to simplify verification and/or

(ii) to obtain a more accurate error bound.

A communication model is studied in detail to support the results.
The Equilibrium Distribution for a Clocked Buffered Switch
Authors: Jaffe Steven
Published: July 2009

A 2-by-2 buffered switch is the basic element of certain parallel data-processing networks. For a switch fed by two independent Bernoulli input streams, we find the joint distribution of the number of messages waiting in the two buffers at equilibrium, in the form of a bivariate generating function. The derivation uses complex-variable techniques developed by Kingman and by Flatto and McKean for the “shortest queue problem.” A number of asymptotic results are given, the principal one being the variance of the total number of waiting messages in the heavy-traffic limit.
An Evolution Model for Monte Carlo Estimation of Equilibrium Network Renewal Parameters
Authors: Elperin T. , Gertsbakh I. , Lomonosov M.
Published: July 2009

This paper presents Monte Carlo techniques for evaluating equilibrium availability and mean up and down periods of a renewable network for a wide class of network operational criteria. The suggested method is based on a graph evolution model that overcomes the main difficulty–hitting low-probability “border” states of the criterion. Theoretical efficiency of the method is briefly discussed and numerical results are presented.
Output and Delay Processes in a Slotted ALOHA Multichannel Packet Radio Network with Capture
Authors: Yue Wuyi , Matsumoto Yutaka
Published: July 2009

In this paper, we exactly analyze the performance of the slotted ALOHA access scheme with capture in a multichannel packet radio communication environment for the IFT (immediate-first-transmission) protocol and the DFT (delayed-first-transmission) protocol. We derive four moment generating functions for the following performance measures: (1) the number of packet deparures in each group of capture level in any slot, (2) the interval time between wo consecutive slot ends with the same number of departures, (3) the interval time between two consecutive slot ends with at least one departure and the number of departures in each group in that slot, and (4) the packet delay for each group. We calculate the averages and higher moments of these performance measures by differentiating the moment generating functions and numerically compare the systems with and without ower capture. The system consists of a finite population of Nstations, both fixed and mobile, that are divided into L different capture groups and access a set of parallel M channels to transmit their packets. Capture effect means that a packet transmitted by a station with a highest capture level can be received accurately, even when other packets in lower capture levels are simultaneously transmitted on the same channel and in the same slot. Numerical comparison to a multichannel system without capture is made. Capture effects on channel utilization, mean packet delay, and coefficients of variation of packet delay and interdeparture time are examined.
On the Assignment of Customers to Parallel Queues
Authors: Hordijk Arie , Koole Ger
Published: July 2009

This paper considers routing to parallel queues in which each queue has its own single server and service times are exponential with nonidentical parameters. We give conditions on the cost function such that the optimal policy assigns customers to a faster queue when that server has a shorter queue. The queues may have finite buffers, and the arrival process can be controlled and can depend on the state and routing policy. Hence our results on the structure of the optimal policy are also true when the assigning control is in the “last” node of a network of service centers. Using dynamic programming we show that our optimality results are true in distribution.
Some Large Deviations Results in Markov Fluid Models
Authors: Ridder Ad , Walrand Jean
Published: July 2009

Markov modulated fluid models are studied in this paper. When the input of 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.
Hitting-Time Densities of a Two-Dimensional Markov Process
Authors: Hesse C. H.
Published: July 2009

This paper deals with the two-dimensional stochastic process (X(t), V(t)) where dX(t) = V(t)dt, V(t) = W(t) + ν for some constant ν and W(t) is a one-dimensional Wiener process with zero mean and variance parameter σ2= 1. We are interested in the first-passage time of (X(t), V(t)) to the plane X = 0 for a process starting from (X(0) = −x, V(0) = ν) with x > 0. The partial differential equation for the Laplace transform of the first-passage time density is transformed into a Schrödinger-type equation and, using methods of global analysis, such as the method of dominant balance, an approximation to the first-passage density is obtained. In a series of simulations, the quality of this approximation is checked. Over a wide range of x and ν it is found to perform well, globally in t. Some applications are mentioned.
The M/G/1 Retrial Queue With Retrial Rate Control Policy
Authors: Choi Bong Dae , Rhee Kyung Hyune , Park Kwang Kyu
Published: July 2009

We consider a single-server retrial queueing system where retrial time is inversely proportional to the number of customers in the system. A necessary and sufficient condition for the stability of the system is found. We obtain the Laplace transform of virtual waiting time and busy period. The transient distribution of the number of customers in the system is also obtained.
The Average Cost Optimality Equation and Critical Number Policies
Authors: Sennott Linn I.
Published: July 2009

We consider a Markov decision chain with countable state space, finite action sets, and nonnegative costs. Conditions for the average cost optimality inequality to be an equality are derived. This extends work of Cavazos-Cadena [8]. It is shown that an optimal stationary policy must satisfy the optimality equation at all positive recurrent states. Structural results on the chain induced by an optimal stationary policy are derived. The results are employed in two examples to prove that any optimal stationary policy must be of critical number form.
Constrained Average Cost Markov Decision Chains
Authors: Sennott Linn I.
Published: July 2009

A Markov decision chain with denumerable state space incurs two types of costs — for example, an operating cost and a holding cost. The objective is to minimize the expected average operating cost, subject to a constraint on the expected average holding cost. We prove the existence of an optimal constrained randomized stationary policy, for which the two stationary policies differ on at most one state. The examples treated are a packet communication system with reject option and a single-server queue with service rate control.
CROSSREG — A Technique for First Passage and Wave Density Analysis
Authors: Rychlik Igor , Lindgren Georg
Published: July 2009

The density of the first passage time in a nonstationary Gaussian process with random mean function can be approximated with arbitrary accuracy from a regression-type expansion. CROSSREG is a package of FORTRAN subroutines that perform intelligent transformations and numerical integrations to produce high-accuracy approximations with a minimum of computer time. The basic routines, collected in the unit ONEREG, give the density of the crossing time of a general bound. An additional set of routines make up the unit TWOREG, which also gives the bivariate density of the crossing time and the value of an accompanying process at the time of the crossing. These routines can be used to find the wavelength and amplitude density in any stationary Gaussian process. ONEREG and TWOREG are special cases of a routine MREG, which is the main routine in CROSSREG.
Continuous Polling on Graphs
Authors: Coffman E. G. , Stolyar Aleksandr
Published: July 2009

Past research on polling systems has been quite restricted in the form of the paths followed by the server. This paper formulates a general, continuous model of such paths that includes closed walks on graphs. Customers arrive by a Poisson process and have general service times. The distribution of arrivals over the path is governed by an absolutely continuous, but otherwise arbitrary, distribution. The main results include a characterization of the stationary state distribution and explicit formulas for expected waiting times. The formulas reveal an interesting decomposition of the system into two components: a fluid limit and an M/G/1 queue.
Stochastic Sequencing on One Machine with Earliness and Tardiness Penalties
Authors: Forst Frank G.
Published: July 2009

In this paper the objective is to find a job sequence that minimizes, stochastically or in expectation, the sum of the total weighted job earliness and the total weighted job tardiness on one machine, when the job processing times are independent and identically distributed random variables. We first derive results for the case in which the jobs share a common, random due date. We then obtain results when the job due dates are distinct, independent random variables.
G-Networks with Signals and Batch Removal
Authors: Gelenbe Erol
Published: July 2009

We consider queueing networks containing customers and signals that were recently introduced in Gelenbe [4]. Both customers and signals can be exogenous or can be obtained by a Markovian transition of a customer after service. A signal entering a queue forces a customer to move on to another queue according to a Markovian routing rule or to leave the network in batch mode. This synchronized or triggered motion is useful in representing the effect of tokens in Petri-nets, for systems in which customers and work can be instantaneously moved from one queue to the other on the arrival of a signal as well as for other network behaviors that are encountered in parallel computer system modelling. We show that this network has product form stationary solution and establish the non-linear customer flow equations that govern it. Network stability is discussed in this new context.
Regularity of Stochastic Processes: A Theory Based on Directional Convexity
Authors: Meester Ludolf E. , Shanthikumar J. George
Published: July 2009

We define a notion of regularity ordering among stochastic processes called directionally convex (dcx) ordering and give examples of doubly stochastic Poisson and Markov renewal processes where such ordering is prevalent. Further-more, we show that the class of segmented processes introduced by Chang, Chao, and Pinedo [3] provides a rich set of stochastic processes where the dcx ordering can be commonly encountered. When the input processes to a large class of queueing systems (single stage as well as networks) are dcx ordered, so are the processes associated with these queueing systems. For example, if the input processes to two tandem /M/c1→/M/c2→…→/M/cm queueing systems are dcx ordered, so are the numbers of customers in the systems. The concept of directionally convex functions (Shaked and Shanthikumar [15]) and the notion of multivariate stochastic convexity (Chang, Chao, Pinedo, and Shanthikumar [4]) are employed in our analysis.
A Note on Equivalence Classes of Directed Acyclic Independence Graphs
Authors: Madigan David
Published: July 2009

Directed acyclic independence graphs (DAIGs) play an important role in recent developments in probabilistic expert systems and influence diagrams (Chyu [1]). The purpose of this note is to show that DAIGs can usefully be grouped into equivalence classes where the members of a single class share identical Markov properties. These equivalence classes can be identified via a simple graphical criterion. This result is particularly relevant to model selection procedures for DAIGs (see, e.g., Cooper and Herskovits [2] and Madigan and Raftery [4]) because it reduces the problem of searching among possible orientations of a given graph to that of searching among the equivalence classes.
A Note on the Residual Entropy Function
Authors: Muliere Pietro , Parmigiani Giovanni , Polson Nicholas G.
Published: July 2009

Interest in the informational content of truncation motivates the study of the residual entropy function, that is, the entropy of a right truncated random variable as a function of the truncation point. In this note we show that, under mild regularity conditions, the residual entropy function characterizes the probability distribution. We also derive relationships among residual entropy, monotonicity of the failure rate, and stochastic dominance. Information theoretic measures of distances between distributions are also revisited from a similar perspective. In particular, we study the residual divergence between two positive random variables and investigate some of its monotonicity properties. The results are relevant to information theory, reliability theory, search problems, and experimental design.
A Technique for Computing Sojourn Times in Large Networks of Interacting Queues
Authors: Anantharam V. , Benchekroun M.
Published: July 2009

Consider a large number of interacting queues with symmetric interactions. In the asymptotic limit, the interactions between any fixed finite subcollection become negligible, and the overall effect of interactions can be replaced by an empirical rate. The evolution of each queue is given by a time inhomogeneous Markov process. This may be considered a technique for writing dynamic Erlang fixed-point equations. We explore this as a tool to approximate sojourn time distributions.
A Versatile Packet Arrival Process and Its Second Order Properties
Authors: Ott Teunis J.
Published: July 2009

In this paper we describe a class of discrete time processes that can be used to model packet arrival streams in packetized communication. Mathematically, (K(t)) can be seen as a discrete time self-exciting point process, as a multitype branching process, or as an epidemic with immigration of infected people. The purpose of this paper is to show that this class of models simultaneously is quite useful and analytically more tractable than is obvious at first glance. It is shown that certain probabilities can reliably be computed using generating function methods, and expressions are given for the second order properties and for the asymptotic index of dispersion.
A Queuing System with a Branching Process Arrival Stream, the Case of Short-Range Dependence
Authors: Ott Teunis J.
Published: July 2009

In a previous paper, we defined and studied a branching process input stream that can be used to model the organization of packets (in packetized communication) in messages. In this paper we derive a central result on the effect that such streams have on a packet switch (or queue) and further study one particular model (the case of so-called short-range dependence), where the distribution of the number of packets in a buffer can explicitly be found (albeit in the form of a transform). The solution to this particular model suggests an approximation for the average buffer content in the general case.
First Passage Time Distribution of a Two-Dimensional Wiener Process with Drift
Authors: Dominé Marco , Pieper Volkmar
Published: July 2009

The two-dimensional correlated Wiener process (or Brownian motion) with drift is considered. The Fokker-Planck (or Kolmogorov forward) equation for the Wiener process(X1(t), X2(t))is solved under absorbing boundary conditions on the linesx1=h1andx2=h2and a fixed starting point (x0,1,x0,2). The first passage (or first exit) time when the process leaves the domainG= ( −∞,h1) × ( −∞,h2) is derived.
Tests of Randomness Based on theK-NNDistances for Data from a Bounded Region
Authors: Rotondi Renata
Published: July 2009

This paper proposes some new statistics based onk-NNdistances for assessing the uniformity of a set of points belonging to ad-dimensional bounded region. Size and power of the tests have been estimated and compared to those of the modified Hopkins' statistic.
Bounds for Stopping Times with Application to the Approximation of Distribution Functions
Authors: Richter Rhonda , Shanthikumar J. George
Published: July 2009

We consider stopping times associated with sequences of non-negative random variables and Poisson processes. With sufficient conditions on the dependence property between the sequences of non-negative random variables (or the Poisson processes) and the stopping times, we develop easily computable stochastic bounds for the stopping times. We use these bounds to develop approximations within the class of generalized phase-type distribution functions for arbitrary distribution functions. The computational tractability of generalized phase-type distribution functions facilitate the computational analysis of complex stochastic systems using these approximate distribution functions. Applications of these approximations to renewal processes are illustrated.
Optimal Routing and Scheduling of Customers with Deadlines
Authors: Sparaggis Panayotis D. , Towsley Don
Published: July 2009

Consider the problem in which impatient customers have to be routed to or scheduled from a set of parallel homogeneous service stations with finite buffer capacities. When the service times and the deadlines of customers are exponentially distributed, we identify the control policies that stochastically minimize the total number of losses by any time t. We study systems with deadlines to the beginning or to the end of service. The results regarding the individual types of losses, i.e., losses due to deadline misses and losses due to buffer overflow, vary across different systems. In all cases we state explicitly the properties and the limitations of the optimal control policies.
Comparing Criticality of Nodes via Minimal Cut (Path) Sets for Coherent Systems
Authors: Meng Fan Chin
Published: July 2009

In 1989, Boland, Proschan, and Tong [2] introduced the notion of criticality ranking among nodes and developed a procedure for obtaining an optimal assignment of components in coherent systems. In this article we obtain characterizations of the criticality ranking in terms of minimal cut (path) sets for coherent systems. Furthermore, utilizing the characterizations, it is shown that the criticality ranking defined by Boland et al. [2] is consistent with the cut-importance ranking introduced by Butler in 1979 [4]. A relationship between the criticality ranking and the well-known and widely used Birnbaum reliability importance measure is also derived.
The Role of a Group of Modules in the Failure of Systems
Authors: Abouammoh A. M. , El-Neweihi Emad , Sethuraman Jayaram
Published: July 2009

Consider a system consisting of a number of modules. The probability that a particular module is among the ones that have already failed by the time of system failure can be used as a measure of the importance of that module. In El-Neweihi and Sethuraman [6], this probability was called the role of a module in the failure of a system and its properties were developed. In this article we propose the number of failed modules from among a particular subgroup of modules as the basis for measuring the role of that subgroup of modules. We study some monotonicity properties of the distribution of that random variable, in some second order r-out-of-k systems. We illustrate the possible extensions of these results to multistate systems. Yet another measure of the role of a particular subgroup of modules can be based on the number of failed components from this subgroup by the time of system failure. We derive some monotonicity properties of the expected value of the number of such failed components.
New Approximations for the Percentage Points of the Chi-Square Distribution
Authors: Lin Jinn-Tyan
Published: July 2009

Techniques of exploratory data analysis are used in the construction of simple approximations for the percentage points of the chi-square distribution. The approximations are direct functions of the degrees of freedom and the tail probability. They are more accurate than Hoaglin's approximations.
Conservation Relations for Fully Shared ATM Buffers
Authors: Kesidis G. , Walrand J.
Published: July 2009

In asynchronous transfer mode (ATM), networks, buffering is required to reduce cell loss and increase bandwidth utilization by the bursty traffic. Several types of traffic with different performance requirements on delay and loss will share buffer resources. We focus on the fully shared buffer with push-out and a randomized service priority rule. Some conservation relations are obtained which can be used to tune the parameters of the buffering and service disciplines.
The Stochastic Optimality of SEPT in Parallel Machine Scheduling
Authors: Chang Cheng-Shang , Hordijk Arie , Righter Rhonda , Weiss Gideon
Published: July 2009

We consider preemptive scheduling on parallel machines where processing times of jobs are i.i.d. but jobs may already have received distinct amounts of service. We show that when processing times are increasing in likelihood ratio, SEPT (shortest expected [remaining] processing time first) stochastically minimizes any increasing and Schur-concave function of the job completion times. The same result holds when processing times are exponential with possibly different means.
A Reversible Model for Consecutive-2-out-of-n: F Systems with Node and Link Failures
Authors: Chen Robert W. , Hwang F. K. , Li Wen-Ching Winnie
Published: July 2009

A consecutive-k-out-of-n: F system is represented by a digraph in which the nodes and certain of the links may fail. System reliability is studied.
A Note on Queueing Networks with Signals and Random Triggering Times
Authors: Chao Xiuli
Published: July 2009

There is a growing interest in networks of queues with customers and signals. The signals in these models carry commands to the service nodes and trigger customers to move instantaneously within the network. In this note we consider networks of queues with signals and random triggering times; that is, when a signal arrives at a node, it takes a random amount of time to trigger a customer to move with distribution depending on the source of the signal. By appropriately choosing the triggering times, we can obtain network models such that a signal changes a customer's service time distribution – for example, the signal increases or decreases the service time of a customer. We show that the stationary distribution of this model has a product form solution.
Clicks in Zero-Crossing-Detecting FM Receivers: Theory and Experiments
Authors: Lindgren Georg , Eriksson Weine
Published: July 2009

Frequency measurements by means of zero-crossing-counting device can be disturbed by noise in many different ways, such as fluctuating zero level or extra zero crossings. This paper presents a mathematical theory for analysis of the effect of noise on a zero-crossing counter. Comparisons are made with experiments made on the production of clicks in a zero-crossing-detecting FM receiver.
Comparing Markov Chains Simulated in Parallel
Authors: Glasserman Paul , Vakili Pirooz
Published: July 2009

We investigate the dependence induced among multiple Markov chains when they are simulated in parallel using a shared Poisson stream of potential event occurrences. One expects this dependence to facilitate comparisons among systems; our results support this intuition. We give conditions on the transition structure of the individual chains implying that the coupled process is an associated Markov chain. Association implies that variance is reduced in comparing increasing functions of the chains, relative to independent simulations, through a routine argument. We also give an apparently new application of association to the problem of selecting the better of two systems from limited data. Under conditions, the probability of incorrect selection is asymptotically smaller when the systems compared are associated than when they are independent. This suggests a further advantage to linking multiple systems through parallel simulation.
Polling in a Closed Network
Authors: Altman Eltan , Yechiali Uri
Published: July 2009

We consider a closed queueing network with a fixed number of customers, where a single server moves cyclically between N stations, rending service in each station according to some given discipline (Gated, Exhaustive, or the Globally Gated regime). When service of a customer (message) ends in station j, it is routed to station k with probability Pjk. We derive explicit expressions for the probability generating function and the moments of the number of customers at the various queues at polling instants and calculate the mean cycle duration and throughput for each service discipline. We then obtain the first moments of the queues' length at an arbitrary point in time. A few examples are given to illustrate the analysis. Finally, we address the problem of optimal dynamic control of the order of stations to be served.
Some Properties of the Poisson Distribution with an Application to Reliability Testing
Authors: Rajgopal Jayant , Mazumdar Mainak , Savits Thomas H.
Published: July 2009

Construction of a certain class of component tests for verification of series system reliability requires the use of some properties of the Poisson distribution that are not commonly known or used. This paper states and proves these results.
(s, S) Inventory Systems with Random Lead Times: Harris Recurrence and Its Implications in Sensitivity Analysis
Authors: Fu Michael C. , Hu Jian-Qiang
Published: July 2009

Most of the previous work on (s, S) inventory systems assumes that lead times for orders are such that orders never cross in time; i.e., the arrival of orders follows the same sequence as the placement of the orders. In this paper we consider more general mechanisms for random lead times. Because the introduction of a general random lead time mechanism makes the system essentially intractable for most performance measures of interest, simulation is a. natural candidate for estimating performance and/or optimizing the system. Two important issues in simulation are the stability and ergodicity of the system. Therefore, we first study some theoretical implications of the mechanism by providing conditions for which the system is stable and Harris ergodic, with the accompanying wide-sense regenerative properties. We then consider the problem of gradient estimation during simulation. Using the technique of perturbation analysis, we derive sample path-based gradient estimates for the finite-horizon average cost per period with respect to the parameters s and S and give a sample path proof of unbiasedness. We then show how stability and ergodicity can be used to simplify the estimators in the limiting infinite-horizon case and to establish strong consistency of the resulting estimators.
On the Regularity of Skip-Free Markov Chains
Authors: Kennedy D. P.
Published: July 2009

Necessary and sufficient conditions for the regularity and recurrence of right-skip-free Markov chains are established. These generalize classical results for the case of birth-and-death processes. Expressions for the general right eigenvectors of such chains are also given.
Analysis of a Customer Assignment Model with No State Information
Authors: Hordijk A. , Koole G. M. , Loeve J. A.
Published: July 2009

In this paper we analyze a queueing network consisting of parallel queues and arriving customers that have to be assigned to one of the queues. The assignment rule may not depend on the numbers of customers in the queues. Our goal is to find a policy that is optimal with respect to the long-run average cost. We will consider two cases: holding costs and waiting times. A recently developed algorithm for Markov decision chains with partial state information is applied. It turns out that the periodic policies found by this algorithm are close, if not equal, to the optimal ones.
When Is a System Better Than the Average of Its Components?
Authors: Egeland Thore
Published: July 2009

This paper provides simple conditions for when the reliability of a system of independent components is better (worse) than the average reliability of the components. This result is useful in cases where little is known of the component reliabilities or the structure.
Optimality of Randomized Trunk Reservation
Authors: Feinberg Eugene A. , Reiman Martin I.
Published: July 2009

We consider a controlled queueing system that is a generalization of the M/M/c/W queue. There are m types of customers that arrive according to independent Poisson processes. Service times are exponential and independent and do not depend on the customer type. There is room in the system for a total of N customers; if there are N customers in the system, new arrivals are lost. Type j customers are more profitable than type (j + 1 ) customers, j = 2,…, m —, and type 1 customers are at least as profitable as type 2 customers. The allowed control is to accept or reject customers at arrival. No preemption of customers in service is allowed. The goal is to maximize the average reward per unit of time subject to a constraint that the blocking probability of type 1 customers is no greater than a given level.

For an M/M/c/c system without a constraint, Miller [12] proved that an optimal policy has a simple threshold structure. We show that, for the constrained problem described above, an optimal policy has a similar structure, but one of the thresholds might have to be randomized. We also derive an algorithm that constructs an optimal policy and describe other forms of optimal policies.
Optimal Customer Return Rate for an M/M/1 Queueing System with Retrials
Authors: Elcan Amie
Published: July 2009

The zero capacity M/M/1 queue with returning customers is examined. Performance measures are calculated and an imposed optimal return rate is determined for customers who return until served. The optimal rate is then calculated for an arbitrary customer as a function of the return rate of the other customers, and limiting cases are analyzed. The other customers may then adjust their return rate each time the arbitrary customer adjusts his/hers until a fixed point solution is obtained. A comparison between systems is made.
Simulated Annealing and Adaptive Search in Global Optimization
Authors: Romeijn H. Edwin , Smith Robert L.
Published: July 2009

Simulated annealing is a class of sequential search techniques for solving continuous global optimization problems. In this paper we attempt to help explain the success of simulated annealing for this class of problems by studying an idealized version of this algorithm, which we call adaptive search. The prototypical adaptive search algorithm generates a sequence of improving points drawn conditionally from samples from a corresponding sequence of probability distributions. Under the condition that the sequence of distributions stochastically dominate in objective function value the uniform distribution, we show that the expected number of improving points required to achieve the global optimum within a prespecified error grows at most linearly in the dimension of the problem for a large class of global optimization problems. Moreover, we derive a cooling schedule for simulated annealing, which follows in a natural way from the definition of the adaptive search algorithm.
An Exponential Inequality for U-Statistics with Applications to Testing
Authors: Bickel Peter J. , Ritov Ya'acov
Published: July 2009

We present a new exponential inequality for degenerate U-statistics. The bound on the tail probability is quadratic for small to medium values of the deviation and linear for larger values. We apply this bound to a family of test statistics and provide the key step in an optimality result for adaptive tests [1].
Minimax vs. Bayes Prediction
Authors: Blackwell D.
Published: July 2009

Let x = (x1, x2, …) be an infinite sequence of 0's and 1's, initially unknown to you. On day n = 1,2,…, you observe hn = (x1, …, xn–1), the first n – 1 terms of the sequence, and must predict xn. What is a good prediction method, and how well can you do?
A Martingale Approach to Regenerative Simulation
Authors: Glynn Peter W. , Iglehart Donald L.
Published: July 2009

The standard regenerative method for estimating steady-state parameters is extended to permit cycles that begin and end in different states. This result is established using the Dynkin martingale and a related solution to Poisson's equation. We compare the variance constant that appears in the associated central limit theorem with that arising from cycles that begin and end in the same state. The standard regenerative method has a smaller variance constant than does the alternative.
Estimating the Number of Aberrant Laboratories
Authors: Olkin Ingram , Guttman Irwin , Philips Robert
Published: July 2009

It has long been observed that independent laboratories differ in reporting the results of repeated experiments. The problem is to detect those laboratories that might be considered aberrant. Previous analyses have been based on an analysis of variance framework or on subset selection for the detection of aberrant laboratories. The present procedure is also based on an ANOVA model but uses a Bayesian estimate of the number of aberrant laboratories. Subsequent to the determination of the aberrant laboratories, a linear model is used to separate sampling and laboratory effects.
Optimal Search for a Moving Target
Authors: MacPhee I. M. , Jordan B. P.
Published: July 2009

Consider the problem of searching for a leprechaun that moves randomly between two sites. The movement is modelled with a two-state Markov chain. One of the sites is searched at each time t = 1,2,…, until the leprechaun is found. Associated with each search of site i is an overlook probability αi and a cost Ci Our aim is to determine the policy that will find the leprechaun with the minimal average cost. Let p denote the probability that the leprechaun is at site 1. Ross conjectured that an optimal policy can be defined in terms of a threshold probability P* such that site 1 is searched if and only if p ≥ P*. We show this conjecture to be correct (i) when α1 = α2 and C1 = C2, (ii) for general Ci when the overlook probabilities α, are small, and (iii) for general αi and Ci for a large range of transition laws for the movement. We also derive some properties of the optimal policy for the problem on n sites in the no-overlook case and for the case where each site has the same αi, and Ci.
A Convexity Property of a Markov-Modulated Queueing Loss System
Authors: Du Charles , Pinedo Michael
Published: July 2009

In this note we consider a single-server queueing loss system with zero buffer. The arrival process is a nonstationary Markov-modulated Poisson process. The arrival process in state i is Poisson with rate λi. The process remains in state i for a time that is exponentially distributed with rate Cαi, with c being a control or speed parameter. The service rate in state i is exponentially distributed with rate μi. The process moves from state i to state j with transition probability qij. We are interested in the loss probability as a function of c. In this note we show that, under certain conditions, the loss probability decreases when the c increases. As such, this result generalizes a result obtained earlier by Fond and Ross.
The Increasing Failure Rate Property of Consecutive-k:-out-of-n Systems
Authors: Cui Lirong , Hawkes Alan G. , Jalali Assad
Published: July 2009

We prove Hwang and Yao's conjecture about failure of consecutive-k-out-of-n systems whose components have independent and identically distributed increasing failure rate (IFR) lifetimes, namely, that for each k ≥ 2 there exists nk such that for every n ≥ nk the system does not preserve IFR. For the cases k = 4 and 5, we present complete solutions. We present further conjectures.