Importance sampling correction versus standard averages of reversible MCMCs in terms of the asymptotic variance

We establish an ordering criterion for the asymptotic variances of two consistent Markov chain Monte Carlo (MCMC) estimators: an importance sampling (IS) estimator, based on an approximate reversible chain and subsequent IS weighting, and a standard MCMC estimator, based on an exact reversible chain. Essentially, we relax the criterion of the Peskun type covariance ordering by considering two different invariant probabilities, and obtain, in place of a strict ordering of asymptotic variances, a bound of the asymptotic variance of IS by that of the direct MCMC. Simple examples show that IS can have arbitrarily better or worse asymptotic variance than Metropolis–Hastings and delayed-acceptance (DA) MCMC. Our ordering implies that IS is guaranteed to be competitive up to a factor depending on the supremum of the (marginal) IS weight. We elaborate upon the criterion in case of unbiased estimators as part of an auxiliary variable framework. We show how the criterion implies asymptotic variance guarantees for IS in terms of pseudo-marginal (PM) and DA corrections, essentially if the ratio of exact and approximate likelihoods is bounded. We also show that convergence of the IS chain can be less affected by unbounded high-variance unbiased estimators than PM and DA chains.     

A note on variance bounding for continuous time Markov Chains

In this paper the notion of variance bounding introduced by Roberts and Rosenthal (2008) is extended to continuous time Markov Chains. Moreover, it is proven that, as in the discrete time case, the notion of variance bounding for reversible Markov Chains is equivalent to the existence of a central limit theorem. A connection with the continuous time Peskun ordering, introduced by Leisen and Mira (2008), concludes the paper.     

Comparison of subdominant eigenvalues of some linear search schemes

The subdominant eigenvalue of the transition probability matrix of a Markov chain is a determining factor in the speed of transition of the chain to a stationary state. However, these eigenvalues can be difficult to estimate in a theoretical sense. In this paper we revisit the problem of dynamically organizing a linear list. Items in the list are selected with certain unknown probabilities and then returned to the list according to one of two schemes: the move-to-front scheme or the transposition scheme. The eigenvalues of the transition probability matrix Q of the former scheme are well-known but those of the latter T are not. Nevertheless the transposition scheme gives rise to a reversible Markov chain. This enables us to employ a generalized Rayleigh-Ritz theorem to show that the subdominant eigenvalue of T is at least as large as the subdominant eigenvalue of Q.     

Estimating Joint Distributions of Markov Chains

Suppose we observe a stationary Markov chain with unknown transition distribution. The empirical estimator for the expectation of a function of two successive observations is known to be efficient. For reversible Markov chains, an appropriate symmetrization is efficient. For functions of more than two arguments, these estimators cease to be efficient. We determine the influence function of efficient estimators of expectations of functions of several observations, both for completely unknown and for reversible Markov chains. We construct simple efficient estimators in both cases.     

On the use of periodicity properties for the efficient numerical solution of certain Markov chains

Markov chains with periodic graphs arise frequently in a wide range of modelling experiments. Application areas range from flexible manufacturing systems in which pallets are treated in a cyclic manner to computer communication networks. The primary goal of this paper is to show how advantage may be taken of this property to reduce the amount of computer memory and computation time needed to compute stationary probability vectors of periodic Markov chains. After reviewing some basic properties of Markov chains whose associated graph is periodic, we introduce a ‘reduced scheme’ in which only a subset of the probability vector need be computed. We consider the effect of the application of both direct and iterative methods to the original Markov chain (permuted to normal periodic form) as well as to the reduced system. We show how the periodicity of the Markov chain may be efficiently computed as the chain itself is being generated. Finally, some numerical experiments to illustrate the theory, are presented.     

Markov Chains Competing for Transitions: Application to Large-Scale Distributed Systems

We consider the behavior of a stochastic system composed of several identically distributed, but non independent, discrete-time absorbing Markov chains competing at each instant for a transition. The competition consists in determining at each instant, using a given probability distribution, the only Markov chain allowed to make a transition. We analyze the first time at which one of the Markov chains reaches its absorbing state. We obtain its distribution and its expectation and we propose an algorithm to compute these quantities. We also exhibit the asymptotic behavior of the system when the number of Markov chains goes to infinity. Actually, this problem comes from the analysis of large-scale distributed systems and we show how our results apply to this domain.     

Markov chain mixing time on cycles

Mixing time quantifies the convergence speed of a Markov chain to the stationary distribution. It is an important quantity related to the performance of MCMC sampling. It is known that the mixing time of a reversible chain can be significantly improved by lifting, resulting in an irreversible chain, while changing the topology of the chain. We supplement this result by showing that if the connectivity graph of a Markov chain is a cycle, then there is an Ω(n²) lower bound for the mixing time. This is the same order of magnitude that is known for reversible chains on the cycle.     

An order-theoretic mixing condition for monotone Markov chains

We discuss the stability of discrete-time Markov chains satisfying monotonicity and an order-theoretic mixing condition that can be seen as an alternative to irreducibility. A chain satisfying these conditions has at most one stationary distribution. Moreover, if there is a stationary distribution, then the chain is stable in an order-theoretic sense.     

Improving efficiency of data augmentation algorithms using Peskun’s theorem

Data augmentation (DA) algorithm is a widely used Markov chain Monte Carlo algorithm. In this paper, an alternative to DA algorithm is proposed. It is shown that the modified Markov chain is always more efficient than DA in the sense that the asymptotic variance in the central limit theorem under the alternative chain is no larger than that under DA. The modification is based on Peskun’s (Biometrika 60:607–612, 1973) result which shows that asymptotic variance of time average estimators based on a finite state space reversible Markov chain does not increase if the Markov chain is altered by increasing all off-diagonal probabilities. In the special case when the state space or the augmentation space of the DA chain is finite, it is shown that Liu’s (Biometrika 83:681–682, 1996) modified sampler can be used to improve upon the DA algorithm. Two illustrative examples, namely the beta-binomial distribution, and a model for analyzing rank data are used to show the gains in efficiency by the proposed algorithms.     

Optimal acceptance probability for simulated annealing

The objective of this note is two-fold: first, to prescribe a rather general form for the acceptance probability which will attain the Gibbs distribution for a stationary Markov chain; second, to find the particular one that will maximize the rate at which equilibrium is reached.     

Computing the nearest reversible Markov chain

Reversible Markov chains are the basis of many applications. However, computing transition probabilities by a finite sampling of a Markov chain can lead to truncation errors. Even if the original Markov chain is reversible, the approximated Markov chain might be non‐reversible and will lose important properties, like the real‐valued spectrum. In this paper, we show how to find the closest reversible Markov chain to a given transition matrix. It turns out that this matrix can be computed by solving a convex minimization problem. Copyright © 2015 John Wiley & Sons, Ltd.     

Central Limit Theorem Started at a Point for?Stationary Processes and Additive Functionals of?Reversible Markov Chains

In this paper we study the almost sure central limit theorem started at a point for additive functionals of a stationary and ergodic Markov chain via a martingale approximation in the almost sure sense. Some of the results provide sufficient conditions for general stationary sequences. We use these results to study the quenched CLT for additive functionals of reversible Markov chains.     

Random walk centrality and a partition of Kemeny’s constant

We consider an accessibility index for the states of a discrete-time, ergodic, homogeneous Markov chain on a finite state space; this index is naturally associated with the random walk centrality introduced by Noh and Reiger (2004) for a random walk on a connected graph. We observe that the vector of accessibility indices provides a partition of Kemeny’s constant for the Markov chain. We provide three characterizations of this accessibility index: one in terms of the first return time to the state in question, and two in terms of the transition matrix associated with the Markov chain. Several bounds are provided on the accessibility index in terms of the eigenvalues of the transition matrix and the stationary vector, and the bounds are shown to be tight. The behaviour of the accessibility index under perturbation of the transition matrix is investigated, and examples exhibiting some counter-intuitive behaviour are presented. Finally, we characterize the situation in which the accessibility indices for all states coincide.     

Transient and Stationary Distributions for the GI/G/k Queue with Lebesgue-Dominated Inter-Arrival Time Distribution

In this paper, the multi-server queue with general service time distribution and Lebesgue-dominated iid inter-arival times is analyzed. This is done by introducing auxiliary variables for the remaining service times and then examining the embedded Markov chain at arrival instants. The concept of piecewise-deterministic Markov processes is applied to model the inter-arrival behaviour. It turns out that the transition probability kernel of the embedded Markov chain at arrival instants has the form of a lower Hessenberg matrix and hence admits an operator–geometric stationary distribution. Thus it is shown that matrix–analytical methods can be extended to provide a modeling tool even for the general multi-server queue.     

Simulating tail asymptotics of a Markov chain

This paper develops a rare event simulation algorithm for a discrete-time Markov chain in the first orthant. The algorithm gives a very good estimate of the stationary distribution along one of the axes and it is shown to be efficient. A key idea is to study an associated time reversed Markov chain that starts at the rare event. We will apply the algorithm to a Markov chain related to a Jackson network with two stations.     

Queue Length Distribution in a FIFO Single-Server Queue with Multiple Arrival Streams Having Different Service Time Distributions

This paper considers the queue length distribution in a class of FIFO single-server queues with (possibly correlated) multiple arrival streams, where the service time distribution of customers may be different for different streams. It is widely recognized that the queue length distribution in a FIFO queue with multiple non-Poissonian arrival streams having different service time distributions is very hard to analyze, since we have to keep track of the complete order of customers in the queue to describe the queue length dynamics. In this paper, we provide an alternative way to solve the problem for a class of such queues, where arrival streams are governed by a finite-state Markov chain. We characterize the joint probability generating function of the stationary queue length distribution, by considering the joint distribution of the number of customers arriving from each stream during the stationary attained waiting time. Further we provide recursion formulas to compute the stationary joint queue length distribution and the stationary distribution representing from which stream each customer in the queue arrived.     

Computing the Stationary Distribution of Absorbing Markov Chains with One Eigenvector of Diagonalizable Transition Matrices

An absorbing Markov chain is an important statistic model and widely used in algorithm modeling for many disciplines, such as digital image processing, network analysis and so on. In order to get the stationary distribution for such model, the inverse of the transition matrix usually needs to be calculated. However, it is still difficult and costly for large matrices. In this paper, for absorbing Markov chains with two absorbing states, we propose a simple method to compute the stationary distribution for models with diagonalizable transition matrices. With this approach, only an eigenvector with eigenvalue 1 needs to be calculated. We also use this method to derive probabilities of the gambler's ruin problem from a matrix perspective. And, it is able to handle expansions of this problem. In fact, this approach is a variant of the general method for absorbing Markov chains. Similar techniques can be used to avoid calculating the inverse matrix in the general method.     

������һ��������������ɶԽǻ�ת�ƾ������������ɷ�����ƽ�ȷֲ�

??An absorbing Markov chain is an important statistic model and widely used in algorithm modeling for many disciplines, such as digital image processing, network analysis and so on. In order to get the stationary distribution for such model, the inverse of the transition matrix usually needs to be calculated. However, it is still difficult and costly for large matrices. In this paper, for absorbing Markov chains with two absorbing states, we propose a simple method to compute the stationary distribution for models with diagonalizable transition matrices. With this approach, only an eigenvector with eigenvalue 1 needs to be calculated. We also use this method to derive probabilities of the gambler's ruin problem from a matrix perspective. And, it is able to handle expansions of this problem. In fact, this approach is a variant of the general method for absorbing Markov chains. Similar techniques can be used to avoid calculating the inverse matrix in the general method.     

Iterated function systems a rising from recursive estimation problems

Summary We show that under suitable conditions the one-step predictor of a finite-state Markov chain from noisy observations has a unique stationary law which is supported by a self-similar set, called the attractor. Under additional symmetry conditions such attractor is either connected, or totally disconnected and perfect. In this latter case the predictor keeps an infinite memory of the past observations. The main problem of interest is to identify those values of the parameters of the chain and the observation process for which this happens. In the binary case, the problem is completely solved. In higher dimension the problem is harder: a complete solution is presented for ternary chains in the completely symmetric persistent case.     

Hypothesis Tests of Convergence in Markov Chain Monte Carlo

Abstract

Deciding when a Markov chain has reached its stationary distribution is a major problem in applications of Markov Chain Monte Carlo methods. Many methods have been proposed ranging from simple graphical methods to complicated numerical methods. Most such methods require a lot of user interaction with the chain which can be very tedious and time-consuming for a slowly mixing chain. This article describes a system to reduce the burden on the user in assessing convergence. The method uses simple nonparametric hypothesis testing techniques to examine the output of several independent chains and so determines whether there is any evidence against the hypothesis of convergence. We illustrate the proposed method on some examples from the literature.