bluuebunny/crossref_metadata_2025 huggingface dataset:
Monotonicity of Positive Dependence with Time for Stationary Reversible Markov Chains
Authors: Hu Taizhong , Joe Harry
Published: July 2009

Let (X1, X2) and (Y1, Y2) be bivariate random vectors with a common marginal distribution (X1, X2) is said to be more positively dependent than (Y1, Y2) if E[h(X1)h(X2)] ≥ E[h(Y1)h(Y2)] for all functions h for which the expectations exist. The purpose of this paper is to study the monotonicity of positive dependence with time for a stationary reversible Markov chain [X1]; that is, (Xs, Xl+s) is less positively dependent as t increases. Both discrete and continuous time and both a denumerable set and a subset of the real line for the state space are considered. Some examples are given to show that the assertions established for reversible Markov chains are not true for nonreversible chains.
Waiting Time in M/G/1 Queues with Impolite Arrival Disciplines
Authors: Òzekici Süleyman , Li Jingwen , Chou Fee Seng
Published: July 2009

We consider a queueing system where arriving customers join the queue at some random position. This constitutes an impolite arrival discipline because customers do not necessarily go to the end of the line upon arrival. Although mean performance measures like the average waiting time and average number of customers in the queue are the same for all such disciplines, we show that the variance of the waiting time increases as the arrival discipline becomes more impolite, in the sense that a customer is more likely to choose a position closer to the server. For the M/G/1 model, we also provide an iterative procedure for computing the moments of the waiting time distribution. Explicit computational formulas are derived for an interesting special model where a customer joins the queue either at the head or at the end of the line.
Maximal Profit Dimensioning and Tariffing of Loss Networks
Authors: Bean N. G. , Taylor P. G.
Published: July 2009

In this paper we present a unified approach to the optimal dimensioning and tariffing of loss networks. In our formulation the optimum is chosen to maximize the profit for the company operating the loss network. We assume that the operating company has the flexibility to determine tariffs and grade of service — although both of these can possibly be subject to regulatory constraints. The fact that the tariffing may affect demand and, hence, the dimensioning makes it essential that the operating company include the tariff/demand trade-off in determining the optimal way to dimension the loss network. A consequence of our formulation is that the optimal tariff structure has a particularly simple form, with the optimal tariff on a particular route separating into a term related to the tariff/demand trade-off on that route and a term that reflects the cost of the circuits used by the route.
On Queueing Networks with Signals and History-Dependent Routing
Authors: Chao Xiuli , Pinedo Michael
Published: July 2009

This paper extends product form results for queueing networks with signals to allow history-dependent routing. The signals in these models carry information to nodes and induce multiple customers to move simultaneously within the network. Two models are studied in this paper. In the first one we assume that routing probabilities of a departing customer from a given class of nodes depend on the amount of service just received by the customer and whether its departure is the result of an actual service completion or the result of an arriving signal. In the second model we assume that the routing probabilities of a customer depend on the number of times this customer's service has been interrupted by signals in the past as well as the cause of its departure. We show that both models possess simple product form solutions. These results provide a new dimension in modeling and analyzing practical systems.
An M/G/l Vacation Model with Two Service Modes
Authors: Nishimura Shoichi , Jiang Yong
Published: July 2009

Consider an M/G/1 type queueing system with two service modes: regular speed and high speed. The service rule is characterized by two switch-over levels nR and nH, where nR and nH are given integers with 0 ≤ nH < nR. The server switches from regular speed mode to high speed mode when the number of customers present at a service completion epoch is equal to or larger than nR and switches from high speed mode to regular speed mode when the number of customers present decreases to nH. A key feature of the model is that the server takes a vacation for setup operations before a new service mode is available. This paper derives for the general model an expression for the generating function of the equilibrium queue-length distribution in terms of the switch-over levels. Two unknown parameters appear in the generating functions. Using a recursive method, we solve these unknown parameters and obtain a computationally tractable algorithm for the steady-state probabilities.
Maximum Values in Queueing Processes
Authors: Berger Arthur W. , Whitt Ward
Published: July 2009

Motivated by extreme-value engineering in service systems, we develop and evaluate simple approximations for the distributions of maximum values of queueing processes over large time intervals. We provide approximations for several different processes, such as the waiting times of successive customers, the remaining workload at an arbitrary time, and the queue length at an arbitrary time, in a variety of models. All our approximations are based on extreme-value limit theorems. Our first approach is to approximate the queueing process by one-dimensional reflected Brownian motion (RBM). We then apply the extremevalue limit for RBM, which we derive here. Our second approach starts from exponential asymptotics for the tail of the steady-state distribution. We obtain an approximation by relating the given process to an associated sequence of i.i.d. random variables with the same asymptotic exponential tail. We use estimates of the asymptotic variance of the queueing process to determine an approximate number of variables in this associated i.i.d. sequence. Our third approach is to simplify GI/G/1 extreme-value limiting formulas in Iglehart [25] by approximating the distribution of an idle period by the stationary-excess distribution of an interarrival time. We use simulation to evaluate the quality of these approximations for the maximum workload. From the simulations we obtain a rough estimate of the time when the extreme-value limit theorems begin to yield good approximations.
Sensitivity Analysis for Monte Carlo Simulation of Option Pricing
Authors: Fu Michael C. , Hu Jian-Qlang
Published: July 2009

Monte Carlo simulation is one alternative for analyzing options markets when the assumptions of simpler analytical models are violated. We introduce techniques for the sensitivity analysis of option pricing, which can be efficiently carried out in the simulation. In particular, using these techniques, a single run of the simulation would often provide not only an estimate of the option value but also estimates of the sensitivities of the option value to various parameters of the model. Both European and American options are considered, starting with simple analytically tractable models to present the idea and proceeding to more complicated examples. We then propose an approach for the pricing of options with early exercise features by incorporating the gradient estimates in an iterative stochastic approximation algorithm. The procedure is illustrated in a simple example estimating the option value of an American call. Numerical results indicate that the additional computational effort required over that required to estimate a European option is relatively small.
Scheduling Independent Tasks to Minimize the Makespan on Identical Machines
Authors: Bruno John , Coffman Edward G. , Downey Peter
Published: July 2009

In this paper we consider scheduling n tasks on m parallel machines where the task processing times are i.i.d. random variables with a common distribution function F. Scheduling is done by an a priori assignment of tasks to machines. We show that if the distribution function F is a Pólya frequency function of order 2 (decreasing reverse hazard rate) then the assignment that attempts to place an equal number of tasks on each machine achieves the stochastically smallest makespan among all assignments. The condition embraces many important distributions, such as the gamma and truncated normal distributions. Assuming that the task processing times have a common density that is a Pólya frequency function of order 2 (increasing likelihood ratio), then we find that flatter schedules have stochastically smaller makespans in the sense of the “joint” likelihood ratio.
Ordering of Tandem Constant-Service Stations to Minimize In-Process Stock Cost
Authors: Winch Janice Kim , Avi-Itzhak Benjamin
Published: July 2009

We study tandem ordering of constant-service stations with unlimited buffers where service at each station adds a certain value to the job. With the goal of minimizing the total expect value of the jobs in the system, we provide conditions under which some particular orderings are optimal and describe a heuristic that finds a near-optimal order for stations of arbitrary service lengths and added values.
A Sequential Assignment Match Process with General Renewal Arrival Times
Authors: David Israel
Published: July 2009

This work studies sequential assignment match processes, in which random offers arrive sequentially according to a renewal process, and when an offer arrives it must be assigned to one of given waiting candidates or rejected. Each candidate as well as each offer is characterized by an attribute. If the offer is assigned to a candidate that it matches, a reward R is received; if it is assigned to a candidate that it does not match, a reward r ≤ R is received; and if it is rejected, there is no reward. There is an arbitrary discount function, which corresponds to the process terminating after a random lifetime. Using continuoustime dynamic programming, we show that if this lifetime is decreasing in failure rate and candidates have distinct attributes, then the policy that maximizes total expected discounted reward is of a very simple form that is easily determined from the optimal single-candidate policy. If the lifetime is increasing in failure rate, the optimal policy can be recursively determined: a solution algorithm is presented that involves scalar rather than functional equations. The model originated in the study of optimal donor-recipient assignment in live-organ transplants. Some other applications are mentioned as well.
Stability of Polling Networks with State-Dependent Server Routing
Authors: Schaβberger R.
Published: July 2009

The polling network considered here consists of a finite collection of stations visited successively by a single server according to a state-dependent routing scheme. At every visit of a station, a possibly random number of customers are served and depart from the network thereafter. The server takes a possibly random time to walk from one station to the next. The network receives groups of customers at Poisson instants. These customers are distributed randomly over the stations and wait until served. A necessary condition for stability is derived, which proves to be also sufficient in certain special cases. Such cases include a starlike network and a ringlike one with a greedy service policy. Mathematically, positive recurrence of a Markov chain is studied.
On the Modular Value and Fractional Part of a Random Variable
Authors: Herschkorn Stephen J.
Published: July 2009

Let X be a random variable with characteristic function ϕ. In the case where X is integer-valued and n is a positive integer, a formula (in terms of ϕ) for the probability that n divides X is presented. The derivation of this formula is quite simple and uses only the basic properties of expectation and complex numbers. The formula easily generalizes to one for the distribution of X mod n. Computational simplifications and the relation to the inversion formula are also discussed; the latter topic includes a new inversion formula when the range of X is finite.

When X may take on a more general distribution, limiting considerations of the previous formulas suggest others for the distribution, density, and moments of the fractional part X — [X]. These are easily derived using basic properties of Fourier series. These formulas also yield an alternative inversion formula for ϕ when the range of X is bounded.

Applications to renewal theory and random walks are suggested. A by-product of the approach is a probabilistic method for the evaluation of infinite series.
Limits and Approximations for the Busy-Period Distribution in Single-Server Queues
Authors: Abate Joseph , Whitt Ward
Published: July 2009

Limit theorems are established and relatively simple closed-form approximations are developed for the busy-period distribution in single-server queues. For the M/G/l queue, the complementary busy-period c.d.f. is shown to be asymptotically equivalent ast→ ∞ to a scaled version of the heavy-traffic limit (obtained asp→ 1), where the scaling parameters are based on the asymptotics ast→ ∞. We call this the asymptotic normal approximation, because it involves the standard normal c.d.f. and density. The asymptotic normal approximation is asymptotically correct ast→ ∞ for each fixedpand asp→ 1 for each fixedtand yields remarkably good approximations for times not too small, whereas the direct heavy-traffic (p→ 1) and asymptotic (t→ ∞) limits do not yield such good approximations. Indeed, even the approximation based on three terms of the standard asymptotic expansion does not perform well unlesstis very large. As a basis for generating corresponding approximations for the busy-period distribution in more general models, we also establish a more general heavy-traffic limit theorem.
A Simple Performability Estimate for Jackson Networks with an Unreliable Output Channel
Authors: van Dijk Nico M.
Published: July 2009

Open Jackson networks are studied in which departures can be blocked such as due to a breakdown of an output channel. A simple performance estimate is provided along with an explicit error bound.
On Suboptimal Policies in Multiclass Tandem Models
Authors: Hordijk Arie , Koole Ger
Published: July 2009

We study two single-server multiclass systems in tandem. As simple optimal policies exist only in special cases, our objective is to study simple policies that perform close to optimality. For one such policy, which is based on the μc rule, we prove that it is optimal in an asymptotic sense. Numerical work comparing this policy with the optimal one is also supplied.
A Full-Information Best-Choice Problem with Allowance
Authors: Tamaki Mitsushi , Shanthikumar J. George
Published: July 2009

This paper considers a variation of the classical full-information best-choice problem. The problem allows success to be obtained even when the best item is not selected, provided the item that is selected is within the allowance of the best item. Under certain regularity conditions on the allowance function, the general nature of the optimal strategy is given as well as an algorithm to determine it exactly. It is also examined how the success probability depends on the allowance function and the underlying distribution of the observed values of the items.
Bicriterion Optimization of an M/G/1 Queue with A Removable Server
Authors: Feinberg Eugene A. , Kim Dong J.
Published: July 2009

This paper studies bicriterion optimization of an M/G/1 queue with a server that can be switched on and off. One criterion is an average number of customers in the system, and another criterion is an average operating cost per unit time. Operating costs consist of switching and running costs. We describe the structure of Pareto optimal policies for a bicriterion problem and solve problems of optimization of one of these criteria under a constraint for another one.
The Availability of Inspected Systems Subject to Random Deterioration
Authors: Klutke Georgia-Ann , Wortman Martin A. , Ayhan Hayriye
Published: July 2009

This paper examines the availability of an inspected system where the rate of deterioration is governed by an exogenous random environment. We develop a qualitative result that exposes the relationship among remaining life, deterioration, and repairs. This result requires no specific distributional assumptions. We use this result in developing a simple bound on stationary availability. We investigate these relationships numerically for a Markovian system and provide insights useful to practitioners in selecting an inspection process that guarantees a target availability.
Optimal Discrete Adjustments for Short Production Runs
Authors: Wiel Scott A. Vander
Published: July 2009

Diameter measurements on successive metal hubs from a machining operation are modeled using a random walk with observation error and linear drift corresponding to tool wear. After producing and measuring a hub, the depth of the cutting tool on the lathe can be adjusted in integer multiples of 0.0001 inches. How should the tool be adjusted?

An optimal discrete adjustment strategy is derived assuming that the lathe automatically corrects for deterministic tool wear. The objective is to minimize expected run costs proportional to the sum of squared diameter deviations from a target plus fixed charges for manual tool adjustments. The optimal strategy makes no manual adjustment if an estimate of the process mean is near target. Otherwise, an adjustment is made to return the estimated mean as near to target as possible within the adjustment resolution.

The region where no adjustments are made widens near the end of the production run where adjustments have only short-term impact. The region converges as the number of remaining periods increases. Plots of expected run costs show that the extra cost of discreteness is small at high resolution but is substantial when the adjustment grid is coarse.
On a New Approach to the Solution of the Nonlinear Filtering Equation of Jump Processes
Authors: Fan Kaisheng
Published: July 2009

An implementable on-line approach to solve the nonlinear filtering equation for a partially observed system in which both the state and observation processes are jump processes is presented. By making use of the special structure of jump processes, the new method allows us to obtain the solution of the resulting nonlinear filtering equation from solving a linear system of ordinary differential equations and a linear system of algebraic equations recursively and via a simple normalization procedure.
Efficient Simulation via Coupling
Authors: Glynn Peter W. , Wong Eugene W.
Published: July 2009

This paper is concerned with how coupling can be used to enhance the efficiency of a certain class of terminating simulations, in Markov process settings in which the stationary distribution is known. We are able to theoretically establish that our coupling-based estimator is often more efficient than the naive estimator. In addition, we discuss extensions of our methodology to Markov process settings in which conventional coupling fails and show (for Doeblin chains) that knowledge of the stationary distribution is sometimes unnecessary.
An Improvement to the Total Hazard Method for System Reliability Simulation
Authors: Cancela Héctor , Khadiri Mohamed El
Published: July 2009

The total hazard Monte Carlo estimator has been successfully applied to estimate the unreliability of multicomponent systems. Nevertheless, there are some cases where it is less efficient than the crude estimator. We propose in this paper a simple modification that improves the performance of the total hazard estimator.
Invariant Probabilities with Geometric Tail
Authors: Lasserre Jean B. , Tijms Henk
Published: July 2009

We present necessary and suffi2ient Foster-type conditions for a countable state Markov chain to have an invariant probability with at least a geometric tail. These conditions are obtained by using a generalized Farkas Theorem in Linear Algebra. The purpose of this note is also to pose an interesting and important research problem that is still largely open.
On Optimal and Equilibrium Retrial Rates in a Queueing System
Authors: Hassin Refael , Haviv Moshe
Published: July 2009

We discuss socially optimal and equilibrium retrial rates in a single-server queueing model. We extend known results, compare the two rates, and suggest ways to impose tolls on retrials (or rebates for waiting) in order to equate the equilibrium rate with the socially optimal one.
Optimal Scheduling of Multiclass Stochastic Systems
Authors: Righter Rhonda
Published: July 2009

We study the problem of scheduling multiclass parallel server queues where the cost for each job is a general class-dependent function of the job's completion time and a second random variable. We characterize the structure of the optimal policy under fairly general conditions on the random variables.
Fixed Point Approximations for Retrial Networks
Authors: Takahara Glen K.
Published: July 2009

Fixed point approximations for blocking probabilities arising from a link independence assumption and a light retrial rate limit are derived for circuitswitched network models that incorporate caller retrials. This approximation is a generalization of the well-known reduced load approximation for loss networks, which retains much of the versatility of this approximation.
The Workload in the M/G/1 Queue with Work Removal
Authors: Boucherie Richard J. , Boxma Onno J.
Published: July 2009

We consider an M/G/1 queue with the special feature of additional negative customers, who arrive according to a Poisson process. Negative customers require no service, but at their arrival a stochastic amount of work is instantaneously removed from the system. We show that the workload distribution in this M/G/1 queue with negative customers equals the waiting time distribution in a GI/G/1 queue with ordinary customers only; the effect of the negative customers is incorporated in the new arrival process.
Optimal Server Allocation to Parallel Queues with Finite-Capacity Buffers
Authors: Wasserman K. M. , Bambos Nicholas
Published: July 2009

In this paper, we study the problem of dynamic allocation of a single server to parallel queues with finite-capacity buffers. The arrival processes are mutually independent, equal rate Poisson processes, and the service times are independent and identically distributed random variables with an arbitrary distribution. We are interested in characterizing the allocation policy that stochastically minimizes the number of customers lost due to buffer overflows. Using a coupling argument, we establish the optimality of the Fewest-Empty-Spaces policy, which allocates the server to the queue with the fewest empty buffer spaces, within the class of nonpreemptive and nonidling policies. The result extends to the class of preemptive policies, if the service times are exponentially distributed. We also briefly discuss the allocation problem under more general statistical assumptions on the arrival processes.
Batch Routing Queueing Networks with Jump-Over Blocking
Authors: Boucherie Richard J.
Published: July 2009

This paper shows that the equilibrium distribution of a queueing network with batch routing continues to be of product form if a batch that cannot enter its destination — for example, as a consequence of capacity constraints — immediately triggers a new transition that takes up the whole batch.
A Simple Relation between the Pattern Probability and the Rate of False Signals in Control Charts
Authors: Hwang Frank K. , Trietsch Dan
Published: July 2009

A special pattern of consecutive points on a control chart often suggests that the process is out of control due to a special cause. Usually, the probability of such a pattern is not difficult to calculate, but its relation to the rate of a false signal in a control chart is unclear. In this paper we give such a relation for a wide class of patterns that includes six of the eight patterns of special cause discussed in the AT&T Statistical Quality Control Handbook (1958). We derive a surprisingly simple formula for the rate of a false signal in terms of the pattern probability and use this result to improve on the test proposed in the handbook. We also use this formula to give a simple proof of a result of Wolfowitz (1944, Annals of Mathematical Statistics 15: 163–172) and Olmstead (1945, Annals of Mathematical Statistics 17: 24–33) on the monotone sequence. Finally, we give an approximation of the rate of a false signal for another wide class of patterns that covers the two remaining patterns of special cause in the AT&T handbook.
First-Passage Distributions of Bidimensional Processes
Authors: Lefebvre Mario
Published: July 2009

Bidimensional processes defined by dx(t) = ρ(x, y) dt and dy(t) = f(y) dt + σ(y) dW(t), where W(t) is a Wiener process, are considered. Let T(x, y, ξ) = inf[t ≥ 0: x(t] = ξ| x(0) = x, y(0) = y). Explicit expressions for the moment generating function of T(x, y, 0) and for the characteristic function of y(T(x, y, ξ)) are obtained in two special cases. The method of similarity solutions is used. Applications to optimal control problems are presented.
Diffusion Limits for Open Networks of Finite-Buffer Queues
Authors: Bardhan Indrajit
Published: July 2009

This paper presents diffusion limits for congestion in networks of finite-buffer queues. We consider both loss networks, such as those in communication systems, and networks with manufacturing blocking. In both cases, the number in system process, under conditions of approximate balance under heavy traffic and appropriate scaling of buffers, is shown to behave like a multidimensional Brownian motion reflected to stay within a rectangle in the positive orthant. The two limits differ in directions of reflection off the faces representing full buffers. The limits suggest possible diffusion approximations for finitebuffer networks.
On the Analysis of the Discrete-Time Geom(n)/G(n)/1/N Queue
Authors: Chaudhry M. L. , Gupta U. C.
Published: July 2009

In this paper, we discuss the late-arrival discrete-time Geom(n)/G(n)/1/N queue with state-dependent arrival and service processes. Whereas the interarrival times are geometrically distributed, service times are conditioned on the system length at the moment of service initiation. The model has wide applications in computer-communications systems, broadband integrated service digital network, asynchronous transfer mode, and so on. The analysis of the model has been carried out, using the supplementary variable technique, and the final results are presented in the form of recursive equations that can be easily implemented on any personal computer. In addition, relations among state probabilities at prearrival, postdeparture, and random epochs have been developed. To demonstrate the effectiveness of our method, some numerical examples have been presented for service-time distributions such as geometric, deterministic, arbitrary, and mixed. The results obtained in this paper should be found useful by system designers who wish to control the congestion by adjusting the service rate if the arrival traffic changes.
Bayes' Estimation of the Number of Component Processes of a Superimposed Process
Authors: Yoshida Olga S. , Leite José G. , Bolfarine Heleno
Published: July 2009

We consider Bayes' estimation of the number of independent homogeneous Poisson processes of a superimposed process with unknown rates. The estimation of the total rate of the undetected processes is also considered. Exact posterior distributions are obtained. Monotonicity and asymptotic properties of the Bayes' estimator are also discussed.
Universal Data Compression Algorithm Based on Approximate String Matching
Authors: Sadeh Ilan
Published: July 2009

A practical source coding scheme based on approximate string matching is proposed. It is an approximate fixed-length string matching data compression combined with a block-coder based on the empirical distribution. A lemma on approximate string matching, which is an extension of the Kac Lemma, is proved. It is shown, based on the lemma, that the deterministic algorithm converts the stationary and ergodic source, u, into an output process v, and under the assumption that v is a stationary process, after the scheme has run for an infinite time, the optimal compression ratio R(D) is achieved. This reduces the problem of the universal lossy coder to the proof of stationarity of the output process ν in the proposed algorithm. The main advantages of the proposed method are the asymptotic sequential behavior of the encoder and the simplicity of the decoder.
Convergence of Departures in Tandem Networks of·/GI/ ∞ Queues
Authors: Prabhakar B. , Mountford T. S. , Bambos N.
Published: July 2009

We consider an infinite series of independent and identical -/GI/∞ queues fed by an arbitrary stationary and ergodic arrival process,A1. LetAibe the arrival process to theith node, and let νibe the law ofAi. Denote by(·) the input–output map of the ·/GI/∞ node; that is, νi+1=(νi). It is known that the Poisson process is a fixed point for. In this paper, we are interested in the asymptotic distribution of the departure process from thenth node, νn+1=n(ν1), asn∞. Using couplings for random walks, this limiting distribution is shown to be either a Poisson process or a stationary ν-Poisson process, depending on the joint distribution ofA1and the service process. This generalizes a result of Vere-Jones (1968,Journal of the Royal Statistical Society, Series B30: 321–333) and is similar in flavor to Mountford and Prabhakar (1995,Annals of Applied Probability5(1): 121–127), where Poisson convergence is established for departures from a series of exponential server queues using coupling methods.
Generalizing the Pollaczek-Khintchine Formula to Account for Arbitrary Work Removal
Authors: Jain Gautam , Sigman Karl
Published: July 2009

Recently, a Pollaczek-Khintchine-like formulation for M/G/l queues with disasters has been obtained. A disaster is said to occur if a negative arrival causes all the customers (and therefore work) to depart from the system immediately. This study generalizes this result further, as it is shown to hold even when negative arrivals cause only part of the work to be demolished. In other words, an arbitrary amount of work, following a known distribution, is allowed to be removed at a negative event. Under these circumstances, a general approach for obtaining the Pollaczek–Khintchine Formula is proposed, which is then illustrated via several examples. Typically, it is seen that the formulainvolves certain parameters that are not explicitly known. The formula itself is made possible due to the number in system being geometric under preemptive last in-first out discipline.
Estimating the Error of a Permutational Central Limit Theorem
Authors: Chao Chern-Ching , Zhao Lincheng , Liang Wen-Qi
Published: July 2009

Motivated by two measures of presortedness, number of runs and oscillation of a permutation, related to the sorting problem, we derive an error bound for normal approximation to the distribution ofHere, αij's are given real numbers and π is a uniformly distributed random permutation of {l,…,n}. The derivation is based on Stein's method.
Predictive Distributions in the Presence of Measurement Errors
Authors: Guttman Irwin , Menzefricke Ulrich
Published: July 2009

We consider a hierarchical linear regression model where the regression parameters for the units have a multivariate normal distribution whose parameters are unknown. Several replications are available for each unit. The design matrices for the units need not be the same. A complicating feature of the model is that each observation is subject to measurement error. The objective of the paper is to derive the predictive distribution of the “true” value of the response at a given design point. A Bayesian treatment is given to the problem. In addition to standard prior distributions, other prior distributions are considered. The calculations are done with the Gibbs sampler. An example is discussed in detail.
Approximating a Cumulative Distribution Function by Generalized Hyperexponential Distributions
Authors: Ou Jihong , Li Jingwen , Özekici Süleyman
Published: July 2009

Recent developments in stochastic modeling show that enormous analytical advantages can be gained if a general cumulative distribution function (c.d.f.) can be approximated by generalized hyperexponential distributions. In this paper, we introduce a procedure to explicitly construct such approximations of an arbitrary c.d.f. Although our approach can be used in different types of stochastic models, the main motivation comes from queueing theory in obtaining approximations of the idle-period distribution and other performance measures in GI/G/1 queues.
Importance Sampling of Test Cases in Markovian Software Usage Models
Authors: Gutjahr Walter J.
Published: July 2009

Recently, some authors have suggested usage models of Markov type as a technique of specifying the estimated operational use distribution of a given program. A main purpose of such models is the derivation of random test cases allowing unbiased estimates on the (un)reliability of the program in its intended environment. In this article, we show that by a shift of the transition probabilities of the Markov chain corresponding to such a model, prior information on the errorjproneness of single-program operations can be taken into account. An unbiased unreliability estimator with reduced variance is obtained. Furthermore, it is shown that minimization of the variance leads to a special stochastic optimization problem that can be demonstrated to be convex, such that efficient solution techniques apply. Some related questions are also treated in a more general, non-Markovian framework.
The Improved Estimation of σ in Quality Control, Revisited
Authors: Angus John E.
Published: July 2009

Recently, Derman and Ross (1995, An improved estimator of a in quality control, Probability in the Engineering and Informational Sciences 9: 411–415) derived an estimator of the standard deviation in the standard quality control model and showed that it had smaller mean squared error than the usual estimator. The new estimator was also shown to be consistent even when the underlying distribution deviates from normality, unlike the usual estimator. In this note, the mean squared error is further improved via shrinkage of the Derman-Ross estimator, and a consistent minimum variance unbiased estimator is presented. Finally, by making use of additional subgroup statistics, a minimum variance unbiased estimator is derived and further improved via shrinkage.
When Is a Renewal Process Convexly Parameterized in Its Mean Parameterization?
Authors: Lynch James D.
Published: July 2009

The convex (concave) parameterization of a generalized renewal process is considered in this paper. It is shown that if the interrenewal times have log concave distributions or have log concave survival functions (i.e., an increasing failure rate distribution), then the renewal process is convexly (concavely) parameterized in its mean parameterization.
On Optimal Ammunition Usage When Hunting Fleeing Targets
Authors: Sato Masahiro
Published: July 2009

A hunter hunts over a planning horizon t with i bullets. The distribution of the value of targets appearing and the probability of a bullet hitting are known. Encountering a target of value w, he has a choice of retiring from hunting completely, shooting a single bullet, or moving on to the next period to find another target. If he retires, he immediately obtains a terminal reward dependent on the remaining periods and bullets. If he fires and succeeds, he obtains the reward w and decides whether to retire or move on to the next epoch. If he misses and the target remains stationary, he must immediately decide whether to fire an additional bullet, retire, or move on to the next period. The objective in this paper is to examine the optimal decision rules that would maximize the total expected reward. We reveal that the optimal decision rule for firing is not always monotone in the number of remaining bullets and the optimal decision rule for retirement may become possibly the following form. It is better to continue hunting than retire, only if the hunter has neither too few bullets nor too many.
Scheduling Jobs That Are Subject to Deterministic Due Dates and Have Deteriorating Expected Rewards
Authors: Ishikida Takashi , Wan Yat-wah
Published: July 2009

A single server processes jobs that can yield rewards but expire on predetermined dates. Expected immediate rewards from each job are deteriorating. The instance is formulated as a multiarmed bandit problem, and an index-based scheduling policy is shown to maximize the expected total reward.
Optimal Scheduling on Parallel Processors with Precedence Constraints and General Costs
Authors: Liu Zhen , Righter Rhonda
Published: July 2009

We consider preemptive and nonpreemptive scheduling of partially ordered tasks on parallel processors, where the precedence relations have an intervalorder, an in-forest, or a uniform out-forest structure. Processing times of tasks are random variables with an increasing in likelihood ratio distribution in the nonpreemptive case and an exponential distribution in the preemptive case. We consider a general cost that is a function of time and of the uncompleted tasks and show that the most successors (MS) policy stochastically minimizes the cost function when it satisfies certain agreeability conditions. A consequence is that the MS policy stochastically minimizes makespan, weighted flowtime, and the weighted number of late jobs.
Scheduling Two-Point Stochastic Jobs to Minimize the Makespan on Two Parallel Machines
Authors: Borst Sem , Bruno John , Coffman E. G. , Phillips Steven
Published: July 2009

Simple optimal policies are known for the problem of scheduling jobs to minimize expected makespan on two parallel machines when the job running-time distribution has a monotone hazard rate. But no such policy appears to be known in general. We investigate the general problem by adopting two-point running-time distributions, the simplest discrete distributions not having monotone hazard rates. We derive a policy that gives an explicit, compact solution to this problem and prove its optimality. We also comment briefly on first-order extensions of the model, but each of these seems to be markedly more difficult to analyze.
Finite-Time Behavior of Slowly Cooled Annealing Chains
Authors: Desai Madhav P. , Rao Vasant B.
Published: July 2009

We present results on the finite-time behavior of the discrete-time, finite-space version of the simulated annealing algorithm. The asymptotic and finite-time behavior of the annealing algorithm under slow cooling will be shown to depend on the largest eigenvalue of a certain matrix. To illustrate the utility of our results, we study the slowly cooled annealing algorithm applied to the maximum matching problem and demonstrate a polynomial randomized approximation property of the algorithm.
Line Reversibility of Multiserver Systems
Authors: Cheng Dinah W.
Published: July 2009

The line reversibility property of a two-stage multiserver system with manufacturing blocking has previously been established using a duality argument between the blocked state and the idle state. In this paper, we provide counterexamples that show this argument does not apply to systems with more than two stages. A focus of this paper is to provide a new proof for the result. Our argument is based on the duality between the service initiation and the service completion events.
Comparison Results for Markov-Modulated Recursive Models
Authors: Bäuerle Nicole , Rieder Ulrich
Published: July 2009

We consider a general discrete-time stochastic recursive model that is influenced by an external Markov chain. Our aim is to investigate the effect that the transition matrix of the external process has on the system states of the model. To answer this question, we use new stochastic ordering concepts. Especially interesting are the results for infinite-stage Markov-modulated models. We illustrate our main results by three applications: an inventory model, a consumption model, and a queueing model for a time division multiplexing system.
Optimal Control for an Mx/G/1 Queue with Two Operation Modes
Authors: Dudin Alexander
Published: July 2009

The controlled Mx/G/1-type queueing model with two modes of operation is considered. The modes are characterized by different service time distributions and input rates. The switchover times are imposed in the model. The embedded stationary queue-length distribution and the explicit dependence of operation criteria on switchover levels are derived.
A Note on Negative Customers, GI/G/1 Workload, and Risk Processes
Authors: Boucherie Richard J. , Boxma Onno J. , Sigman Karl
Published: July 2009

This note illustrates that a combination of the approach in our previous papers (Boucherie and Boxma, 1996,Probability in the Engineering and Informational Sciences10: 261–277; Jain and Sigman, 1996,Probability in the Engineering and Informational Sciences10: 519–531) directly leads to a Pollaczek-Khintchine form for the workload in a queue with negative customers. The same technique is also applied to risk processes with lump additions.
The Downs-Thomson Effect in a Markov Process
Authors: Calvert Bruce
Published: July 2009

Suppose customers pass through a network of two queues in parallel. A statedependent routing policy gives individuals their quickest journey. The Downs-Thomson effect is any increase in the long-run expected journey time caused by an increase in the service rates. This effect may occur.
Estimation of an Exponential Distribution
Authors: Brown Mark
Published: July 2009

Consider a samplefrom an exponential distribution with unknown parameter θ From the sample, we wish to estimate the entire distribution,(Borel sets). If an estimatoris used for, we are concerned with proximity ofto, under total variation distance,the maximum likelihood estimate of θ, define, where, the 1 – (a/2) percentile from the standard normal. Then,. The preceding approximation to the 1 — α percentile ofis very accurate even for smallnWe also consider the problem of obtaining a confidence band for the survival function, possessing minimal maximum width. Finally, a class of estimators ofis compared to the maximum likelihood estimator from the viewpoint of total variation distance loss function.
A Double Band Control Policy of a Brownian Perishable Inventory System
Authors: Perry David
Published: July 2009

The blood bank system is a typical example of a perishable inventory system. The commodity arrival and customer demand processes are stochastic. However, the stored items have a constant lifetime. In this study, we introduce a diffusion approximation to this system. The stock level is represented by the amount of items arriving during the age of the oldest item; it is assumed to fluctuate as an alternating two-sided regulated Brownian motion between barriers 0 and 1. Hittings of level 0 are outdatings and hittings of level 1 are unsatisfied demands. Also, there are two predetermined switchover levels, a and b, with 0 ≤ a < b ≤ 1. Whenever the stock level process upcrosses level b, the controller generates a switch in the drift from γ = γ0 to γ = γ1, while downcrossings of level a generate switches from γ1 to γ0. A useful martingale is introduced for analyzing the stationary law of the controlled process as well as the total expected discounted cost.
On the (S – 1, S) Stock Model for Renewal Demand Processes:Poisson's poison
Authors: Smith Marcel A. J. , Dekker Rommert
Published: July 2009

In the standard (S – 1, S) stock model, demand follows a Poisson process. It has appeared to many stock analysts that this model causes an abundance of stock in reality. In case demand is caused by failure or is derived from another process, demand typically doesnotfollow a Poisson process. In this paper, we discuss the (S – 1, S) stock model where demand follows a renewal process and the lead time is deterministic. Moreover, we will extend this to compound renewal demand and multi-echelon inventory systems. Our goal is to show the severe influence of taking the Poisson process for granted.
Equilibrium Strategies for Processor Sharing and Random Queues with Relative Priorities
Authors: Haviv Moshe , van der Wal Jan
Published: July 2009

We consider a memoryless single-server queue in which users can purchase relative priority so as to reduce their expected waiting costs, which are linear with time. Relative priority is given in proportion to a price paid by customers present in the system. For two service disciplines, (weighted) processor sharing and (weighted) random entrance, we find the unique pure and symmetric Nash equilibrium price paid by the customers.
Branch and Bound Algorithm for Ordering of Tandem Constant-Service Stations
Authors: Winch Janice Kim
Published: July 2009

We study tandem ordering of constant-service stations with unlimited buffers and arbitrary arrival process where service at each station adds a certain value to the job. The goal is to order the stations such that the total expected value of the jobs in the system or, equivalently, the work-in-process inventory cost is minimized. Assuming that the added value–service length ratio increases with the service length, we provide a branch and bound method that finds an optimal order.
An Approximation of the Interval Availability Distribution
Authors: Smith Marcel A. J.
Published: July 2009

In this paper, we consider the interval availability distribution of a two-state single unit. We fit the interval availability distribution directly to a beta distribution, such that the probability of nil and a 100% availability is correct as well as the expectation and the variance. The method is fast and easy to implement and gives good results.
Modeling Stochastic Lead Times in Multi-Echelon Systems
Authors: Diks E. B. , van der Heijden M. C.
Published: July 2009

In many multi-echelon inventory systems, the lead times are random variables. A common and reasonable assumption in most models is that replenishment orders do not cross, which implies that successive lead times are correlated. However, the process that generates such lead times is usually not well defined, which is especially a problem for simulation modeling. In this paper, we use results from queuing theory to define a set of simple lead time processes guaranteeing that (a) orders do not cross and (b) prespecified means and variances of all lead times in the multiechelon system are attained.
An Analysis of Poisson Moving-Average Processes
Authors: McCormick William P. , Park YouSung
Published: July 2009

Al-Osh and Alzaid (1988,Statistical Papers29: 281–300) introduced a class of Poisson moving-average processes. In this paper, we analyze certain properties of such models. In particular, we show that the model has the property of time reversibility. Regression properties of the model are also given. Furthermore, we determine the asymptotic limit distribution for the sample autocovariance function and establish the asymptotic validity of a bootstrap approximation.
Multiscale Stochastic Approximation for Parametric Optimization of Hidden Markov Models
Authors: Bhatnagar Shalabh , Borkar Vivek S.
Published: July 2009

A two–time scale stochastic approximation algorithm is proposed for simulation-based parametric optimization of hidden Markov models, as an alternative to the traditional approaches to “infinitesimal perturbation analysis.” Its convergence is analyzed, and a queueing example is presented.
An Alternative Proof for a known Result of Noncentral Wishart Distribution
Authors: Lee Tian-Shyug , Chang Kwang-Chow
Published: July 2009

In the theory of multivariate statistics, it is well known that given a sample of n independent p-variate normally distributed random vectors with a common variance-covariance matrix, if at least one of the n vectors has nonzero means, then the sum of squares about the sample mean of the n vectors has a noncentral Wishart distribution. However, a detailed proof for this known result is rarely found in literature. In this paper, we present a formal and complete proof for the well-known result together with an example of its applications.