First Hitting Time Analysis of the Independence Metropolis Sampler

In this paper, we study a special case of the Metropolis algorithm, the Independence Metropolis Sampler (IMS), in the finite state space case. The IMS is often used in designing components of more complex Markov Chain Monte Carlo algorithms. We present new results related to the first hitting time of individual states for the IMS. These results are expressed mostly in terms of the eigenvalues of the transition kernel. We derive a simple form formula for the mean first hitting time and we show tight lower and upper bounds on the mean first hitting time with the upper bound being the product of two factors: a “local” factor corresponding to the target state and a “global” factor, common to all the states, which is expressed in terms of the total variation distance between the target and the proposal probabilities. We also briefly discuss properties of the distribution of the first hitting time for the IMS and analyze its variance. We conclude by showing how some non-independence Metropolis–Hastings algorithms can perform better than the IMS and deriving general lower and upper bounds for the mean first hitting times of a Metropolis–Hastings algorithm.     

Integral-Type Functionals Downward of Single Death Processes

In this paper we consider the integral-typefunctional downward of single death processes in the finite state space, including the Laplace transformation of its distribution and its polynomial moments as well as the distribution of staying times. As applications, a new proof for the recursive and explicit representation of high order moments of the first hitting times in the denumerable state space is presented; meanwhile, the estimates on the lower bound and the upper one of convergence rate in strong ergodicity are obtained.     

Sampling colourings of the triangular lattice

We show that the Glauber dynamics on proper 9‐colourings of the triangular lattice is rapidly mixing, which allows for efficient sampling. Consequently, there is a fully polynomial randomised approximation scheme (FPRAS) for counting proper 9‐colourings of the triangular lattice. Proper colourings correspond to configurations in the zero‐temperature anti‐ferromagnetic Potts model. We show that the spin system consisting of proper 9‐colourings of the triangular lattice has strong spatial mixing. This implies that there is a unique infinite‐volume Gibbs distribution, which is an important property studied in statistical physics. Our results build on previous work by Goldberg, Martin and Paterson, who showed similar results for 10 colours on the triangular lattice. Their work was preceded by Salas and Sokal's 11‐colour result. Both proofs rely on computational assistance, and so does our 9‐colour proof. We have used a randomised heuristic to guide us towards rigourous results. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 40, 501–533, 2012     

Finite Intervals in the Lattice of Topologies

We discuss the question whether every finite interval in the lattice of all topologies on some set is isomorphic to an interval in the lattice of all topologies on a finite set – or, equivalently, whether the finite intervals in lattices of topologies are, up to isomorphism, exactly the duals of finite intervals in lattices of quasiorders. The answer to this question is in the affirmative at least for finite atomistic lattices. Applying recent results about intervals in lattices of quasiorders, we see that, for example, the five-element modular but non-distributive lattice cannot be an interval in the lattice of topologies. We show that a finite lattice whose greatest element is the join of two atoms is an interval of T ₀-topologies iff it is the four-element Boolean lattice or the five-element non-modular lattice. But only the first of these two selfdual lattices is an interval of orders because order intervals are known to be dually locally distributive.     

The invariance principle for Banach space valued random variables

We extend the invariance principle to triangular arrays of Banach space valued random variables, and as an application derive the invariance principle for lattices of random variables. We also point out how the q-dimensional time parameter Yeh-Wiener process is naturally related to a one dimensional time Wiener process with an infinite dimensional Banach space as a state space.     

New enumerative results on two-dimensional directed animals

We list several open problems concerning the enumeration of directed animals on two-dimensional lattices. We show that most of these problems are special cases of two central problems: calculating the position generating function and the perimeter and area generating function for square lattice animals.

We propose a possible direction for solving these two problems: we extend Dhar's correspondence between hard particle gas models and enumeration of animals according to the area, and show that each of the main two generating functions is, essentially, the density of a one-dimensional gas model given by the stationary distribution of a probabilistic transition.

We are able to compute the density of certain stationary distributions. We thus obtain new bivariate generating functions for directed animals on the square and triangular lattices. We derive from these results the generating functions for animals on the decorated square and triangular lattices, as well as the average number of loops in directed animals.     

Perturbation analysis in finite LD‐QBD processes and applications to epidemic models

In this paper, our interest is in the perturbation analysis of level‐dependent quasi‐birth‐and‐death (LD‐QBD) processes, which constitute a wide class of structured Markov chains. An LD‐QBD process has the special feature that its space of states can be structured by levels (groups of states), so that a tridiagonal‐by‐blocks structure is obtained for its infinitesimal generator. For these processes, a number of algorithmic procedures exist in the literature in order to compute several performance measures while exploiting the underlying matrix structure; among others, these measures are related to first‐passage times to a certain level L(0) and hitting probabilities at this level, the maximum level visited by the process before reaching states of level L(0), and the stationary distribution. For the case of a finite number of states, our aim here is to develop analogous algorithms to the ones analyzing these measures, for their perturbation analysis. This approach uses matrix calculus and exploits the specific structure of the infinitesimal generator, which allows us to obtain additional information during the perturbation analysis of the LD‐QBD process by dealing with specific matrices carrying probabilistic insights of the dynamics of the process. We illustrate the approach by means of applying multitype versions of the susceptible‐infective (SI) and susceptible‐infective‐susceptible (SIS) epidemic models to the spread of antibiotic‐sensitive and antibiotic‐resistant bacterial strains in a hospital ward.     

Minimizing atomic configurations of short range pair potentials in two dimensions: crystallization in the Wulff shape

We investigate ground state configurations of atomic systems in two dimensions interacting via short range pair potentials. As the number of particles tends to infinity, we show that low-energy configurations converge to a macroscopic cluster of finite surface area and constant density, the latter being given by the density of atoms per unit volume in the triangular lattice. In the special case of the Heitmann–Radin sticky disc potential and exact ground states, we show that the macroscopic cluster has a (unique) Wulff shape. This is done by showing that the atomistic energy of crystalline configurations, after subtracting off a bulk part and re-scaling, Gamma-converges to a macroscopic anisotropic surface energy.     

Hitting time of large subsets of the hypercube

We study the simple random walk on the n‐dimensional hypercube, in particular its hitting times of large (possibly random) sets. We give simple conditions on these sets ensuring that the properly rescaled hitting time is asymptotically exponentially distributed, uniformly in the starting position of the walk. These conditions are then verified for percolation clouds with densities that are much smaller than (n log n)^‐1. A main motivation behind this article is the study of the so‐called aging phenomenon in the Random Energy Model, the simplest model of a mean‐field spin glass. Our results allow us to prove aging in the REM for all temperatures, thereby extending earlier results to their optimal temperature domain. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

Optimal control problem of the uncertain second‐order circuit based on first hitting criteria

First hitting criteria of a system are to initially achieve some performance indeces of the target state set. This paper primarily investigates the optimal control problem of the uncertain second‐order circuit based on first hitting criteria. First, considering time efficiency and different from the ordinary expected utility criterion over an infinite time horizon, two first hitting criteria which are reliability index and reliable time criteria are innovatively proposed. Second, assuming the circuit output voltage as an uncertain variable when the historical data is lacking, we better model the real circuit system with the uncertain second‐order differential equation which is essentially the uncertain fractional‐order differential equation. Then, based on the first hitting time theorem of the uncertain fractional‐order differential equation, the distribution function of the first hitting time under the second‐order circuit system is proposed and the uncertain second‐order circuit optimal control model (reliability index and reliable time‐based model) is transformed into corresponding crisp optimal problem. Lastly, analytic expressions of the optimal control for the reliability index model are obtained. Meanwhile, sufficient condition and guidance for parameters for the optimal solution of the reliable time‐based model are derived, and corresponding numerical examples are also given to demonstrate the fluctuation of our optimal solution for different parameters.     

Exact bound for the convergence of metropolis chains

In this note, we present a calculation which gives us the exact bound for the convergence of Metropolis chains in a finite state space and therefore improves the existing results which are only for the upper bounds of such convergence (see the references below). Our result is based on an interesting observation on the transition probability of Metropolis chains     

Pathwise Duals of Monotone and Additive Markov Processes

This paper develops a systematic treatment of monotonicity-based pathwise dualities for Markov processes taking values in partially ordered sets. We show that every Markov process that takes values in a finite partially ordered set and whose generator can be represented in monotone maps has a pathwise dual process. In the special setting of attractive spin systems, this has been discovered earlier by Gray. We show that the dual simplifies a lot when the state space is a lattice (in the order-theoretic meaning of the word) and all monotone maps satisfy an additivity condition. This leads to a unified treatment of several well-known dualities, including Siegmund’s dual for processes with a totally ordered state space, duality of additive spin systems, and a duality due to Krone for the two-stage contact process, and allows for the construction of new dualities as well. We show that the well-known representation of additive spin systems in terms of open paths in a graphical representation can be generalized to additive Markov processes taking values in general lattices, but for the process and its dual to be representable on the same underlying space, we need to assume that the lattice is distributive. In the final section, we show how our results can be generalized from finite state spaces to interacting particle systems with finite local state spaces.     

A Note On Subloop Lattices

Pálfy and Pudlák (Algebra Universalis 11, 22–27, 1980) posed the question: is every finite lattice isomorphic to an interval sublattice of the lattice of subgroups of a finite group? in this paper we will look at examples of lattices that can be realized as subloop lattices but not as subgroup lattices. This is a first step in answering a new question: is every finite lattice isomorphic to an interval sublattice of the subloop lattice of a finite loop?     

Finite pseudocomplemented lattices: The spectra and the Glivenko congruence

Recently, Gr?tzer, Gunderson and Quackenbush have characterized the spectra of finite pseudocomplemented lattices, solving a problem raised by G. Gr?tzer in his first monograph on lattice theory from 1971. In this note we discuss the tight connection between the spectra and the Glivenko congruence of finite pseudocomplemented lattices.     

Exit Times from Equilateral Triangles

In this paper we obtain a closed form expression of the expected exit time of a Brownian motion from equilateral triangles. We consider first the analogous problem for a symmetric random walk on the triangular lattice and show that it is equivalent to the ruin problem of an appropriate three player game. A suitable scaling of this random walk allows us to exhibit explicitly the relation between the respective exit times. This gives us the solution of the related Poisson equation.     

Exit Times from Equilateral Triangles

In this paper we obtain a closed form expression of the expected exit time of a Brownian motion from equilateral triangles. We consider first the analogous problem for a symmetric random walk on the triangular lattice and show that it is equivalent to the ruin problem of an appropriate three player game. A suitable scaling of this random walk allows us to exhibit explicitly the relation between the respective exit times. This gives us the solution of the related Poisson equation.     

Layer-projective lattices. I

The class of layer-projective lattices is singled out. For example, it contains the lattices of subgroups of finite Abelianp-groups, finite modular lattices of centralizers that are indecomposable into a finite sum, and lattices of subspaces of a finite-dimensional linear space over a finite field that are invariant with respect to a linear operator with zero eigenvalues. In the class of layer-projective lattices, the notion of type (of a lattice) is naturally introduced and the isomorphism problem for lattices of the same type is posed. This problem is positively solved for some special types of layer-projective lattices. The main method is the layer-wise lifting of the coordinates. Translated fromMatematicheskie Zametki, Vol. 63, No. 2, pp. 170–182, February, 1998.     

Embedding Finite Lattices into Finite Biatomic Lattices

For a class C of finite lattices, the question arises whether any lattice in C can be embedded into some atomistic, biatomic lattice in C. We provide answers to the question above for C being, respectively,– the class of all finite lattices;– the class of all finite lower bounded lattices (solved by the first author's earlier work);– the class of all finite join-semidistributive lattices (this problem was, until now, open).We solve the latter problem by finding a quasi-identity valid in all finite, atomistic, biatomic, join-semidistributive lattices but not in all finite join-semidistributive lattices.     

Hitting times with taboo for a random walk

For a symmetric homogeneous and irreducible random walk on the d-dimensional integer lattice, which have a finite variance of jumps, we study passage times (taking values in [0,??]) determined by a starting point x, a hitting state y, and a taboo state z. We find the probability that these passage times are finite, and study the distribution tail. In particular, it turns out that, for the above-mentioned random walks on ? ^d except for a simple random walk on ?, the order of the distribution tail decrease is specified by dimension d only. In contrast, for a simple random walk on ?, the asymptotic properties of hitting times with taboo essentially depend on mutual location of the points x, y, and z. These problems originated in recent study of a branching random walk on ? ^d with a single source of branching.     

Algorithmic computation of generalized symmetries of nonlinear evolution and lattice equations

A straightforward algorithm for the symbolic computation of generalized (higher‐order) symmetries of nonlinear evolution equations and lattice equations is presented. The scaling properties of the evolution or lattice equations are used to determine the polynomial form of the generalized symmetries. The coefficients of the symmetry can be found by solving a linear system. The method applies to polynomial systems of PDEs of first order in time and arbitrary order in one space variable. Likewise, lattices must be of first order in time but may involve arbitrary shifts in the discretized space variable. The algorithm is implemented in Mathematica and can be used to test the integrability of both nonlinear evolution equations and semi‐discrete lattice equations. With our Integrability Package, generalized symmetries are obtained for several well‐known systems of evolution and lattice equations. For PDEs and lattices with parameters, the code allows one to determine the conditions on these parameters so that a sequence of generalized symmetries exists. The existence of a sequence of such symmetries is a predictor for integrability. This revised version was published online in June 2006 with corrections to the Cover Date.