A Fixed Point Approach to the Classification of Markov Chains with a Tree Structure

In this paper, we study the classification problem of discrete time and continuous time Markov processes with a tree structure. We first show some useful properties associated with the fixed points of a nondecreasing mapping. Mainly we find the conditions for a fixed point to be the minimal fixed point by using fixed point theory and degree theory. We then use these results to identify conditions for Markov chains of M/G/1 type or GI/M/1 type with a tree structure to be positive recurrent, null recurrent, or transient. The results are generalized to Markov chains of matrix M/G/1 type with a tree structure. For all these cases, a relationship between a certain fixed point, the matrix of partial differentiation (Jacobian) associated with the fixed point, and the classification of the Markov chain with a tree structure is established. More specifically, we show that the Perron-Frobenius eigenvalue of the matrix of partial differentiation associated with a certain fixed point provides information for a complete classification of the Markov chains of interest.     

Approximating M/G/1 Waiting Time Tail Probabilities

Abstract

We propose a new approximation formula for the waiting time tail probability of the M/G/1 queue with FIFO discipline and unlimited waiting space. The aim is to address the difficulty of obtaining good estimates when the tail probability has non-exponential asymptotics. We show that the waiting time tail probability can be expressed in terms of the waiting time tail probability of a notional M/G/1 queue with truncated service time distribution plus the tail probability of an extreme order statistic. The Cramér–Lundberg approximation is applied to approximate the tail probability of the notional queue. In essence, our technique extends the applicability of the Cramér–Lundberg approximation to cases where the standard Lundberg condition does not hold. We propose a simple moment-based technique for estimating the parameters of the approximation; numerical results demonstrate that our approximation can yield very good estimates over the whole range of the argument.     

Estimation in M/Er /1 queueing systems

In this paper, the maximum likelihood estimates of the parameters for the M/E_r /1 queueing model are derived when the queue size at each departure point is observed. A numerical example is generated by simulating a finite Markov chain to illustrate the methodology for estimating the parameters with variable Erlang service time distribution. The problem of hypothesis testing and simultaneous Confidence regions of the parameter is also investigated.0     

Characterizing the BMAP/MAP/1 Departure Process via the ETAQA Truncation

Abstract

We propose a family of finite approximations for the departure process of a BMAP/MAP/1 queue. The departure process approximations are derived via an exact aggregate solution technique (called ETAQA) applied to M/G/1-type Markov processes. The proposed approximations are indexed by a parameter n(n > 1), which determines the size of the output model as n + 1 block levels of the M/G/1-type process. This output approximation preserves exactly the marginal distribution of the true departure process and the lag correlations of the interdeparture times up to lag n ? 2. Experimental results support the applicability of the proposed approximation in traffic-based decomposition of queueing networks.     

The rate of convergence to stationarity for M/G/1 models with admission controls via coupling

We study the workload processes of two M/G/1 queueing systems with restricted capacity: in Model 1 any service requirement that would exceed a certain capacity threshold is truncated; in Model 2 new arrivals do not enter the system if they have to wait more than a fixed threshold time in line. For Model 1 we obtain several results concerning the rate of convergence to equilibrium. In particular, we derive uniform bounds for geometric ergodicity with respect to certain subclasses. For Model 2 geometric ergodicity follows from the finiteness of the moment-generating function of the service time distribution. We derive bounds for the convergence rates in special cases. The proofs use the coupling method.     

Confidence Intervals of Performance Measures for an M/G/1 Queueing System

In this article, we discuss constructing confidence intervals (CIs) of performance measures for an M/G/1 queueing system. Fiducial empirical distribution is applied to estimate the service time distribution. We construct fiducial empirical quantities (FEQs) for the performance measures. The relationship between generalized pivotal quantity and fiducial empirical quantity is illustrated. We also present numerical examples to show that the FEQs can yield new CIs dominate the bootstrap CIs in relative coverage (defined as the ratio of coverage probability to average length of CI) for performance measures of an M/G/1 queueing system in most of the cases.     

A Spectral Method for a Nonpreemptive Priority BMAP/G/1 QUEUE

Abstract

In this paper we consider a nonpreemptive priority queue with two priority classes of customers. Customers arrive according to a batch Markovian arrival process (BMAP). In order to calculate the boundary vectors we propose a spectral method based on zeros of the determinant of a matrix function and the corresponding eigenvectors. It is proved that there are M zeros in a set Ω, where M is the size of the state space of the underlying Markov process. The zeros are calculated by the Durand-Kerner method, and the stationary joint probability of the numbers of customers of classes 1 and 2 at departures is derived by the inversion of the two-dimensional Fourier transform. For a numerical example, the stationary probability is calculated.     

Bayesian estimation for the M/G/1 queue using a phase-type approximation

This article deals with Bayesian inference and prediction for M/G/1 queueing systems. The general service time density is approximated with a class of Erlang mixtures which are phase-type distributions. Given this phase-type approximation, an explicit evaluation of measures such as the stationary queue size, waiting time and busy period distributions can be obtained. Given arrival and service data, a Bayesian procedure based on reversible jump Markov Chain Monte Carlo methods is proposed to estimate system parameters and predictive distributions.     

Explicit Formulae for the Queue Length Distribution of Batch Arrival Systems

Abstract

A G ^θ I/G/1-type batch arrival system is considered. Explicit formulae for the distribution of queue length both at the fixed time t and as t → ∞ are obtained. The study is based on the generalization of Korolyuk's method for semi-markov random walks.     

β-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.     

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.     

Computing the conditional stationary distribution in Markov chains of level-dependent M/G/1-type

This paper considers the computation of the conditional stationary distribution in Markov chains of level-dependent M/G/1-type, given that the level is not greater than a predefined threshold. This problem has been studied recently and a computational algorithm is proposed under the assumption that matrices representing downward jumps are nonsingular. We first show that this assumption can be eliminated in a general setting of Markov chains of level-dependent G/G/1-type. Next we develop a computational algorithm for the conditional stationary distribution in Markov chains of level-dependent M/G/1-type, by modifying the above-mentioned algorithm slightly. In principle, our algorithm is applicable to any Markov chain of level-dependent M/G/1-type, if the Markov chain is irreducible and positive-recurrent. Furthermore, as an input to the algorithm, we can set an error bound for the computed conditional distribution, which is a notable feature of our algorithm. Some numerical examples are also provided.     

A Robust Variable Selection to t-type Joint Generalized Linear Models via Penalized t-type Pseudo-likelihood

Although the t-type estimator is a kind of M-estimator with scale optimization, it has some advantages over the M-estimator. In this article, we first propose a t-type joint generalized linear model as a robust extension to the classical joint generalized linear models for modeling data containing extreme or outlying observations. Next, we develop a t-type pseudo-likelihood (TPL) approach, which can be viewed as a robust version to the existing pseudo-likelihood (PL) approach. To determine which variables significantly affect the variance of the response variable, we then propose a unified penalized maximum TPL method to simultaneously select significant variables for the mean and dispersion models in t-type joint generalized linear models. Thus, the proposed variable selection method can simultaneously perform parameter estimation and variable selection in the mean and dispersion models. With appropriate selection of the tuning parameters, we establish the consistency and the oracle property of the regularized estimators. Simulation studies are conducted to illustrate the proposed methods.     

Sojourn time in an M/M/1 processor sharing queue with permanent customers

We explicitly compute the sojourn time distribution of an arbitrary customer in an M/M/1 processor sharing (PS) queue with permanent customers. We notably exhibit the orthogonal structure associated with this queuing system and we show how sieved Pollaczek polynomials and their associated orthogonality measure can be used to obtain an explicit representation for the complementary cumulative distribution function of the sojourn time of a customer. This explicit formula subsequently allows us to compute the two first moments of this random variable and to study the asymptotic behavior of its distribution. The most salient result is that the decay rate depends on the load of the system and the number K of permanent customers. When the load is above a certain threshold depending on K, the decay rate is identical to that of a regular M/M/1 PS queue.     

Explicit formulae and convergence rate for the system M α /G/1/N as N→∞

The paper deals with the system M ^α /G/1/N with a finite number of waiting places in which arrivals can occur in a group. The number of customers in the line and the virtual waiting time are studied both in the transient and in the stationary regime. Special attention is paid to the stationary distributions of these functionals as N→∞. The number of customers lost during a busy period is considered as well.     

Bayesian analysis of Er/M/1 and Er/M/c queues

Bayesian inference and prediction tasks for Er/M/1 and Er/M/c queues are undertaken. Equilibrium probabilities of the queue size and waiting time distributions are estimated using conditional Monte-Carlo simulation methods. We illustrate that some standard queueing measures do not exist when independent priors are used for the arrival and service rates of a G/M/1 queue.     

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.     

Profust reliability of linear and circular type F and G systems having two failure criteria under Markov dependency

In this study, the profust reliabilities of (n, f, k): F(G) and < n, f, k > : F(G) systems for Markov dependent components are investigated. Having two failure criteria are the common features of these four systems. The usage of both fuzzy approach and two failure criteria in the same system provides us more realistic approach to evaluate the reliability of more complex systems. The component configurations are examined for both linear and circular sequences and the working principle of systems are studied for both F and G systems. Under all these assumptions, the profust reliabilities of (n, f, k): F(G) and < n, f, k > : F(G) systems are obtained using the distribution of run statistics. Also a new membership function different from the linear membership function which is generally used in the literature is proposed. Some numerical results which allow the comparison of the systems from various perspectives and various figures for both linear and circular type systems are presented. Some special cases (between Markov – iid assumption, conventional – profust reliability) are also considered.     

The rules of conditional inference: Is there a universal definition of nonformation?

Summary We consider the ideas of sufficiency and ancillarity for parametric models with nuisance parameters, and more generally Barndorff-Nielsen's notion of nonformation. The original four definitions of non-formation, namelyB-,S-,G- andM-nonformation, each cover different types of models. We stress the interpretation of nonformation in terms of the idea of perfect fit. This leads to a new definition of nonformation, calledI-nonformation, which is well suited for inference in exponential families. We also consider Rémon's concept ofL-sufficiency, and a recent extension toL-nonformation, due to Barndorff-Nielsen, which unifies and extendsB-,S- andG- nonformation. We study the relations between these six definitions, and show that they are all special cases ofM-nonformation. All animals are equal, but some animals are more equal than others. From ‘Animal Farm’, by G. Orwell (1945).     

Matrix–geometric analysis of the discrete time Gi/G/1 system

In this paper, we show that the discrete GI/G/1 system can be analysed as a QBD process with infinite blocks. Most importantly, we show that Matrix–geometric method can be used for analyzing this general queue system including establishing its stability criterion and for obtaining the explicit stationary probability and the waiting time distributions. This also settles the unwritten myth that Matrix–geometric method is limited to cases with at least one Markov based characterizing parameter, i.e. either interarrival or service times, in the case of queueing systems.