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.     

Some variational formulas on additive functionals of symmetric Markov chains

For symmetric continuous time Markov chains, we obtain some formulas on total occupation times and limit theorems of additive functionals by using large deviation theory.

     

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.     

Singular perturbed Markov chains and exact behaviors of simulated annealing processes

We study asymptotic properties of discrete and continuous time generalized simulated annealing processesX(·) by considering a class of singular perturbed Markov chains which are closely related to the large deviation of perturbed diffusion processes. Convergence ofX(t) in probability to a setS ₀ of desired states, e.g., the set of global minima, and in distribution to a probability concentrated onS ₀ are studied. The corresponding two critical constants denoted byd and withd are given explicitly. When the cooling schedule is of the formc/logt, X(t) converges weakly forc>0. Whether the weak limit depends onX(0) or concentrates onS ₀ is determined by the relation betweenc, d, and . Whenc>, the expression for the rate of convergence for each state is also derived.     

Limiting distributions of functionals of Markov chains

Let \s{X_n, n ? 0\s} and \s{Y_n, n ? 0\s} be two stochastic processes such that Y_n depends on X_n in a stationary manner, i.e. P(Y_n ? A\vbX_n) does not depend on n. Sufficient conditions are derived for Y_n to have a limiting distribution. If X_n is a Markov chain with stationary transition probabilities and Y_n = f(X_n,..., X_n+k) then Y_n depends on X_n is a stationary way. Two situations are considered: (i) \s{X_n, n ? 0\s} has a limiting distribution (ii) \s{X_n, n ? 0\s} does not have a limiting distribution and exits every finite set with probability 1. Several examples are considered including that of a non-homogeneous Poisson process with periodic rate function where we obtain the limiting distribution of the interevent times.     

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

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

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.     

Moderate deviations for time-varying dynamic systems driven by non-homogeneous Markov chains with Two-time Scales

Motivated by problems arising in time-dependent queues and dynamic systems with random environment, this work develops moderate deviations principles for dynamic systems driven by a fast-varying non-homogeneous Markov chain in continuous time. A distinct feature is that the Markov chain is time dependent or inhomogeneous, so are the dynamic systems. Under irreducibility of the non-homogeneous Markov chain, moderate deviations of a non-homogeneous functional are established first. With the help of a martingale problem formulation and a functional central limit theorem for the two timescale system, both upper and lower bounds of moderate deviations are obtained for the rapidly fluctuating Markovian systems. Then applications to queueing systems and dynamic systems modulated by a fast-varying Markov chain are examined.     

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.     

Rate function of large deviation for a class of nonhomogeneous markov chains on supercritical percolation network

We model an epidemic with a class of nonhomogeneous Markov chains on the supercritical percolation network on ℤ ^d . The large deviations law for the Markov chain is given. Explicit expression of the rate function for large deviation is obtained.     

On an extremal property of Markov chains and sufficiency of Markov strategies in Markov decision processes with the Dubins-Savage criterion

An inequality regarding the minimum ofP(lim inf(X _n D _n )) is proved for a class of random sequences. This result is related to the problem of sufficiency of Markov strategies for Markov decision processes with the Dubins-Savage criterion, the asymptotical behaviour of nonhomogeneous Markov chains, and some other problems.     

Multi-dimensional asymptotically quasi-Toeplitz Markov chains and their application in queueing theory

Multi-dimensional asymptotically quasi-Toeplitz Markov chains with discrete and continuous time are introduced. Ergodicity and non-ergodicity conditions are proven. Numerically stable algorithm to calculate the stationary distribution is presented. An application of such chains in retrial queueing models with Batch Markovian Arrival Process is briefly illustrated. AMS Subject Classifications Primary 60K25 · 60K20     

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.     

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.     

Quasi-stationarity and quasi-ergodicity of general Markov processes

In this paper, we study the quasi-stationarity and quasi-ergodicity of general Markov processes. We show, among other things, that if X is a standard Markov process admitting a dual with respect to a finite measure m and if X admits a strictly positive continuous transition density p(t, x, y) (with respect to m) which is bounded in (x, y) for every t > 0, then X has a unique quasi-stationary distribution and a unique quasi-ergodic distribution. We also present several classes of Markov processes satisfying the above conditions.     

On the structure of 1-dependent Markov chains

Any stationary 1-dependent Markov chain with up to four states is a 2-block factor of independent, identically distributed random variables. There is a stationary 1-dependent Markov chain with five states which is not, even though every 1-dependent renewal process is a 2-block factor.     

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.