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_∞.     

Markov chains with almost exponential hitting times

If a Markov chain converges rapidly to stationarity, then the time until the first hit on a rarely-visited set of states is approximately exponentially distributed; moreover an explicit bound for the error in this approximation can be given. This complements results of Keilson.     

Ergodic degrees for continuous-time Markov chains

This paper studies the existence of the higher orders deviation matrices for continuous time Markov chains by the moments for the hitting times. An estimate of the polynomial convergence rates for the transition matrix to the stationary measure is obtained. Finally, the explicit formulas for birth-death processes are presented.     

Hitting time in a finite non-homogeneous Markov chain with applications

This paper deals with the computation of the hitting time for a non-homogeneous discrete time Markov chain (NHDTMC or NHMC). We first give the basic definitions of NHMC, then we analyse the hitting time and its survivor function. We also give the sufficient conditions for the existence of the mean hitting time. Finally, a numerical example and an application of this development in reliability evaluation are given in order to illustrate our results. © 1998 John Wiley & Sons, Ltd.     

Q-矩阵第一特征值估计的Monte Carlo方法

本文对给定的可逆马氏链所对应的 Q-矩阵给出了它的第一非零特征值的 Monte Carlo估计方法 .具体做法是通过增加一个状态构造一个新的可逆马氏链 ,然后利用增加状态的击中时分布去估计第一非零特征值 .     

层次模型Markov链的观测与统计

对于连续时间的层次模型M arkov链,所有的转移速率都可以由最底层状态的逗留时间和击中时间分布惟一决定,因而整个M arkov链的统计性质由它们的统计所决定.并给出了相应的算法和数例.     

Limiting process of absorbing Markov chains

We outline an approach to investigate the limiting law of an absorbing Markov chain conditional on having not been absorbed for long time. The main idea is to employ Donsker-Varadhan＇s entropy functional which is typically used as the large deviation rate function for Markov processes. This approach provides an interpretation for a certain quasi-ergodicity     

Nash inequalities for finite Markov chains

This paper develops bounds on the rate of decay of powers of Markov kernels on finite state spaces. These are combined with eigenvalue estimates to give good bounds on the rate of convergence to stationarity for finite Markov chains whose underlying graph has moderate volume growth. Roughly, for such chains, order (diameter) steps are necessary and suffice to reach stationarity. We consider local Poincaré inequalities and use them to prove Nash inequalities. These are bounds onl ₂-norms in terms of Dirichlet forms andl ₁-norms which yield decay rates for iterates of the kernel. This method is adapted from arguments developed by a number of authors in the context of partial differential equations and, later, in the study of random walks on infinite graphs. The main results do not require reversibility.     

Occupation measures for Markov chains

We give simple proofs of large deviation theorems for the occupation measure of a Markov chain using a regeneration argument to establish existence and convexity theory to identify the rate function.     

The convergence of matrix transforms for certain Markov chains

In this paper it is shown that, for certain classes of matrices, the matrix transform of a periodic strongly ergodic stochastic matrix P converges.     

Future independent times and Markov chains

Summary A random timeT is a future independent time for a Markov chain (X _n ) ₀ ifT is independent of (X _T+n ) _n ^/ =0 and if (X _T+n ) _n ^/ =0 is a Markov chain with initial distribution and the same transition probabilities as (X _n ) ₀ . This concept is used (with the conditional stationary measure) to give a new and short proof of the basic limit theorem of Markov chains, improving somewhat the result in the null-recurrent case.This work was supported by the Swedish Natural Science Research Council and done while the author was visiting the Department of Statistics, Stanford University     

Stopping times for quantum Markov chains

In the paper we introduce stopping times for quantum Markov states. We study algebras and maps corresponding to stopping times, give a condition of strong Markov property and give classification of projections for the property of accessibility. Our main result is a new recurrence criterium in terms of stopping times (Theorem 1 and Corollary 2). As an application of the criterium we study how, in Section 6, the quantum Markov chain associated with the one-dimensional Heisenberg (usually non-Markovian) process, obtained from this quantum Markov chain by restriction to a diagonal subalgebra, is such that all its states are recurrent. We were not able to obtain this result from the known recurrence criteria of classical probability.Supported by GNAFA-CNR, Bando n. 211.01.25.     

Necessary embedding conditions for state-wise monotone Markov chains

In previous work, the embedding problem is examined within the entire set of discrete-time Markov chains. However, for several phenomena, the states of a Markov model are ordered categories and the transition matrix is state-wise monotone. The present paper investigates the embedding problem for the specific subset of state-wise monotone Markov chains. We prove necessary conditions on the transition matrix of a discrete-time Markov chain with ordered states to be embeddable in a state-wise monotone Markov chain regarding time-intervals with length 0.5: A transition matrix with a square root within the set of state-wise monotone matrices has a trace at least equal to 1.     

Exponential bounds for discrete-time singularly perturbed Markov chains

This paper develops exponential type upper bounds for scaled occupation measures of singularly perturbed Markov chains in discrete time. By considering two-time scale in the Markov chains, asymptotic analysis is carried out. The cases of the fast changing transition probability matrix is irreducible and that are divisible into l ergodic classes are examined first; the upper bounds of a sequence of scaled occupation measures are derived. Then extensions to Markov chains involving transient states and/or nonhomogeneous transition probabilities are dealt with. The results enable us to further our understanding of the underlying Markov chains and related dynamic systems, which is essential for solving many control and optimization problems.     

Gradient flows of the entropy for finite Markov chains

Let K be an irreducible and reversible Markov kernel on a finite set X. We construct a metric W on the set of probability measures on X and show that with respect to this metric, the law of the continuous time Markov chain evolves as the gradient flow of the entropy. This result is a discrete counterpart of the Wasserstein gradient flow interpretation of the heat flow in Rn by Jordan, Kinderlehrer and Otto (1998). The metric W is similar to, but different from, the L²-Wasserstein metric, and is defined via a discrete variant of the Benamou-Brenier formula.     

On confidence intervals from simulation of finite Markov chains

Consider a finite state irreducible Markov reward chain. It is shown that there exist simulation estimates and confidence intervals for the expected first passage times and rewards as well as the expected average reward, with 100% coverage probability. The length of the confidence intervals converges to zero with probability one as the sample size increases; it also satisfies a large deviations property.     

关于可列非齐次马氏链的若干极限定理

设{Xn,n≥0}是一列非齐次马尔科夫链,{an,n≥0}是一列固定的非负整数序列.首先构造了一个带参数的广义似然比函数,然后利用Borel-Cantelli引理证明随机变量序列几乎处处收敛性,得到了关于可列非齐次马氏链序偶广义平均的若干极限定理,推广了已有的结果.     

On additive functionals of Markov chains

Let{S _n } _n=0 ^∞ be a Harris-recurrent Markov chain on a measurable state space. We prove strong approximation results for the additive functionals . Research supported by the Hungarian National Foundation for Scientific Research, Grant No. 1905. Mathematical Institute of the Hungarian Academy of Sciences, Budapest, P.O.B. 127, H-1364, Hungary. Research supported by an NSERC Canada Grant, Carleton University. Department of Mathematics and Statistics, Carleton University, Ottawa, Canada K1S 5B6.     

Inverse problems for ergodicity of Markov chains

For continuous-time Markov chains, we provide criteria for non-ergodicity, non-algebraic ergodicity, non-exponential ergodicity, and non-strong ergodicity. For discrete-time Markov chains, criteria for non-ergodicity, non-algebraic ergodicity, and non-strong ergodicity are given. Our criteria are in terms of the existence of solutions to inequalities involving the Q-matrix (or transition matrix P in time-discrete case) of the chain. Meanwhile, these practical criteria are applied to some examples, including a special class of single birth processes and several multi-dimensional models.