Asymptotic normality of high level-large time crossings of a Gaussian process

We prove the asymptotic normality of the standardized number of crossings of a centered stationary mixing Gaussian process when both the level and the time horizon go to infinity in such a way that the expected number of crossings also goes to infinity.     

Sample path methods in the control of queues

Sample path methods are now among the most used techniques in the control of queueing systems. However, due to the lack of mathematical formalism, they may appear to be non-rigorous and even sometimes mysterious. The goal of this paper is threefold: to provide a general mathematical setting, to survey the most popular sample path methods including forward induction, backward induction and interchange arguments, and to illustrate our approach through the study of a number of classical scheduling and routing optimization problems arising in queueing theory.Z. Liu was supported in part by the CEC DG XIII under the ESPRIT BRA grants QMIPS.P. Nain was supported in part by NSF under grant NCR-9116183 and by the CEC DG XIII under the ESPRIT BRA grants QMIPS.D. Towsley was supported in part by NSF under grant NCR-9116183.     

Sample path properties of stochastic integrals,and stochastic differentiation

Let B be a Brownian motion, and X = H.B be a stochastic integral of B. We give conditions on the smoothness of the process H which imply that if Ms a singular point of the sample path of B (ω) (such as a local maximum, a slow point, or a fast point) then t is also a singular point of X (ω). In the final section we give an application to stochastic differential equations     

Sensitivity analysis for shortest path problems and maximum capacity path problems in undirected graphs

This paper addresses sensitivity analysis questions concerning the shortest path problem and the maximum capacity path problem in an undirected network. For both problems, we determine the maximum and minimum weights that each edge can have so that a given path remains optimal. For both problems, we show how to determine these maximum and minimum values for all edges in O(m + K log K) time, where m is the number of edges in the network, and K is the number of edges on the given optimal path.     

Moments of the number of upcrossings of an absolutely continuous process at points of density of a sample path derivative associated set

For a separable process on the unit interval with a.s. absolutely continuous sample paths a kth factorial moment formula is found for the number of sample path upcrossings of zero which occur at points of density (in a weak sense) of the set where the sample path derivative exceeds a fixed value. In the case where the sample path derivative is continuous on the closed unit interval the moment formula reduces to a simple variation of the Cramér-Leadbetter formula for the corresponding kth factorial moment of the number of unconstrained upcrossings.     

Generalized level crossings and tangencies of a random field with smooth sample functions

Tangencies and level crossings of a random field X:$\text{R}$^m₊×Ω→$\text{R}$ⁿ (which is not necessarily Gaussian) are studied under the assumption that almost every sample path is continuously differentiable. If n=m and if the random field has uniformly bounded sample derivatives and uniformly bounded densities for the distributions of the X_l, then for a compact K?$\text{R}$^m₊ and any fixed level, the restriction to K of almost every sample path has no tangencies to the level and at most finitely many crossings. The case of n≠m is also examined. Some generic properties, which hold for a residual set of random fields, are analyzed. Proofs involve the concepts of regularity and transversality from differential topology.     

How to optimize discrete-event systems from a single sample path by the score function method

We present a method for deriving theoptimal solution of a class of mathematical programming problems, associated with discrete-event systems and in particular with queueing models, while using asingle sample path (single simulation experiment) from the underlying process. Our method, called thescore function method, is based on probability measure transformation derived from the efficient score process and generating statistical counterparts to the conventional deterministic optimization procedures (e.g. Lagrange multipliers, penalty functions, etc.). Applications of our method to optimization of various discrete-event systems are presented, and numerical results are given.Research supported by the L. Edelstein Research Fund at the Technion-Israel Institute of Technology.     

Smoothed perturbation analysis for queues with finite buffers

Applying the technique of smoothed perturbation analysis (SPA) to theGI/G/1/K queue, we derive gradient estimators for two performance measures: the mean steady-state system time of a served customer and the probability that an arriving customer is rejected. Unbiasedness of the estimators follows from results of a previous general framework on SPA estimators. However, in that framework, the estimators often require the simulation of numerous additional sample subpaths, possibly making the technique practically infeasible in applications. We exploit some of the special structure of theGI/G/1/K queue to come up with an estimator which requires at most the simulation of a single additional sample subpath. By establishing certain regenerative properties, we provide a strong consistency proof for the estimator.     

Infinitesimal perturbation analysis for queueing networks with general service time distributions

We study infinitesimal perturbation analysis (IPA) for queueing networks with general service time distributions. By general we mean that the distributions may have discrete components. We show that in the presence of service time distributions with discrete components commuting condition (CC) is no longer sufficient for unbiasedness of IPA. To overcome this difficulty, we introduce the notion of separability of realvalued random variables, and show that separability of service times together with (CC) establishes unbiasedness of IPA for queueing systems with general service time distributions. It turns out that the piecewise analyticity of service times is a sufficient condition for separability.     

Practical extensions to a minimum cost flow model for level of repair analysis

The level of repair analysis (LORA) gives answers to three questions that are posed when deciding on how to maintain capital goods: (1) which components to repair upon failure and which to discard, (2) at which locations in the repair network to perform each type of repairs, and (3) at which locations in the network to deploy resources, such as test equipment. The goal is to achieve the lowest possible life cycle costs. Various models exist for the LORA problem. However, they tend to be restrictive in that specific business situations cannot be incorporated, such as having repair equipment with finite capacity or the occurrence of unsuccessful repairs or no-fault-founds. We discuss and model such practically relevant extensions to an existing minimum cost flow formulation for the LORA problem. In an extensive numerical experiment, we show that incorporating the model refinements leads to a substantial change in the costs in general. The repair strategy changes substantially only when incorporating finite resource capacities or a probability of unsuccessful repair that is decreasing with an increasing echelon level.     

Joint optimization of level of repair analysis and spare parts stocks

In the field of after sales service logistics for capital goods, generally, METRIC type methods are used to decide where to stock spare parts in a multi-echelon repair network such that a target availability of the capital goods is achieved. These methods generate a trade-off curve of spares investment costs versus backorders. Backorders of spare parts lead to unavailability of the capital goods. Inputs in the spare parts stocking problem are decisions on (1) which components to repair upon failure and which to discard, and (2) at which locations in the repair network to perform the repairs and discards. The level of repair analysis (LORA) can be used to make such decisions in conjunction with the decisions (3) at which locations to deploy resources, such as test equipment that are required to repair, discard, or move components. Since these decisions significantly impact the spare parts investment costs, we propose to solve the LORA and spare parts stocking problems jointly. We design an algorithm that finds efficient solutions. In order for the algorithm to be exact and because of its computational complexity, we restrict ourselves to two-echelon, single-indenture problems. In a computational experiment, we show that solving the joint problem is worthwhile, since we achieve a cost reduction of over 43% at maximum (5.1% on average) compared with using a sequential approach of first solving a LORA and then the spare parts stocking problem.     

ǿ��������Һ�������Ϣ����M���ƺͷ�λ�����ƵĽ�������

In this paper, we apply the empirical likelihood technique to propose a new class of M-estimators and quantile estimators in the presence of some auxiliary information under strong mixing samples. It is shown that the proposed M-estimators and quantile estimators are consistent and asymptotically normally distributed with smaller asymptotic variances than those of the usual M-estimators and quantile estimators.     

Almost sure limit points of and the number of boundary crossings related to SLLN and LIL for record times,inter-record times and the number of record values

In this paper, the almost sure limit points and the moments of the number of boundary crossings of some functions of record times, inter-record times and the frequency of record values of a sequence of independent and identically distributed continuous random variables are studied.     

A mathematical model for the calculation of ceramic batch formulas

In the ceramic field the process of forming a ceramic body consists of several steps that must be executed efficiently and controlled closely to achieve the desired product. A major step in the process is the selection of raw materials, which not only will provide the necessary oxides, but also will melt and fine well to form a high-quality product. This process, if carried out on a trial-and-error manner, may lead to an uneconomical production cost due to wrong materials being selected. In addition, some important physical batch characteristics may be ignored owing to the increase in computational requirements if more constraints are added to the process. In this paper we propose the mathematical modelling approach, which has gained very little attention from researchers in this field, as an alternative to the trial-and-error approach. The model presented in this paper may be used to calculate the batch formula of a designed product without first knowing its empirical formula. An illustrated example of the use of this model is also provided.     

On Some Reliability Applications of Rice's Formula for the Intensity of Level Crossings

Let X be a stationary process with absolutely continuous sample paths. If is finite and if the distribution of X(0) is absolutely continuous, then, for almost all u, the crossing intensity () of the level u by X(t) is given by the generalized Rice's formula . The classical Rice's formula for (), which is valid for a fixed level u, , holds under more restrictive technical conditions that can be difficult to check in applications. In this paper it is shown that often in practice the weaker form of Rice's formula (valid for almost all u) is sufficient. Three engineering problems are discussed; prediction of fatigue life time; computing the average stress at slams and analysis of crest height of sea waves.     

Sample path moderate deviations for the cumulative fluid produced by an increasing number of exponential on-off sources

We consider the superposition of the cumulative fluid generated by an increasing number of stationary iid on-off sources with exponential iid on- and off-time distributions. We establish a family of sample path large deviation principles when the fluid is centered and then scaled with a factor between the inverse of the number of sources and its square root. The common rate function in this family also appears in a large deviation principle for the tail probabilities of an integrated Ornstein–Uhlenbeck process. When the produced fluid is centered and scaled with the square root of the inverse of the number of sources it converges to this integrated Ornstein–Uhlenbeck process in distribution. We discuss several representations of the rate function. We apply the results to queueing systems loaded with on-off traffic and approaching critical loading.      

An algorithm for the number of path homomorphisms

A homomorphism of a graph G₁=(V₁,E₁) to a graph G₂=(V₂,E₂) is a mapping from the vertex set V₁ of G₁ to the vertex set V₂ of G₂ which preserves edges. In this paper we provide an algorithm to determine the number of homomorphisms from an arbitrary finite undirected path to another arbitrary finite undirected path.     

Using algorithmic thinking to design algorithms: The case of critical path analysis

Algorithmic thinking is emerging as an important competence in mathematics education, yet research appears to be lagging this shift in curricular focus. The aim of this generative study is to examine how students use the cognitive skills of algorithmic thinking to design algorithms. Task-based interviews were conducted with four pairs of Year 12 students (n = 8) to analyze how they used decomposition and abstraction to specify the projects, designed algorithms to solve scheduling problems by first devising fundamental operations and then using algorithmic concepts to account for complex and special cases of the problems, and tested and debugged their algorithms. A deductive-inductive analytical process was used to classify students’ responses according to the four cognitive skills to develop sets of subskills to describe how the students engaged these cognitive skills.