Minimal auxiliary Markov chains through sequential elimination of states

When using an auxiliary Markov chain to compute the distribution of a pattern statistic, the computational complexity is directly related to the number of Markov chain states. Theory related to minimal deterministic finite automata have been applied to large state spaces to reduce the number of Markov chain states so that only a minimal set remains. In this paper, a characterization of equivalent states is given so that extraneous states are deleted during the process of forming the state space, improving computational efficiency. The theory extends the applicability of Markov chain based methods for computing the distribution of pattern statistics.     

Convergence in the Wasserstein Metric for Markov Chain Monte Carlo Algorithms with Applications to Image Restoration

Abstract

In this paper, we show how the time for convergence to stationarity of a Markov chain can be assessed using the Wasserstein metric, rather than the usual choice of total variation distance. The Wasserstein metric may be more easily applied in some applications, particularly those on continuous state spaces. Bounds on convergence time are established by considering the number of iterations required to approximately couple two realizations of the Markov chain to within ε tolerance. The particular application considered is the use of the Gibbs sampler in the Bayesian restoration of a degraded image, with pixels that are a continuous grey-scale and with pixels that can only take two colours. On finite state spaces, a bound in the Wasserstein metric can be used to find a bound in total variation distance. We use this relationship to get a precise O(N log N) bound on the convergence time of the stochastic Ising model that holds for appropriate values of its parameter as well as other binary image models. Our method employing convergence in the Wasserstein metric can also be applied to perfect sampling algorithms involving coupling from the past to obtain estimates of their running times.     

Tuning tempered transitions

The method of tempered transitions was proposed by Neal (Stat. Comput. 6:353–366, 1996) for tackling the difficulties arising when using Markov chain Monte Carlo to sample from multimodal distributions. In common with methods such as simulated tempering and Metropolis-coupled MCMC, the key idea is to utilise a series of successively easier to sample distributions to improve movement around the state space. Tempered transitions does this by incorporating moves through these less modal distributions into the MCMC proposals. Unfortunately the improved movement between modes comes at a high computational cost with a low acceptance rate of expensive proposals. We consider how the algorithm may be tuned to increase the acceptance rates for a given number of temperatures. We find that the commonly assumed geometric spacing of temperatures is reasonable in many but not all applications.     

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.     

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.     

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.     

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.     

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 New Policy Evaluation Algorithm for Markov Decision Processes with Quasi Birth-Death Structure

ABSTRACT

This paper describes a new algorithm for policy evaluation for Markov decision processes (MDP) that possess a quasi birth-death structure. The proposed algorithm is based on matrix analytic methods which use probabilistic concepts associated with restricting the underlying Markov process to certain state subsets. A telecommunications application example shows that the method offers significant computational reduction compared to a standard MDP policy evaluation approach.     

Model-averaged ℓ1 regularization using Markov chain Monte Carlo model composition

Bayesian model averaging (BMA) is an effective technique for addressing model uncertainty in variable selection problems. However, current BMA approaches have computational difficulty dealing with data in which there are many more measurements (variables) than samples. This paper presents a method for combining ?₁ regularization and Markov chain Monte Carlo model composition techniques for BMA. By treating the ?₁ regularization path as a model space, we propose a method to resolve the model uncertainty issues arising in model averaging from solution path point selection. We show that this method is computationally and empirically effective for regression and classification in high-dimensional data sets. We apply our technique in simulations, as well as to some applications that arise in genomics.     

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.     

Reliabilities of a single-unit system with multi-phased missions

ABSTRACT

Phased-mission systems (PMS) can be widely found in a lot of practical application areas. Reliability evaluations and analysis for this kind of systems become important issues. The reliability of PMS is typically defined as the probability that the system successfully accomplishes the missions of all phases. However, the k-out-of-n system success criterion for PMS has not been investigated. In this paper, according to this criterion, we develop two new models, which are static and dynamic, respectively. The assumptions for these two models are described in detail as well. The system reliabilities for both models are presented for the first time by employing finite Markov chain imbedding approach (FMCIA). In terms of FMCIA, we define different state spaces for the two models, and transition probability matrices are obtained. Then some numerical examples are given to illustrate the application of FMCIA. Finally, some discussions are made and conclusions are summarized.     

Statistical Inference for Partially Hidden Markov Models

ABSTRACT

In this article we introduce a new missing data model, based on a standard parametric Hidden Markov Model (HMM), for which information on the latent Markov chain is given since this one reaches a fixed state (and until it leaves this state). We study, under mild conditions, the consistency and asymptotic normality of the maximum likelihood estimator. We point out also that the underlying Markov chain does not need to be ergodic, and that identifiability of the model is not tractable in a simple way (unlike standard HMMs), but can be studied using various technical arguments.     

Statistical analysis of the number of self-overlapping leftmost repeats in an homogeneous stationary Markov chain on finite states

ABSTRACT

This article addresses the problem of repeats detection used in the comparison of significant repeats in sequences. The case of self-overlapping leftmost repeats for large sequences generated by an homogeneous stationary Markov chain has not been treated in the literature. In this work, we are interested by the approximation of the number of self-overlapping leftmost long enough repeats distribution in an homogeneous stationary Markov chain. Using the Chen–Stein method, we show that the number of self-overlapping leftmost long enough repeats distribution is approximated by the Poisson distribution. Moreover, we show that this approximation can be extended to the case where the sequences are generated by a m-order Markov chain.     

Hamiltonian Monte Carlo acceleration using surrogate functions with random bases

For big data analysis, high computational cost for Bayesian methods often limits their applications in practice. In recent years, there have been many attempts to improve computational efficiency of Bayesian inference. Here we propose an efficient and scalable computational technique for a state-of-the-art Markov chain Monte Carlo methods, namely, Hamiltonian Monte Carlo. The key idea is to explore and exploit the structure and regularity in parameter space for the underlying probabilistic model to construct an effective approximation of its geometric properties. To this end, we build a surrogate function to approximate the target distribution using properly chosen random bases and an efficient optimization process. The resulting method provides a flexible, scalable, and efficient sampling algorithm, which converges to the correct target distribution. We show that by choosing the basis functions and optimization process differently, our method can be related to other approaches for the construction of surrogate functions such as generalized additive models or Gaussian process models. Experiments based on simulated and real data show that our approach leads to substantially more efficient sampling algorithms compared to existing state-of-the-art methods.     

Uniform Ergodicity of the Particle Gibbs Sampler

The particle Gibbs sampler is a systematic way of using a particle filter within Markov chain Monte Carlo. This results in an off‐the‐shelf Markov kernel on the space of state trajectories, which can be used to simulate from the full joint smoothing distribution for a state space model in a Markov chain Monte Carlo scheme. We show that the particle Gibbs Markov kernel is uniformly ergodic under rather general assumptions, which we will carefully review and discuss. In particular, we provide an explicit rate of convergence, which reveals that (i) for fixed number of data points, the convergence rate can be made arbitrarily good by increasing the number of particles and (ii) under general mixing assumptions, the convergence rate can be kept constant by increasing the number of particles superlinearly with the number of observations. We illustrate the applicability of our result by studying in detail a common stochastic volatility model with a non‐compact state space.     

Multiple window discrete scan statistic for higher-order Markovian sequences

Accurate and efficient methods to detect unusual clusters of abnormal activity are needed in many fields such as medicine and business. Often the size of clusters is unknown; hence, multiple (variable) window scan statistics are used to identify clusters using a set of different potential cluster sizes. We give an efficient method to compute the exact distribution of multiple window discrete scan statistics for higher-order, multi-state Markovian sequences. We define a Markov chain to efficiently keep track of probabilities needed to compute p-values for the statistic. The state space of the Markov chain is set up by a criterion developed to identify strings that are associated with observing the specified values of the statistic. Using our algorithm, we identify cases where the available approximations do not perform well. We demonstrate our methods by detecting unusual clusters of made free throw shots by National Basketball Association players during the 2009–2010 regular season.     

Markov Systems in a General State Space

In this article, we introduce and study Markov systems on general spaces (MSGS) as a first step of an entire theory on the subject. Also, all the concepts and basic results needed for this scope are given and analyzed. This could be thought of as an extension of the theory of a non homogeneous Markov system (NHMS) and that of a non homogeneous semi-Markov system on countable spaces, which has realized an interesting growth in the last thirty years. In addition, we study the asymptotic behaviour or ergodicity of Markov systems on general state spaces. The problem of asymptotic behaviour of Markov chains has been central for finite or countable spaces since the foundation of the subject. It has also been basic in the theory of NHMS and NHSMS. Two basic theorems are provided in answering the important problem of the asymptotic distribution of the population of the memberships of a Markov system that lives in the general space (X, ?(X)). Finally, we study the total variability from the invariant measure of the Markov system given that there exists an asymptotic behaviour. We prove a theorem which states that the total variation is finite. This problem is known also as the coupling problem.     

Approximate Bayesian inference for latent Gaussian models by using integrated nested Laplace approximations

Summary.  Structured additive regression models are perhaps the most commonly used class of models in statistical applications. It includes, among others, (generalized) linear models, (generalized) additive models, smoothing spline models, state space models, semiparametric regression, spatial and spatiotemporal models, log-Gaussian Cox processes and geostatistical and geoadditive models. We consider approximate Bayesian inference in a popular subset of structured additive regression models, latent Gaussian models , where the latent field is Gaussian, controlled by a few hyperparameters and with non-Gaussian response variables. The posterior marginals are not available in closed form owing to the non-Gaussian response variables. For such models, Markov chain Monte Carlo methods can be implemented, but they are not without problems, in terms of both convergence and computational time. In some practical applications, the extent of these problems is such that Markov chain Monte Carlo sampling is simply not an appropriate tool for routine analysis. We show that, by using an integrated nested Laplace approximation and its simplified version, we can directly compute very accurate approximations to the posterior marginals. The main benefit of these approximations is computational: where Markov chain Monte Carlo algorithms need hours or days to run, our approximations provide more precise estimates in seconds or minutes. Another advantage with our approach is its generality, which makes it possible to perform Bayesian analysis in an automatic, streamlined way, and to compute model comparison criteria and various predictive measures so that models can be compared and the model under study can be challenged.     

Specifying a Gaussian Markov Random Field by a Sparse Cholesky Triangle

ABSTRACT

This note discusses the approach of specifying a Gaussian Markov random field (GMRF) by the Cholesky triangle of the precision matrix. A such representation can be made extremely sparse using numerical techniques for incomplete sparse Cholesky factorization, and provide very computational efficient representation for simulating from the GMRF. However, we provide theoretical and empirical justification showing that the sparse Cholesky triangle representation is fragile when conditioning a GMRF on a subset of the variables or observed data, meaning that the computational cost increases.