bluuebunny/crossref_metadata_2025 huggingface dataset:
The Subgroup Algorithm for Generating Uniform Random Variables
Authors: Diaconis Persi , Shahshahani Mehrdad
Published: July 2009

We suggest a simple algorithm for Monte Carlo generation of uniformly distributed variables on a compact group. Example include random permutations, Rubik's cube positions, orthogonal, unitary, and symplectic matrices, and elements ofGLnover a finite field. the algorithm reduces to the “standard” fast algorithm when there is one, but many new example are included.
Gibbs' Measures on Combinatorial Objects and the Central Limit Theorem for an Exponential Family of Random Trees
Authors: Steele Michael
Published: July 2009

A model for random trees is given which provides an embedding of the uniform model into an exponential family whose natural parameter is the expected number of leaves. The model is proved to be analytically and computationally tractable. In particular, a central limit theorem (CLT) for the number of leaves of a random tree is given which extends and sharpens Rényi's CLT for the uniform model. The method used is general and is shown to provide tractable exponential families for a variety of combinatorial objects.
Are Mass Extinctions Really Periodic?
Authors: Ross Sheldon M.
Published: July 2009

It is argued that the analysis of family extinction data that resulted in the claim of a 26-Myr periodicity of mass extinctions was flawed in that it did not allow for the possibility of a symmetric random walk model, which is shown to be perfectly consistent with the data.
Identifying Coefficients in the Spectral Representation for First Passage Time Distributions
Authors: Brown Mark , Shao Yi-Shi
Published: July 2009

The spectral approach to first passage time distributions for Markov processes requires knowledge of the eigenvalues and eigenvectors of the infinitesimal generator matrix. We demonstrate that in many cases knowledge of the eigenvalues alone is sufficient to compute the first passage time distribution.
Reliability of Complex Devices in Random Environments
Authors: Çinlar E. , Özekici S.
Published: July 2009

The lifetimes of the components of a device depend on each other because of their joint dependence on the environmental conditions. We introduce intrinsic age processes, one for each component, to handle such dependence. The data required can be obtained by experiments under controlled laboratory conditions. The computations needed for randomly varying conditions are recursive and can be used for making decisions regarding maintenance and replacement.
Approximations in Renewal Theory
Authors: Ross Sheldon M.
Published: July 2009

A renewal process [N(t), t ≥ 0] with interarrival times Xi, for i ≥ 1 and renewal function m (t) is considered. Let Gn, λ denote the gamma distribution with parameters n and λ–that is, dGn, λ(x) = λε–λx(λx)n-1/(n – 1)

In Section 1 we show how m(t) can be approximated by f m(s) dGn, n/t(s). In addition, we show that these approximations constitute an increasing sequence of lower bounds when the interarrival distribution has the decreasing failure rate property. In Section 2 we show how the integrated renewal function can be approximated in a similar fashion by a decreasing sequence of upper bounds. In Section 3 we consider the problem of approximating the residual life (also called excess life) and the renewal age distribution and their means, and in Section 4 we consider the distribution of N(t). Finally, in Section 5 we remark on the relationship between our approximations and the Feller technique for inverting a Laplace transform.
Fault Diversity in Software Reliability
Authors: boland Philip J. , proschan Frank , Tong Y. L.
Published: July 2009

Diversity of bugs or faults in a software system is a factor contributing to software unreliability which has not yet been appropriately emphasized. This paper is written with the intention of demonstrating the impact of fault diversity on the time to detection of software bugs. A new discrete software reliability model based on the multinomial distribution is introduced. It is shown that for models of this type, the more diverse the fault probabilities are, the longer (stochastically) it takes to detect or eliminate any n faults, while the smaller (stochastically) will be the number of faults detected or eliminated during a given amount of time (or during a given number of inputs to the system). The impact of fault diversity is also demonstrated for the Jelinski–Moranda model.
An Inventory With Constant Demand and Poisson Restocking
Authors: Baxter Laurence A. , Lee Eui Yong
Published: July 2009

An inventory whose stock decreases linearly with time is considered. The inventory may be replenished at the instants at which a deliveryman arrives provided that the level of the inventory does not exceed a certain threshold; deliveries are made according to a Poisson process. A partial differential equation for the distribution function of the level of the inventory is solved to yield a formula for the corresponding Laplace–Stieltjes transform. The evaluation of the transform is discussed and explicit results are obtained for the stationary case.
Interval Availability Distribution for A 1-out-of-2 Reliability System with Repair
Authors: Heijden M. C. van der
Published: July 2009

This paper deals with a two-unit reliability model having one operating unit and one cold standby unit and with ample repair facilities. An approximate method is given for the calculation of the probability distribution of the proportion of time that the system is available in a given time period. The approximate method first computes the mean-time-to-failure and the meantime-to-repair and next approximates the up-and-down process of the two-unit reliability system by an alternating renewal process having exponentially distributed on and off periods. Numerical investigations show a satisfactory performance of the approximation. Also, a sensitivity analysis is given.
Exact Maximum Likelihood Estimate of a Finite Population Size
Authors: Leite Jose Galvão , Oishi Jorge , Pereira Carlos Alberto de Bragança
Published: July 2009

Using data obtained by the general capture/recapture sequential sampling process, an exact analytical expression for the maximum likelihood (ML) estimate of the population size, N, is introduced. As a consequence, it is shown that bounded likelihood functions have at most two maxima. For the simple one-by-one case the ML estimate is unique.
Some Results on Weighted Distributions for Positive-Valued Random Variables
Authors: Kochar S. C. , Gupta R. P.
Published: July 2009

For nonnegative random variables, the weighted distributions have been compared with the original distributions with the help of partial orderings of probability distributions. Bounds on the moments of the weighted distributions have been obtained in terms of the moments of the original distributions for some nonparametric classes of aging distributions.
System Reliability Analysis in the Presence of Dependent Component Failures
Authors: Hagstrom Jane N. , Mak King-Tim
Published: July 2009

We consider the impact that the introduction of dependent component failures has on the computational difficulty of system reliability analysis. We develop general strategies for computing system reliability when components are subject to dependent failures. In the process, we identify a significant number of cases where computing the system reliability in the presence of dependent failures is not significantly harder than writing down the joint probability distribution and computing the system reliability when the components fail independently.
Consecutive-2 systems on trees
Authors: Santha Miklos , Znang Yanjun
Published: July 2009

This paper studies consecutive-2 systems on trees. We show that given a set of probability values, the optimal assignment for binary trees depends on the particular values, whereas for k−regular trees, which are closely related to binary trees, it depends only on their relative ordering. In our proof, we introduce the notion of first-term-invariance, which might have further applications. We also show that the problem of computing the failure probability of consecutive-2 system is #P-complete in general, though the problem on trees is shown to be strongly polynomial.
A Terminal Bay Relief Strategy
Authors: Doverspik R. D.
Published: July 2009

This paper explores a new, more optimal policy for planning terminal bays for the provisioning of circuits in a telephone operating company. This new policy regularly monitors the terminal bay inventory and orders K units when the spare reaches a certain parameter, R. For particular office characteristics the optimal (R, K) pair which minimizes cost is determined, subject to a performance constraint. A probabilistic circuit demand model is formulated and a combination of simulation and analytic approximation is used to calculate the cost and performance measure. In order to prove that the new policy is more economical, the new policy is compared, via another simulation, to the present policy of a typical telephone operating company.
Hashing with Linear Probing under Nonuniform Probabilities
Authors: Aldous David
Published: July 2009

Probabilistic analyses of hashing algorithms usually assume that hash values are uniformly distributed over addresses. We study how one of the simplest schemes, hashing with linear probing, behaves in the nonuniform case. A simple measure μ of nonuniformity is the probability two keys hash to the same address, divided by this probability in the uniform case. It turns out that the effect of nonuniformity is to multiply mean search lengths by μ. For high loads, the longest search is multiplied by approximately μ also. Our theoretical results are asymptotics: simulations show good fits with predictions for mean search lengths, but bad fits for longest search lengths.
On the Comparison of two Software Relibility Estimators
Authors: Derman Cyrus , Koh Showlong P.
Published: July 2009

Two different estimators of the failure rate of software are compared. It is shown that one tends to be better when the number of errors is small to moderate and the other when the number of errors is large.
A Stochastic Differential Game with Safe and Risky Choices
Authors: McNamara J. M.
Published: July 2009

This paper considers a two-person zero-sum stochastic differential game. The dynamics of the game are given by a one-dimensional stochastic differential equation whose diffusion coefficient may be controlled by the players. The drift coefficient is held constant and cannot be controlled. Player l's objective is to maximize the probability that the state at final time, T, is positive, while Player 2's objective is to maximize the probability that the state is negative.
Dynamic Repair Allocation for a k−Out−of−n System Maintained by Distinguishable Repairmen
Authors: Katehakis Michael N. , Melolidakis Costis
Published: July 2009

We consider a K-out-of-N system maintained by R repairmen, where the lifetime of the ith component is an exponentially distributed random variable with parameter μi. Repairmen are distinguishable, and the time it takes the rth repairman to repair a failed component is an exponentially distributed random variable with parameter λr. Repaired components are as good as new and preemptions are allowed. We show that the policy that assigns the faster repairmen to the most reliable components is optimal with respect to several optimality criteria.

The approach we take in establishing stochastic optimality with respect to the number of functioning components is of wide applicability to different classes of stochastic optimization problems.
Optimal Consecutive-k−Out−of−n Systems under a Fixed Budget
Authors: Chang G. J. , Hwang F. K.
Published: July 2009

A consecutive-k−out−of−n system is a graph with n vertices where the system fails if and only if some path of k consecutive vertices all fail. The assumption is made that qi, is the failing probability of the ith vertex and the states of the vertices are statistically independent. The problem is to find the best system, i.e., a set {q1, …,qn}, and its assignment to the vertices of the system graph that maximizes the reliability of the system, under the constraint that the product of qi's is a constant. We solve the problem for all lines and some cycles. We then extend our results to trees and show that for given n and k the best tree is a star and the worst is a line.
When Many Wrongs Make a Right
Authors: Lippman Steven A. , Mamer John W.
Published: July 2009

When confronted by a sequence of independent, identical, favorable-though- risky investments, a risk-averse agent will in fact elect to invest as part of a large syndicate even if he or she would not undertake even one of the investments by himself or herself. This willingness to invest emanates from the risk reduction associated with the risk pooling effected by the syndicate. Our first two theorems describe the syndicate size needed to induce the agent's participation.

The consequence of adding risks is considered next. We demonstrate that the agent will undertake a large number of these independent investments by himself or herself even if each investment taken by itself constitutes a poor risk. The conditions needed to ensure this somewhat surprising result are (a) moment bounds on the investments, and (b) either a polynomial or an exponential bound on the lower tail of the agent's utility function. Finally, we draw the connection between this result, proper risk aversion, and monotonicity of the agent's absolute aversion to risk.
Probabilistic Analysis of a Greedy Heuristic for Euclidean Matching
Authors: Avis David , Davis Burgess , Steele J. Michael
Published: July 2009

Given a collection of n points in the plane, the Euclidean matching problem is the task of decomposing the collection into matched pairs connected by line segments in such a way as to minimize the sum of all the segment lengths. The greedy heuristic provides an approximate solution to the Euclidean matching problem by successively matching the two closest unmatched points. We study the behavior of Gn, the sum of the lengths of the segments produced by the greedy heuristic.
Balance of Recurrece Order in Time-Inhomogenous Markov Chains with Application to Simulated Annealing
Authors: Connors D. P. , Kumar P. R.
Published: July 2009

We define a notion of order of recurrence for the states and transitions of a general class of time-inhomogeneous Markov chains with transition probabilities proportional to powers of a small vanishing parameter. These orders are shown to satisfy a balance equation across every edge cut in the associated graph. The resulting order balance equations allow computation of the orders of recurrence of the states, and thereby the determination of the asymptotic behavior of the Markov chain.

The method of optimization by simulated annealing is a special case of such Markov processes, and can therefore be treated by means of these balance equations. In particular, in this special situation we show that there holds a detailed balance of order of recurrence across every edge in the graph. Moreover, the sum of the order of recurrence of a state and its cost is shown to be a constant in each connected set of recurrent states. By this approach, we determine the necessary and sufficient condition on the “rate of cooling” to guarantee that a minimum of the optimization problem is hit with probability one. Moreover, the rates of convergence of the probabilities can be deduced from the orders of recurrence.
Dynamic Performance Evaluation of Communication/Computer Systems with Highly Reliable Components
Authors: Kubat Peter , Sumita Ushio , Masuda Yasushi
Published: July 2009

System components of communication/computer networks are quite reliable in that their average uptimes are much larger than the average repair/replacement time of a failed unit. By taking this observation into account, a semiMarkov model is developed with a simple regenerative structure, thereby providing strong analytical and computational tractability. Expressions of a variety of dynamic performability measures, such as the cumulative system processing capacity and the task completion time, are explicitly derived. Computational procedures for evaluating such time-dependent performability measures are developed based on these theoretical results combined with the Laguerre transform method. The power and the efficiency of the computational procedures are demonstrated through a numerical example.
Analysis of theGI/GI/1 Queue and its Variations via the LCFS Preemptive Resume Discipline and Its Random Walk Interpretation
Authors: Shalmon Michael
Published: July 2009

The unfinished work at arrival instants (FCFS waiting time) can be computed via the LCFS preemptive resume discipline. Analyzing the GI/GI/1 queue in this way gives full interpretation in queuing theoretic language to Feller's analysis of the fluctuations of the random walk. Also, this approach leads naturally to stochastic decompositions for the queue with set-up times, and for other variations of the standard queue. For the M/G/1 queue, the derivations are qualitative, and there are additional connections to branching processes.
Single-Server with Delay-Dependent Arrival Streams
Authors: Brill P. H.
Published: July 2009

This paper derives the steady-state distribution of the virtual wait in GI/M1 queues in which the interarrival times depend on the virtual wait. Applications are queues in which the time it will take for the system to start servicing a new arrival (virtual wait) affects the generation of new arrivals. Such queues arise in airport or large-city freeway traffic control systems. Related state-dependent situations occur in production-inventory systems, cash flow in banking or in insurance systems, dam control systems, and in natural sciences. The method of analysis is by means of system-point level crossing theory.
On the Three-Moment Approximation of a General Distribution by a Coxian Distribution
Authors: Van Der Heijden M. C.
Published: July 2009

The Coxian-2 distribution is a very useful distribution for queuing and reliability analysis. It is important to know when a general probability distribution can be approximated by a Coxian-2 distribution by fitting the first three moments. For a positive random variable with a squared coefficient of variation larger than 1, a lower bound on its third moment is known for which a three-moment fit exists. To complete the figure, in this note lower and upper bounds on the third moment are derived when the squared coefficient of variation is between 0.5 and 1. Also, we characterize the C2-distributions that correspond to these bounds.
A Note on Approximating Mean Occupation Times of Continuous-Time Markov Chains
Authors: Ross Sheldon M.
Published: July 2009

In [1] an approach to approximate the transition probabilities and mean occupation times of a continuous-time Markov chain is presented. For the chain under consideration, let Pij(t) and Tij(t) denote respectively the probability that it is in state j at time t, and the total time spent in j by time t, in both cases conditional on the chain starting in state i. Also, let Y1,…, Yn be independent exponential random variables each with rate λ = n/t, which are also independent of the Markov chain.
Two Applications of Urn Processes The Fringe Analysis of Search Trees and The Simulation of Quasi-Stationary Distributions of Markov Chains
Authors: Aldous David , Flannery Barry , Palacios José Luis
Published: July 2009

From an urn containing colored balls, one ball is drawn and replaced by a random number of differently colored balls, with the distribution of the added balls depending only on the color of the ball drawn. Under mild regularity conditions, the proportions of different colors will converge to deterministic limits. Two applications of this standard result are described.
Optimal Control of a Model for a System Subject to Continuous Wear
Authors: Baxter Laurence A. , Lee Eui Yong
Published: July 2009

The state of a system is modelled by Brownian motion with negative drift and an absorbing barrier at the origin. A repairman arrives according to a Poisson process of rate λ. If the state of the system at arrival of the repairman does not exceed a certain threshold, he/she increases it by a random amount, otherwise no action is taken. Costs are assigned to each visit of the repairman, to each repair, and to the system being in state 0. It is shown that there exists a unique arrival rate λ which minimizes the average cost per unit time over an infinite horizon.
Length-Biased Orderings with Applications
Authors: Alzaid Abdulhamid A.
Published: July 2009

A new partial ordering generated by the set of star-shaped functions is introduced. This ordering is equivalent to the stochastic comparison of the length-biased distributions which are frequently appropriate for certain natural sampling plans in biometry, reliability, and survival analysis studies. It is shown that the length-biased ordering fits in the framework of stochastic and variatiility orderings. It enjoys many properties similar to those of the stochastic and variability orderings.
Active Redundancy Allocation in Coherent Systems
Authors: Boland Philip J. , Neweihi Emad El , Proschan Frank
Published: July 2009

We introduce in this paper a new measure of component importance, called redundancy importance, in coherent systems. It is a measure of importance for the situation in which an active redundancy is to be made in a coherent system. This measure of component importance is compared with both the (Birnbaum) reliability importance and the structural importance of a component in a coherent system. Various models of component redundancy are studied, with particular reference to k/out / of / n systems, parallel-series systems, and series-parallel systems.
A Simple Proof of Instability of a Random-Access Communication Channel
Authors: Ross Sheldon M.
Published: July 2009

We give an extremely simple argument to prove that in infinite user-commurlication channels, under the Aloha protocol, the number of successful transmissions is finite with probability 1. The same result is then shown to hold for those back-off protocols whose transmission probabilities are bounded away from 0.
Asymptotic Analysis for Buffer Behavior in Communication Systems
Authors: Tijms H. C. , Van Ommeren J. C. W.
Published: July 2009

An important problem in computer communication systems is the design of finite buffers such that a small overflow probability is achieved. For the case of batch input and general service times, we derive an asymptotically exponential expansion for the overflow probability when the batch-arrival process is Poissonian. Next, the results are extended to handle applications with periodic service opportunities and random interruptions in service. A convenient model to handle these types of applications is the versatile queueing model with exceptional first services.
Stochastic Decision Theory
Authors: Cockett J. Robin B. , Zrida Jalel , Birdwell J. Douglas
Published: July 2009

The manipulations and basic results of stochastic decision theory are introduced. The manipulations of idempotence, transposition, and repetition, introduced for deterministic decision trees, can be used to manipulate stochastic trees. However, there are two major differences. First, in order to obtain a complete set of manipulations it is necessary to introduce an additional rule calledindifference. Second, these identities must be treated as rules of inference. Not all the rules can be soundly applied in both directions; in particular, idempotence is a one-way rule.

A manipulation of a stochastic decision tree not only alters the structure of the tree, but also the probability distributions associated with the tree. This allows probability calculation to be viewed as structural manipulation. In particular, a retrieval corresponds to a conditional probability calculation. The algorithm for doing this calculation has, therefore, many applications. For example, the solution to the classical state-estimation problem and the retrieval of information from probabilistic or uncertain knowledge bases may both be viewed as an application of this algorithm.

The main result of this paper is that these manipulations are complete and sound. In order to prove this result, it is necessary to have a semantic setting for these theories. The setting chosen is the category ofdescription spaceswhich is a generalization of the category of bounded measure spaces with maps which do not increase measure. The proof of this result exploits the retrieval properties of stochastic terms and its relationship to conditional probability calculations in the models.
On W.P.1 Convergence of A Parallel Stochastic Approximation Algorithm
Authors: Yin G. , Zhu Y. M.
Published: July 2009

To find zeros or locate maximum values of a regression function with noisy measurements, a commonly used algorithm is the RM or KW procedure. In various applications, the dimensionality of the problems involved might be quite large. As a result, enormous memory space and extensive computation time may be needed. Motivated by the recent progress in stochastic approximation methods for decentralized and distributed computing, a parallel stochastic approximation algorithm is developed in this paper. The essence is to take advantage of state-space decompositions, and to exploit the opportunities provided by parallel processing and asynchronous communication. In lieu of utilizing a single processor as in the classical cases, a number of parallel processors are employed to solve the underlying problem in a cooperative way. First, the large dimensional vector is partitioned into a number of subvectors with relatively small dimension, then each of the subvectors is assigned to one of the processors. The processors compute and communicate in an asynchronous manner and at random times. Under rather weak conditions, the global convergence of the parallel algorithm is obtained via the methods of randomly varying truncations.
Scheduling Stochastic Jobs with a Two-Point Distribution on Two Parallel Machines
Authors: Coffman E.G. , Hofri M. , Weiss G.
Published: July 2009

We analyze the optimal preemptive sequencing ofnjobs on two machines to minimize expected total flow time. The running times of the jobs are independent samples from the distributionPr(X= 1) =p,Pr(X= κ + 1) = 1 −p. We verify that the shortest-expected-remaining-processing-time (SERPT) policy, which is optimal for independent and identically distributed (i.i.d.) running times with a monotone hazard-rate distribution, is not optimal for this distribution. However, we prove that ifp≥ 1/κ, then the number of decisions where SERPT and an optimal policy disagree is bounded by a constant independent ofn. Forp< 1/k, we prove that theexpectednumber of such decisions has a similar bound. In addition, bounds on the expected increase in flow times under SERPT are derived; these bounds are also independent ofn.
Some Replacement Policies in a Random Environment
Authors: Shaked Moshe , Shanthikumar J. George
Published: July 2009

Several models of maintenance of repairable multicomponent systems, subjected to a random environment, are introduced in this paper. For each model, it is shown how various probabilistic quantities of interest are “monotone” as a function of the probability law of the environment or as a function of other parameters of the model. Also, conditions are given which imply the positive dependence of the failure times, or of the counters of the number of failures, in these models.
A Monotonicity Result for Inspecting Independent Items
Authors: Hwang F.K. , Papastavridis S.G.
Published: July 2009

Recently, the conjecture that the expected number of tests is nondecreasing in the failure probability for binomial group testing has been proved. The proof has also been extended to three models of multiaccess systems. However, probabilistic algorithms are used as a crucial part of these proofs. In this paper, we give conceptually simpler new proofs without using probabilistic algorithms. We also extend the result to a more general model where the number of tests is replaced by a cost function.
Some Asymptotic Analysis of Resistant Rules For Outlier Labeling
Authors: Angus John E.
Published: July 2009

Previous studies have examined the behavior of outlier detection rules for symmetric distributions that label as “outside” any observations that fall outside the interval [FL – k(Fu – FL), Fu + k(Fu – FL)], where FL and FU are functions of the order statistics estimating the 0.25 and 0.75 quantiles of the distribution underlying the i.i.d. sample. A measure of the performance of this type of rule is the “some-outside rate” per sample computed with respect to a given (usually Gaussian) null distribution. The “some-outside rate” (SOR) per sample is the probability that the sample will contain one or more observations labeled as “outside,” given that the null distribution is the true distribution. In this paper, asymptotic expansions of k = kn as a function of n that guarantee an asymptotically constant, prespecified SOR are given for a variety of symmetric null distributions including the Gaussian, double exponential, logistic, and Cauchy distributions. The main theorem also applies to the case of a nonsymmetric null distribution by slightly modifying the labeling rule.
On the Interchangeability and Stochastic Ordering of Exponential Queues in Tandem with Blocking
Authors: Chao Xiuli , Pinedo Michael , Sigman Karl
Published: July 2009

For a two-station tandem system with a general arrival process, exponential ervice times, and blocking, we show that the distribution of the departure process does not change when the two stations are interchanged. Blocking here means that for some fixed b≥1, any customer completing service at the first station when b customers are at the second station cannot enter the second queue, and the first station cannot start serving a new customer until a service completion occurs at the second station. This result remains true if arrivals are lost when there are a(a≥0) customers in the system. We also show that when the sum of the service rates is held constant, each departure epoch is stochastically minimized if the two rates are equal. For a and b infinite, our results reduce to those given by Weber [14] and Lehtonen [8]. Our proof is based on a coupling method first used by Lehtonen. The same results hold for a blocking mechanism in which a customer completing its service at the first station must restart service when b customers are present at the second.
A Moment-Iteration Method for Approximating the Waiting-Time Characteristics of the GI/G/1 Queue
Authors: De Kok A. G.
Published: July 2009

In this paper, a moment-iteration method is introduced. The method is used to solve Lindley's integral equation for the GI/G/l queue. From several forms of this integral equation, we derive the first two moments of the waiting-time distribution, the waiting probability, and the percentiles of the conditional waiting time. Numerical evidence is given that the method yields excellent results. The flexibility of the method provides the opportunity to solve the GI/G/l queue for all interarrival time distributions of practical interest. To show that the moment-iteration method is generally applicable, we give some results for an (s, S)-model with order-size-dependent lead times and finite production capacity of the supplier.
Properties of Conditionally Independent Generalized Gamma Distributions
Authors: Lee Mel-Ling Ting , Gross* Alan J.
Published: July 2009

Models of life time observations that have conditionally independent generalized gamma distributions are investigated. Positive dependency among the unconditional joint distribution is discussed. General formula for moment inequalities are given. Conditional hazard rate, mean residual life functions, and bounds for system reliabilities are also discussed. An application was given.
Replication Schemes For Limiting Expectations
Authors: Fox Bennett L. , Glynn Peter W.
Published: July 2009

We show that natural estimators occurring in certain simulation settings have convergence rates less than the canonical rate usually associated with simulation. These natural estimators use replication schemes that attenuate bias. For some important examples, we find alternative estimators that converge at the canonical rate. The implications of these asymptotic comparisons for choosing good strategies when the computer-time budget is modest are discussed.
Minimum Variance Unbiased Estimation of Software Reliability
Authors: Nayak Tapan K.
Published: July 2009

As the formal methods of proving correctness of a computer program are still very inadequate, in practice when a new piece of software is developed and all obvious errors are removed, it is tested with different (random) inputs in order to detect the remaining errors and assess its quality. We suppose that whenever the program fails the error causing the failure can be detected and removed correctly. Thus, the quality of the software increases as testing goes on. In this paper, we consider two different models and present the minimum variance unbiased estimators of the expected failure rate of the revised software at any time of testing t, based on the data generated up to that point.
Policy Improvement and the Newton–Raphson Algorithm for Renewal Reward Processes
Authors: McNamara J. M.
Published: July 2009

We consider a renewal reward process in continuous time. The supremum average reward, γ* for this process can be characterised as the unique root of a certain function. We show how one can apply the Newton–Raphson algorithm to obtain successive approximations to γ*, and show that the successive approximations so obtained are the same as those obtained by using the policy improvement technique.
A Class of Decision Processes Showing Policy-Improvement/Newton–Raphson Equivalence
Authors: Whittle P.
Published: July 2009

A condition expressed in Eq. (7) is given which, with one simplifying regularity condition, ensures that the policy-improvement algorithm is equivalent to application of the Newton–Raphson algorithm to an optimality condition. It is shown that this condition covers the two known cases of such equivalence, and another example is noted. The condition is believed to be necessary to within transformations of the problem, but this has not been proved.
Approximating the Stochastic Network by its M Shortest Paths
Authors: Dodin Bajis
Published: July 2009

Given a stochastic activity network in which the length of some or all of the arcs are random variables with known probability distributions. This paper concentrates on identifying the shortest path and the M shortest paths in the network and on using the M paths to identify surrogate stochastic networks which are amenable for deriving analytical solutions. First, it identifies the M shortest paths using a certain form of stochastic dominance. Second, it identifies the M shortest paths by applying the deterministic methods to the network resulting from replacing the random length of every arc by its mean value. The two sets of the M paths are compared with those obtained by Monte Carlo sampling. Finally, the paper investigates how the distributional properties of the shortest path in the surrogate network compare with those of the shortest path in the original stochastic network.
A Bayesian Approach to Simulated Annealing
Authors: Van Laarhoven P.J.M. , Boender C.G.E. , Aarts E.H.L. , Kan A. H. G. Rinnooy
Published: July 2009

Simulated annealing is a probabilistic algorithm for approximately solving large combinatorial optimization problems. The algorithm can mathematically be described as the generation of a series of Markov chains, in which each Markov chain can be viewed as the outcome of a random experiment with unknown parameters (the probability of sampling a cost function value). Assuming a probability distribution on the values of the unknown parameters (the prior distribution) and given the sequence of configurations resulting from the generation of a Markov chain, we use Bayes's theorem to derive the posterior distribution on the values of the parameters. Numerical experiments are described which show that the posterior distribution can be used to predict accurately the behavior of the algorithm corresponding to the next Markov chain. This information is also used to derive optimal rules for choosing some of the parameters governing the convergence of the algorithm.
Evaluating Reliability of Stochastic Flow Networks
Authors: Fishman George S. , Shaw Tien-Yi Danny
Published: July 2009

This paper describes a highly efficient Monte Carlo sampling plan for evaluating the probability that the flow value in a stochastic flow network is greater than or equal to a prespecified leveld. A stochastic flow network can characterize communication, transportation, and water or oil distribution systems. The paper first derives lower and upper bounds on the probability of interest and then describes how one can concentrate sampling in a specialized region of the arc capacity state space to increase the statistical efficiency of the resulting estimate. The paper also gives expressions for worst-case sample sizes needed to meet specified bounds on variances and coefficients of variation and illustrates the proposed sampling plan with an example.
On Two Problems Involving Partial Sums
Authors: Brown Mar
Published: July 2009

Two problems are considered: (1) The expected waiting time for the partial sums of i.i.d. positive integer-valued random variables to be a multiple of k for the first time. For aperiodic distributions this expected value is shown to equal k. The periodic case is considered, as well as the waiting time for the partial sums to equal r modulo k. (2) For two independent sequences of partial sums of positive i.i.d. random variables, the expected value of the smallest common partial sum is derived. If both distributions are aperiodic, this expected value is the product of the two means. The periodic case is considered, as well as the case of more than two sequences.
Control Policies for Two Classes of Inventory Systems via a Duality-Equivalence Relationship
Authors: Perry D. , Posner M. J. M.
Published: July 2009

Two classes of inventory systems are considered, and modeled under a control policy of the bang-bang type. For the first, items and demands for those items arrive independently and singly at a system. Unsatisfied demands are lost, and items staying on the shelf too long are considered unsuitable for use and are rejected. For the second, items are produced continuously over time with fixed rate in a storage/production system with capacity k, in which demands of exponential size arrive according to a Poisson process, and no backorders are allowed. The problem of controlling the demand rate in the first model is shown to be equivalent to the problem of controlling the production rate in the second model. Optimization methods are then considered for both models employing discounted cost and averaged cost rate criteria for the optimal selection of switchover levels for arrival and demand rates.
The Move-to-Front Rule for Multiple Lists
Authors: Courcoubetis Costas , Weber Richard R.
Published: July 2009

A number of data items (1,2,…,n) are to be maintained in a structure which consists of several linear lists. Successive requests to access items are independent random variables, and the probability that a particular request is for item i is pi. The cost of accessing the jth item from the front of a list is j. For a single list, the move-to-front rule (MF) has been extensively studied and has been shown to provide good performance. In some actual circumstances, MF is the only physically realizable or convenient policy. We extend the study of move-to-front by examining the case where items are kept in several lists. Following its access, an item must be replaced at the front of one of the lists. In certain cases, assuming the pi's are known, the policy which minimizes the average retrieval cost takes a particularly simple form: no item is ever moved from the list in which it is placed initially.
Processor Reordering Rules
Authors: Ross Shledon M.
Published: July 2009

We consider a problem in which jobs continually arrive to a set of n processors that are arranged in an ordered list. When a job arrives the first processor in line attempts to process it; if it is unsuccessful then the next in line attempts it, and so on. Each time that processor j attempts to process a job it is, independently of all else, successful with (an unknown) probability pj. After a job has been completed or all n attempts have failed then, based on the result, we can reorder the processors before the next job arrives, with the objective being to minimize the average number of attempts per job. This paper compares the transposition rule and the move to the front rule.
Message Delay Distribution in Generalized Time Division Multiple Access (TDMA)
Authors: Rom Raphael , Sidi Moshe
Published: July 2009

In the classical TDMA, which has been the subject of extensive research in the past, a single slot is allocated to each and every user within every frame. In many situations this leads to an inefficient utilization of the channel calling for a nonhomogeneous allocation of slots. This paper focuses on a generalized TDMA scheme in which users are allocated more than a single slot per frame, not necessarily contiguous. We derive the delay distribution and buffer occupancy for such a scheme as well as the expected values of these quantities.
Some Alternate Characterizations of Reliability Domination
Authors: Boesch F. T. , Satyanarayana A. , Suffel C. L.
Published: July 2009

An important problem in reliability theory is to determine the reliability of a system from the reliability of its components. If E is a finite set of components, then certain subsets of E are prescribed to be the operating states of the system. A formation is any collection F of minimal operating states whose union is E. Reliability domination is defined as the total number of odd cardinality formations minus the total number of even cardinality formations. The purpose of this paper is to establish some new results concerning reliability domination. In the special case where the system can be identified with a graph or digraph, these new results lead to some new graph-theoretic properties and to simple proofs of certain known theorems. The pertinent graph-theoretic properties include spanning trees, acyclic orientations, Whitney's broken cycles, and Tutte's internal activity associated with the chromatic polynomial.
Coupled Processor: A Second-Order Continuous-State-Space Model
Authors: Takahashi Haruhisa
Published: July 2009

A second-order continuous-state-space model for two-dimensional queueing systems is developed in this article. A particular problem is treated but the results can apply to some other two-dimensional queueing problems directly. The generating function for the model is obtained by applying a Riemann boundary value problem and leads to a computationally feasible solution.
The Capacity of the White Gaussian Noise Channel
Authors: Bretienbach Jerome R.
Published: July 2009

The capacity of the white Gaussian noise (WGN) channel is widely stated asS/N0nats/unit time. This conclusion is commonly derived either formally, or from the capacity,Wln(l +S/N0W), of the corresponding band-limited channel with bandwidthW, by takingW→8. In this paper, the WGN channel capacity is instead found directly by treating WGN as an arbitrary noise sequence that whitens in a general sense. In addition, the coding theorems proved make explicit the class of allowable receivers, either finite- or infinite-dimensional correlation receivers, or unconstrained. The capacities for these three receiver classes are found to be, respectively:S/N0forS> 0, and 0 forS= 0; and 8 for allS≥ 0. In those cases where the capacity is infinite, actual transmitter–receiver pairs are specified that achieve capacity.
Randomized Play-the-Leader Rules for Sequential Sampling from Two Populations
Authors: Durham S. D. , Yu† K. F.
Published: July 2009

Observations may be taken from one of the two populations. A randomized selection rule is one that chooses the populations according to some determined odds. The odds for choosing a population the next time may be dependent on all the observations taken so far from both populations. In this paper, the odds are made for the randomized selection rule in such a way that the number of observations from the better population relative to the number of observations from the other population grows at prescribed rates, typically of exponential order or faster. The rules include randomized play-the-winner rules and randomized analogues of Robbins' R̄ rules. Some Monte Carlo investigations are conducted to study these randomized selection rules for moderate sample sizes.
Linear Dependence in Consecutive k-out-of-n: F Systems
Authors: Boland Philip J. , Proschan Frank , Tong Y. L.
Published: July 2009

A consecutive k−out−of-n: F system is a coherent system of n-ordered components that functions if and only if there is no consecutive run of k failures among the components. Examples of such systems exist in telecommunications, oil pipelines, and integrated circuitry. Most of the research in reliability of consecutive k−out-of-n: F systems assumes that the components function independently of one another. In this paper, we develop a model incorporating positive dependence between adjacent components and show that for k ≥ (n + l)/2, the reliability of the system is a decreasing function of this dependence.
Sequential Assignment Match Processes with Arrivals of Candidates and Offers
Authors: David Israel , Yechiali Uri
Published: July 2009

An infinite random stream of ordered pairs arrives sequentially in discrete time. A pair consists of a “candidate” and an “offer,” each of which is either of type I (with probability p) or of type II (with probability q = 1 – p). Offers are to be assigned to candidates, yielding a reward R > 0 if they match in type, or a smaller reward 0 ≤ r ≤ R if not. An arriving candidate resides in the system until it is assigned, whereas an arriving offer is either assigned immediately to one of the waiting candidates or lost forever. We show that the optimal long-term average reward is R, independent of the population proportion p and the “second prize” r, and that the optimal average reward policy is to assign only a match. Optimal policies for discounted and finite horizon models are also derived.
Bayes Burn-In Decision Procedures
Authors: Clarotti C. A. , Spizzichino F.
Published: July 2009

The burn-in problem is reframed in a decision-making context. The role of the predictive life distribution in the burn-in decision problem is highlighted. The case in which the predictive distribution is a mixture of exponentials is discussed extensively.
Stability of On-Line Bin Packing with Random Arrivals and Long-Run-Average Constraints
Authors: Courcobetis Coastas , Weber Richard
Published: July 2009

Items of various types arrive at a bin-packing facility according to random processes and are to be combined with other readily available items of different types and packed into bins using one of a number of possible packings. One might think of a manufacturing context in which randomly arriving subassemblies are to be combined with subassemblies from an existing inventory to assemble a variety of finished products. Packing must be done on-line; that is, as each item arrives, it must be allocated to a bin whose configuration of packing is fixed. Moreover, it is required that the packing be managed in such a way that the readily available items are consumed at predescribed rates, corresponding perhaps to optimal rates for manufacturing these items. At any moment, some number of bins will be partially full. In practice, it is important that the packing be managed so that the expected number of partially full bins remains uniformly bounded in time. We present a necessary and sufficient condition for this goal to be realized and describe an algorithm to achieve it.