A new look at Markov processes of G/M/1-type

We present a new method for deriving the stationary distribution of an ergodic Markov process of G/M/1-type in continuous-time, by deriving and making use of a new representation for each element of the rate matrices contained in these distributions. This method can also be modified to derive the Laplace transform of each transition function associated with Markov processes of G/M/1-type.     

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.     

Strong laws of large numbers for the mth-order asymptotic odd–even Markov chains indexed by an m-rooted Cayley tree

In this article, we will study the strong laws of large numbers and asymptotic equipartition property (AEP) for mth-order asymptotic odd–even Markov chains indexed by an m-rooted Cayley tree. First, the definition of mth-order asymptotic odd–even Markov chains indexed by an m-rooted Cayley tree is introduced, then the strong limit theorem for this Markov chains is established. Next, the strong laws of large numbers for the frequencies of ordered couple of states for mth-order asymptotic odd–even Markov chains indexed by an m-rooted Cayley tree are obtained. Finally, we prove the AEP for this Markov chains.     

The Waiting Time Distribution of a Type k Customer in a Discrete-Time MMAP[K]/PH[K]/c (c = 1, 2) Queue Using QBDs

Abstract

This paper presents an improved method to calculate the delay distribution of a type k customer in a first-come-first-serve (FCFS) discrete-time queueing system with multiple types of customers, where each type has different service requirements, and c servers, with c = 1, 2 (the MMAP[K]/PH[K]/c queue). The first algorithms to compute this delay distribution, using the GI/M/1 paradigm, were presented by Van Houdt and Blondia [Van Houdt, B.; Blondia, C. The delay distribution of a type k customer in a first come first served MMAP[K]/PH[K]/1 queue. J. Appl. Probab. 2002, 39 (1), 213–222; The waiting time distribution of a type k customer in a FCFS MMAP[K]/PH[K]/2 queue. Technical Report; 2002]. The two most limiting properties of these algorithms are: (i) the computation of the rate matrix R related to the GI/M/1 type Markov chain, (ii) the amount of memory needed to store the transition matrices A _l and B _l . In this paper we demonstrate that each of the three GI/M/1 type Markov chains used to develop the algorithms in the above articles can be reduced to a QBD with a block size which is only marginally larger than that of its corresponding GI/M/1 type Markov chain. As a result, the two major limiting factors of each of these algorithms are drastically reduced to computing the G matrix of the QBD and storing the 6 matrices that characterize the QBD. Moreover, these algorithms are easier to implement, especially for the system with c = 2 servers. We also include some numerical examples that further demonstrate the reduction in computational resources.     

Tree Structured QBD Markov Chains and Tree‐Like QBD Processes

Abstract

In this paper, we show that an arbitrary tree structured quasi‐birth–death (QBD) Markov chain can be embedded in a tree‐like QBD process with a special structure. Moreover, we present an algebraic proof that applying the natural fixed point iteration (FPI) to the nonlinear matrix equation V = B + ∑ _s=1 ^d U _s (I ? V)^?1 D _s that solves the tree‐like QBD process, is equivalent to the more complicated iterative algorithm presented by Yeung and Alfa (1996).     

β-Invariant Measures for Transition Matrices of GI/M/1 Type

In this paper, we study transition matrices of GI/M/1 type by using the approach proposed in Li and Zhao.[13] Li, Q.L. and Zhao, Y.Q. 2002. “A constructive method for finding β-invariant measures for transition matrices of M/G/1 type”. In Matrix-Analytic Methods Theory and Applications 237–263. New Jersey: World Scientific. [Crossref] , [Google Scholar] We obtain conditions on the α-classification of states for the transition matrix of GI/M/1 type. Unlike for matrices of M/G/1 type where association of the matrix multiplication can be easily justified, for matrices of GI/M/ type, we first construct formal expressions for the β-invariant measure based on a representation of factorization of the transition matrix, and then show that it is a β-invariant measure directly. We also prove some spectral properties for the matrix of GI/M/1 type, which are not only used in constructing a formal expression for the β-invariant measure, but also of their own interest. We point out that the spectral analysis required for studying matrices of GI/M/1 type is much more sophisticated than that for matrices of M/G/1 type. Finally, we discuss connections of expressions for the β-invariant measure provided in this paper and in the literature.     

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.     

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.     

Conditional entropy,entropy density,and strong law of large numbers for generalized controlled tree-indexed Markov chains

In this paper, we first introduces a tree model without degree boundedness restriction namely generalized controlled tree T, which is an extension of some known tree models, such as homogeneous tree model, uniformly bounded degree tree model, controlled tree model, etc. Then some limit properties including strong law of large numbers for generalized controlled tree-indexed non homogeneous Markov chain are obtained. Finally, we establish some entropy density properties, monotonicity of conditional entropy, and entropy properties for generalized controlled tree-indexed Markov chains.     

Strong law of large numbers of the delayed sums for Markov Chains indexed by a Cayley tree

Abstract

In this paper, we will study the strong law of large numbers of the delayed sums for Markov chains indexed by a Cayley tree with countable state spaces. Firstly, we prove a strong limit theorem for the delayed sums of the bivariate functions for Markov chains indexed by a Cayley tree. Secondly, the strong law of large numbers for the frequencies of occurrence of states of the delayed sums is obtained. As a corollary, we obtain the strong law of large numbers for the frequencies of occurrence of states for countable Markov chains indexed by a Cayley tree.     

The group inverse of finite homogeneous QBD processes

Generalized inverses of I?P, where P is a stochastic matrix, play an important role in the theory of Markov chains. In particular, the group inverse (I?P)^# has a probabilistic interpretation and is well suited for algorithmic implementation. We determine (I?P)^# for finite homogeneous quasi-birth-and-death (QBD) processes by exploiting both the structure of the process and the probabilistic properties of the group inverse.     

Large deviations of multiclass M/G/1 queues

Consider a multiclass M/G/1 queue where queued customers are served in their order of arrival at a rate which depends on the customer class. We model this system using a chain with states represented by a tree. Since the service time distribution depends on the customer class, the stationary distribution is not of product form so there is no simple expression for the stationary distribution. Nevertheless, we can find a harmonic function on this chain which provides information about the asymptotics of this stationary distribution. The associated h‐transformation produces a change of measure that increases the arrival rate of customers and decreases the departure rate thus making large deviations common. The Canadian Journal of Statistics 37: 327–346; 2009 © 2009 Statistical Society of Canada     

Phase Type Distributions with Finite Support

This research is motivated by the fact that many random variables of practical interest have a finite support. For fixed a < b, we consider the distribution of a random variable X = (a + Ymod(b ? a)), where Y is a phase type (PH) random variable. We demonstrate that as we traverse for Y the entire set of PH distributions (or even any subset thereof like Coxian that is dense in the class of distributions on [0, ∞)), we obtain a class of matrix exponential distributions dense in (a, b). We call these Finite Support Phase Type Distributions (FSPH) of the first kind. A simple example shows that though dense, this class by itself is not very efficient for modeling; therefore, we introduce (and derive the EM algorithms for) two other classes of finite support phase type distributions (FSPH). The properties of denseness, connection to Markov chains, the EM algorithm, and ability to exploit matrix-based computations should all make these classes of distributions attractive not only for applied probability but also for a much wider variety of fields using statistical methodologies.     

MARKOV CHAINS SATISFYING SIMPLE DRIFT CONDITIONS FOR SUBGEOMETRIC ERGODICITY

This paper is concerned with ergodic Markov chains satisfying a sequence of drift conditions that imply (f, r)- regularity of the chain, by which subgeometric ergodicity is ensured. An interesting exact trade-off result between the exponents of f and r for a special class of state space models by Tuominen and Tweedie (1994) is extended here from integers to real numbers for general Markov chains satisfying these drift conditions simultaneously as well as standard requirements for ergodic Markov chains. In Section 3, we will illustrate by the state space models that the utilization of these drift conditions is a very convenient way to show subgeometric ergodicity of Markov chains including the exact trade-off between the exponents of f and r.     

Nonparametric empirical Bayes for the Dirichlet process mixture model

The Dirichlet process prior allows flexible nonparametric mixture modeling. The number of mixture components is not specified in advance and can grow as new data arrive. However, analyses based on the Dirichlet process prior are sensitive to the choice of the parameters, including an infinite-dimensional distributional parameter G ₀. Most previous applications have either fixed G ₀ as a member of a parametric family or treated G ₀ in a Bayesian fashion, using parametric prior specifications. In contrast, we have developed an adaptive nonparametric method for constructing smooth estimates of G ₀. We combine this method with a technique for estimating α, the other Dirichlet process parameter, that is inspired by an existing characterization of its maximum-likelihood estimator. Together, these estimation procedures yield a flexible empirical Bayes treatment of Dirichlet process mixtures. Such a treatment is useful in situations where smooth point estimates of G ₀ are of intrinsic interest, or where the structure of G ₀ cannot be conveniently modeled with the usual parametric prior families. Analysis of simulated and real-world datasets illustrates the robustness of this approach.     

A functional central limit theorem for Markov additive processes with an application to the closed Lu–Kumar network

A functional central limit theorem for a class of time-homogeneous continuous-time Markov processes (X,Y) is proved. The process X is a positive recurrent Markov process on a countable-state space and the process Y has conditionally independent increments given X. The pair (X,Y) is called a Markov additive process. This paper unifies and generalizes several functional central limit theorems for Markov additive processes. An explicit expression for the variance parameter of the limit process is calculated using the local characteristics of the X process. The functional central limit theorem is then used to prove a heavy traffic limit theorem for the closed Lu–Kumar network.     

A block bootstrap comparison for sparse chains

In this paper we apply the sequential bootstrap method proposed by Collet et al. [Bootstrap Central Limit theorem for chains of infinite order via Markov approximations, Markov Processes and Related Fields 11(3) (2005), pp. 443–464] to estimate the variance of the empirical mean of a special class of chains of infinite order called sparse chains. For this process, we show that we are able to compute numerically the true value of the standard error with any fixed error.

Our main goal is to present a comparison, for sparse chains, among sequential bootstrap, the block bootstrap method proposed by Künsch [The jackknife and the Bootstrap for general stationary observations, Ann. Statist. 17 (1989), pp. 1217–1241] and improved by Liu and Singh [Moving blocks jackknife and Bootstrap capture week dependence, in Exploring the limits of the Bootstrap, R. Lepage and L. Billard, eds., Wiley, New York, 1992, pp. 225–248] and the bootstrap method proposed by Bühlmann [Blockwise bootstrapped empirical process for stationary sequences, Ann. Statist. 22 (1994), pp. 995–1012].     

On L 1-consistency of kernel-type density estimator for stationary markov processes

A convergence result for kernel type density estimators, proved by Devroye and Gyrofi (1985), is extended to stationary Markov processess satisfying (G ₂-condition introduced by Rosenblatt (1970).     

Reliability Analysis of Unrepairable Systems with k-out-of-m:G Subsystems Subject to Suspended Animation

Two unrepairable series structure systems with k-out-of-m:G subsystems and spares are investigated. The first one consists of a k-out-of-m:G subsystem and a series subsystem while the other consists of two k-out-of-m:G subsystems. The systems have identical components with identical lifetime distributions and the working components are suspended as soon as the systems are down. Two Markov models are proposed for the reliability analysis of such systems and closed form results on the reliability and the mean time to failure (MTTF) are presented. Numerical examples are given to illustrate the impact of several parameters on the reliability of the systems.