Perturbation models

A Markov chain (with a discrete state space and a continuous parameter) is perturbed by forcing a chain to return to “permissible” states whenever it happens to enter “forbidden” states, with returns governed by a replacement distribution.The compensation method is employed to obtain the distribution for the modified chain, in terms of the original chain and the perturbation mechanism.Emphasis is placed on ergodic chains, and interpretation of results in terms of perturbation theory of semi-groups and the ergodic potential theory (based on the fundamental matrix of a chain) is mentioned.     

Generalization performance of least-square regularized regression algorithm with Markov chain samples

The previously known works describing the generalization of least-square regularized regression algorithm are usually based on the assumption of independent and identically distributed (i.i.d.) samples. In this paper we go far beyond this classical framework by studying the generalization of least-square regularized regression algorithm with Markov chain samples. We first establish a novel concentration inequality for uniformly ergodic Markov chains, then we establish the bounds on the generalization of least-square regularized regression algorithm with uniformly ergodic Markov chain samples, and show that least-square regularized regression algorithm with uniformly ergodic Markov chains is consistent.     

用耦合方法研究马氏链f-指数遍历

该文在一般状态空间下研究马氏链指数遍历性,指数遍历马氏链,增加条件π(f~p)<∞, p> 1,利用耦合方法得到了存在满的吸收集,使得马氏链在其上是f-指数遍历的.     

Fuzzy Markov Chains and Decision-Making

Decision-making in an environment of uncertainty and imprecision for real-world problems is a complex task. In this paper it is introduced general finite state fuzzy Markov chains that have a finite convergence to a stationary (may be periodic) solution. The Cesaro average and the -potential for fuzzy Markov chains are defined, then it is shown that the relationship between them corresponds to the Blackwell formula in the classical theory of Markov decision processes. Furthermore, it is pointed out that recurrency does not necessarily imply ergodicity. However, if a fuzzy Markov chain is ergodic, then the rows of its ergodic projection equal the greatest eigen fuzzy set of the transition matrix. Then, the fuzzy Markov chain is shown to be a robust system with respect to small perturbations of the transition matrix, which is not the case for the classical probabilistic Markov chains. Fuzzy Markov decision processes are finally introduced and discussed.     

The central limit theorem for Markov chains with normal transition operators, started at a point

The central limit theorem and the invariance principle, proved by Kipnis and Varadhan for reversible stationary ergodic Markov chains with respect to the stationary law, are established with respect to the law of the chain started at a fixed point, almost surely, under a slight reinforcing of their spectral assumption. The result is valid also for stationary ergodic chains whose transition operator is normal. Received: 28 March 2000 / Revised version: 25 July 2000 /?Published online: 15 February 2001     

一类非齐次马氏链的绝对平均强遍历性

引用马氏链绝对平均强遍历的概念,首先给出齐次马氏链绝对平均强遍历与强遍历的等价性,其次通过引进另一个强遍历的非齐次马氏链,给出一个非齐次马氏链绝对平均强遍历的充分条件.     

Entangled Markov chains

Motivated by the problem of finding a satisfactory quantum generalization of the classical random walks, we construct a new class of quantum Markov chains which are at the same time purely generated and uniquely determined by a corresponding classical Markov chain. We argue that this construction yields as a corollary, a solution to the problem of constructing quantum analogues of classical random walks which are “entangled” in a sense specified in the paper.The formula giving the joint correlations of these quantum chains is obtained from the corresponding classical formula by replacing the usual matrix multiplication by Schur multiplication.The connection between Schur multiplication and entanglement is clarified by showing that these quantum chains are the limits of vector states whose amplitudes, in a given basis (e.g. the computational basis of quantum information), are complex square roots of the joint probabilities of the corresponding classical chains. In particular, when restricted to the projectors on this basis, the quantum chain reduces to the classical one. In this sense we speak of entangled lifting, to the quantum case, of a classical Markov chain. Since random walks are particular Markov chains, our general construction also gives a solution to the problem that motivated our study.In view of possible applications to quantum statistical mechanics too, we prove that the ergodic type of an entangled Markov chain with finite state space (thus excluding random walks) is completely determined by the corresponding ergodic type of the underlying classical chain. Mathematics Subject Classification (2000) Primary 46L53, 60J99; Secondary 46L60, 60G50, 62B10     

非齐次马尔科夫链遍历性的一些结果

本文利用两个非齐次马尔科夫链的转移矩阵列的比较，讨论了两个链启遍历性的关系，得到一个非齐次马尔科夫链是强遍历的一些充分条件．本文还分析了非齐次马尔科夫链的一致强、弱遍历性的关系，得到一个非齐次马尔科夫链是一致强遍历的一些充分条件．     

On a decomposition for infinite transition matrices

Heyman gives an interesting factorization of I-P, where P is the transition probability matrix for an ergodic Markov chain. We show that this factorization is valid if and only if the Markov chain is recurrent. Moreover, we provide a decomposition result which includes all ergodic, null recurrent as well as the transient Markov chains as special cases. Such a decomposition has been shown to be useful in the analysis of queues. This revised version was published online in June 2006 with corrections to the Cover Date.     

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.     

Positive dependence in Markov chains

A general notion of positive dependence among successive observations in a finite-state stationary process is studied, with particular attention to the case of a stationary ergodic Markov chain. This dependence condition can be expressed as a positivity condition on the joint probability matrices of pairs of observations. Some useful conditions equivalent to positive dependence are obtained for reversible chains, but shown not to be equivalent for nonreversible chains.     

A note on a variation of Doeblin's condition for uniform ergodicity of Markov chains

Summary We introduce a simple variation of Doeblin's condition, Condition D*, that assures the uniform ergodicity of a Markov chain. It is also shown that for non-homogeneous chains our conditions are equivalent to Dobrushin's weak ergodic coefficient.     

Cutoffs for product chains

We consider products of ergodic Markov chains and discuss their cutoffs in total variation. Our framework is general in that rates to pick up coordinates are not necessary equal, and different coordinates may correspond to distinct chains. We give necessary and sufficient conditions for cutoffs of product chains in terms of those of coordinate chains under certain conditions. A comparison of mixing times between the product chain and its coordinate chains is made in detail as well. Examples are given to show that neither cutoffs for product chains nor for coordinate chains imply others in general.     

二重非齐次马氏链的遍历性及其应用

给出二重非齐次马氏链的强遍历性,绝对平均强遍历性,Cesaro平均收敛的概念．利用二维马氏链的遍历性和C-K方程,建立了二维马氏链与二重非齐次马氏链遍历性的关系．并讨论了齐次二重马氏链绝对平均强遍历与强遍历的等价性．最后给出Cesaro平均收敛在马氏决策过程和信息论中应用．     

����״̬�����������Եij���֤��

In this paper, we introduce the definitions of geometric strongly ergodic, strongly ergodic and weakly ergodic for continuous-state Markov chains, then we give a primary proof of equivalence of the ergodicities for continuous-state Markov chains.     

On One Property of a Regular Markov Chain

We prove that if a certain row of the transition probability matrix of a regular Markov chain is subtracted from the other rows of this matrix and then this row and the corresponding column are deleted, then the spectral radius of the matrix thus obtained is less than 1. We use this property of a regular Markov chain for the construction of an iterative process for the solution of the Howard system of equations, which appears in the course of investigation of controlled Markov chains with single ergodic class and, possibly, transient states.     

Sensitivity analysis of discrete Markov chains via matrix calculus

Markov chains are often used as mathematical models of natural phenomena, with transition probabilities defined in terms of parameters that are of interest in the scientific question at hand. Sensitivity analysis is an important way to quantify the effects of changes in these parameters on the behavior of the chain. Many properties of Markov chains can be written as simple matrix expressions, and hence matrix calculus is a powerful approach to sensitivity analysis. Using matrix calculus, we derive the sensitivity and elasticity of a variety of properties of absorbing and ergodic finite-state chains. For absorbing chains, we present the sensitivities of the moments of the number of visits to each transient state, the moments of the time to absorption, the mean number of states visited before absorption, the quasistationary distribution, and the probabilities of absorption in each of several absorbing states. For ergodic chains, we present the sensitivity of the stationary distribution, the mean first passage time matrix, the fundamental matrix, and the Kemeny constant. We include two examples of application of the results to demographic and ecological problems.     

马氏链平稳分布存在与唯一性的简洁证明与计算

本文考虑可数状态离散时间齐次马氏链平稳分布的存在与唯一性.放弃以往大多数文献中要求马氏链是不可约,正常返且非周期(即遍历)的条件,本文仅需要马氏链是不可约和正常返的(但可能是周期的,因而可能是非遍历的).在此较弱的条件下,本文不仅给出了平稳分布存在与唯一性的简洁证明,而且还给出了平稳分布的计算方法.     

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.

     

Central Limit Theorem Started at a Point for?Stationary Processes and Additive Functionals of?Reversible Markov Chains

In this paper we study the almost sure central limit theorem started at a point for additive functionals of a stationary and ergodic Markov chain via a martingale approximation in the almost sure sense. Some of the results provide sufficient conditions for general stationary sequences. We use these results to study the quenched CLT for additive functionals of reversible Markov chains.