bluuebunny/crossref_metadata_2025 huggingface dataset:
Simulating Average Delay–Variance Reduction by Conditioning
Authors: Ross Sheldon M.
Published: July 2009

An improved simulation estimator of the expected total delay of the first n customers in the systems GI/M/k and GI/G/I is obtained by replacing the (raw data) delay of customer i by its expected delay given the state of the system upon its arrival. It is improved in the sense that the sum of the first n such values has the same mean and smaller variance than the usual (raw) estimator. The only constraint on the arrival process is that it be independent of the process of service times.
An Improvement Over the Information Lower Bound in Binomial Group Testing
Authors: Yao Y.C.
Published: July 2009

The group-testing problem for a binomial set of items is considered. It is desired to classify all items as good or defective with a minimum expected number of group tests. An improvement over the information lower bound, via a weak concavity property, is made for the minimum expected number of group tests.
Product Forms for Stochastic Interference Systems
Authors: Dijk N.M. Van , Veltkamp J.P.
Published: July 2009

Systems are studied that consist of interfering components which are alternatively active (busy) and passive (idle) for random periods. Such systems naturally arise from the performance evaluation of computer models. A concrete invariance condition is imposed on the interferences allowed. Under this condition, the steady-state vector of active components is shown to be of product form as well as to be robust to distributional forms of active and passive periods. The proof is simple and self-contained. A number of concrete and generic examples is provided. These include resource sharing mechanisms, hierarchical circuit switchings, parallel processing, priorities, and breakdowns.
Conditions Under Which a Markov Chain Converges to its Steady State in Finite Time
Authors: Glynn Peter W. , Iglehart Donald L.
Published: July 2009

Analysis of the initial transient problem of Monte Carlo steady-state simulation motivates the following question for Markov chains: when does there exist a deterministic Tsuch that P{X(T) = y|(0) = x} = ®(y), where ρ is the stationary distribution of X? We show that this can essentially never happen for a continuous-time Markov chain; in discrete time, such processes are i.i.d. provided the transition matrix is diagonalizable.
Spectral Theory for Skip-Free Markov Chains
Authors: Abate Joseph , Whitt Ward
Published: July 2009

The distribution of upward first passage times in skip-free Markov chains can be expressed solely in terms of the eigenvalues in the spectral representation, without performing a separate calculation to determine the eigenvectors. We provide insight into this result and skip-free Markov chains more generally by showing that part of the spectral theory developed for birth-and-death processes extends to skip-free chains. We show that the eigenvalues and eigenvectors of skip-free chains can be characterized in terms of recursively defined polynomials. Moreover, the Laplace transform of the upward first passage time from 0 to n is the reciprocal of the nth polynomial. This simple relationship holds because the Laplace transforms of the first passage times satisfy the same recursion as the polynomials except for a normalization.
A Random-Bit Generator for use in Simulating the Reliability of a Coherent System
Authors: Butler David A.
Published: July 2009

Consider the problem of simulating w independent Bernoulli random variables X1 X2, …, Xw, so that {Xk = 1 = zk}, using a computer with a w–bit word length. A conventional method would be to generate w pseudorandom numbers uniform in [0,1], then “threshold” them with the values zk. This paper proposes an alternative method that only requires c pseudorandom numbers, where c is large enough so that the numbers zk are approximated satisfactorily with c bits. In many cases, c ≪ w and so fewer pseudorandom numbers are required. The new method is tested against the conventional method by employing both in simulations to estimate the reliabilities of several coherent systems. The results show that the new method is much faster.
Optimization Applications of Compensators of Poisson Random Measures
Authors: He Shengwu
Published: July 2009

Compensator or dual predictable projection is one of the main concepts of the general theory of stochastic processes, established by a French probabilistic school. In general, it is a considerably abstract concept and difficult to grasp. But in the Poisson case, it affords very powerful tools to calculate the expectation of certain stochastic integrals with respect to Poisson processes and random measures. Naturally, compensators can be used to solve certain problems of applied probability, involved in Poisson processes and random measures. In this direction, Brémaud and Jacod [1] had used the compensators of Poisson processes to solve the optimal dispatching problem, investigated by Ross [4] originally. In this note, we use the compensators of Poisson random measures to solve two optimal stopping problems: house selling and the burglary problem. The solutions are simple and completely rigorous as well. Our objective is to attract more attention to this method of using compensators. To facilitate reading, we introduce some fundamental results on marked point processes and Poisson random measures and their compensators.
On Optimal Consecutive k-out-of-n: F Systems Subject to a Fixed Product of Failure Probabilities
Authors: Yao Y. C.
Published: July 2009

A consecutive−k−out−of−n:F system is an n−vertex graph where the system fails if and only if some k consecutive vertices all fail. Assuming that the n vertices have, independently, the respective failure probabilities q1,…, qn, the problem is to find, subject to πqi = Q (a constant), a set of q1,…, qn so as to maximize the system reliability. In the case that the graph is a circle (or cycle), Chang and Hwang [1] conjectured that q1 =… = qn, = Q1/n is optimal if n and k are relatively prime. In this paper, it is shown that the conjecture is true for sufficiently small Q. It is also shown by counterexample that the conjecture is not true in general.
Bounds and Approximations for the Transient Behavior of Continuous-Time Markov Chains
Authors: Yoon Bok Sik , Shanthikumar J. George
Published: July 2009

Discretization is a simple, yet powerful tool in obtaining time-dependent probability distribution of continuous-time Markov chains. One of the most commonly used approaches is uniformization. A recent addition to such approaches is an external uniformization technique. In this paper, we briefly review these different approaches, propose some new approaches, and discuss their performances based on theoretical bounds and empirical computational results. A simple method to get lower and upper bounds for first passage time distribution is also proposed.
A General Model for the Scheduling of Alternative Stochastic Jobs that may Fail
Authors: Fay N. A. , Glazebrook K. D.
Published: July 2009

The standard single-machine scheduling problem is modified to take into account unsuccessful job completions. We use a result due to Nash to analyze problems in which some jobs are alternative to one another in the sense that only one of a set of alternative jobs need be completed successfully. Conditions are proposed under which a nonpreemptive strategy is optimal for processing such a system.
Further Properties of Reliability Importance for Continuum Structure Functions
Authors: Baxter Laurence A. , Lee Seung Min
Published: July 2009

A continuum structure function (CSF) is a nondecreasing mapping from the unit hypercube to the unit interval. The Kim-Baxter definition of the reliability importance of component i in a CSF at system level α, Ri(α), say, is reviewed. Conditions under which Ri(α) is positive, under which Ri(α) is a continuous function of α, and under which Ri(α) ≥ Rj(α) uniformly in α are presented. A simple algorithm for evaluating Ri(α) is described.
Average Cost Semi-Markov Decision Processes and the Control of Queueing Systems
Authors: Sennott Linn I.
Published: July 2009

Semi-Markov decision processes underlie the control of many queueing systems. In this paper, we deal with infinite state semi-Markov decision processes with nonnegative, unbounded costs and finite action sets. Axioms for the existence of an expected average cost optimal stationary policy are presented. These conditions generalize the work in Sennott [22] for Markov decision processes. Verifiable conditions for the axioms to hold are obtained. The theory is applied to control of the M/G/l queue with variable service parameter, with on-off server, and with batch processing, and to control of the G/M/m queue with variable arrival parameter and customer rejection. It is applied to a timesharing network of queues with a single server and finally to optimal routing of Poisson arrivals to parallel exponential servers. The final section extends the existence result to compact action spaces.
Estimating the Mean Number of Renewals By Simulation
Authors: Ross Sheldon M.
Published: July 2009

An estimator, based on a simulation, is given for the expected number of events by time t of a renewal process. The estimator is obtained by combining the techniques of control variates and conditional expectation.
Scheduling Multiclass Single Server Queueing Systems to Stochastically Maximize the Number of Successful Departures
Authors: Righter Rhonda , Shanthikumar J. George
Published: July 2009

We wish to schedule heterogeneous jobs on a single machine to stochastically maximize the number of jobs that are correctly completed before a random due date. Jobs arrive according to an arbitrary arrival process. Job i has probability ci, that it will be correctly completed, and a processing time that has distribution Fi. Jobs that are incorrectly processed cannot be reprocessed, and jobs that are not completed by the due date are assumed to be incorrectly processed. The machine is subject to breakdowns and repairs. Both premptive and non-preemptive policies are considered. We give conditions under which simple index rules are optimal. This generalizes and extends the results of Derman et al. [3], Pinedo and Rammouz [9], and Buyukkoc et al. [2], who derive policies that maximize the expected number of jobs correctly completed by the due date. We also consider policies that stochastically minimize the number of correct job completions. For single class systems, we give conditions under which FCFS (first-come-first-served) or LAST (least-attained-service-time) service disciplines stochastically minimize or maximize the number in the system.
Calculation of the Availability of a Two-Unit Parallel System With Cold Standby
Authors: Van Der Duyn Schouten Frank A. , Ronner Tjerk
Published: July 2009

A two-unit parallel system with cold standby, Markovian degradation of the working unit and one repair facility is considered. The calculation of the availability of this system under a control-limit repair policy is discussed. Iterative schemes for computing the availability in case of Erlangian repair-time distributions are presented along with numerical results.
Crossing Properties of Mixture Distributions
Authors: Boland Philip J. , Proschan Frank , Tong Y. L.
Published: July 2009

Mixture distributions are a frequently used tool in modelling random phenomena. We consider mixtures of densities from a one-parameter exponenvial family of distributions. Using the tools of totally positive functions and the variation-diminishing property of such, we study the effect of sign-crossing properties of two mixing densities μ1and μ2on the resulting mixture distributionsf1andf2. The results enable us to make stochastic and variability cornparisons for binomial-beta, mixed Weibull, and mixed gamma distributions.
Concepts of Setwise Dependence
Authors: Chhetry Devendra , Sampson Allan R. , Kimeldorf George
Published: July 2009

This paper motivates and introduces a number of new concepts of positive dependence among sets of random variables. In particular, setwise positive upper (and lower) orthant dependence, setwise association, and other related concepts are studied and their relationships are explored. These new concepts are applied to various multivariate normal distributions, some of which have both positive and negative covariances. A variety of new and interesting inequalities are also obtained.
On Repair Age Residual Repair Life in the Minimal Repair Process
Authors: Kirmani S.N.U.A. , Gupta Ramesh C.
Published: July 2009

Some properties of repair age (the elapsed time since the last repair) and the residual repair life (the time until the next repair) are studied for the minimal repair process under various assumptions on the aging characteristics of the equipment under maintenance. Bounds on expected repair age and expected residual repair life are obtained. Some characterizations of the Poisson process are also proved.
A Quasi-Reversibility Approach to the Insensitivity of Generalized Semi-Markov Processes
Authors: Konstantopoulos Panagiotis , Walrand Jean
Published: July 2009

This paper is concerned with a certain property of the stationary distribution of a generalized semi-Markov process (GSMP) known as insensitivity. It is well-known that the so-called Matthes' conditions form a necessary and sufficient algebraic criterion for insensitivity. Most proofs of these conditions are basically algebraic. By interpreting a GSMP as a simple queueing network, we are able to show that Matthes' conditions are equivalent to the quasi-reversibility of the network, thus obtaining another simple proof of the sufficiency of these conditions. Furthermore, we apply our method to find a simple criterion for the insensitivity of GSMP's with generalized routing (in a sense that is introduced in the paper).
A Functional Equation Arising in a Queue With a Gating Mechanism
Authors: Jagerman David L. , Sengupta Bhaskar
Published: July 2009

Our primary aim in this paper is to study a functional equation that arises in a problem of queueing. Consider a queue with compound Poisson arrivals and general service times with a gating mechanism. The gating mechanism takes in at most m(≤∞) customers at a time for service and serves these customers according to the processor-sharing discipline. In this paper, we examine various performance characteristics for this queue. The characteristics include waiting-time distribution, queue-length distribution, time spent with the server, and batch-size distribution for service.
The Central Limit Theorem and the Law of Large Numbers for Pair-Connectivity in Bernoulli Trees
Authors: Siegrist Kyle T. , Amin Ashok T. , Slater Peter J.
Published: July 2009

Consider the standard network reliability model in which each edge of a given (n, m)-graph G is deleted, independently of all others, with probability q = 1– p (0 <p < 1). The pair-connectivity random variable X is defined to be the number of connected pairs of vertices that remain in G. The mean of X has been proposed as a measure of reliability for failure-prone communications networks in which the edge deletions correspond to failures of the communications links. We consider deviations from the mean, the law of large numbers, and the central limit theorem for X as n → ∞. Some explicit results are obtained when G is a tree using martingale difference sequences. Stars and paths are treated in detail.
Tandem Conveyor Queues
Authors: Baccelli F. , Coffman E.G. , Gilbert E.N.
Published: July 2009

This paper analyzes a queueing system in which a constant-speed conveyor brings new items for service and carries away served items. The conveyor is a sequence of cells each able to hold at most one item. At each integer time, a new cell appears at the queue's input position. This cell holds an item requiring service with probability a, holds a passerby requiring no service with probability b, and is empty with probability (1– a – b). Service times are integers synchronized with the arrival of cells at the input, and they are geometrically distributed with parameter μ. Items requiring service are placed in an unbounded queue to await service. Served items are put in a second unbounded queue to await replacement on the conveyor in cells at the input position. Two models are considered. In one, a served item can only be placed into a cell that was empty on arrival; in the other, the served item can be placed into a cell that was either empty or contained an item requiring service (in the latter case unloading and loading at the input position can take place in the same time unit). The stationary joint distribution of the numbers of items in the two queues is studied for both models. It is verified that, in general, this distribution does not have a product form. Explicit results are worked out for special cases, e.g., when b = 0, and when all service times are one time unit (μ = 1). It is shown how the analysis of the general problem can be reduced to the solution of a Riemann boundary-value problem.
The Longer Queue Model
Authors: Flatto Leopold
Published: July 2009

Two queues forming two independent Poisson processes are served by one server with exponential service time. The server always works on the longer queue and, in case that they are of equal length, chooses either one with probability ½. Let πij be the probability that the two queue lengths equal i andj at equilibrium and π(z, w) = ∑πi j Ziwj. We determine π(z, w) and derive from this asymptotic formulas forπij as i, j → ∞. These asymptotic formulas are used to study the interdependence of the queue lengths. In particular, we obtain limit laws for the queue lengths conditioned on each other.
Schur Structure Functions
Authors: Abouammah A. M. , El-Neweihi E. , Proschan F.
Published: July 2009

We define two new classes of multistate coherent systems by requiring, among other conditions, that their structure functions be Schur-concave (Schurconvex). The M + 1 performance levels of both the systems and their components are represented by the set [0, 1,…, M]. We present basic structural properties of the new classes. In particular, we study in some detail the number and form of the critical upper (lower) vectors to the various performance levels. We also present some probabilistic aspects of the new classes.
Travelling Salesman with a Self-Similar Itinerary
Authors: Lalley Steven P.
Published: July 2009

Let X1, X2,… be i.i.d. random points in R2 with distribution v, and let Ln be the length of the shortest path through X1,…, Xn. The exact almost sure rate of growth of Ln, is obtained under the assumption that v is self-similar in an appropriate sense. This extends a well-known theorem of Beardwood, Halton, and Hammersley.
Integration of Discrete-Time Correlated Markov Processes in a TDM System
Authors: Chang Cheng-Shang , Chao Xiuli , Pinedo Michael
Published: July 2009

In this paper, we consider a discrete-time queueing model for a Time Division Multiplexing (TDM) system with integration of voice and data (a model introduced by Li and Mark [16]). The voice traffic is a superposition of N Markov chains, which alternate between two states: the talkspurt state and the silence state. The data traffic is Poisson and independent of the voice sources. We show that the average queue size is increasing in certain correlation coefficients of the voice sources, increasing convex in the proportion of time the voice sources are in talkspurts, increasing convex in the number of voice sources, and increasing convex in the data traffic intensity. However, it is decreasing convex in the number of channels. These structural results yield various bounds. To take video traffic into account as well, we adapt a model of Maglaris et al. [18]. In their model, video traffic is generated by a continuous-state autoregressive Markov process that matches the average rate and the autocovariance of the output of a video coder. We show that if we replace their autoregressive model by a two-state Markov chain model with the same rate and correlation coefficient, we obtain an upper bound for the queue size. This replacement enables us to treat the video traffic as a voice source and use the techniques developed for dealing with voice/data integration to obtain bounds and estimates.
On the Failure Rates of Consecutive−k−out−of−n Systems
Authors: Hwang F.K. , Yao Y.C.
Published: July 2009

It is known that the lifetime of a k−out−of−n system has increasing failure rate (IFR) if all of its components have independent and identically distributed IFR lifetimes. Derman, Lieberman, and Ross raised the same question for consecutive−k−out−of−n systems. But the scarcity of results gives no clue as to whether most of such systems have IFR's. In this paper, we completely solve the k = 2 and k = 3 cases. We prove that these systems, with a handful of exceptions, do not have IFR's (contradicting the result of Derman, Lieberman, and Ross that a consecutive-2-out-of-n cycle has IFR for any n). Our result suggests the conjecture that for every fixed k there exists nk such that for every n ≧ nk a consecutive-k−out−of−n system does not have IFR. We also prove that for every fixed d there exists nd large enough such that for all n ≧ nd a consecuive.(n – d)−out−of−n system has IFR. In particular, if the system is a line, then nd = 3d +1 for d ≧ 1.
TP2-Orderings and the IFR Property with Applications
Authors: Durham S. , Lynch J. , Padgett W.J.
Published: July 2009

In this paper, TP2 orderings of distributions and of survival functions are considered. It is shown that the first passage time of a Markov process with TP2- ordered transition distributions has an increasing failure rate (IFR). Conditions are also given for which mixtures of IFR distributions are IFR. A formula is obtained for the failure rate when the strength distribution is a function of both load and strength. This formula, in conjunction with the TP2-ordering on the strength survival functions and log-concavity of the strength and load variables, leads to an increasing failure rate for the strength distribution. Finally, two models based on this theory are presented which explain the IFR character of the strength distribution of fibrous composite materials.
A New Algorithm for Computing the Ergodic Probability Vector for Large Markov Chains
Authors: Sumita Ushlo , Rieders Maria
Published: July 2009

A novel algorithm is developed which computes the ergodic probability vector for large Markov chains. Decomposing the state space into lumps, the algorithm generates a replacement process on each lump, where any exit from a lump is instantaneously replaced at some state in that lump. The replacement distributions are constructed recursively in such a way that, in the limit, the ergodic probability vector for a replacement process on one lump will be proportional to the ergodic probability vector of the original Markov chain restricted to that lump. Inverse matrices computed in the algorithm are of size (M – 1), where M is the number of lumps, thereby providing a substantial rank reduction. When a special structure is present, the procedure for generating the replacement distributions can be simplified. The relevance of the new algorithm to the aggregation-disaggregation algorithm of Takahashi [29] is also discussed.
Thinning of Point Processes—Martingale Method
Authors: He Shengwu , Wang Jiagang
Published: July 2009

By using the martingale method, we show that thinning of an arbitrary point process produces independent thinned processes if and only if the original point process is (nonhomogeneous) Poisson. Thinning is a classical problem for point processes. It is well-known that independent homogeneous Poisson processes result from constant Bernoulli thinnings of homogeneous Poisson processes. In fact, the conclusion remains true for nonconstant Bernoulli thinnings of nonhomogeneous Poisson processes. processes. In fact, the conclusion remains true for nonconstant Bernoulli thinnings of nonhomogeneous Poisson processes. It is easy to see that the converse is also true, i.e., if the thinned processes are independent nonhomogeneous Poisson processes, so are the original processes. But if we only suppose the thinned processes are independent, nothing is concerned with their distribution law, the problem of whether or not the original processes are (nonhomogeneous) Poisson becomes interesting and challenging, which is the objective of this paper. It is considerably surprising for us to arrive at the affirmative answer. So far as this problem is concerned, the most work was done under the renewal assumption. For example, Bremaud [1] showed that for arbitrary delayed renewal processes, the existence of a pair of uncorrelated thinned processes is sufficient to guarantee that the original process is Poisson. It is natural that the mathematical tools to solve the problem in this case be typical ones for renewal theory, such as renewal equations and Laplace-Stieltjes transformations. Obviously, they are not available for nonrenewal processes. We find out that the martingale method is the most efficient one to solve this problem in the general case. More precisely, we use mainly the dual predictable projections of point processes. In fact, the distribution law of a point process is determined uniquely by its dual predictable projection (see [5]), and Ma [6] offered us a very useful criterion of independence of jump processes having no common jump time through their dual predictable projections. Based on these results, it is not a long way to arrive at the destination.
Dynamic Scheduling of a Four-Station Queueing Network
Authors: Laws C. N. , Louth G. M.
Published: July 2009

This paper is concerned with the problem of optimally scheduling a multiclass open queueing network with four single-server stations in which dynamic control policies are permitted. Under the assumption that the system is heavily loaded, the original scheduling problem can be approximated by a dynamic control problem involving Brownian motion. We reformulate and solve this problem and, from the interpretation of the solution, we obtain two dynamic scheduling policies for our queueing network. We compare the performance of these policies with two static scheduling policies and a lower bound via simulation. Our results suggest that under either dynamic policy the system, at least when heavily loaded, exhibits the form of resource pooling given by the solution to the approximating control problem. Furthermore, even when lightly loaded the system performs better under the dynamic policies than under either static policy.
Examples for the Theory of Strong Stationary Duality with Countable State Spaces
Authors: Diaconis Persi , Fill James Allen
Published: July 2009

LetX1,X2,… be an ergodic Markov chain on the countable state space. We construct astrong stationary dualchainX*whose first hitting times give sharp bounds on the convergence to stationarity forX. Examples include birth and death chains, queueing models, and the excess life process of renewal theory. This paper gives the first extension of the stopping time arguments of Aldous and Diaconis [1,2] to infinite state spaces.
Optimal Control and Trunk Reservation in Loss Networks
Authors: Key Peter B.
Published: July 2009

Consider a stochastic loss network, where calls or customer types arrive and have to find a path through the network to a given destination, and where our aim is to maximize the gain (suitably defined) from the network. In general there will be a number of paths available, and when a call arrives the two questions to answer are first, should the call be accepted, and secondly, if it is accepted which route should it take? The answer to the first question is in some sense harder than the second, and all dynamic routing or control policies have some explicit or implicit mechanism for rejecting calls and so answer the question in some way.
Optimal Maintenance Schedules of Computer Software
Authors: Wee Nam-Sook
Published: July 2009

We present a decision procedure to determine the optimal maintenance intervals of a computer software throughout its operational phase. Our model accounts for the average cost per each maintenance activity and the damage cost per failure with the future cost discounted. Our decision policy is optimal in the sense that it minimizes the expected total cost. Our model assumes that the total number of errors in the software has a Poisson distribution with known mean λ and each error causes failures independently of other errors at a known constant failure rate. We study the structures of the optimal policy in terms of λ and present efficient numerical algorithms to compute the optimal maintenance time intervals, the optimal total number of maintenances, and the minimal total expected cost throughout the maintenance phase.
Variance Reduction in Simulation via Random Hazards
Authors: Ross Sheldon M.
Published: July 2009

The use of the total hazard variable in simulation is studied. When estimating the mean time until a certain event occurs, this variable can be a powerful variance-reducing control variate. When estimating a small probability, it can be utilized as a direct estimator. Applications to reliability, quality control, and queueing are given.
Search in a Maze
Authors: Gal S. , Anderson E. J.
Published: July 2009

Suppose that you find yourself trapped in a maze about which you know nothing except that it has an exit point. We present an optimal strategy that will lead you to the exit point in minimum expected time. This strategy ensures that the expected total length of the arcs you traverse will not exceed the sum of the lengths of the arcs in the maze.
On Maxima and Minima of Partial Sums of Strongly Interchangeable Random Variables
Authors: Ott Teunis J. , Shanthikumar J. George
Published: July 2009

We introduce the concept of “strong interchangeability” of random vectors. Strongly interchangeable random vectors arise naturally in packetized voice channels, M/G/1 queues, symmetric queueing networks, and other standard symmetric distributions. We study some properties of strongly interchangeable random vectors. We show that if (X1, …, XN) is a strongly interchangeable random vector, then even though there is no Markov property, taboo probabilities can be used to compute the joint distribution of ŽN = min1≤n≤N σnk=IXk and ZN = max1≤n≤N σnk=1Xk. For a special instance of this problem that arises in packetized voice communication, it is shown that the resulting algorithm essentially has a complexity of order N4. When ( σnk=1Xk, n = 1,… N) is an associated random vector bound for the joint distribution of ŽN and ZN are obtained and applied to the packetized voice communication problem.
A Band and Bound Technique for Simple Random Algorithms
Authors: Rego Vernon
Published: July 2009

A simple random algorithm (SRA) is an algorithm whose behavior is governed by a first-order Markov chain. The expected time complexity of an SRA, given its initial state, is essentially the time to absorption of the underlying chain. The standard approach in computing the expected runtime is numerical. Under certain conditions on the probability transition matrix of an SRA, bounds on its expected runtime can be obtained using simple probabilistic arguments. In particular, one can obtain upper and lower (average time) logarithmic bounds for certain algorithms based on SRAs.
Improving Stochastic Relaxation for Gussian Random Fields
Authors: Barone Piero , Frigessi Arnolodo
Published: July 2009

In this paper, we are concerned with the simulation of Gaussian random fields by means of iterative stochastic algorithms, which are compared in terms of rate of convergence. A parametrized class of algorithms, which includes stochastic relaxation (Gibbs sampler), is proposed and its convergence properties are established. A suitable choice for the parameter improves the rate of convergence with respect to stochastic relaxation for special classes of covariance matrices. Some examples and numerical experiments are given.
Optimal Stopping in Oil Exploration with Small and Large Oilfields
Authors: Benkherouf Lakdere
Published: July 2009

The same applies when a success occurs in large fields; in this case, p1 = 0. If at least one success occurs in each oilfield after a certain number of wells are drilled, then we reach a position where the number of undiscovered fields is represented by simple Euler distributions, and the results of Section 4.1 showed that the optimal rule is a one-step look-ahead rule.
A Characterization of Lindley and Singpurwalla's Bivariate Lomax Distribution
Authors: Roy Dilip
Published: July 2009

Bivariate Lomax distribution due to Lindley and Singpurwalla has been characterized through the bivariate extension of a univariate characterizing property of the Lomax distribution.
On the Optimality of the Generalized Shortest Queue Policy
Authors: Hordijk Arie , Koole Ger
Published: July 2009

Consider a queueing model in which arriving customers have to choose between m parallel servers, each with its own queue. We prove for general arrival streams that the policy which assigns to the shortest queue is stochastically optimal for models with finite buffers and batch arrivals.
Optimal Binomial Group Testing with a Test History
Authors: Chen B. , Hu X. D. , Hwang F. K.
Published: July 2009

The classical binomial group-testing problem considers the use of a minimal number of group tests to identify all defectives in a set of items, each of which independently has probability p of being defective. The minimization problem is very difficult, and the only major result is that for p ≥ (3 - □ root;5) /2, Unger proved that one-by-one testing is the best. Recently, to study the complexity of the group-testing problem, researchers have considered the more general case in which the items have already been tested. Interestingly, Unger's result still holds in this case. However, since the items are no longer equivalent (nor independent), the sequencing of items of testing becomes a legitimate problem, one that did not arise in the classical case. In this paper, we give optimal sequencing under general conditions on the test history.
Pocket-Calculator Approximation to the Normal Tail
Authors: Lin Jinn-Tyan
Published: July 2009

This paper proposes a pocket-calculator approximation to the normal tail that is more convenient and more accurate than Hamaker's [1] and Lew's [2] over a wide range, when measured in terms of the number of keystrokes and absolute relative error, respectively.
Geometric Ergodicity of the ALOHA-system and a Coupled Processors Model
Authors: Spieksma F. M.
Published: July 2009

μ-Geometric ergodicity of two-dimensional versions of the ALOHA and coupled processors models is verified by checking μ-geometric recurrence. Ergodicity and convergence of the Laplace-Stieltjes transforms in a neighborhood of 0 are necessary and sufficient conditions for the first model. The second model is exponential, for which ergodicity suffices to establish the required results.
Monotonicity of the Loss Probabilities of Single Server Finite Queues with Respect to Convex Order of Arrival or Service Processes
Authors: Miyazawa Masakiyo , Shanthikumar J. George
Published: July 2009

The loss probabilities of customers in the Mx/GI/1/k, GI/Mx/l/k and their related queues such as server vacation models are compared with respect to the convex order of several characteristics, for example, batch size, of the arrival or service process. In the proof, we give a characterization of a truncation expression for a stationary distribution of a finite Markov chain, which is interesting in itself.
Time to Stationarity for a Continuous-Time Markov Chain
Authors: Fill James Allen
Published: July 2009

Separation is one measure of distance from stationarity for Markov chains. Strong stationary times provide bounds on separation and so aid in the analysis of mixing rates. The precise connection between separation and strong stationary times was drawn by Aldous and Diaconis (1987) (Advances in Applied Mathematics8: 69−97) for discrete time chains. We develop the corresponding foundational theory for continuous time chains; several new and interesting mathematical issues arise.
On Nonpreemptive Policies for Stochastic Single-Machine Scheduling with Breakdowns
Authors: Glazebrook Kevin D.
Published: July 2009

A set of stochastic jobs is to be processed on a single machine that is subject to breakdown. All jobs make progress as they are processed in the absence of machine breakdowns. However, breakdowns cause setbacks to (possibly) all jobs in the system, except those that have already been completed. With machines subject only to fairly mild restrictions on this “damage” process, we demonstrate the existence of a nonpreemptive policy that is optimal in the class of all preemptive ones.
Optimal Advertizing Policy for Selling a Single Asset
Authors: Assaf David , Levikson Benny
Published: July 2009

Suppose we have a single asset that we would like to sell. As time goes by, independent and identically distributed offers with a common known distribution F are given to us. At any given moment, we may either accept the current offer or reject it, thereby losing it forever. The rate at which offers arrive follows a nonhomogeneous Poisson process whose instantaneous intensity is under our control, using advertizing in a manner to be described. Our objective is, roughly, that of maximizing the total discounted expected reward composed of the offer we decide to accept, minus the total advertizing costs.
On Simulating Wiener Integrals and Their Expectations
Authors: Korzeniowski A. , Hawkins D.L.
Published: July 2009

An approximation scheme for evaluating Wiener integrals by simulating Brownian motion is studied. The rate of convergence and numerical results are given, including an application to the heat equation by using the Feynman-Kac formula.
Spectral Analysis, without Eigenvectors, for Markov Chains
Authors: Brown Mark
Published: July 2009

The Lagrange-Sylvester interpolation polynomial approach provides a simple, eigenvector-free representation for finite diagonalizable matrices. This paper discusses the Lagrange-Sylvester methodology and applies it to skip free to the right Markov chains. It leads to relatively simple, eigenvalue-based expressions for first passage time distributions and transition probabilities.
On Flows in Stochastic Marked Graphs
Authors: Baccelli F. , Bambos N. , Walrand J.
Published: July 2009

In this work, the discrete event systems called Stochastic Marked Graphs (SMGs) are investigated from a stability point of view. Being a special class of Timed Petri Nets with stochastic firing times, they are studied under general assumptions of stationarity and ergodicity of the firing times and ergodicity of flows of their free strongly connected components. The values of the flows of tokens in an SMG are specified as functions of the intrinsic rates of its free strongly connected components, and various stability issues are discussed.
Sensitivity Analysis for the System Reliability Function
Authors: Fishman George S.
Published: July 2009

Sensitivity analysis is an integral part of virtually every study of system reliability. This paper describes a Monte Carlo sampling plan for estimating this sensitivity in system reliability to changes in component reliabilities. The unique feature of the approach is that sample data collected on K independent replications using a specified component reliability vector p are transformed by an importance function into unbiased estimates of system reliability for each component reliability vector q in a set of vectors Q. Moreover, this importance function together with available prior information about the given system enables one to produce estimates that require considerably less computing time to achieve a specified accuracy for all |Q| reliability estimates than a set of |Q| crude Monte Carlo sampling experiments would require to estimate each of the |Q| system reliabilities separately. As the number of components in the system grows, the relative efficiency continues to favor the proposed method.

The paper shows the intimate relationship between the proposal and the method of control variates. Next, it relates the proposal to the estimation of coefficients in a reliability polynomial and indicates how this concept can be used to improve computing efficiency in certain cases. It also describes a procedure that determines the p vector, to be used in the sampling experiment, that minimizes a bound on the worst-case variance. The paper also derives individual and simultaneous confidence intervals that hold for every fixed sample size K. An example illustrates how the proposal works in an s-t connectedness problem.
A Study of the Role of Modules in the Failure of Systems
Authors: Neweihi Emad El , Sethuraman Jayaram
Published: July 2009

Since the introduction of the concept of coherent systems and the description of the reliability of such systems in terms of the reliabilities of the components, the concept of importance of a component has created a new and fruitful area of research. Two distinct concepts of importance can be found in the literature. We take the view that the importance of a component or a module that is part of a system can be derived directly from the role of the component or the module in the failure of the system. Here again, it is possible that there will be several definitions of role. In this paper we define the role of a module (or component) to be the probability that the module is among all the modules (or components) that failed at the time of system failure. The role of a module depends on the structure of the system in terms of the modules, the structure of the module in terms of its components and the distribution of lifetimes of the components. In this paper we study the role of a module under several structures and distributions for lifetimes. We establish various monotonicity properties and indicate applications of these properties to optimal allocation. Another quantity that describes the nature of the components in sustaining the system is the number of components that fail at the time of the failure of the system. We establish monotonicity properties for the expected number of failed components and also indicate applications to optimal allocation.
Decomposable Probabilistic Influence Diagrams
Authors: Chyu C. C.
Published: July 2009

Probabilistic influence diagrams are a useful stochastic modeling tool. To calculate probabilities of interest relative to a probabilistic influence diagram efficiently, it will be helpful for us to use an associated decomposable-directed graph. We first explore and discuss some graph-theoretic and conditional independence properties of decomposable probabilistic influence diagrams. These properties are helpful in providing an efficient algorithm for obtaining a posterior decomposable probabilistic influence diagram given the state of one or more observed nodes. The connection between Shachter's “sequential creation of conditionally barren nodes” concept and Lauritzen and Spiegeihalter's “moralization and triangulation” algorithm for calculating probabilities relative to a probabilistic influence diagram is made explicit. We also discuss how to use wisely the concepts of “sequential creation of conditionally barren nodes” and “merging nodes” together with the graph-theoretic properties of decomposable directed graphs to compute probabilities relative to probabilistic influence diagrams.
Reliabilities of Double-Loop Networks
Authors: Hwang F.K. , Li Wen-Ching Winnie
Published: July 2009

A double-loop network G(h1, h2) has n nodes represented by the n residues modulo n and 2n links given by i ↦i + h1, i ↦ i + h2, i = 0,1,…,n – 1.We consider the reliability model where each link fails independently with probability p, the nodes always work, and the network fails if it is not strongly connected. There exists no known polynomial time algorithm to compute the reliabilities of general double-loop networks. When p is small, the reliability is dominated by the link connectivity. As all strongly connected double.loop networks have link connectivity exactly 2, a finer measure of reliability is needed. In this paper we give such a measure and show how to use it to obtain the most reliable double-loop networks.
Chi-Square Goodness of Fit: A Failure Rate Perspective
Authors: Brown Mark , Flicker Marcia H.
Published: July 2009

Employing a failure rate approach, we propose a test statistic,, for the classic goodness-of-fit problem. It is then shown that a variation of, obtained by replacing observed variances by expected variances (an unwise change in our point of view), leads to the classical test statistic,x2. We argue thatshould be better approximated by a chi-square distribution, and thus employing, the truep−values should be closer to the nominalp−values than underx2Various other comparisons of the two tests are made.
A Simple Numerical Approach for Infinite-State Markov Chains
Authors: Tijms Henk C. , Coevering Michel C. T. Van De
Published: July 2009

This paper presents a simple and practical approach to solving the equilibrium equations for a class of Markov chains with an infinite number of states. Markov chains arising in queueing and inventory applications often have the property that the state probabilities exhibit a geometric tail behavior. The basic idea of the approach is to reduce the infinite system of linear equations to a finite system using the geometric tail behavior of the equilibrium probabilities. The reduction typically leads to a remarkably small system of linear equations that can be routinely solved by a Gaussian elimination method. An application is given to the single-server queue with scheduled arrivals.
A Note on Stochastic Scheduling on a Single Machine Subject to Breakdown–The Preemptive Repeat Model
Authors: Frostig Esther
Published: July 2009

This paper considers scheduling n jobs on one machine to minimize the expected weighted flowtime and the number of late jobs. The processing times of the jobs are independent random variables. The machine is subject to failure and repair where the uptimes are exponentially distributed. We find the optimal policies for the preemptive repeat model.
On the Variance of the Hazard Estimator in Simulation
Authors: Lieberman Gerald J. , Ross Sheldon M.
Published: July 2009

Suppose a discrete time Markov process is simulated so as to estimate p, the probability that it enters the set of states A before it enters the set of states B, for disjoint sets A and B. It is shown that the total hazard, which is an unbiased estimator of p, has a variance that is bounded above by p(2 – p).
Renewal Networks: Connectivity and Reachability on a Time Interval
Authors: Colbourn Charles J. , Lomonosov Michael V.
Published: July 2009

Efficiently computable bounds are developed for the time to first failure in a communications network with renewable links. The bounds approximate a network with bidirectional or unidirectional links by acyclic networks with unidirectional links.
Strongly Consistent Steady-State Derivative Estimates
Authors: Glasserman Paul , Hu Jian-Qiang , Strickland Stephen G.
Published: July 2009

We establish strong consistency (i.e., almost sure convergence) of infinitesimal perturbation analysis (IPA) estimators of derivatives of steady-state means for a broad class of systems. Our results substantially extend previously available results on steady-state derivative estimation via IPA.

Our basic assumption is that the process under study is regenerative, but our analysis uses regenerative structure in an indirect way: IPA estimators are typically biased over regenerative cycles, so straightforward differentiation of the regenerative ratio formula does not necessarily yield a valid estimator of the derivative of a steady-state mean. Instead, we use regeneration to pass from unbiasedness over fixed, finite time horizons to convergence as the time horizon grows. This provides a systematic way of extending results on unbiasedness to strong consistency.

Given that the underlying process regenerates, we provide conditions under which a certain augmented process is also regenerative. The augmented process includes additional information needed to evaluate derivatives; derivatives of time averages of the original process are time averages of the augmented process. Thus, through this augmentation we are able to apply standard renewal theory results to the convergence of derivatives.