Hypergroup deformations and Markov chains

Persi Diaconis and Phil Hanlon in their interesting paper⁽⁴⁾ give the rates of convergence of some Metropolis Markov chains on the cubeZ ^d (2). Markov chains on finite groups that are actually random walks are easier to analyze because the machinery of harmonic analysis is available. Unfortunately, Metropolis Markov chains are, in general, not random walks on group structure. In attempting to understand Diaconis and Hanlon's work, the authors were led to the idea of a hypergroup deformation of a finite groupG, i.e., a continuous family of hypergroups whose underlying space isG and whose structure is naturally related to that ofG. Such a deformation is provided forZ ^d (2), and it is shown that the Metropolis Markov chains studied by Diaconis and Hanlon can be viewed as random walks on the deformation. A direct application of the Diaconis-Shahshahani Upper Bound Lemma, which applies to random walks on hypergroups, is used to obtain the rate of convergence of the Metropolis chains starting at any point. When the Markov chains start at 0, a result in Diaconis and Hanlon⁽⁴⁾ is obtained with exactly the same rate of convergence. These results are extended toZ ^d (3).Research supported in part by the Office of Research and Sponsored Programs, University of Oregon.     

Remarks on the speed of convergence of mixing coefficients and applications

We study dependence coefficients for copula-based Markov chains. We provide new tools to check the convergence rates of mixing coefficients of copula-based Markov chains. We apply results to the Metropolis–Hastings algorithm. A necessary condition for symmetric copulas is given and mixtures of copulas are studied.     

On a Generalization of the Preconditioned Crank–Nicolson Metropolis Algorithm

Metropolis algorithms for approximate sampling of probability measures on infinite dimensional Hilbert spaces are considered, and a generalization of the preconditioned Crank–Nicolson (pCN) proposal is introduced. The new proposal is able to incorporate information on the measure of interest. A numerical simulation of a Bayesian inverse problem indicates that a Metropolis algorithm with such a proposal performs independently of the state-space dimension and the variance of the observational noise. Moreover, a qualitative convergence result is provided by a comparison argument for spectral gaps. In particular, it is shown that the generalization inherits geometric convergence from the Metropolis algorithm with pCN proposal.     

Perturbation bounds for Monte Carlo within Metropolis via restricted approximations

The Monte Carlo within Metropolis (MCwM) algorithm, interpreted as a perturbed Metropolis–Hastings (MH) algorithm, provides an approach for approximate sampling when the target distribution is intractable. Assuming the unperturbed Markov chain is geometrically ergodic, we show explicit estimates of the difference between the $n$th step distributions of the perturbed MCwM and the unperturbed MH chains. These bounds are based on novel perturbation results for Markov chains which are of interest beyond the MCwM setting. To apply the bounds, we need to control the difference between the transition probabilities of the two chains and to verify stability of the perturbed chain.     

Geometric analysis for the metropolis algorithm on Lipschitz domains

This paper gives geometric tools: comparison, Nash and Sobolev inequalities for pieces of the relevant Markov operators, that give useful bounds on rates of convergence for the Metropolis algorithm. As an example, we treat the random placement of N hard discs in the unit square, the original application of the Metropolis algorithm.     

Weak convergence of Markov chain sampling methods and annealing algorithms to diffusions

Simulated annealing algorithms have traditionally been developed and analyzed along two distinct lines: Metropolis-type Markov chain algorithms and Langevin-type Markov diffusion algorithms. Here, we analyze the dynamics of continuous state Markov chains which arise from a particular implementation of the Metropolis and heat-bath Markov chain sampling methods. It is shown that certain continuous-time interpolations of the Metropolis and heat-bath chains converge weakly to Langevin diffusions running at different time scales. This exposes a close and potentially useful relationship between the Markov chain and diffusion versions of simulated annealing.The research reported here has been supported by the Whirlpool Foundation, by the Air Force Office of Scientific Research under Contract 89-0276, and by the Army Research Office under Contract DAAL-03-86-K-0171 (Center for Intelligent Control Systems).     

An Adaptive Version for the Metropolis Adjusted Langevin Algorithm with a Truncated Drift

This paper extends some adaptive schemes that have been developed for the Random Walk Metropolis algorithm to more general versions of the Metropolis-Hastings (MH) algorithm, particularly to the Metropolis Adjusted Langevin algorithm of Roberts and Tweedie (1996). Our simulations show that the adaptation drastically improves the performance of such MH algorithms. We study the convergence of the algorithm. Our proves are based on a new approach to the analysis of stochastic approximation algorithms based on mixingales theory.      

An efficient sampling scheme for dynamic generalized models

A multimove sampling scheme for the state parameters of non-Gaussian and nonlinear dynamic models for univariate time series is proposed. This procedure follows the Bayesian framework, within a Gibbs sampling algorithm with steps of the Metropolis–Hastings algorithm. This sampling scheme combines the conjugate updating approach for generalized dynamic linear models, with the backward sampling of the state parameters used in normal dynamic linear models. A quite extensive Monte Carlo study is conducted in order to compare the results obtained using our proposed method, conjugate updating backward sampling (CUBS), with those obtained using some algorithms previously proposed in the Bayesian literature. We compare the performance of CUBS with other sampling schemes using two real datasets. Then we apply our algorithm in a stochastic volatility model. CUBS significantly reduces the computing time needed to attain convergence of the chains, and is relatively simple to implement.     

Rescaled Simulated Annealing—Accelerating Convergence of Simulated Annealing by Rescaling the States Energies

This paper presents a new metaheuristic, called rescaled simulated annealing (RSA) which is particularly adapted to combinatorial problems where the available computational effort to solve it is limited. Asymptotic convergence on optimal solutions is established and the results are favorably compared to the famous ones due to Mitra, Romeo, and Sangiovanni-Vincentelli (Mitra, Romeo, and Sangiovanni-Vincentelli. (1986). Adv. Appl. Prob. 18, 747–771.) for simulated annealing (SA). It is based on a generalization of the Metropolis procedure used by the SA algorithm. This generalization consists in rescaling the energies of the states candidate for a transition, before applying the Metropolis criterion. The direct consequence is an acceleration of convergence, by avoiding dives and escapes from high energy local minima. Thus, practically speaking, less transitions need to be tested with RSA to obtain a good quality solution. As a corollary, within a limited computational effort, RSA provides better quality solutions than SA and the gain of performance of RSA versus SA is all the more important since the available computational effort is reduced. An illustrative example is detailed on an instance of the Traveling Salesman Problem.     

Bayesian cylindrical data modeling using Abe–Ley mixtures

This paper proposes a Metropolis–Hastings algorithm based on Markov chain Monte Carlo sampling, to estimate the parameters of the Abe–Ley distribution, which is a recently proposed Weibull-Sine-Skewed-von Mises mixture model, for bivariate circular-linear data. Current literature estimates the parameters of these mixture models using the expectation-maximization method, but we will show that this exhibits a few shortcomings for the considered mixture model. First, standard expectation-maximization does not guarantee convergence to a global optimum, because the likelihood is multi-modal, which results from the high dimensionality of the mixture’s likelihood. Second, given that expectation-maximization provides point estimates of the parameters only, the uncertainties of the estimates (e.g., confidence intervals) are not directly available in these methods. Hence, extra calculations are needed to quantify such uncertainty. We propose a Metropolis–Hastings based algorithm that avoids both shortcomings of expectation-maximization. Indeed, Metropolis–Hastings provides an approximation to the complete (posterior) distribution, given that it samples from the joint posterior of the mixture parameters. This facilitates direct inference (e.g., about uncertainty, multi-modality) from the estimation. In developing the algorithm, we tackle various challenges including convergence speed, label switching and selecting the optimum number of mixture components. We then (i) verify the effectiveness of the proposed algorithm on sample datasets with known true parameters, and further (ii) validate our methodology on an environmental dataset (a traditional application domain of Abe–Ley mixtures where measurements are function of direction). Finally, we (iii) demonstrate the usefulness of our approach in an application domain where the circular measurement is periodic in time.     

Structured Markov Chain Monte Carlo

Abstract

This article introduces a general method for Bayesian computing in richly parameterized models, structured Markov chain Monte Carlo (SMCMC), that is based on a blocked hybrid of the Gibbs sampling and Metropolis—Hastings algorithms. SMCMC speeds algorithm convergence by using the structure that is present in the problem to suggest an appropriate Metropolis—Hastings candidate distribution. Although the approach is easiest to describe for hierarchical normal linear models, we show that its extension to both nonnormal and nonlinear cases is straightforward. After describing the method in detail we compare its performance (in terms of run time and autocorrelation in the samples) to other existing methods, including the single-site updating Gibbs sampler available in the popular BUGS software package. Our results suggest significant improvements in convergence for many problems using SMCMC, as well as broad applicability of the method, including previously intractable hierarchical nonlinear model settings.     

An adaptive simulated annealing algorithm

In this paper, inspired by the idea of Metropolis algorithm, a new sample adaptive simulated annealing algorithm is constructed on finite state space. This new algorithm can be considered as a substitute of the annealing of iterative stochastic schemes. The convergence of the algorithm is shown.     

Convergence of Clock Processes and Aging in Metropolis Dynamics of a Truncated REM

We study the aging behavior of a truncated version of the Random Energy Model evolving under Metropolis dynamics. We prove that the natural time-time correlation function defined through the overlap function converges to an arcsine law distribution function, almost surely in the random environment and in the full range of time scales and temperatures for which such a result can be expected to hold. This establishes that the dynamics ages in the same way as Bouchaud’s REM-like trap model, thus extending the universality class of the latter model. The proof relies on a clock process convergence result of a new type where the number of summands is itself a clock process. This reflects the fact that the exploration process of Metropolis dynamics is itself an aging process, governed by its own clock. Both clock processes are shown to converge to stable subordinators below certain critical lines in their time-scale and temperature domains, almost surely in the random environment.     

A Dirichlet form approach to MCMC optimal scaling

This paper shows how the theory of Dirichlet forms can be used to deliver proofs of optimal scaling results for Markov chain Monte Carlo algorithms (specifically, Metropolis–Hastings random walk samplers) under regularity conditions which are substantially weaker than those required by the original approach (based on the use of infinitesimal generators). The Dirichlet form methods have the added advantage of providing an explicit construction of the underlying infinite-dimensional context. In particular, this enables us directly to establish weak convergence to the relevant infinite-dimensional distributions.     

Performance of the Gibbs,Hit-and-Run,and Metropolis Samplers

Abstract

We consider the performance of three Monte Carlo Markov-chain samplers—the Gibbs sampler, which cycles through coordinate directions; the Hit-and-Run (H&R) sampler, which randomly moves in any direction; and the Metropolis sampler, which moves with a probability that is a ratio of likelihoods. We obtain several analytical results. We provide a sufficient condition of the geometric convergence on a bounded region S for the H&R sampler. For a general region S, we review the Schervish and Carlin sufficient geometric convergence condition for the Gibbs sampler. We show that for a multivariate normal distribution this Gibbs sufficient condition holds and for a bivariate normal distribution the Gibbs marginal sample paths are each an AR(1) process, and we obtain the standard errors of sample means and sample variances, which we later use to verify empirical Monte Carlo results. We empirically compare the Gibbs and H&R samplers on bivariate normal examples. For zero correlation, the Gibbs sampler provides independent data, resulting in better performance than H&R. As the absolute value of the correlation increases, H&R performance improves, with H&R substantially better for correlations above .9. We also suggest and study methods for choosing the number of replications, for estimating the standard error of point estimators and for reducing point-estimator variance. We suggest using a single long run instead of using multiple iid separate runs. We suggest using overlapping batch statistics (obs) to get the standard errors of estimates; additional empirical results show that obs is accurate. Finally, we review the geometric convergence of the Metropolis algorithm and develop a Metropolisized H&R sampler. This sampler works well for high-dimensional and complicated integrands or Bayesian posterior densities.     

Gibbs/Metropolis algorithms on a convex polytope

This paper gives sharp rates of convergence for natural versions of the Metropolis algorithm for sampling from the uniform distribution on a convex polytope. The singular proposal distribution, based on a walk moving locally in one of a fixed, finite set of directions, needs some new tools. We get useful bounds on the spectrum and eigenfunctions using Nash and Weyl-type inequalities. The top eigenvalues of the Markov chain are closely related to the Neumann eigenvalues of the polytope for a novel Laplacian.     

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.     

Convergence of locally and globally interacting Markov chains

We study the long run behaviour of interactive Markov chains on infinite product spaces. In view of microstructure models of financial markets, the interaction has both a local and a global component. The convergence of such Markov chains is analyzed on the microscopic level and on the macroscopic level of empirical fields. We give sufficient conditions for convergence on the macroscopic level. Using a perturbation of the Dobrushin–Vasserstein contraction technique we show that macroscopic convergence implies weak convergence of the underlying Markov chain. This extends the basic convergence theorem of Vasserstein for locally interacting Markov chains to the case where an additional global component appears in the interaction.     

From metropolis to diffusions: Gibbs states and optimal scaling

This paper investigates the behaviour of the random walk Metropolis algorithm in high-dimensional problems. Here we concentrate on the case where the components in the target density is a spatially homogeneous Gibbs distribution with finite range. The performance of the algorithm is strongly linked to the presence or absence of phase transition for the Gibbs distribution; the convergence time being approximately linear in dimension for problems where phase transition is not present. Related to this, there is an optimal way to scale the variance of the proposal distribution in order to maximise the speed of convergence of the algorithm. This turns out to involve scaling the variance of the proposal as the reciprocal of dimension (at least in the phase transition-free case). Moreover, the actual optimal scaling can be characterised in terms of the overall acceptance rate of the algorithm, the maximising value being 0.234, the value as predicted by studies on simpler classes of target density. The results are proved in the framework of a weak convergence result, which shows that the algorithm actually behaves like an infinite-dimensional diffusion process in high dimensions.     

Tunneling of the hard‐core model on finite triangular lattices

We consider the hard‐core model on finite triangular lattices with Metropolis dynamics. Under suitable conditions on the triangular lattice sizes, this interacting particle system has 3 maximum‐occupancy configurations and we investigate its high‐fugacity behavior by studying tunneling times, that is, the first hitting times between these maximum‐occupancy configurations, and the mixing time. The proof method relies on the analysis of the corresponding state space using geometrical and combinatorial properties of the hard‐core configurations on finite triangular lattices, in combination with known results for first hitting times of Metropolis Markov chains in the equivalent zero‐temperature limit. In particular, we show how the order of magnitude of the expected tunneling times depends on the triangular lattice sizes in the low‐temperature regime and prove the asymptotic exponentiality of the rescaled tunneling time leveraging the intrinsic symmetry of the state space.