Perturbed Markov Chains with Damping Component

The paper is devoted to studies of regularly and singularly perturbed Markov chains with damping component. In such models, a matrix of transition probabilities is regularised by adding a special damping matrix multiplied by a small damping (perturbation) parameter ε. We perform a detailed perturbation analysis for such Markov chains, particularly, give effective upper bounds for the rate of approximation for stationary distributions of unperturbed Markov chains by stationary distributions of perturbed Markov chains with regularised matrices of transition probabilities, asymptotic expansions for approximating stationary distributions with respect to damping parameter, explicit coupling type upper bounds for the rate of convergence in ergodic theorems for n-step transition probabilities, as well as ergodic theorems in triangular array mode.

     

Occupation Measures of Singularly Perturbed Markov Chains with Absorbing States

Abstract This paper develops asymptotic properties of singularly perturbed Markov chains with inclusion of absorbing states. It focuses on both unscaled and scaled occupation measures. Under mild conditions, a mean-square estimate is obtained. By averaging the fast components, we obtain an aggregated process. Although the aggregated process itself may be non-Markovian, its weak limit is a Markov chain with much smaller state space. Moreover, a suitably scaled sequence consisting of a component of scaled occupation measures and a component of the aggregated process is shown to converge to a pair of processes with a switching diffusion component. * The research of this author is supported in part by the National Science Foundation under Grant DMS-9877090 ** The research of this author is supported in part by the Office of Naval Research Grant N00014-96-1-0263 *** The research of this author is supported in part by Wayne State University     

Sub-stochastic matrix analysis for bounds computation—Theoretical results

Performance evaluation of complex systems is a critical issue and bounds computation provides confidence about service quality, reliability, etc. of such systems. The stochastic ordering theory has generated a lot of works on bounds computation. Maximal lower and minimal upper bounds of a Markov chain by a st-monotone one exist and can be efficiently computed. In the present work, we extend simultaneously this last result in two directions. On the one hand, we handle the case of a maximal monotone lower bound of a family of Markov chains where the coefficients are given by numerical intervals. On the other hand, these chains are sub-chains associated to sub-stochastic matrices. We prove the existence of this maximal bound and we provide polynomial time algorithms to compute it both for discrete and continuous Markov chains. Moreover, it appears that the bounding sub-chain of a family of strictly sub-stochastic ones is not necessarily strictly sub-stochastic. We establish a characterization of the families of sub-chains for which these bounds are strictly sub-stochastic. Finally, we show how to apply these results to a classical model of repairable system. A forthcoming paper will present detailed numerical results and comparison with other methods.     

Some stochastic properties of “semi-magic” and “magic” Markov chains

Gustafson and Styan (Gustafson and Styan, Superstochastic matrices and Magic Markov chains, Linear Algebra Appl. 430 (2009) 2705-2715) examined the mathematical properties of superstochastic matrices, the transition matrices of “magic” Markov chains formed from scaled “magic squares”. This paper explores the main stochastic properties of such chains as well as “semi-magic” chains (with doubly-stochastic transition matrices). Stationary distribution, generalized inverses of Markovian kernels, mean first passage times, variances of the first passage times and expected times to mixing are considered. Some general results are developed, some observations from the chains generated by MATLAB are discussed, some conjectures are presented and some special cases, involving three and four states, are explored in detail.     

Estimations pour les chaînes de Markov réversibles

We give Gaussian lower and upper bounds for reversible Markov chains on a graph under two geometric assumptions (volume regularity and Poincaré inequality). This is first proved for continuous-time Markov chains via a parabolic Harnack inequality. Then, the estimates for the discrete-time Markov chains are derived by comparison.     

随机有序马尔可夫链收敛速度显式界的注记

弱化Scott与Tweedie在计算马氏链收敛速度界时的条件,即变一步转移概率为m(m≥1)步转移概率,并运用不同于Scott与Tweedie的方法,计算出马氏链几何收敛速度r~n的界,从而推广了已有的结论.     

Asymptotic Optimality of Isoperimetric Constants

In this paper, we investigate the existence of L ²(π)-spectral gaps for π-irreducible, positive recurrent Markov chains with a general state space Ω. We obtain necessary and sufficient conditions for the existence of L ²(π)-spectral gaps in terms of a sequence of isoperimetric constants. For reversible Markov chains, it turns out that the spectral gap can be understood in terms of convergence of an induced probability flow to the uniform flow. These results are used to recover classical results concerning uniform ergodicity and the spectral gap property as well as other new results. As an application of our result, we present a rather short proof for the fact that geometric ergodicity implies the spectral gap property. Moreover, the main result of this paper suggests that sharp upper bounds for the spectral gap should be expected when evaluating the isoperimetric flow for certain sets. We provide several examples where the obtained upper bounds are exact.     

Moderate Deviations for Empirical Measures of Markov Chains: Upper Bounds

We obtain upper bounds for moderate deviations of empirical measures of Markov chains with general state space in the -topology under the minimal assumption of geometric ergodicity. The regeneration-split chain method and a result on projective systems are employed in the proof.     

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.     

Local approximations of Markov random walks by diffusions

We consider triangular arrays of Markov random walks that can be approximated by an accompanying sequence of diffusion processes. We give uniform bounds for approximation of scaled transition probabilities by transition densities of the diffusion process. In particular, we state local limit theorems for the case that the Markov random walks converge weakly to a diffusion process.     

Metastability in stochastic dynamics of disordered mean-field models

We study a class of Markov chains that describe reversible stochastic dynamics of a large class of disordered mean field models at low temperatures. Our main purpose is to give a precise relation between the metastable time scales in the problem to the properties of the rate functions of the corresponding Gibbs measures. We derive the analog of the Wentzell-Freidlin theory in this case, showing that any transition can be decomposed, with probability exponentially close to one, into a deterministic sequence of “admissible transitions”. For these admissible transitions we give upper and lower bounds on the expected transition times that differ only by a constant factor. The distributions of the rescaled transition times are shown to converge to the exponential distribution. We exemplify our results in the context of the random field Curie-Weiss model. Received: 26 November 1998 / Revised version: 21 March 2000 / Published online: 14 December 2000     

Imprecise stochastic processes in discrete time: global models,imprecise Markov chains,and ergodic theorems

We justify and discuss expressions for joint lower and upper expectations in imprecise probability trees, in terms of the sub- and supermartingales that can be associated with such trees. These imprecise probability trees can be seen as discrete-time stochastic processes with finite state sets and transition probabilities that are imprecise, in the sense that they are only known to belong to some convex closed set of probability measures. We derive various properties for their joint lower and upper expectations, and in particular a law of iterated expectations. We then focus on the special case of imprecise Markov chains, investigate their Markov and stationarity properties, and use these, by way of an example, to derive a system of non-linear equations for lower and upper expected transition and return times. Most importantly, we prove a game-theoretic version of the strong law of large numbers for submartingale differences in imprecise probability trees, and use this to derive point-wise ergodic theorems for imprecise Markov chains.     

Subgeometric ergodicity for continuous-time Markov chains

In this paper, subgeometric ergodicity is investigated for continuous-time Markov chains. Several equivalent conditions, based on the first hitting time or the drift function, are derived as the main theorem. In its corollaries, practical drift criteria are given for ?-ergodicity and computable bounds on subgeometric convergence rates are obtained for stochastically monotone Markov chains. These results are illustrated by examples.     

Eigentime identity for transient Markov chains

An eigentime identity is proved for transient symmetrizable Markov chains. For general Markov chains, if the trace of Green matrix is finite, then the expectation of first leap time is uniformly bounded, both of which are proved to be equivalent for single birth processes. For birth-death processes, the explicit formulas are presented. As an application, we give the bounds of exponential convergence rates of (sub-) Markov semigroup Pt from l_∞ to l_∞.     

Heat kernels of non-symmetric jump processes with exponentially decaying jumping kernel

In this paper we study the transition densities for a large class of non-symmetric Markov processes whose jumping kernels decay exponentially or subexponentially. We obtain their upper bounds which also decay at the same rate as their jumping kernels. When the lower bounds of jumping kernels satisfy the weak upper scaling condition at zero, we also establish lower bounds for the transition densities, which are sharp.     

Hoeffding's inequality for Markov processes via solution of Poisson's equation

We investigate Hoeffding's inequality for both discrete-time Markov chains and continuous-time Markov processes on a general state space. Our results relax the usual aperiodicity restriction in the literature, and the explicit upper bounds in the inequalities are obtained via the solution of Poisson's equation. The results are further illustrated with applications to queueing theory and reective diffusion processes.     

Fluctuations of interacting Markov chain Monte Carlo methods

We present a multivariate central limit theorem for a general class of interacting Markov chain Monte Carlo algorithms used to solve nonlinear measure-valued equations. These algorithms generate stochastic processes which belong to the class of nonlinear Markov chains interacting with their empirical occupation measures. We develop an original theoretical analysis based on resolvent operators and semigroup techniques to analyze the fluctuations of their occupation measures around their limiting values.     

A Markov Chain analysis of genetic algorithms with power of 2 cardinality alphabets

In this paper we model the run time behavior of GAs using higher cardinality representations as Markov chains, define the states of the Markov Chain and derive the transition probabilities of the corresponding transition matrix. We analyze the behavior of this chain and obtain bounds on its convergence rate and bounds on the runtime complexity of the GA. We further investigate the effects of using binary versus higher cardinality representation of a search space.     

Symmetric Markov chains on with unbounded range

We consider symmetric Markov chains on where we do not assume that the conductance between two points must be zero if the points are far apart. Under a uniform second moment condition on the conductances, we obtain upper bounds on the transition probabilities, estimates for exit time probabilities, and certain lower bounds on the transition probabilities. We show that a uniform Harnack inequality holds if an additional assumption is made, but that without this assumption such an inequality need not hold. We establish a central limit theorem giving conditions for a sequence of normalized symmetric Markov chains to converge to a diffusion on corresponding to an elliptic operator in divergence form.

     

Ergodic Theorems and Ergodic Decomposition for Markov Chains

This paper considers Markov chains on a locally compact separable metricspace, which have an invariant probability measure but with no otherassumption on the transition kernel. Within this context, the limit providedby several ergodic theorems is explicitly identified in terms of the limitof the expected occupation measures. We also extend Yosidasergodic decomposition for Feller-like kernels to arbitrarykernels, and present ergodic results for empirical occupation measures, aswell as for additive-noise systems.