Expansion And Isoperimetric Constants For Product Graphs

Vertex and edge isoperimetric constants of graphs are studied. Using a functional-analytic approach, the growth properties, under products, of these constants is analyzed.     

Entrywise perturbation theory and error analysis for Markov chains

Summary Grassmann, Taksar, and Heyman introduced a variant of Gaussian climination for computing the steady-state vector of a Markov chain. In this paper we prove that their algorithm is stable, and that the problem itself is well-conditioned, in the sense of entrywise relative error. Thus the algorithm computes each entry of the steady-state vector with low relative error. Even the small steady-state probabilities are computed accurately. The key to our analysis is to focus on entrywise relative error in both the data and the computed solution, rather than making the standard assessments of error based on norms. Our conclusions do not depend on any Condition numbers for the problem.This work was supported by NSF under grants DMS-9106207 and DDM-9203134     

Geometric ergodicity for classes of homogeneous Markov chains

The paper deals with non asymptotic computable bounds for the geometric convergence rate of homogeneous ergodic Markov processes. Some sufficient conditions are stated for simultaneous geometric ergodicity of Markov chain classes. This property is applied to nonparametric estimation in ergodic diffusion processes.     

Mixed and Isoperimetric Estimates on the Log-Sobolev Constants of Graphs and Markov Chains

Two types of lower bounds are obtained on the log-Sobolev constants of graphs and Markov chains. The first is a mixture of spectral gap and logarithmic isoperimetric constant, the second involves the Gaussian isoperimetric constant. The sharpness of both types of bounds is tested on some examples. Product generalizations of some of these results are also briefly given. Received March 1, 1999/Revised July 17, 2000 RID="*" ID="*" Research supported in part by the NSF Grant No. DMS–9803239. The author greatly enjoyed the hospitality of CIMAT, Gto, Mexico, where part of this work was done.     

Occupation times in systems of null recurrent Markov processes

Summary We study asymptotic properties of differences of occupation times for infinite systems of noninteracting Markovian particles. Under a suitable normalisation we prove convergence in law to a nondegerate Gaussian field. We also obtain large deviations properties. These results generalise previous results obtained separately by both authors.Supported in part by the Office of Graduate Studies and Research (1990), University of Maryland and by NSF Grant No. DMS 9207928Supported in part by the Fonds Institutionnel de Recherche, Université du Québec à Trois-Rivières and by the Natural Sciences and Engineering Research Council of Canada, Grant No. OGP0042137     

Potential analysis for positive recurrent Markov chains with asymptotically zero drift: Power-type asymptotics

We consider a positive recurrent Markov chain on R⁺${\mathbb{R}}^{+}$ with asymptotically zero drift which behaves like −_c1/x$-c_1/x$ at infinity; this model was first considered by Lamperti. We are interested in tail asymptotics for the stationary measure. Our analysis is based on construction of a harmonic function which turns out to be regularly varying at infinity. This harmonic function allows us to perform non-exponential change of measure. Under this new measure Markov chain is transient with drift like _c2/x$c_2/x$ at infinity and we compute the asymptotics for its Green function. Applying further the inverse transform of measure we deduce a power-like asymptotic behaviour of the stationary tail distribution. Such a heavy-tailed stationary measure happens even if the jumps of the chain are bounded. This model provides an example where possibly bounded input distributions produce non-exponential output.     

Large deviations and related problems for absorbing Markov chains

In this paper, large deviations and their connections with several other fundamental topics are investigated for absorbing Markov chains. A variational representation for the Dirichlet principal eigenvalues is given by the large deviation approach. Kingman’s decay parameters and mean ratio quasi-stationary distributions of the chains are also characterized by the large deviation rate function. As an application of these results, we interpret the “stationarity” of mean ratio quasi-stationary distributions via a concrete example. An application to quasi-ergodicity is also discussed.     

Poisson type approximations for the Markov binomial distribution

The Markov binomial distribution is approximated by the Poisson distribution with the same mean, by a translated Poisson distribution and by two-parametric Poisson type signed measures. Using an adaptation of Le Cam’s operator technique, estimates of accuracy are proved for the total variation, local and Wasserstein norms. In a special case, asymptotically sharp constants are obtained. For some auxiliary results, we used Stein’s method.     

Markov Integrated Semigroups and their Applications to Continuous-Time Markov Chains

A Markov integrated semigroup G(t) is by definition a weaklystar differentiable and increasing contraction integrated semigroup on l _∞. We obtain a generation theorem for such semigroups and find that they are not integrated C ₀-semigroups unless the generators are bounded. To link up with the continuous-time Markov chains (CTMCs), we show that there exists a one-to-one relationship between Markov integrated semigroups and transition functions. This gives a clear probability explanation of G(t): it is just the mean transition time, and allows us to define and to investigate its q-matrix. For a given q-matrix Q, we give a criterion for the minimal Q-function to be a Feller-Reuter-Riley (FRR) transition function, this criterion gives an answer to a long-time question raised by Reuter and Riley (1972). This research was supported by the China Postdoctoral Science Foundation (No.2005038326).     

New perturbation bounds for denumerable Markov chains

This paper is devoted to perturbation analysis of denumerable Markov chains. Bounds are provided for the deviation between the stationary distribution of the perturbed and nominal chain, where the bounds are given by the weighted supremum norm. In addition, bounds for the perturbed stationary probabilities are established. Furthermore, bounds on the norm of the asymptotic decomposition of the perturbed stationary distribution are provided, where the bounds are expressed in terms of the norm of the ergodicity coefficient, or the norm of a special residual matrix. Refinements of our bounds for Doeblin Markov chains are considered as well. Our results are illustrated with a number of examples.     

Fluctuations of empirical means at low temperature for finite Markov chains with rare transitions in the general case

Summary. The integrated autocovariance and autocorrelation time are essential tools to understand the dynamical behavior of a Markov chain. We study here these two objects for Markov chains with rare transitions with no reversibility assumption. We give upper bounds for the autocovariance and the integrated autocorrelation time, as well as exponential equivalents at low temperature. We also link their slowest modes with the underline energy landscape under mild assumptions. Our proofs will be based on large deviation estimates coming from the theory of Wentzell and Freidlin and others [4, 3, 12], and on coupling arguments (see [6] for a review on the coupling method). Received 5 August 1996 / In revised form: 6 August 1997     

On the log-Sobolev constant for the simple random walk on the n-cycle: the even cases

Consider the simple random walk on the n-cycle . For this example, Diaconis and Saloff-Coste (Ann. Appl. Probab. 6 (1996) 695) have shown that the log-Sobolev constant α is of the same order as the spectral gap λ. However the exact value of α is not known for n>4. (For n=2, it is a well known result of Gross (Amer. J. Math. 97 (1975) 1061) that α is . For n=3, Diaconis and Saloff-Coste (Ann. Appl. Probab. 6 (1996) 695) showed that . For n=4, the fact that follows from n=2 by tensorization.) Based on an idea that goes back to Rothaus (J. Funct. Anal. 39 (1980) 42; 42 (1981) 110), we prove that if n?4 is even, then the log-Sobolev constant and the spectral gap satisfy . This implies that when n is even and n?4.     

Blackwell Optimality in the Class of Markov Policies for Continuous-Time Controlled Markov Chains

This paper deals with Blackwell optimality for continuous-time controlled Markov chains with compact Borel action space, and possibly unbounded reward (or cost) rates and unbounded transition rates. We prove the existence of a deterministic stationary policy which is Blackwell optimal in the class of all admissible (nonstationary) Markov policies, thus extending previous results that analyzed Blackwell optimality in the class of stationary policies. We compare our assumptions to the corresponding ones for discrete-time Markov controlled processes.     

The Markov chain asymptotics of random mapping graphs

In this paper the limit behavior of random mappings with n vertices is investigated. We first compute the asymptotic probability that a fixed class of finite non-intersected subsets of vertices are located in different components and use this result to construct a scheme of allocating particles with a related Markov chain. We then prove that the limit behavior of random mappings is actually embedded in such a scheme in a certain way. As an application, we shall give the asymptotic moments of the size of the largest component.     

Forward and reverse representations for Markov chains

In this paper we carry over the concept of reverse probabilistic representations developed in Milstein, Schoenmakers, Spokoiny [G.N. Milstein, J.G.M. Schoenmakers, V. Spokoiny, Transition density estimation for stochastic differential equations via forward–reverse representations, Bernoulli 10 (2) (2004) 281–312] for diffusion processes, to discrete time Markov chains. We outline the construction of reverse chains in several situations and apply this to processes which are connected with jump–diffusion models and finite state Markov chains. By combining forward and reverse representations we then construct transition density estimators for chains which have root-N$N$ accuracy in any dimension and consider some applications.     

A Resistance Bound Via An Isoperimetric Inequality

An isoperimetric upper bound on the resistance is given. As a corollary we resolve two problems, regarding mean commute time on finite graphs and resistance on percolation clusters. Further conjectures are presented.     

Spectral computations for birth and death chains

We consider the spectrum of birth and death chains on an n$n$-path. An iterative scheme is proposed to compute any eigenvalue with exponential convergence rate independent of n$n$. This allows one to determine the whole spectrum in order n²$n^2$ elementary operations. Using the same idea, we also provide a lower bound on the spectral gap, which is of the correct order on some classes of examples.     

Upper escape rate of Markov chains on weighted graphs

We obtain an upper escape rate function for a continuous time minimal symmetric Markov chain defined on a locally finite weighted graph. This upper rate function, which has the same form as the manifold setting, is given in terms of the volume growth with respect to an adapted path metric. Our approach also gives a weak form of Folz’s theorem on the conservativeness as a consequence.