Transportation inequalities for hidden Markov chains and applications

We prove some transportation inequalities for hidden Markov chains, generalize the results proved by Kontorovich and Ramanan in two directions and give some applications to log-likelihood functions and hypothesis testing.     

On multiple Markov chains

The aim of this paper is to examine multiple Markov dependence for the discrete as well as for the continuous parameter case. In both cases the Markov property with arbitrary parameter values is investigated and it is shown that it leads to the degeneration of the multiple Markov dependence to the simple one.     

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 the representation of finite multiple Markov chains by weighted circuits

In this paper circuit chains of superior order are defined as multiple Markov chains for which transition probabilities are expressed in terms of the weights of a finite class of circuits in a finite set, in connection with kinetic properties along the circuits. Conversely, it is proved that if we join any finite doubly infinite strictly stationary Markov chain of order r for which transitions hold cyclically with a second chain with the same transitions for the inverse time-sense, then they may be represented as circuit chains of order r.     

On perturbation bounds for continuous-time Markov chains

We suggest an approach to obtaining general estimates of stability in terms of special “weighted” norms related to total variation. Two important classes of continuous-time Markov chains are considered for which it is possible to obtain exact convergence rate estimates (and hence, guarantee exact stability estimates): birth–death–catastrophes processes, and queueing models with batch arrivals and group services.     

Nash Inequalities for Markov Processes in Dimension One

In this paper, we give characterizations of Nash inequalities for birth-death process and diffusion process on the line. As a by-product, we prove that for these processes, transience implies that the semigroups P(t) decay as ∥P(t)∥_1→∞≥Ct ₋₁. Sufficient conditions for general Markov chains are also obtained. Received November 29, 2000, Revised February 21, 2001, Accepted March 16, 2001     

一维Markov过程的Nash不等式

本文得到了生灭过程和一维扩散过程满足Nash不等式的判别准则,并证明 了对此二类过程,非常返性蕴含相应半群如下收敛速度||P(t)||1→∞≤Ct-1.同时也给 出一般马氏链满足Nash不等式的充分条件.     

A semidefinite bound for mixing rates of Markov chains

We study general geometric techniques for bounding the spectral gap of a reversible Markov chain. We show that the best bound obtainable using these techniques can be computed in polynomial time via semidefinite programming, and is off by at most a factor of order log²n, where n is the number of states. © 1997 John Wiley & Sons, Inc. Random Struct. Alg., 11 , 299–313 (1997)     

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.     

Stability and monotonicity for interactive Markov chains

In a Markov chain model of a social process, interest often centers on the distribution of the population by state. One question, the stability question, is whether this distribution converges to an equilibrium value. For an ordinary Markov chain (a chain with constant transition probabilities), complete answers are available. For an interactive Markov chain (a chain which allows the transition probabilities governing each individual to depend on the locations by state of the rest of the population), few stability results are available. This paper presents new results. Roughly, the main result is that an interactive Markov chain with unique equilibrium will be stable if the chain satisfies a certain monotonicity property. The property is a generalization to interactive Markov chains of the standard definition of monotonicity for ordinary Markov chains.     

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.     

Isomorphism theorems for Markov chains

The isomorphism theorem of Dynkin is definitely an important tool to investigate the problems raised in terms of local times of Markov processes. This theorem concerns continuous time Markov processes. We give here an equivalent version for Markov chains.     

Discrete time Markov chains with interval probabilities

The parameters of Markov chain models are often not known precisely. Instead of ignoring this problem, a better way to cope with it is to incorporate the imprecision into the models. This has become possible with the development of models of imprecise probabilities, such as the interval probability model. In this paper we discuss some modelling approaches which range from simple probability intervals to the general interval probability models and further to the models allowing completely general convex sets of probabilities. The basic idea is that precisely known initial distributions and transition matrices are replaced by imprecise ones, which effectively means that sets of possible candidates are considered. Consequently, sets of possible results are obtained and represented using similar imprecise probability models.We first set up the model and then show how to perform calculations of the distributions corresponding to the consecutive steps of a Markov chain. We present several approaches to such calculations and compare them with respect to the accuracy of the results. Next we consider a generalisation of the concept of regularity and study the convergence of regular imprecise Markov chains. We also give some numerical examples to compare different approaches to calculations of the sets of probabilities.     

随机环境中马氏链与马氏双链间的相互关系

比较圆满地解决了单无限和双无限环境及其对应的双链和原过程四者间的相互关系．特别地,澄清了一些误解,纠正了其中的错误结论,为进一步深入研究随机环境中马氏链提供了非常明晰的基本概念．     

Exact formula for sensitivity analysis of Markov chains

Given a family of Markov chains whose transition matrices depend on a parameter vector, we given an exact formula for the gradient of the equilibrium distribution with respect to that parameter even in the case of multiple ergodic classes and transient states. This formula generalizes previous results in the ergodic case.     

A fluctuation theory for Markov chains

A fluctuation theory for Markov chains on an ordered countable state space is developed, using ladder processes. These are shown to be Markov renewal processes. Results are given for the joint distribution of the extremum (maximum or minimum) and the first time the extremum is achieved. Also a new classification of the states of a Markov chain is suggested. Two examples are given.     

Eigentime identity for asymmetric finite Markov chains

Two kinds of eigentime identity for asymmetric finite Markov chains are proved both in the ergodic case and the transient case.     

关于非齐次马氏链的一个定理

给出了Csiszar和Krner关于独立随机变量序列的一个定理的一个推广,该定理的推论是关于相对熵的,在统计假设检验及编码理论中起着重要的作用.利用非齐次马氏链的一个强大数定律将这个定理推广到非齐次马氏链上.