Bounds on regeneration times and convergence rates for Markov chains

In many applications of Markov chains, and especially in Markov chain Monte Carlo algorithms, the rate of convergence of the chain is of critical importance. Most techniques to establish such rates require bounds on the distribution of the random regeneration time T that can be constructed, via splitting techniques, at times of return to a “small set” C satisfying a minorisation condition P(x,·)(·), xC. Typically, however, it is much easier to get bounds on the time τ_C of return to the small set itself, usually based on a geometric drift function , where . We develop a new relationship between T and τ_C, and this gives a bound on the tail of T, based on ,λ and b, which is a strict improvement on existing results. When evaluating rates of convergence we see that our bound usually gives considerable numerical improvement on previous expressions.     

On potentials of ergodic Markov chains

Two theorems on the existence of the potential of an ergodic Markov chain in an arbitrary phase space are proved.DeceasedTranslated from Ukrainskii Matematicheskii Zhurnal, Vol. 46, No. 4, pp. 446–449, April, 1994.This work was supported by the Ukrainian State Committee on Science and Technology.     

Learning from uniformly ergodic Markov chains

Evaluation for generalization performance of learning algorithms has been the main thread of machine learning theoretical research. The previous bounds describing the generalization performance of the empirical risk minimization (ERM) algorithm are usually established based on independent and identically distributed (i.i.d.) samples. In this paper we go far beyond this classical framework by establishing the generalization bounds of the ERM algorithm with uniformly ergodic Markov chain (u.e.M.c.) samples. We prove the bounds on the rate of uniform convergence/relative uniform convergence of the ERM algorithm with u.e.M.c. samples, and show that the ERM algorithm with u.e.M.c. samples is consistent. The established theory underlies application of ERM type of learning algorithms.     

Algebraic convergence for discrete-time ergodic markov chains

This paper studies the l-ergodicity for discrete-time recurrent Markov chains.It proves that thel-order deviation matrix exists and is finite if and only if the chain is(l+2)-ergodic,and then the algebraicdecay rates of the n-step transition probability to the stationary distribution are obtained.The criteria forl-ergodicity are given in terms of existence of solution to an equation.The main results are,illustrated by someexamples.     

Uniform ergodic convergence and averaging along Markov chain trajectories

LetP(x, A) be a transition probability on a measurable space (S, Σ) and letX _n be the associated Markov chain.Theorem. Letf∈B(S, Σ). Then for anyx∈S we haveP _x a.s. $$\mathop {\underline {\lim } }\limits_{n \to \infty } \frac{1}{n}\sum\limits_{k = 1}^n {f(X_k ) \geqslant } \mathop {\underline {\lim } }\limits_{n \to \infty } \mathop {\inf }\limits_{x \in S} \frac{1}{n}\sum\limits_{k = 1}^n {P^k f(x)} $$ and (implied by it) a corresponding inequality for the lim. If 1/n∑ _k=1 ⁿ P ^k f converges uniformly, then for everyx∈S, 1/n ∑ _k=1 ⁿ f(X _k ) convergesP _x a.s. Applications are made to ergodic random walks on amenable locally compact groups. We study the asymptotic behavior of 1/n∑ _k=1 ⁿ μ ^k *f and of 1/n∑ _k=1 ⁿ f(X _k ) via that ofΨ _n *f(x)=m(A _n )^?1∫ _An f(xt), where {A _n } is a Følner sequence, in the following cases: (i)f is left uniformly continuous (ii) μ is spread out (iii)G is Abelian. Non-Abelian Example: Let μ be adapted and spread-out on a nilpotent σ-compact locally compact groupG, and let {A _n } be a Følner sequence. If forf∈B(G, ∑) m(A _n )^?1∫ _An f(xt)dm(t) converges uniformly, then 1/n∑ _k=1 ⁿ f(X _k ) converges uniformly, andP _x convergesP _x a.s. for everyx∈G.     

The occurrence of sequence patterns in ergodic Markov chains

The occupation measure identity is used to derive the expected waiting time for the first occurrence of a fixed finite pattern in a sequence of observations generated by an ergodic Markov chain.     

The ergodic theory of Markov chains in random environments

Summary A general formulation of the stochastic model for a Markov chain in a random environment is given, including an analysis of the dependence relations between the environmental process and the controlled Markov chain, in particular the problem of feedback. Assuming stationary environments, the ergodic theory of Markov processes is applied to give conditions for the existence of finite invariant measure (equilibrium distributions) and to obtain ergodic theorems, which provide results on convergence of products of random stochastic matrices. Coupling theory is used to obtain results on direct convergence of these products and the structure of the tail -field. State properties including classification and communication properties are discussed.     

Minimal rates of entropy convergence for completely ergodic systems

If (X,T) is a completely ergodic system, then there exists a positive monotone increasing sequence {a _n } _n ^1/∞ with lim _n →∞a _n =∞ and a positive concave functiong defined on [1, ∞) for whichg(x)/x ² isnot integrable such that for all nontrivial partitions α ofX into two sets.     

On the central limit theorem for geometrically ergodic Markov chains

Let X₀,X₁,... be a geometrically ergodic Markov chain with state space and stationary distribution . It is known that if h: R satisfies (|h|²⁺)< for some >0, then the normalized sums of the X_is obey a central limit theorem. Here we show, by means of a counterexample, that the condition (|h|²⁺)< cannot be weakened to only assuming a finite second moment, i.e., (h²)<.Reasearch supported by the Swedish Research Council.     

Estimation of spectral gap for Markov chains

The study of the convergent rate (spectral gap) in theL ²-sense is motivated from several different fields: probability, statistics, mathematical physics, computer science and so on and it is now an active research topic. Based on a new approach (the coupling technique) introduced in [7] for the estimate of the convergent rate and as a continuation of [4], [5], [7–9], [23] and [24], this paper studies the estimate of the rate for time-continuous Markov chains. Two variational formulas for the rate are presented here for the first time for birth-death processes. For diffusions, similar results are presented in an accompany paper [10]. The new formulas enable us to recover or improve the main known results. The connection between the sharp estimate and the corresponding eigenfunction is explored and illustrated by various examples. A previous result on optimal Markovian couplings^[4] is also extended in the paper.Research supported in part by NSFC, Qin Shi Sci & Tech. Foundation and the State Education Commission of China.     

Spectral gap and convergence rate for discrete-time Markov chains

Let P be a transition matrix which is symmetric with respect to a measure π.The spectral gap of P in L2(π)-space,denoted by gap(P),is defined as the distance between 1 and the rest of the spectrum of P.In this paper,we study the relationship between gap(P) and the convergence rate of Pn.When P is transient,the convergence rate of P n is equal to 1 gap(P).When P is ergodic,we give the explicit upper and lower bounds for the convergence rate of Pn in terms of gap(P).These results are extended to L∞(π)-space.     

On the mixing property and the ergodic principle for nonhomogeneous Markov chains

We study different types of limit behavior of infinite dimension discrete time nonhomogeneous Markov chains. We show that the geometric structure of the set of those Markov chains which have asymptotically stationary density depends on the considered topologies. We generalize and correct some results from Ganikhodjaev et al. (2006) [3].     

The ergodic theorems for Markov chains with an arbitrary phase space

The ergodic theorems are formulated both is the case of the uniform ergodicity and in the absence of this latter under more general conditions than before. The conditions laid down on the transition function in the case of nonuniform ergodicity are less restrictive than these by Athreya-Ney and Nummelin. In contrast to these latter the restrictions are set not on the initial transition function, but on that of the imbedded Markov chain which is constructed by the instants of the recurrence to some fixed set. The proof is based on the spectral theory of Banach algebras.