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.     

On a result for finite Markov chains

In an undergraduate course on stochastic processes, Markov chains are discussed in great detail. Textbooks on stochastic processes provide interesting properties of finite Markov chains. This note discusses one such property regarding the number of steps in which a state is reachable or accessible from another state in a finite Markov chain with M (≥ 2) states.     

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.     

Algorithms for finding steady state probabilities for some special classes of finite state Markov chains

Efficient algorithms for finding steady state probabilities are presented and compared with the Gaussian elimination method for two special classes of finite state Markov chains. One class has block matrix steps and a possible jump of up to k block steps, and the other is a generalization of the class considered by Shanthikumar and Sargent where each element is a matrix.     

Limit theorems for Markov chains of finite rank

We consider a Markov chain with a general state space, but whose behavior is governed by finite matrices. After a brief exposition of the basic properties of this chain, its convenience as a model is illustrated by three limit theorems. The ergodic theorem, the central limit theorem, and an extreme-value theorem are expressed in terms of dominant eigenvalues of finite matrices and proved by simple matrix theory.     

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.     

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.

     

A ratio limit theorem for the finite nonhomogeneous Markov chains

A new simple proof concerning the structure of the tail σ-field of a nonhomogeneous Markov chain as well as a result regarding the asymptotic behaviour of the ratio between the transition probabilities and the absolute probabilities of the chain are given. It is shown that the latter result can be used to characterize the atomic sets of the tail σ-field.     

Bounds for the quasi-stationary distribution of some specialized Markov chains

The quasi-stationary distributions of Markov chains have been investigated by many papers and are known to have considerable practical importance in, e.g., biological, chemical and applied probability models. However, computation of the quasi-stationary distributions is often nontrivial, which has limited its use in practice despite the usefulness of its own, except for some simple cases. This paper develops some bounds, which are relatively easy to calculate, for the quasi-stationary distribution of some specialized Markov chains.     

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.     

Spectral analysis of finite Markov chains with spherical symmetries

We generalize the classical Fourier analysis of Gelfand pairs to the setting of groups acting not transitively on a set X. We use this analysis to determine the spectrum of several random walks on graphs. Moreover, as byproduct, we show that, for a new urn diffusion model, the cut-off phenomenon holds.     

On the class of Markov chains with finite convergence time

We study the necessary and sufficient conditions for a finite ergodic Markov chain to converge in a finite number of transitions to its stationary distribution. Using this result, we describe the class of Markov chains which attain the stationary distribution in a finite number of steps, independent of the initial distribution. We then exhibit a queueing model that has a Markov chain embedded at the points of regeneration that falls within this class. Finally, we examine the class of continuous time Markov processes whose embedded Markov chain possesses the property of rapid convergence, and find that, in the case where the distribution of sojourn times is independent of the state, we can compute the distribution of the system at time t in the form of a simple closed expression.     

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.