bluuebunny/crossref_metadata_2025 huggingface dataset:
Two-Stage Release Rule Procedure in a Regenerative Dam
Authors: Bar-Lev Shaul K. , Perry David
Published: July 2009

We consider a dam model with a compound Poisson input having positive jumps in which the release rule can be dynamically controlled between two release functions, r1 and r2. The dam process has two switchover levels, a and b, 0 < a < b < ∞, which are prescribed to switch the release rule from r2 to r1 only when the dam downcrosses levels and switch from r1 to r2 only when the dam upcrosses level b. We derive integral equations whose solutions determine the stationary distribution of the dam content and demonstrate such a determination explicitly for the case of exponential jumps. We also compute an expression for the average number of switches from r1 to r2, and vice versa; consider an approximation to the general case (with b − a being sufficiently large with respect to r1 and r2 and the jump sizes), which allows the use of asymptotic results from renewal theory; and study the wet period analysis for the case of exponential jumps.
Quasi-Statically Cooled Markov Chains
Authors: Desai Madhav , Kumar Sunil , Kumar P. R.
Published: July 2009

We consider time-inhomogeneous Markov chains on a finite state-space, whose transition probabilitiespij(t) = cijε(t)Vij are proportional to powers of a vanishing small parameter ε(t). We determine the precise relationship between this chain and the corresponding time-homogeneous chains pij= cijε(t)vij, as ε ↘ 0. Let {} be the steady-state distribution of this time-homogeneous chain. We characterize the orders {ηι} in = θ(εηι). We show that if ε(t) ↘ 0 slowly enough, then the timewise occupation measures βι := sup { q > 0 | Prob(x(t) = i) = + ∞}, called the recurrence orders, satisfy βi — βj = ηj — ηi. Moreover, : = { ηι|ηι = minj} is the set of ground states of the time-homogeneous chain, then x(t) → . in an appropriate sense, whenever η(t) is “cooled” slowly. We also show that there exists a critical ρ* such that x(t) → if and only if = + ∞. We characterize this critical rate as ρ* = max.min min max. Finally, we provide a graph algorithm for determining the orders [ηi] [βi] and the critical rate ρ*.
On Separation for Birth-Death Processes
Authors: Kijima Masaaki
Published: July 2009

This article considers separation for a birth-death process on a finite state space S = [1,2,…, N]. Separation is defined by si(t) = 1 – minj∈sPij(t)/πj, as in Fill [5,6], where Pij(t) denotes the transition probabilities of the birth-death process and πj the stationary probabilities. Separation is a measure of nonstationarity of Markov chains and provides an upper bound of the variation distance. Easily computable upper bounds for si-(t) are given, which consist of simple exponential functions whose parameters are the eigenvalues of the infinitesimal generator or its submatrices of the birth-death process.
Laplace Transform Characterization of Probabilistic Orderings
Authors: Kebir Y.
Published: July 2009

Using the Laplace transform, we characterize, by means of necessary and sufficient conditions, the property that two life distributions are ordered in the sense of stochastic ordering, hazard rate ordering, backward hazard rate ordering, and likelihood ratio ordering.
Dependence and Aging Properties of Lifetimes with Schur-Constant Survival Functions
Authors: Caramellino Lucia , Spizzichino Fabio
Published: July 2009

For n-dimensional survival functions, we study some probabilistic aspects of the Schur-constant property. The latter is of interest in that it extends the “lack-of-memory” property in a Bayesian context. Some general facts are studied in detail, and related results about interdependence, aging, and extendibility are presented.
On a Class of Stochastic Arrangement Inequalities Arising in Optimal Allocation of Resources
Authors: Li Haijun
Published: July 2009

Motivated by stochastic allocation problems, we study sufficient conditions that imply a general class of stochastic arrangement inequalities. This class includes many known and useful arrangement inequalities in the literature. Some illustrative examples in reliability theory are also given.
Order-Preserving Shock Models
Authors: Kebir Y.
Published: July 2009

To date, research in shock models has been primarily concerned with the classpreserving properties of certain shock and damage kernels. This article focuses on the order-preserving properties of those kernels. We show that they preserve stochastic ordering, hazard rate ordering, backward hazard rate ordering, and likelihood ratio ordering.
Analysis of an Algorithm for Random Sampling
Authors: Hurley Catherine B. , Mahmoud Hosam M.
Published: July 2009

We analyze a standard algorithm for sampling m items without replacement from a computer file of n records. The algorithm repeatedly selects a record at random from the file, rejecting records that have previously been selected, until m records are obtained. The running time of the algorithm has two components: a rejection component and a search component. We show that the probability distribution of the rejection component undergoes an infinite series of phase transitions, depending on the order of magnitude of m relative to n. We identify an infinite number of ranges of m, each with a different behavior. The rejection component is distributed as a linear combination of Poisson-like random variables. The search component is customarily done using a hash table with separate chaining. The analysis of the hashing scheme in this problem differs from previous hashing analyses, as the number of lookups in the hash table for each insertion has a geometric distribution. We show that the average overall cost of searching is asymptotically linear with only two phase transitions in the coefficient of linearity.
A Multiple Stopping Problem
Authors: Preater J.
Published: July 2009

In the context of team recruitment, we discuss an optimal multiple stopping problem for an infinite independent and identically distributed sequence, with general reward function and constant observation cost. We establish the existence and nature of an optimal stopping rule. For the particular case where team quality is governed by the fitness of the weakest member, we show that the recruiter should be more discriminating with either a better, or a larger, group of appointees in hand.
Deep-Penetration Calculations for Scattering Neutrons by Importance Sampling
Authors: Kollman Craig
Published: July 2009

Neutron scatter in a homogeneous solid is modelled as a one-dimensional i.i.d. random walk with killing. Importance sampling is used to estimate the extremely small probability that the random walk crosses a large level before killing occurs. The theory of large deviations provides insight into the selection of the probability measure used in the simulations. A sample problem demonstrates the variance reduction possible when this technique is used.
The Loss Probability in Finite-Buffer Queues with Batch Arrivals and Complete Rejection
Authors: Gouweleeuw Frank N.
Published: July 2009

This note extends a recently proposed approximation for the loss probability to the batch-arrival Finite-buffer queues with complete rejection. Also, a condition is stated under which the approximation is exact.
Optimality Aspects of Greedy Schemes in Parallel Processing of Random Graph-Structured Jobs
Authors: Bambos Nicholas , Chen Shou C.
Published: July 2009

Parallel processing systems with jobs structured as random graphs, where the nodes correspond to executable tasks and the directed edges to precedence constraints, are studied from a queueing theoretic point of view under general stationarity assumptions on the job flows. Jobs need to have their tasks processed non-preemptively by a set of uniform processors. Simple, natural greedy schemes of allocating processors to tasks are shown to asymptotically minimize the long-term average execution time per job. The stability condition for this queueing system is specified, and greedy allocation schemes are shown to stabilize the system under the maximum possible job arrival rate. Some recurrence properties of the system state are also established.
On Monte Carlo Estimates in Network Reliability
Authors: Lomonosov M.
Published: July 2009

The paper considers representations of network reliability measures as the mean value of a random variable defined on the trajectories of a certain Markov process and investigates utility of such formulae for Monte Carlo (MC) estimating. Such an MC estimator is called (ε,δ)-polynomial if its relative error is less than ε with probability >1 – δ, for any sample size equal to or greater than a polynomial of ε-1, δ-1, and the size of the network. One of the main results: The suggested MC estimator for the disconnectedness probability of a multiterminal network is (ε,δ)-polynomial, under a certain natural condition on the edge failure probabilities. The method applies also to estimating the percolation critical point and certain equilibrium characteristics of renewal networks.
Priority Ordering in Interruptible Electric Power Service with Irreversible Early Notification
Authors: Strauss Todd , Oren Shmuel
Published: July 2009

A multi-period model of interruptible electric power service that includes early notification may be described as a stochastic control problem:whom to notify when. When customer interruption losses are multiplicative or submodular, an optimal priority ordering exists, allowing for a simple notification policy.
A Set of Algorithms for the Incomplete Gamma Functions
Authors: Temme N. M.
Published: July 2009

This paper gives fast and reliable algorithms for the numerical evaluation of the incomplete gamma functions and for auxiliary functions, such as functions related with the gamma function and error function. All these functions are of basic importance in applied probability problems.
On the Decrease in Dependence with Lag for Stationary Markov Chains
Authors: Fang Zhaoben , Hu Taizhong , Joe Harry
Published: July 2009

Results and conditions that quantify the decrease in dependence with lag for stationary Markov chains are obtained. Notions of dependence that are used are the concordance or positive quadrant dependence ordering, measures of dependence based on ψ-divergences such as the relative entropy measure of dependence, and the Goodman-Kruskal measure of association. The general results are mainly for first-order Markov chains, but there are also some results for higher order Markov chains.
Fluid Model Driven by an Ornstein-Uhlenbeck Process
Authors: Kulkarni Vidyadhar , Rolski Tomasz
Published: July 2009

In this paper we consider a fluid model of a single buffer in a random external environment modeled by an Ornstein-Uhlenbeck process. Such a model appears as the limiting case of the multiplexing model of Anick, Mitra, and Sondhi [2] in a heavy traffic environment. We use the change of measure technique to derive an exponential upper bound on the tail probabilities of the steady-state buffer content. We also establish an asymptotic upper and lower exponential bounds on the tail probabilities.
Optimal Allocation of Components in k-out-of-R Parallel Modules Systems
Authors: Meng Fan Chin
Published: July 2009

In this note using the notion of node criticality in Boland, Proschan, and Tong [2] and modular decompositions of coherent systems, we obtain algorithms and guidelines for allocating components in a k-out-of-R parallel modules system to maximize the system reliability. An illustrative example is given to compare a special case of our results with the previous result for series-parallel systems due to El-Neweihi, Proschan, and Sethuraman [5].
A Direct Approximation for the Percentiles of the t Distribution
Authors: Lin Jinn-Tyan
Published: July 2009

In contrast to the usual approach of using a normalizing transformation, a direct approximation for the percentiles of the t distribution is developed by using techniques of exploratory data analysis. The approximation is convenient to use and has sufficient accuracy for many applications of the t distribution.
Improving Poisson Approximations
Authors: Peköz Erol A. , Ross Sheldon M.
Published: July 2009

LetX1,…,Xn, be indicator random variables, and setWe present a method for estimating the distribution ofWin settings whereWhas an approximately Poisson distribution. Our method is shown to yield estimates significantly better than straight Poisson estimates when applied to Bernoulli convolutions, urn models, the circularkofn:Fsystem, and a matching problem. Error bounds are given.
Optimal Stochastic Dynamic Scheduling in Multi-Class Queues with Tardiness and/or Earliness Penalties
Authors: Pandelis Dimitrios G. , Teneketzis Demosthenis
Published: July 2009

Tasks belonging to N classes arrive for processing in a multi-server facility. Each arriving task has a due date (deterministic or random) associated with the completion of its service. If the service of a task is completed at a time other than the task's due date, an earliness or tardiness penalty is incurred. We determine properties of dynamic nonidling nonpreemptive and dynamic nonidling preemptive scheduling strategies that minimize an infinite horizon expected discounted cost due to the earliness and tardiness penalties. We provide examples that illustrate the properties of the optimal strategies.
Optimal Assemblies of Consecutive-2 Link Systems
Authors: Du D. Z. , Hwang F. K.
Published: July 2009

Recently, the well-studied consecutive-2 (out-of-n) system has been extended to the consecutive-2 link system, in which links are also part of the system and can be failed. Furthermore, links of the two types i → i + 1 and i → i + 2 are recognized to be different entities. We study the optimal assembly problem for the link system and obtain results that generalize previous results on the consecutive-2 system.
A Stochastic Model to Capture Space and time Dynamics in Wireless Communication Systems
Authors: Massey William A. , Whitt Ward
Published: July 2009

We construct a version of the recently developed Poisson-Arrival-Location Model (PALM) to study communicating mobiles on a highway, giving the distribution of calls in progress and handoffs as a function of time and space. In a PALM arrivals generated by a nonhomogeneous Poisson process move independently through a general state space according to a location stochastic process. If, as an approximation, we ignore capacity constraints, then we can use this model to describe the performance of wireless communication systems. Our basic model here is for traffic on a one-way, single-lane, semi-infinite highway, with movement specified by a deterministic location function. For the highway PALM considered here, key quantities are the call density, the handoff rate, the call-origination-rate density and the call-termination-rate density, which themselves are simply related by two fundamental conservation equations. We show that the basic highway PALM can be applied, together with independent superposition, to treat more complicated models. Our analysis provides connections between teletraffic theory and highway traffic theory.
Test Point Optimization in a Branching-Process-Based Reliability Model
Authors: Danninger Gabriele , Gutjahr Walter J.
Published: July 2009

We describe a model for a random failure set in a fixed interval of the real line. (Failure sets are considered in input-domain-based theories of software reliability.) The model is based on an extended binary splitting process. Within the described model, we investigate the problem of how to select k test points such that the probability of finding at least one point of the failure set is maximized. It turns out that for values k > 2, the objective functions to be maximized are closely related to solutions of the Poisson-Euler-Darboux partial differential equation. Optimal test points are determined for arbitrary k in an asymptotic case where the failure set is, in a certain sense, “small” and “intricate,” which is the relevant case for practical applications.
Gerald J. Lieberman
Authors: Bowker Albert H. , Olkin Ingram , Veinott Arthur F.
Published: July 2009

Gerald J. Lieberman was born on December 31, 1925, in Brooklyn, New York, after a hectic New Year's Eve trip to the hospital. His father, Joseph, spelled his last name Liberman, but his mother, Ida, preferred Lieberman, the spelling that she and some of Joseph's siblings used. Joseph and Ida had come to this country from Lithuania. Joseph worked for the Metropolitan Life Insurance Company, and they lived in an “historic” section of Flatbush. The much wanted baby boy was the center of the family, which included two doting older sisters, Shirley and Rosalind. He grew fast — one of the tallest boys in nearby Public School 197 — and achieved his adult height at about the age of 13. As a boy, he was described as towheaded and gawky. Jerry did not realize that he had a middle initial until he was 15 and needed a birth certificate to get a work permit. Jerry asked his parents if they had given him a middle initial, but they did not remember. In any case, since the J does not stand for anything, Jerry likes to quip that his middle name is Jinitial.
Goodness-of-Fit Tests for Probability Distributions and Spectral Distributions
Authors: Anderson T. W.
Published: July 2009

In the fall of 1948 in my course on Least Squares in the Department of Mathematical Statistics at Columbia University (and in the spring in Correlation and Chi-Square), I was particularly impressed by one of the students— Gerald J. Lieberman. I was disappointed that this promising student left Columbia after one year, but it was not long until our paths met again. It is a pleasure to dedicate this paper to my colleague and close friend!
Reliability for a System with Dependent Components
Authors: Derman Cyrus , Ross Sheldon
Published: July 2009

A general type of model that results in components having a negative type of dependence is proposed. Specifically, a system of dependent binary components, in which component i is said to function if at least one of a given number of multinomial trials results in that outcome, is considered. The multinomial probabilities that maximize the probability of a k-of-n system are determined. Some approximations for the system reliability are proposed first for a system that functions unless k consecutive components are failed and then for a general system. A simulation method that uses a variance reduction technique to estimate the reliability is presented.
A Discounted-Cost Continuous-Time Flexible Manufacturing and Operator Scheduling Model Solved by Deconvexification Over Time
Authors: Eaves B. Curtis , Rothblum Uriel G.
Published: July 2009

A discounted-cost, continuous-time, infinite-horizon version of a flexible manufacturing and operator scheduling model is solved. The solution procedure is to convexify the discrete operator-assignment constraints to obtain a linear program and then to regain the discreteness and obtain an approximate manufacturing schedule by deconvexification of the solution of the linear program over time. The strong features of the model are the accommodation of linear inequality relations among the manufacturing activities and the discrete manufacturing scheduling, whereas the weak features are intra-period relaxation of inventory availability constraints and the absence of inventory costs, setup times, and setup charges.
Markov Branching Decision Chains with Interest-Rate-Dependent Rewards
Authors: Huang Ying , Veinott Arthur F.
Published: July 2009

Finite-state-and-action Markov branching decision chains are studied with bounded endogenous expected population sizes and interest-rate-dependent one-period rewards that are analytic in the interest rate at zero. The existence of a stationary strong-maximum-present-value policy is established. Miller and Veinott's [1969] strong policy-improvement method is generalized to find in finite time a stationary n-present-value optimal policy and, when the one-period rewards are rational in the interest rate, a stationary strong-maximum-present-value policy. This extends previous studies of Blackwell [1962], Miller and Veinott [1969], Veinott [1974], and Rothblum [1974, 1975], in which the one-period rewards are independent of the interest rate, and Denardo [1971] in which semi-Markov decision chains with small interest rates are studied. The problem of finding a stationary n-present-value optimal policy is also formulated as a staircase linear program in which the objective function and right-hand sides, but not the constraint matrix, depend on the interest rate, and solutions for all small enough positive interest rates are sought. The optimal solutions of the primal and dual are polynomials in the reciprocal of the interest rate. A constructive rule is given for finding a stationary n-present-value optimal policy from an optimal solution of the asymptotic linear program. This generalizes the linear programming approaches for finding maximum-reward-rate and maximum-present-value policies for Markov decision chains studied by Manne [1960], d'Epenoux [1960, 1963], Balinski [1961], Derman [1962], Denardo and Fox [1968], Denardo [1970], Derman and Veinott [1972], Veinott [1973], and Hordijk and Kallenberg [1979, 1984].
Lot Sizes in Serial Manufacturing with Random Yields
Authors: Sobel Matthew J.
Published: July 2009

In a job-shop manufacturing environment, consider a model in which the “job” is processed at several stages with random yields. Nondefective items move through the stages to supply a possibly random demand. At each stage there are linear costs of processing and work-in-process inventories and there are convex costs of end-item inventory. Decisions specify the lot sizes that are processed at the various stages. Easy computations specify a simply structured decision rule that minimizes the expected total cost.
Toward a Formal Derivation of the Expected Behavior of Prefix B-Trees
Authors: Mahmoud Hosam M. , Orlandić Ratko
Published: July 2009

Via order statistics we analyze the average length of all separators in random Prefix B-trees. From this result we draw some conclusions and conjectures concerning the average overall storage of random Prefix B-trees.
Central Limit Theorem for Time to Broadcast in Radio Networks
Authors: Ravishankar Krishnamurthi , Singh Suresh
Published: July 2009

We study the problem of broadcasting in a system where nodes are equipped with radio transmitters with constant radius of transmission. A message originating at a node has to be transmitted to all the other nodes in the system. We prove the central limit theorem and the law of large numbers for the number of time steps required to complete a broadcast for the case when the nodes are placed on a line independently uniformly distributed. We show that the number of time steps required to broadcast is 3n/4 in probability.
A Bound on the Rate of Convergence for the Discrete Gibbs Sampler
Authors: Dinwoodie I. H.
Published: July 2009

We give a computable bound on the rate of convergence of the occupation measure for the Gibbs sampler to the stationary distribution.
A Globally Gated Polling System with a Dormant Server
Authors: Borst S. C.
Published: July 2009

We study a globally gated polling system with a dormant server, which makes a halt at its home base when there are no customers present in the system. We derive an explicit expression for the cycle time distribution as well as for the waiting-time distribution at each of the queues. As a justification of the dormant server policy, we show the waiting time at each of the queues to be smaller (in the increasing-convex-ordering sense) than in the ordinary nondormant server case.
Customer Scheduling with Incomplete Information
Authors: Rieder Ulrich , Weishaupt Jürgen
Published: July 2009

A stochastic scheduling model with linear waiting costs and unknown routing probabilities is considered. Using a Bayesian approach and methods of Bayesian dynamic programming, we investigate the finite-horizon stochastic scheduling problem with incomplete information. In particular, we study an equivalent nonstationary bandit model and show the monotonicity of the total expected reward and of the Gittins index. We derive the monotonicity and well-known structural properties of the (greatest) maximizers, the so-called stay-on-a-winnerproperty and the stopping-property. The monotonicity results are based on a special partial ordering on .
Effective Bandwidths for Stationary Sources
Authors: Courcoubetis Costas , Weber Richard
Published: July 2009

At a buffered switch in an ATM (asynchronous transfer mode) network it is important to know what combinations of different types of traffic can be carried simultaneously without risking more than a very small probability of overflowing the buffer. We show that a simple and serviceable measure of effective bandwidths may be computed for stationary traffic sources. For large buffers the effective bandwidth of a source is a function only of its mean rate, index of dispersion, and the size of the buffer.
Finding the Conjugate of Markov Fluid Processes
Authors: Mandjes Michel , Ridder Ad
Published: July 2009

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

Approximations for the univariate normal integral are employed to develop a simple approximation in terms of elementary functions for the bivariate normal integral. The accuracy of the approximation is quite sufficient for many practical cases.
An Improved Estimator of σ in Quality Control
Authors: Derman Cyrus , Ross Sheldon
Published: July 2009

We present a new estimator for the standard deviation parameter in the standard quality control model. We argue that it has a smaller mean square error than the usual estimator when the data are normal and that, unlike the usual estimator, it remains consistent even when the data are not normal.
Extending Blackwell's Strengthening of Azuma's Martingale Inequality
Authors: Ross Sheldon M.
Published: July 2009

We extend a recent strengthening of Azuma's inequality to allow for a non symmetric bound on the martingale differences.
Accelerated Regeneration for Markov Chain Simulations
Authors: Andradóttir Sigrún , Calvin James M. , Glynn Peter W.
Published: July 2009

This paper describes a generalization of the classical regenerative method of simulation output analysis. Instead of blocking a generated sample path on returns to a fixed return state, a more general scheme to randomly decompose the path is used. In some cases, this decomposition scheme results in regeneration times that are a supersequence of the classical regeneration times. This “accelerated” regeneration is advantageous in several simulation contexts. It is shown that when this decomposition scheme accelerates regeneration relative to the classical regenerative method, it also yields a smaller asymptotic variance of the regenerative variance estimator than the classical method. Several other contexts in which increased regeneration frequency is beneficial are also discussed.
Computing Optimal Policies for Markovian Decision Processes Using Simulation
Authors: Burnetas Apostolos N. , Katehakis Michael N.
Published: July 2009

A simulation method is developed for computing average reward optimal policies, for a finite state and action Markovian decision process. It is shown that the method is consistent; i.e., it produces solutions arbitrarily close to the optimal. Various types of estimation errors and confidence bounds are examined. Finally, it is shown that the probability distribution of the number of simulation cycles required to compute an e-optimal policy satisfies a large deviations property.
Preservation of Stochastic Orderings under Random Mapping by Point Processes
Authors: Shaked Moshe , Wong Tityik
Published: July 2009

Let N = [N(t), t ≥ 0] be a point process, and let T1 and T2 be two positive random variables that are independent of N. Define Mk = N(Tk), k = 1,2. In this paper we study conditions on the process N under which some stochastic orders between T1 and T2 are transformed into stochastic orders between M1 and M2. In some cases the converses are also shown to be true. Some applications and examples are given.
A Coupling Proof of the Asymptotic Normality of the Permutation Oscillation
Authors: Angus John E.
Published: July 2009

For eachn≥ 1, let Πn= (π1, π2, …, πn) be a random permutation of the integers 1,2, …,n. The quantityBn= Σmeasures the degree of oscillation of Πnand is an important measure in the study of sorting algorithms. In this work the asymptotic normality ofBnis derived under the assumption that, for eachn≥ 1, Πnis uniformly distributed over then! permutations of 1,2, …,n. The proof relies on coupling (π1, π2, …, πn) with a sequence of independent and identically distributedU(0,1) random variables and offers a more probabilistic and computationally simpler alternative to the method of moments proof of Chao, Bai, and Liang (1993,Probability in the Engineering and Informational Sciences7: 227–235).
Fitting Discrete Distributions on the First Two Moments
Authors: Adan Ivo , van Eenige Michel , Resing Jacques
Published: July 2009

In this paper we present a simple method to fit a discrete distribution on the first two moments of a given random variable. With the Fitted distribution we solve approximately Lindley's equation for the D/G/1 queue with discrete service-time distribution using a moment-iteration method. Numerical results show excellent performance of the method.
Optimal Allocation of Machines to Distinguishable Repairmen in Order to Maximize Some Reward Functions
Authors: Frostig Esther
Published: July 2009

We consider N unreliable machines that are maintained by M repairmen. The time until failure of machine i, and its repair by repairman j, are exponentially distributed random variable with parameters λi, and μj, respectively. All failure times and repair times are independent. Machine i earns ci, per unit time, while it is working. We wish to maximize the expected total discounted reward. It is shown that when the following conditions are satisfied — c1 ≥ … ≥ cN and c1/λ1≥…≥cN/λN, the policy that assigns the fastest repairman to the machine with the lowest index is optimal. Moreover, it is shown that when the second condition is replaced by λ≤ … ≤λN, then this policy maximizes, stochastically, the number of the most reliable machines at every time t.
Monotone Stochastic Recursions and their Duals
Authors: Asmussen Søren , Sigman Karl
Published: July 2009

A duality is presented for real-valued stochastic sequences [Vn] defined by a general recursion of the formVn+1=f(Vn,Un), with [Un] a stationary driving sequence andfnonnegative, continuous, and monotone in its first variable. The duality is obtained by defining a dual function g off, which if used recursively on the time reversal of [Un] defines a dual risk process. As a consequence, we prove that steady-state probabilities forVncan always be expressed as transient probabilities of the dual risk process. The construction is related to duality of stochastically monotone Markov processes as studied by Siegmund (1976, The equivalence of absorbing and reflecting barrier problems for stochastically monotone Markov processes,Annals of Probability4: 914–924). Our method of proof involves an elementary sample-path analysis. A variety of examples are given, including random walks with stationary increments and two reflecting barriers, reservoir models, autoregressive processes, and branching processes. Finally, general stability issues of the content process are dealt with by expressing them in terms of the dual risk process.
Policies without Memory for the Infinite-Armed Bernoulli Bandit under the Average-Reward Criterion
Authors: Herschkorn Stephen J. , Peköz Erol , Ross Sheldon M.
Published: July 2009

We consider a bandit problem with infinitely many Bernoulli arms whose unknown parameters are i.i.d. We present two policies that maximize the almost sure average reward over an infinite horizon. Neither policy ever returns to a previously observed arm after switching to a new one or retains information from discarded arms, and runs of failures indicate the selection of a new arm. The first policy is nonstationary and requires no information about the distribution of the Bernoulli parameter. The second is stationary and requires only partial information; its optimality is established via renewal theory. We also develop ε-optimal stationary policies that require no information about the distribution of the unknown parameter and discuss universally optimal stationary policies.
Some Results on Interarrival Times of Nonhomogeneous Poisson Processes
Authors: Kochar Subhash C.
Published: July 2009

It is well known that in the case of a Poisson process with constant intensity function the interarrival times are independent and identically distributed, each having exponential distribution. We study this problem when the intensity function is monotone. In particular, we show that in the case of a nonhomogeneous Poisson process with decreasing (increasing) intensity the interarrival times are increasing (decreasing) in the hazard rate ordering sense and they are also jointly likelihood ratio ordered (cf. Shanthikumar and Yao, 1991, Bivariate characterization of some stochastic order relations, Advances in Applied Probability 23: 642–659). This result is stronger than the usual stochastic ordering between the successive interarrival times. Also in this case, the interarrival times are conditionally increasing in sequence and, as a consequence, they are associated. We also consider the problem of comparing two nonhomogeneous Poisson processes in terms of the ratio of their intensity functions and establish some results on the successive number of events from one process occurring between two consecutive occurrences from the second process.
On Queues with Interarrival Times Proportional to Service Times
Authors: Cidon Israel , Guréin Roch , Khamisy Asad , Sidi Moshe
Published: July 2009

We analyze a family of queueing systems where the interarrival timeIn+1between customersnandn+ 1 depends on the service timeBnof customern. Specifically, we consider cases where the dependency betweenIn+1andBnis aproportionalityrelation andBnis an exponentially distributed random variable. Such dependencies arise in the context of packet-switched networks that use rate policing functions to regulate the amount of data that can arrive to a link within any given time interval. These controls result in significant dependencies between the amount of work brought in by customers/packets and the time between successive customers. The models developed in the paper and the associated solutions are, however, of independent interest and are potentially applicable to other environments.

Several scenarios that consist of adding an independent random variable to the interarrival time, allowing the proportionality to be random and the combination of the two are considered. In all cases, we provide expressions for the Laplace-Stieltjes Transform of the waiting time of a customer in the system. Numerical results are provided and compared to those of an equivalent system without dependencies.
Variance Reduction for Simulating Transient GI/G/1 Behavior
Authors: Asmussen Søren , Wang Chia-Li
Published: July 2009

A variety of methods for reducing the variance on Monte Carlo estimators of the expected waiting time Wn of the nth customer in a GI/G/1 queue are studied. The ideas involve Spitzer's identity, importance sampling, and sums with stratified or controlled randomized length.
On the Rate of Convergence of the Ross Approximation to the Renewal Function
Authors: Angus John E. , Hong Xiao
Published: July 2009

Consider a renewal process [N(t), t>0]. For fixed t > 0 and each n ≥ 1, let yn,1, …, Yn,n be independent exponentials each having mean t/n, independent of the renewal process. Ross [2] developed a recursion for the sequence of approximations mn = EN(Yn,1 + … + Yn,n) that converges to m(t)if the renewal function m(·) = EN(·) is continuous at t > 0. In this note, we derive an upper bound on the rate of convergence of this sequence under mild conditions on m near t. Tightness of this bound is discussed in terms of regularity conditions on m.
A Note on Time Monotonicity for Performability Models
Authors: Van Dijk Nico M.
Published: July 2009

For a class of performability models with component-interdependent repairs and breakdowns, monotonicity is shown over time for expected availability measures. This result is of interest to justify steady-state bounds.
Discrete Search for an Intelligent Object: The Leprechaun's Problem
Authors: Berry Scott
Published: July 2009

An optimal search among discrete cells for a Markovian object has been labeled the leprechaun problem. This paper discusses the leprechaun's problem: How should the leprechaun behave in order to maximize the probability of being found? A subjective Bayesian approach is taken in modeling the leprechaun.
Optimal Sequencing in Multiserver Systems
Authors: Pandelis Dimitrios G. , Teneketzis Demosthenis
Published: July 2009

We analyze service systems where Nservers (N > 2) move one at a time along an array of stations to satisfy a known number of requests for service. Processing a request consists of determining the server to satisfy the request. The cost of processing a request is determined by the distance the server that performs the request has to move. We determine qualitative properties of sequencing strategies that minimize the expected cost incurred by the service of all requests when the array of stations is on a circle or an interval.
Optimal Admission Controls for Erlang's Loss System with Phase-Type Arrivals
Authors: Ziedins Ilze
Published: July 2009

It is known that a threshold policy (or trunk reservation policy) is optimal for Erlang's loss system under certain assumptions. This paper examines the robustness of this policy under departures from the standard assumption of Poisson arrivals and shows that the optimal policy has a generalized trunk reservation form.
Analysis of a Discrete-Time Queueing System with a Markov-Modulated input Process and constant service Rate
Authors: Choi Woo-Yong , Jun Chi-Hyuck
Published: July 2009

We propose a new approach to the analysis of a discrete-time queueing system whose input is generated by a Markov-modulated process and whose service rate is constant. Renewal cycles are identified and the system state on each renewal cycle is modeled as a one-dimensional Markov chain.
Overflow Asymptotics for large Communications Systems with General Markov Fluid Sources
Authors: Mandjes Michel
Published: July 2009

This paper is concerned with overflows in queues fed by Markov fluid input. The results are asymptotic in the number of sources; that is, we let the number of users grow large. The main objectives of this study are to characterize both overflow probability and the “most probable way” in which overflow occurs. Applying large deviations techniques, known results (Weiss, 1986, Advances in Applied Probability 18: 506–532) for exponential on-off sources are extended to general Markov fluid input. Successively, zero, small, and large buffers are treated. Finally, results for multiclass input are given.
Information in Continuous Time Decision Models with Many Agents
Authors: Bassan Bruno , Brezzi Monica , Scarsini Marco
Published: July 2009

Several agents with different subjective probabilities make a binary decision at a time determined by a planner. Each agent chooses the action that has the highest probability of success. Given that their probabilities differ, so will their choices. From time 0 until decision time, all the agents are entitled to access the same increasing flow of information. The planner, who gains from having as many agents as possible making the right choice, faces the following tradeoff: the more information she feeds to the agents, the better off they will be in making their decisions, but the less likely they will be to diversify their actions, so the more difficult it will be for her to hedge her positions. The model gives rise to a continuous time optimal stopping problem.
Minimizing the Makespan and Flowtime in Two-Machine Stochastic Open Shops
Authors: Lee Tian-Shyug , Klutke Georgia-Ann
Published: July 2009

In this paper, we present some new results on the makespan and flowtime in a two-parallel machine open shop. A set of n jobs is to be processed on two machines, the order of processing being immaterial. For the case where the machines are identical, and the jobs are nonoverlapping ordered, we show that the sequences that stochastically minimize the makespan are longest processing time first-shortest processing time first (LPT-SPT). Within this class of sequences, we show that the SPT sequence stochastically minimizes the flowtime.
A Method for Computing Double Band Policies for Switching between Two Diffusions
Authors: Avram Florin , Karaesmen Fikri
Published: July 2009

We develop a method for computing the optimal double band [b, B] policy for switching between two diffusions with continuous rewards and switching costs. The two switch levels [b, B] are obtained as perturbations of the single optimal switching point a of the control problem with no switching costs. More precisely, we find that in the case of average reward problems the optimal switch levels can be obtained by intersecting two curves: (a) the function, γ(a), which represents the long-run average reward if we were to switch between the two diffusions at a and switches were free, and (b) a horizontal line whose height depends on the size of the transaction costs. Our semianalytical approach reduces, for example, the solution of a problem recently posed by Perry and Bar-Lev (1989, in Stochastic Analysis and Applications 7: 103–115) to the solution of one nonlinear equation.
Ageing Characteristics of the Weibull Mixtures
Authors: Gupta Pushpa L. , Gupta Ramesh C.
Published: July 2009

It is well known that mixtures of decreasing failure rate (DFR) distributions have the DFR property. A similar result is, of course, not true for increasing failure rate (IFR) distributions. In a recent note, Gurland and Sethuraman (1994,Technometrks36(4): 416–418) presented two examples where mixtures of IFR distributions show DFR property. In this paper, we present a general approach to study the mixtures of distributions and show that the failure rates of the unconditional and conditional distributions cross at most at one point. Mixtures of Weibull distribution with a shape parameter greater than 1 are examined in detail. This also enables us to study the monotonic properties of the mean residual life function of the mixture. Some examples are provided to illustrate the results.
Stochastic Monotonicities in Jackson Queueing Networks
Authors: Lindvall Torgny
Published: July 2009

When starting from 0, a standard M/M/kqueueing process has a second-order stochastic monotonicity property of a strong kind: its increments are stochastically decreasing (the SDI property). A first attempt to generalize this to the Jackson queueing network fails. This gives us reason to reexamine the underlying theory for stochastic monotonicity of Markov processes starting from a zero-point, in order to find a condition on a function of a Jackson network process to have the SDI property. It turns out that the total number of customers at timethas the desired property, if the network is idle at time O. We use couplings in our analysis; they are also of value in the comparison of two networks with different parameters.
Stochastic Inventory Models with Limited Production Capacity and Periodically Varying Parameters
Authors: Aviv Yossi , Federgruen Awi
Published: July 2009

We consider a single-item, periodic-review inventory model with uncertain demands in which each period's production volume is limited by a capacity level. The demand distributions, capacity levels, and cost parameters vary according to a periodic pattern. We prove that modified base-stock policies are optimal for the finite-horizon planning model and for both the infinite-horizon discounted and undiscounted cost criterion. We further show that the optimal base-stock levels can be calculated via a simple but efficient value-iteration method. Finally, we have conducted a comprehensive numerical study to ascertain the efficiency of this solution method as well as various qualitative properties of the performance of capacitated production/inventory systems under periodically varying demand and cost patterns.
A Note on Bounds and Error Bounds for Nonexponential Batch Arrival Systems
Authors: Miyazawa Masakiyo , van Dijk Nico M.
Published: July 2009

This note studies the comparison of finite-buffer and nonexponential batch arrival systems of the form Gx/M/c/c + N with the corresponding systems, with N replaced by N', where N' can be smaller, larger, or infinite. If N' = ∞ the service times can be arbitrarily distributed. Both comparison and error bounds are obtained for performance measures such as the throughput, the idle probability, and the active server distribution. The results are of practical interest to establish computational reductions, either by infinite-space approximation or by reduced finite truncations. Two different proof techniques will be employed: the sample path approach and the Markov reward approach. The comparison of these two techniques is of interest in itself, showing the advantage and disadvantage of each.
Monotonicity of Optimal Performance Measures for Polling Systems
Authors: Van Oyen Mark P.
Published: July 2009

We consider scheduling a single server in a multiclass queue subject to setup times and setup costs. We examine the issue of whether or not reductions in the mean and variance of the setup time distributions can lead to degraded system performance. Provided that setups are reduced according to a stochastically smaller ordering, we show that if an optimal policy is used both for the original system and for the system with reduced setup times, then an improvement in performance is guaranteed. Even in cases for which a truly optimal policy is unknown, idling can be employed to avoid degradation of performance as setup times are cut. We extend this approach to show that system performance is monotonic with respect to service time distributions, switching costs, holding costs, and uniform reductions in the arrival rates. Extensions to sequencedependent setups and job feedback are noted.