A Poisson Limit Theorem for Reliability Models Based on Markov Chains

Abstract

In this article, we deal with a class of discrete-time reliability models. The failures are assumed to be generated by an underlying time inhomogeneous Markov chain. The multivariate point process of failures is proved to converge to a Poisson-type process when the failures are rare. As a result, we obtain a Compound Poisson approximation of the cumulative number of failures. A rate of convergence is provided.     

AN INFINITE-PHASE QUASI-BIRTH-AND-DEATH MODEL FOR THE NON-PREEMPTIVE PRIORITY M/PH/1 QUEUE

This paper considers a single server queue that handles arrivals from N classes of customers on a non-preemptive priority basis. Each of the N classes of customers features arrivals from a Poisson process at rate λ _i and class-dependent phase type service. To analyze the queue length and waiting time processes of this queue, we derive a matrix geometric solution for the stationary distribution of the underlying Markov chain. A defining characteristic of the paper is the fact that the number of distinct states represented within the sub-level is countably infinite, rather than finite as is usually assumed. Among the results we obtain in the two-priority case are tractable algorithms for the computation of both the joint distribution for the number of customers present and the marginal distribution of low-priority customers, and an explicit solution for the marginal distribution of the number of high-priority customers. This explicit solution can be expressed completely in terms of the arrival rates and parameters of the two service time distributions. These results are followed by algorithms for the stationary waiting time distributions for high- and low-priority customers. We then address the case of an arbitrary number of priority classes, which we solve by relating it to an equivalent three-priority queue. Numerical examples are also presented.     

Approximated Transient Queue Length and Waiting Time Distributions via Steady State Analysis

Abstract

We propose a method to approximate the transient performance measures of a discrete time queueing system via a steady state analysis. The main idea is to approximate the system state at time slot t or on the n-th arrival–-depending on whether we are studying the transient queue length or waiting time distribution–-by the system state after a negative binomially distributed number of slots or arrivals. By increasing the number of phases k of the negative binomial distribution, an accurate approximation of the transient distribution of interest can be obtained.

In order to efficiently obtain the system state after a negative binomially distributed number of slots or arrivals, we introduce so-called reset Markov chains, by inserting reset events into the evolution of the queueing system under consideration. When computing the steady state vector of such a reset Markov chain, we exploit the block triangular block Toeplitz structure of the transition matrices involved and we directly obtain the approximation from its steady state vector. The concept of the reset Markov chains can be applied to a broad class of queueing systems and is demonstrated in full detail on a discrete-time queue with Markovian arrivals and phase-type services (i.e., the D-MAP/PH/1 queue). We focus on the queue length distribution at time t and the waiting time distribution of the n-th customer. Other distributions, e.g., the amount of work left behind by the n-th customer, that can be acquired in a similar way, are briefly touched upon.

Using various numerical examples, it is shown that the method provides good to excellent approximations at low computational costs–-as opposed to a recursive algorithm or a numerical inversion of the Laplace transform or generating function involved–-offering new perspectives to the transient analysis of practical queueing systems.     

A class of small deviation theorems for the random variables associated with mth-order asymptotic circular Markov chains

ABSTRACT

In this article, we study a class of small deviation theorems for the random variables associated with mth-order asymptotic circular Markov chains. First, the definition of mth-order asymptotic circular Markov chain is introduced, then by applying the known results of the limit theorem for mth-order non homogeneous Markov chain, the small deviation theorem on the frequencies of occurrence of states for mth-order asymptotic circular Markov chains is established. Next, the strong law of large numbers and asymptotic equipartition property for this Markov chains are obtained. Finally, some results of mth-order nonhomogeneous Markov chains are given.     

Estimation of the Entropy Rate of a Countable Markov Chain

We consider here ergodic homogeneous Markov chains with countable state spaces. The entropy rate of the chain is an explicit function of its transition and stationary distributions. We construct estimators for this entropy rate and for the entropy of the stationary distribution of the chain, in the parametric and nonparametric cases. We study estimation from one sample with long length and from many independent samples with given length. In the parametric case, the estimators are deduced by plug-in from the maximum likelihood estimator of the parameter. In the nonparametric case, the estimators are deduced by plug-in from the empirical estimators of the transition and stationary distributions. They are proven to have good asymptotic properties.     

Mixing and moments properties of a non-stationary copula-based Markov process

Abstract

We provide conditions under which a non-stationary copula-based Markov process is geometric β-mixing and geometric ρ-mixing. Our results generalize some results of Beare who considers the stationary case. As a particular case we introduce a stochastic process, that we call convolution-based Markov process, whose construction is obtained by using the C-convolution operator which allows the increments to be dependent. Within this subclass of processes we characterize a modified version of the standard random walk where copulas and marginal distributions involved are in the same elliptical family. We study mixing and moments properties to identify the differences compared to the standard case.     

On the Exponential Decay Rate of the Tail of a Discrete Probability Distribution

Abstract

We give a sufficient condition for the exponential decay of the tail of a discrete probability distribution π = (π _n ) _n≥0 in the sense that lim _n→∞(1/n) log∑ _i>n π _i  = ?θ with 0 < θ < ∞. We focus on analytic properties of the probability generating function of a discrete probability distribution, especially, the radius of convergence and the number of poles on the circle of convergence. Furthermore, we give an example of an M/G/1 type Markov chain such that the tail of its stationary distribution does not decay exponentially.     

Parameter Estimation in Minification Processes

Abstract

In this article it is proved that the stationary Markov sequences generated by minification models are ergodic and uniformly mixing. These results are used to establish the optimal properties of estimators for the parameters in the model. The problem of estimating the parameters in the exponential minification model is discussed in detail.     

Central Limit Theorem approximations for the number of runs in Markov-dependent binary sequences

We consider Markov-dependent binary sequences and study various types of success runs (overlapping, non-overlapping, exact, etc.) by examining additive functionals based on state visits and transitions in an appropriate Markov chain. We establish a multivariate Central Limit Theorem for the number of these types of runs and obtain its covariance matrix by means of the recurrent potential matrix of the Markov chain. Explicit expressions for the covariance matrix are given in the Bernoulli and a simple Markov-dependent case by expressing the recurrent potential matrix in terms of the stationary distribution and the mean transition times in the chain. We also obtain a multivariate Central Limit Theorem for the joint number of non-overlapping runs of various sizes and give its covariance matrix in explicit form for Markov dependent trials.     

Asymptotic Methods of Enumeration and Applications to Markov Chain Models

Abstract

The purpose of this article is to present analytic methods for determining the asymptotic behaviour of the coefficents of power series that can be applied to homogeneous discrete quasi death and birth processes. It turns that there are in principle only three types for the asymptotic behaviour. The process either converges to the stationary distribution or it can be approximated in terms of a reflected Brownian motion or by a Brownian motion. In terms of Markov chains these cases correspond to positive recurrence, to null recurrence, and to non recurrence. The same results hold for the continuous case, too.     

Stationary distributions for a class of Markov-modulated tandem fluid queues

ABSTRACT

We consider a model consisting of two fluid queues driven by the same background continuous-time Markov chain, such that the rates of change of the fluid in the second queue depend on whether the first queue is empty or not: when the first queue is nonempty, the content of the second queue increases, and when the first queue is empty, the content of the second queue decreases.

We analyze the stationary distribution of this tandem model using operator-analytic methods. The various densities (or Laplace–Stieltjes transforms thereof) and probability masses involved in this stationary distribution are expressed in terms of the stationary distribution of some embedded process. To find the latter from the (known) transition kernel, we propose a numerical procedure based on discretization and truncation. For some examples we show the method works well, although its performance is clearly affected by the quality of these approximations, both in terms of accuracy and run time.     

Markov chain Monte Carlo exact tests for incomplete two-way contingency tables

We consider testing the quasi-independence hypothesis for two-way contingency tables which contain some structural zero cells. For sparse contingency tables where the large sample approximation is not adequate, the Markov chain Monte Carlo exact tests are powerful tools. To construct a connected chain over the two-way contingency tables with fixed sufficient statistics and an arbitrary configuration of structural zero cells, an algebraic algorithm proposed by Diaconis and Sturmfels [Diaconis, P. and Sturmfels, B. (1998). The Annals of statistics, 26, pp. 363–397.] can be used. However, their algorithm does not seem to be a satisfactory answer, because the Markov basis produced by the algorithm often contains many redundant elements and is hard to interpret. We derive an explicit characterization of a minimal Markov basis, prove its uniqueness, and present an algorithm for obtaining the unique minimal basis. A computational example and the discussion on further basis reduction for the case of positive sufficient statistics are also given.     

A note on the passage time of finite-state Markov chains

Consider a Markov chain with finite state {0, 1, …, d}. We give the generation functions (or Laplace transforms) of absorbing (passage) time in the following two situations: (1) the absorbing time of state d when the chain starts from any state i and absorbing at state d; (2) the passage time of any state i when the chain starts from the stationary distribution supposed the chain is time reversible and ergodic. Example shows that it is more convenient compared with the existing methods, especially we can calculate the expectation of the absorbing time directly.     

Long-Range Dependence of Markov Renewal Processes

This paper examines long‐range dependence (LRD) and asymptotic properties of Markov renewal processes generalizing results of Daley for renewal processes. The Hurst index and discrepancy function, which is the difference between the expected number of arrivals in (0, t] given a point at 0 and the number of arrivals in (0, t] in the time stationary version, are examined in terms of the moment index. The moment index is the supremum of the set of r > 0 such that the rth moment of the first return time to a state is finite, employing the solidarity results of Sgibnev. The results are derived for irreducible, regular Markov renewal processes on countable state spaces. The paper also derives conditions to determine the moment index of the first return times in terms of the Markov renewal kernel distribution functions of the process.     

Workload Process,Waiting Times,and Sojourn Times in a Discrete Time MMAP[K]/SM[K]/1/FCFS Queue

Abstract

In this paper, we study the total workload process and waiting times in a queueing system with multiple types of customers and a first-come-first-served service discipline. An M/G/1 type Markov chain, which is closely related to the total workload in the queueing system, is constructed. A method is developed for computing the steady state distribution of that Markov chain. Using that steady state distribution, the distributions of total workload, batch waiting times, and waiting times of individual types of customers are obtained. Compared to the GI/M/1 and QBD approaches for waiting times and sojourn times in discrete time queues, the dimension of the matrix blocks involved in the M/G/1 approach can be significantly smaller.     

Level-Phase Independence for Fluid Queues

ABSTRACT

A Markov-modulated fluid queue is a two-dimensional Markov process; the first dimension is continuous and is usually called the level, and the second is the state of a Markov process that determines the evolution of the level, it is usually called the phase. We show that it is always possible to modify the transition rules at the boundary level of the fluid queue in order to obtain independence between the level and the phase under the stationary distribution. We obtain this result by exploiting the similarity between fluid queues and Quasi-Birth-and-Death (QBD) processes.     

Stochastic monotonicity and comparability of Markov chains with block-monotone transition matrices and their applications to queueing systems

ABSTRACT

Motivated by various applications in queueing theory, this article is devoted to the stochastic monotonicity and comparability of Markov chains with block-monotone transition matrices. First, we introduce the notion of block-increasing convex order for probability vectors, and characterize the block-monotone matrices in the sense of the block-increasing order and block-increasing convex order. Second, we characterize the Markov chain with general transition matrix by martingale and provide a stochastic comparison of two block-monotone Markov chains under the two block-monotone orders. Third, the stochastic comparison results for the Markov chains corresponding to the discrete-time GI/G/1 queue with different service distributions under the two block-monotone orders are given, and the lower bound and upper bound of the Markov chain corresponding to the discrete-time GI/G/1 queue in the sense of the block-increasing convex order are found.     

The strong law of large numbers and the Shannon-McMillan theorem for the mth-order nonhomogeneous Markov chains indexed by an m rooted Cayley tree

ABSTRACT

In this article, we studied the strong law of large numbers(LLN) and Shannon-McMillan theorem for an mth-order nonhomogeneous Markov chain indexed by an m- rooted Cayley tree. This article generalized the relative results of level mth-order nonhomogeneous Markov chains indexed by an m- rooted Cayley tree.     

ASYMPTOTIC PROPERTIES FOR MAXIMUM LIKELIHOOD ESTIMATORS FOR RELIABILITY AND FAILURE RATES OF MARKOV CHAINS

ABSTRACT

In this paper, we shall study a homogeneous ergodic, finite state, Markov chain with unknown transition probability matrix. Starting from the well known maximum likelihood estimator of transition probability matrix, we define estimators of reliability and its measurements. Our aim is to show that these estimators are uniformly strongly consistent and converge in distribution to normal random variables. The construction of the confidence intervals for availability, reliability, and failure rates are also given. Finally we shall give a numerical example for illustration and comparing our results with the usual empirical estimator results.