Estimating Stochastic Dynamical Systems Driven by a Continuous-Time Jump Markov Process

We discuss the use of a continuous-time jump Markov process as the driving process in stochastic differential systems. Results are given on the estimation of the infinitesimal generator of the jump Markov process, when considering sample paths on random time intervals. These results are then applied within the framework of stochastic dynamical systems modeling and estimation. Numerical examples are given to illustrate both consistency and asymptotic normality of the estimator of the infinitesimal generator of the driving process. We apply these results to fatigue crack growth modeling as an example of a complex dynamical system, with applications to reliability analysis.      

A production system with two job classes,changeover times and revisitation

This paper, motivated by the need to predict performance of production systems with random arrivals, setup times and revisitation, presents an imbedded Markov chain analysis of the underlyingM/G/1 queue with two customer classes, changeover times and instantaneous Bernoulli feedback. It is assumed that jobs are scheduled according to the exhaustive alternative priority queue discipline. Expressions for the mean waiting time and the nonsaturation condition are derived under two different priority assignments to the repeat customers. Sojourn times under these priority assignments are shown to possess a convex ordering. Results of the study are also applicable to data communication networks that operate under cyclic switching mechanisms. Research supported in part by Natural Sciences and Engineering Research Council of Canada.     

Markov modulated Bernoulli process

We consider a Bernoulli process where the success probability changes with respect to a Markov chain. Such a model represents an interesting application of stochastic processes where the parameters are not constants; rather, they are stochastic processes themselves due to their dependence on a randomly changing environment. The model operates in a random environment depicted by a Markov chain so that the probability of success at each trial depends on the state of the environment. We will concentrate, in particular, on applications in reliability theory to motivate our model. The analysis will focus on transient as well as long-term behaviour of various processes involved.     

The Cumulative Idle Time in an ND/D/1 Queue

An ND/D/1 queueing model means that N independent periodic sources are served by a single server and the packets have the same size. These models have received close attention as general queueing models in telecommunications. Both discrete models, where it is only permitted to transmit packets at fixed time instances, and also continuous models, where the time of transmission is not restricted, can be applied in the modeling. This paper provides the exact distribution of the cumulative idle time duration in such queuing systems and also proposes accurate approximation formulae for large systems. The results of this paper are of practical significance because existing approximations of the distribution of the cumulative idle time can be replaced by the proposed formulae.AMS subject classification: 68M20, 60K25This revised version was published online in June 2005 with corrected coverdate     

Asymptotic expansions of backward equations for two-time-scale Markov chains in continuous time

This work develops asymptotic expansions for solutions of systems of backward equations of time- inhomogeneous Maxkov chains in continuous time. Owing to the rapid progress in technology and the increasing complexity in modeling, the underlying Maxkov chains often have large state spaces, which make the computa- tional tasks ihfeasible. To reduce the complexity, two-time-scale formulations are used. By introducing a small parameter ε〉 0 and using suitable decomposition and aggregation procedures, it is formulated as a singular perturbation problem. Both Markov chains having recurrent states only and Maxkov chains including also tran- sient states are treated. Under certain weak irreducibility and smoothness conditions of the generators, the desired asymptotic expansions axe constructed. Then error bounds are obtained.     

A BMAP/G/1 Retrial Queue with a Server Subject to Breakdowns and Repairs

In this paper, we consider a BMAP/G/1 retrial queue with a server subject to breakdowns and repairs, where the life time of the server is exponential and the repair time is general. We use the supplementary variable method, which combines with the matrix-analytic method and the censoring technique, to study the system. We apply the RG-factorization of a level-dependent continuous-time Markov chain of M/G/1 type to provide the stationary performance measures of the system, for example, the stationary availability, failure frequency and queue length. Furthermore, we use the RG-factorization of a level-dependent Markov renewal process of M/G/1 type to express the Laplace transform of the distribution of a first passage time such as the reliability function and the busy period.     

Mixing properties of the generalized T, T-1-process

Consider a general random walk on ℤ^d together with an i.i.d. random coloring of ℤ^d. TheT, T ^-1-process is the one where time is indexed by ℤ, and at each unit of time we see the step taken by the walk together with the color of the newly arrived at location. S. Kalikow proved that ifd = 1 and the random walk is simple, then this process is not Bernoulli. We generalize his result by proving that it is not Bernoulli ind = 2, Bernoulli but not Weak Bernoulli ind = 3 and 4, and Weak Bernoulli ind ≥ 5. These properties are related to the intersection behavior of the past and the future of simple random walk. We obtain similar results for general random walks on ℤ^d, leading to an almost complete classification. For example, ind = 1, if a step of sizex has probability proportional to l/|x|^α (x ⊋ 0), then theT, T ^-1-process is not Bernoulli when α ≥2, Bernoulli but not Weak Bernoulli when 3/2 ≤α < 2, and Weak Bernoulli when 1 < α < 3/2. Research partially carried out while a guest of the Department of Mathematics, Chalmers University of Technology, Sweden in January 1996. Research supported by grants from the Swedish Natural Science Research Council and from the Royal Swedish Academy of Sciences.     

A single-server discrete-time queue with correlated positive and negative customer arrivals

An MMBP/Geo/1 queue with correlated positive and negative customer arrivals is studied. In the infinite-capacity queueing system, positive customers and negative customers are generated by a Bernoulli bursty source with two correlated geometrically distributed periods. I.e., positive and negative customers arrive to the system according to two different geometrical arrival processes. Under the late arrival scheme (LAS), two removal disciplines caused by negative customers are investigated in the paper. In individual removal scheme, a negative customer removes a positive customer in service if any, while in disaster model, a negative customer removes all positive customers in the system if any. The negative customer arrival has no effect on the system if it finds the system empty. We analyze the Markov chains underlying the queueing systems and evaluate the performance of two systems based on generating functions technique. Some explicit solutions of the system, such as the average buffer content and the stationary probabilities are obtained. Finally, the effect of several parameters on the system performance is shown numerically.     

Multi-Server Queueing Systems with Multiple Priority Classes

We present the first near-exact analysis of an M/PH/k queue with m > 2 preemptive-resume priority classes. Our analysis introduces a new technique, which we refer to as Recursive Dimensionality Reduction (RDR). The key idea in RDR is that the m-dimensionally infinite Markov chain, representing the m class state space, is recursively reduced to a 1-dimensionally infinite Markov chain, that is easily and quickly solved. RDR involves no truncation and results in only small inaccuracy when compared with simulation, for a wide range of loads and variability in the job size distribution. Our analytic methods are then used to derive insights on how multi-server systems with prioritization compare with their single server counterparts with respect to response time. Multi-server systems are also compared with single server systems with respect to the effect of different prioritization schemes—“smart” prioritization (giving priority to the smaller jobs) versus “stupid” prioritization (giving priority to the larger jobs). We also study the effect of approximating m class performance by collapsing the m classes into just two classes. Supported by NSF Career Grant CCR-0133077, NSF Theory CCR-0311383, NSF ITR CCR-0313148, and IBM Corporation via Pittsburgh Digital Greenhouse Grant 2003. AMS subject classification: 60K25, 68M20, 90B22, 90B36     

Continuous and discrete flows over time

Network flows over time form a fascinating area of research. They model the temporal dynamics of network flow problems occurring in a wide variety of applications. Research in this area has been pursued in two different and mainly independent directions with respect to time modeling: discrete and continuous time models. In this paper we deploy measure theory in order to introduce a general model of network flows over time combining both discrete and continuous aspects into a single model. Here, the flow on each arc is modeled as a Borel measure on the real line (time axis) which assigns to each suitable subset a real value, interpreted as the amount of flow entering the arc over the subset. We focus on the maximum flow problem formulated in a network where capacities on arcs are also given as Borel measures and storage might be allowed at the nodes of the network. We generalize the concept of cuts to the case of these Borel Flows and extend the famous MaxFlow-MinCut Theorem.     

Bayesian estimation of system reliability in Brownian stress-strength models

A stress-strength system fails as soon as the applied stress,X, is at least as much as the strength,Y, of the system. Stress and strength are time-varying in many real-life systems but typical statistical models for stress-strength systems are static. In this article, the stress and strength processes are dynamically modeled as Brownian motions. The resulting stress-strength system is then governed by a time-homogeneous Markov process with an absorption barrier at O. Conjugate as well as non-informative priors are developed for the model parameters and Markov chain sampling methods are used for posterior inference of the reliability of the stress-strength system. A generalization of this model is described next where the different stress-strength systems are assumed to be exchangeable. The proposed Bayesian analyses are illustrated in two examples where we obtain posterior estimates as well as perform model checking by cross-validation.     

A batch arrival retrial queue with two phases of service and Bernoulli vacation schedule

We consider an M X /G/1 queueing system with two phases of heterogeneous service and Bernoulli vacation schedule which operate under a linear retrial policy. In addition, each individual customer is subject to a control admission policy upon the arrival. This model generalizes both the classical M/G/1 retrial queue with arrivals in batches and a two phase batch arrival queue with a single vacation under Bernoulli vacation schedule. We will carry out an extensive stationary analysis of the system , including existence of the stationary regime, embedded Markov chain, steady state distribution of the server state and number of customer in the retrial group, stochastic decomposition and calculation of the first moment.     

Spatial mixing and nonlocal Markov chains

We consider spin systems with nearest‐neighbor interactions on an n‐vertex d‐dimensional cube of the integer lattice graph . We study the effects that the strong spatial mixing condition (SSM) has on the rate of convergence to equilibrium of nonlocal Markov chains. We prove that when SSM holds, the relaxation time (i.e., the inverse spectral gap) of general block dynamics is O(r), where r is the number of blocks. As a second application of our technology, it is established that SSM implies an O(1) bound for the relaxation time of the Swendsen‐Wang dynamics for the ferromagnetic Ising and Potts models. We also prove that for monotone spin systems SSM implies that the mixing time of systematic scan dynamics is . Our proofs use a variety of techniques for the analysis of Markov chains including coupling, functional analysis and linear algebra.     

Queue length distributions in a markov model of a multistage clocked queueing network

In [4], we treated the problem of passage through a discrete-time clock-regulated multistage queueing network by modeling the input time series {a_n} to each queue as a Markov chain. We showed how to transform probability transition information from the input of one queue to the input of the next in order to predict mean queue length at each stage. The Markov approximation is very good for p = E(a_n) ≦ ½, which is in fact the range of practical utility. Here we carry out a Markov time series input analysis to predict the stage to stage change in the probability distribution of queue length. The main reason for estimating the queue length distribution at each stage is to locate “hot spots”, loci where unrestricted queue length would exceed queue capacity, and a quite simple expression is obtained for this purpose.