Slow convergence of the Gibbs sampler

We consider the Gibbs sampler as a tool for generating an absolutely continuous probability measure ≥ on R^d. When an appropriate irreducibility condition is satisfied, the Gibbs Markov chain (X_n;n ≥ 0) converges in total variation to its target distribution ≥. Sufficient conditions for geometric convergence have been given by various authors. Here we illustrate, by means of simple examples, how slow the convergence can be. In particular, we show that given a sequence of positive numbers decreasing to zero, say (b_n;n ≥ 1), one can construct an absolutely continuous probability measure ≥ on R^d which is such that the total variation distance between ≥ and the distribution of X_n, converges to 0 at a rate slower than that of the sequence (b_n;n ≥ 1). This can even be done in such a way that ≥ is the uniform distribution over a bounded connected open subset of R^d. Our results extend to hit-and-run samplers with direction distributions having supports with symmetric gaps.     

A Hellinger distance approach to MCMC diagnostics

Bayesian analysis often requires the researcher to employ Markov Chain Monte Carlo (MCMC) techniques to draw samples from a posterior distribution which in turn is used to make inferences. Currently, several approaches to determine convergence of the chain as well as sensitivities of the resulting inferences have been developed. This work develops a Hellinger distance approach to MCMC diagnostics. An approximation to the Hellinger distance between two distributions f and g based on sampling is introduced. This approximation is studied via simulation to determine the accuracy. A criterion for using this Hellinger distance for determining chain convergence is proposed as well as a criterion for sensitivity studies. These criteria are illustrated using a dataset concerning the Anguilla australis, an eel native to New Zealand.     

Commuting Matrices in the Queue Length and Sojourn Time Analysis of MAP/MAP/1 Queues

Queues with Markovian arrival and service processes, i.e., MAP/MAP/1 queues, have been useful in the analysis of computer and communication systems and different representations for their stationary sojourn time and queue length distribution have been derived. More specifically, the class of MAP/MAP/1 queues lies at the intersection of the class of QBD queues and the class of semi-Markovian queues. While QBD queues have a matrix exponential representation for their queue length and sojourn time distribution of order N and N², respectively, where N is the size of the background continuous time Markov chain, the reverse is true for a semi-Markovian queue. As the class of MAP/MAP/1 queues lies at the intersection, both the queue length and sojourn time distribution of a MAP/MAP/1 queue has an order N matrix exponential representation. The aim of this article is to understand why the order N² distributions of the sojourn time of a QBD queue and the queue length of a semi-Markovian queue can be reduced to an order N distribution in the specific case of a MAP/MAP/1 queue. We show that the key observation exists in establishing the commutativity of some fundamental matrices involved in the analysis of the MAP/MAP/1 queue.     

Discretisation for inference on normal mixture models

The problem of inference in Bayesian Normal mixture models is known to be difficult. In particular, direct Bayesian inference (via quadrature) suffers from a combinatorial explosion in having to consider every possible partition of n observations into k mixture components, resulting in a computation time which is O(k ⁿ). This paper explores the use of discretised parameters and shows that for equal-variance mixture models, direct computation time can be reduced to O(D ^k n ^k), where relevant continuous parameters are each divided into D regions. As a consequence, direct inference is now possible on genuine data sets for small k, where the quality of approximation is determined by the level of discretisation. For large problems, where the computational complexity is still too great in O(D ^k n ^k) time, discretisation can provide a convergence diagnostic for a Markov chain Monte Carlo analysis.     

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.     

Metropolized independent sampling with comparisons to rejection sampling and importance sampling

Although Markov chain Monte Carlo methods have been widely used in many disciplines, exact eigen analysis for such generated chains has been rare. In this paper, a special Metropolis-Hastings algorithm, Metropolized independent sampling, proposed first in Hastings (1970), is studied in full detail. The eigenvalues and eigenvectors of the corresponding Markov chain, as well as a sharp bound for the total variation distance between the nth updated distribution and the target distribution, are provided. Furthermore, the relationship between this scheme, rejection sampling, and importance sampling are studied with emphasis on their relative efficiencies. It is shown that Metropolized independent sampling is superior to rejection sampling in two respects: asymptotic efficiency and ease of computation.     

A continuous-time HMM approach to modeling the magnitude-frequency distribution of earthquakes

The magnitude-frequency distribution (MFD) of earthquake is a fundamental statistic in seismology. The so-called b-value in the MFD is of particular interest in geophysics. A continuous time hidden Markov model (HMM) is proposed for characterizing the variability of b-values. The HMM-based approach to modeling the MFD has some appealing properties over the widely used sliding-window approach. Often, large variability appears in the estimation of b-value due to window size tuning, which may cause difficulties in interpretation of b-value heterogeneities. Continuous-time hidden Markov models (CT-HMMs) are widely applied in various fields. It bears some advantages over its discrete time counterpart in that it can characterize heterogeneities appearing in time series in a finer time scale, particularly for highly irregularly-spaced time series, such as earthquake occurrences. We demonstrate an expectation–maximization algorithm for the estimation of general exponential family CT-HMM. In parallel with discrete-time hidden Markov models, we develop a continuous time version of Viterbi algorithm to retrieve the overall optimal path of the latent Markov chain. The methods are applied to New Zealand deep earthquakes. Before the analysis, we first assess the completeness of catalogue events to assure the analysis is not biased by missing data. The estimation of b-value is stable over the selection of magnitude thresholds, which is ideal for the interpretation of b-value variability.     

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.     

Inference for Adaptive Time Series Models: Stochastic Volatility and Conditionally Gaussian State Space Form

In this paper we model the Gaussian errors in the standard Gaussian linear state space model as stochastic volatility processes. We show that conventional MCMC algorithms for this class of models are ineffective, but that the problem can be alleviated by reparameterizing the model. Instead of sampling the unobserved variance series directly, we sample in the space of the disturbances, which proves to lower correlation in the sampler and thus increases the quality of the Markov chain.

Using our reparameterized MCMC sampler, it is possible to estimate an unobserved factor model for exchange rates between a group of n countries. The underlying n + 1 country-specific currency strength factors and the n + 1 currency volatility factors can be extracted using the new methodology. With the factors, a more detailed image of the events around the 1992 EMS crisis is obtained.

We assess the fit of competitive models on the panels of exchange rates with an effective particle filter and find that indeed the factor model is strongly preferred by the data.     

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.     

A computational procedure for estimation of the mixing time of the random-scan Metropolis algorithm

Many situations, especially in Bayesian statistical inference, call for the use of a Markov chain Monte Carlo (MCMC) method as a way to draw approximate samples from an intractable probability distribution. With the use of any MCMC algorithm comes the question of how long the algorithm must run before it can be used to draw an approximate sample from the target distribution. A common method of answering this question involves verifying that the Markov chain satisfies a drift condition and an associated minorization condition (Rosenthal, J Am Stat Assoc 90:558–566, 1995; Jones and Hobert, Stat Sci 16:312–334, 2001). This is often difficult to do analytically, so as an alternative, it is typical to rely on output-based methods of assessing convergence. The work presented here gives a computational method of approximately verifying a drift condition and a minorization condition specifically for the symmetric random-scan Metropolis algorithm. Two examples of the use of the method described in this article are provided, and output-based methods of convergence assessment are presented in each example for comparison with the upper bound on the convergence rate obtained via the simulation-based approach.     

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.     

Stochastic approximation Monte Carlo importance sampling for approximating exact conditional probabilities

Importance sampling and Markov chain Monte Carlo methods have been used in exact inference for contingency tables for a long time, however, their performances are not always very satisfactory. In this paper, we propose a stochastic approximation Monte Carlo importance sampling (SAMCIS) method for tackling this problem. SAMCIS is a combination of adaptive Markov chain Monte Carlo and importance sampling, which employs the stochastic approximation Monte Carlo algorithm (Liang et al., J. Am. Stat. Assoc., 102(477):305–320, 2007) to draw samples from an enlarged reference set with a known Markov basis. Compared to the existing importance sampling and Markov chain Monte Carlo methods, SAMCIS has a few advantages, such as fast convergence, ergodicity, and the ability to achieve a desired proportion of valid tables. The numerical results indicate that SAMCIS can outperform the existing importance sampling and Markov chain Monte Carlo methods: It can produce much more accurate estimates in much shorter CPU time than the existing methods, especially for the tables with high degrees of freedom.     

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.     

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.     

Modeling systems with two dependent components under bivariate shock models

Series and parallel systems consisting of two dependent components are studied under bivariate shock models. The random variables N₁ and N₂ that represent respectively the number of shocks until failure of component 1 and component 2 are assumed to be dependent and phase-type. The times between successive shocks are assumed to follow a continuous phase-type distribution, and survival functions and mean time to failure values of series and parallel systems are obtained in matrix forms. An upper bound for the joint survival function of the components is also provided under the particular case when the times between shocks follow exponential distribution.     

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

Maximum Likelihood Estimation in Gaussian Chain Graph Models under the Alternative Markov Property

Abstract.  The Andersson–Madigan–Perlman (AMP) Markov property is a recently proposed alternative Markov property (AMP) for chain graphs. In the case of continuous variables with a joint multivariate Gaussian distribution, it is the AMP rather than the earlier introduced Lauritzen–Wermuth–Frydenberg Markov property that is coherent with data-generation by natural block-recursive regressions. In this paper, we show that maximum likelihood estimates in Gaussian AMP chain graph models can be obtained by combining generalized least squares and iterative proportional fitting to an iterative algorithm. In an appendix, we give useful convergence results for iterative partial maximization algorithms that apply in particular to the described algorithm.     

ON TRANSITION PROBABILITIES OF SKIP-FREE MARKOV CHAINS

Consider an ergodic Markov chain X(t) in continuous time with an infinitesimal matrix Q = (q_ij) defined on a finite state space {0, 1,…, N}. In this note, we prove that if X(t) is skip-free positive (negative, respectively), i.e., q_ij, = 0 for j > i+ 1 (i > j+ 1), then the transition probability p_ij(t) = Pr[X(t)=j | X(0) =i] can be represented as a linear combination of p_0N(t) (p^(m)_(N0)(t)), 0 ≤ m ≤N, where f^(m)(t) denotes the mth derivative of a function f(t) with f⁽⁰⁾(t) =f(t). If X(t) is a birth-death process, then p_ij(t) is represented as a linear combination of p_0N^(m)(t), 0 ≤m≤N - |i-j|.