A computational algorithm for the loss probability in the M/G/1+PH queue

This article develops a computational algorithm for the loss probability in the stationary M/G/1 queue with impatient customers whose impatience times follow a phase-type distribution (M/G/1+PH). The algorithm outputs the loss probability, along with an upper-bound of its numerical error due to truncation, and it is readily applicable to the M/D/1+PH, M/PH/1+PH, and M/Pareto/1+PH queues.     

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.     

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.     

On Block Skip Free Transition Matrices and First Passage Times

Starting from an abstract setting which extends the property “skip free to the left” for transition matrices to a partition of the state space, we develop bounds for the mean hitting time of a Markov chain to an arbitrary subset from an arbitrary initial law. We apply our theory to the embedded Markov chains associated with the M/G/1 and the GI/M/1 queueing systems. We also illustrate its applicability with an asymptotic analysis of a non-reversible Markovian star queueing network with losses.     

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.     

ON THE MAP/G/1 QUEUE WITH LEBESGUE-DOMINATED SERVICE TIME DISTRIBUTION AND LCFS PREEMPTIVE REPEAT SERVICE DISCIPLINE

The present paper contains an analysis of the MAP/G/1 queue with last come first served (LCFS) preemptive repeat service discipline and Lebesgue-dominated service time distribution. The transient distribution is given in terms of a recursive formula. The stationary distribution as well as the stability condition are obtained by means of Markov renewal theory via a QBD representation of the embedded Markov chain at departures and arrivals.     

Parameter estimation for a special class of Markov chains

The followin paper is dedicated to a special class of stationary Markov chains. The transition probabilities are constructed from bivariate distribution functions of the Morgenstem-Type. These Markov chains are defined by their stationary distribution and a parameter a controlling the correlation between succeeding values of the chain. Relevant properties of the Markov chain are discussed. Some estimations of the parameter a are studied. The maximum likelihood estimator is compared with a simple estimator.     

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.     

Perfect simulation of an inventory model for perishable products

We study an inventory model for perishable products with a critical-number ordering policy under the assumption that demand for the product forms an i.i.d. sequence, so that the state of the system forms a Markov chain. Explicit calculation of the stationary distribution has proved impractical in cases where items have reasonably long lifetimes and for systems with large under-up-to levels. Using the recently developed coupling-from-the-past method, we introduce a technique to estimate the stationary distribution of the Markov chain via perfect simulation. The Markov chain that results from the use of a critical-number policy is particularly amenable to these simulation techniques, despite not being ordered in its initial state, since the recursive equations satisfied by the Markov chain enable us to identify specific demand patterns where the backward coupling occurs.     

Shift Techniques and Canonical Factorizations in the Solution of M/G/1-Type Markov Chains

ABSTRACT

By using properties of canonical factorizations, we prove that under very mild assumptions, the shifted cyclic reduction method (SCR) can be applied for solving QBD problems with no breakdown and that it always converges. For general M/G/1 type Markov chains we prove that SCR always converges if no breakdown is encountered. Numerical experiments showing the acceleration provided by SCR versus cyclic reduction are presented.     

A distance-based diagnostic for trans-dimensional Markov chains

Over the last decade the use of trans-dimensional sampling algorithms has become endemic in the statistical literature. In spite of their application however, there are few reliable methods to assess whether the underlying Markov chains have reached their stationary distribution. In this article we present a distance-based method for the comparison of trans-dimensional Markov chain sample output for a broad class of models. This diagnostic will simultaneously assess deviations between and within chains. Illustration of the analysis of Markov chain sample-paths is presented in simulated examples and in two common modelling situations: a finite mixture analysis and a change-point problem.     

Variance estimation in the central limit theorem for Markov chains

This article concerns the variance estimation in the central limit theorem for finite recurrent Markov chains. The associated variance is calculated in terms of the transition matrix of the Markov chain. We prove the equivalence of different matrix forms representing this variance. The maximum likelihood estimator for this variance is constructed and it is proved that it is strongly consistent and asymptotically normal. The main part of our analysis consists in presenting closed matrix forms for this new variance. Additionally, we prove the asymptotic equivalence between the empirical and the maximum likelihood estimation (MLE) for the stationary distribution.     

A new strategy for speeding Markov chain Monte Carlo algorithms

Markov chain Monte Carlo (MCMC) methods have become popular as a basis for drawing inference from complex statistical models. Two common difficulties with MCMC algorithms are slow mixing and long run-times, which are frequently closely related. Mixing over the entire state space can often be aided by careful tuning of the chain's transition kernel. In order to preserve the algorithm's stationary distribution, however, care must be taken when updating a chain's transition kernel based on that same chain's history. In this paper we introduce a technique that allows the transition kernel of the Gibbs sampler to be updated at user specified intervals, while preserving the chain's stationary distribution. This technique seems to be beneficial both in increasing efficiency of the resulting estimates (via Rao-Blackwellization) and in reducing the run-time. A reinterpretation of the modified Gibbs sampling scheme introduced in terms of auxiliary samples allows its extension to the more general Metropolis-Hastings framework. The strategies we develop are particularly helpful when calculation of the full conditional (for a Gibbs algorithm) or of the proposal distribution (for a Metropolis-Hastings algorithm) is computationally expensive. Partial financial support from FAR 2002-3, University of Insubria is gratefully acknowledged.     

Minimal Markov Basis for Tests of Main Effect Models for 2p-1 Fractional Factorial Designs of Resolution p

We consider conditional exact tests of factor effects in design of experiments for discrete response variables. Similarly to the analysis of contingency tables, Markov chain Monte Carlo methods can be used to perform exact tests, especially when large-sample approximations of the null distributions are poor and the enumeration of the conditional sample space is infeasible. In order to construct a connected Markov chain over the appropriate sample space, one approach is to compute a Markov basis. Theoretically, a Markov basis can be characterized as a generator of a well-specified toric ideal in a polynomial ring and is computed by computational algebraic software. However, the computation of a Markov basis sometimes becomes infeasible, even for problems of moderate sizes. In the present article, we obtain the closed-form expression of minimal Markov bases for the main effect models of 2^{p ? 1} fractional factorial designs of resolution p.     

Bayesian quantile regression for longitudinal data models

In this paper, we discuss a fully Bayesian quantile inference using Markov Chain Monte Carlo (MCMC) method for longitudinal data models with random effects. Under the assumption of error term subject to asymmetric Laplace distribution, we establish a hierarchical Bayesian model and obtain the posterior distribution of unknown parameters at τ-th level. We overcome the current computational limitations using two approaches. One is the general MCMC technique with Metropolis–Hastings algorithm and another is the Gibbs sampling from the full conditional distribution. These two methods outperform the traditional frequentist methods under a wide array of simulated data models and are flexible enough to easily accommodate changes in the number of random effects and in their assumed distribution. We apply the Gibbs sampling method to analyse a mouse growth data and some different conclusions from those in the literatures are obtained.     

Reversible jump Markov chain Monte Carlo algorithms for Bayesian variable selection in logistic mixed models

In this article, to reduce computational load in performing Bayesian variable selection, we used a variant of reversible jump Markov chain Monte Carlo methods, and the Holmes and Held (HH) algorithm, to sample model index variables in logistic mixed models involving a large number of explanatory variables. Furthermore, we proposed a simple proposal distribution for model index variables, and used a simulation study and real example to compare the performance of the HH algorithm with our proposed and existing proposal distributions. The results show that the HH algorithm with our proposed proposal distribution is a computationally efficient and reliable selection method.     

Efficient use of exact samples

Propp and Wilson (Random Structures and Algorithms (1996) 9: 223–252, Journal of Algorithms (1998) 27: 170–217) described a protocol called coupling from the past (CFTP) for exact sampling from the steady-state distribution of a Markov chain Monte Carlo (MCMC) process. In it a past time is identified from which the paths of coupled Markov chains starting at every possible state would have coalesced into a single value by the present time; this value is then a sample from the steady-state distribution.Unfortunately, producing an exact sample typically requires a large computational effort. We consider the question of how to make efficient use of the sample values that are generated. In particular, we make use of regeneration events (cf. Mykland et al. Journal of the American Statistical Association (1995) 90: 233–241) to aid in the analysis of MCMC runs. In a regeneration event, the chain is in a fixed reference distribution– this allows the chain to be broken up into a series of tours which are independent, or nearly so (though they do not represent draws from the true stationary distribution).In this paper we consider using the CFTP and related algorithms to create tours. In some cases their elements are exactly in the stationary distribution; their length may be fixed or random. This allows us to combine the precision of exact sampling with the efficiency of using entire tours.Several algorithms and estimators are proposed and analysed.     

Perfect slice samplers

Perfect sampling allows the exact simulation of random variables from the stationary measure of a Markov chain. By exploiting monotonicity properties of the slice sampler we show that a perfect version of the algorithm can be easily implemented, at least when the target distribution is bounded. Various extensions, including perfect product slice samplers, and examples of applications are discussed.