Nonnegativity of principal minors of generalized inverses of M-matrices

The result of principal interest established in this paper is that if A is an n × n singular irreducible M-matrix, then a large class of generalized inverses of A possesses the property that each of its elements has all its principal minors nonnegative. The class contains both the group and the Moore-Penrose generalized inverses of A. In an application of our results it is shown that the fundamental matrix of a continuous (in time) ergodic Markov chain on a finite state space has all its principal minors nonnegative.     

Estimates on the amplitude of the first Dirichlet eigenvector in discrete frameworks

Consider a finite absorbing Markov generator, irreducible on the non-absorbing states. PerronFrobenius theory ensures the existence of a corresponding positive eigenvector ψ. The goal of the paper is to give bounds on the amplitude max ψ/ min ψ. Two approaches are proposed: One using a path method and the other one, restricted to the reversible situation, based on spectral estimates. The latter approach is extended to denumerable birth and death processes absorbing at 0 for which infinity is an entrance boundary. The interest of estimating the ratio is the reduction of the quantitative study of convergence to quasi-stationarity to the convergence to equilibrium of related ergodic processes, as seen by Diaconis and Miclo(2014).     

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.     

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.     

Geometric ergodicity for classes of homogeneous Markov chains

The paper deals with non asymptotic computable bounds for the geometric convergence rate of homogeneous ergodic Markov processes. Some sufficient conditions are stated for simultaneous geometric ergodicity of Markov chain classes. This property is applied to nonparametric estimation in ergodic diffusion processes.     

A linear-time algorithm for classifying the states of a finite Markov chain

Classifying the states of a finite Markov chain requires the identification of all irreducible closed sets and the set of transient states. This paper presents an algorithm for identifying these states that executes in time O(MAX(|V|, |E|)) where number of states and |E| is the number of positive entries in the Markov matrix. The algorithm finds the closed strongly connected components of the transition graph using a depth-first search.     

The Central Limit Theorem for Markov Chains with General State Space

We consider a Markov chain with general state space and an embedded Markov chain sampled at the times of successive returns to a subsetA₀ of the state space.We assume that the latter chain is uniformly ergodic but the originalMarkov chain need not possess this property.We develop amodification of the spectralmethod and utilize it in proving the central limit theorem for theMarkov chain under consideration.     

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

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

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

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

Sample path optimality for a Markov optimization problem

We study a unichain Markov decision process i.e. a controlled Markov process whose state process under a stationary policy is an ergodic Markov chain. Here the state and action spaces are assumed to be either finite or countable. When the state process is uniformly ergodic and the immediate cost is bounded then a policy that minimizes the long-term expected average cost also has an nth stage sample path cost that with probability one is asymptotically less than the nth stage sample path cost under any other non-optimal stationary policy with a larger expected average cost. This is a strengthening in the Markov model case of the a.s. asymptotically optimal property frequently discussed in the literature.     

Asymptotic variance rate of the output of a transfer line with no buffer storage and cycle-dependent failures

In this study the variability properties of the output of transfer lines are investigated. The asymptotic variance rate of the output of an N-station synchronous transfer line with no interstation buffers and cycle-dependent failures is analytically determined. Unlike the other studies, the analytical method presented in this study yields a closed-form expression for the asymptotic variance rate of the output. The method is based on a general result derived for irreducible recurrent Markov chains. Namely, the limiting variance of the number of visits to a state of an irreducible recurrent Markov chain is obtained from the n-step transition probability function. Thus, the same method can be used in other applications where the limiting variance of the number of visits to a state of an irreducible recurrent Markov chain is of interest. Numerical results show that the asymptotic variance rate of the output does not monotonically increase as the number of stations in the transfer line increases. The asymptotic variance rate of the output may first increase and then decrease depending on the station parameters. This property of the production rate is investigated through numerical experiments and the results are presented.     

Waiting times of a finite-capacity multi-server model with non-preemptive priorities

We consider a non-preemptive head of the line multi-server priority model with finite capacity. The arrival processes of the different priority classes are independent Poisson processes. The service times are exponentially distributed and identical for the different priority classes. The model is described by a homogeneous continuous-time Markov chain. For the two-class model we derive an explicit representation of its steady-state distribution. Applying matrix-analytic methods we calculate the Laplace-Stieltjes Transform of the actual waiting time of each priority class of a p-class system.     

Symbolic representations of nonexpansive group automorphisms

Ifα is an irreducible nonexpansive ergodic automorphism of a compact abelian groupX (such as an irreducible nonhyperbolic ergodic toral automorphism), thenα has no finite or infinite state Markov partitions, and there are no nontrivial continuous embeddings of Markov shifts inX. In spite of this we are able to construct a symbolic spaceV and a class of shift-invariant probability measures onV each of which corresponds to anα-invariant probability measure onX. Moreover, everyα-invariant probability measure onX arises essentially in this way. The last part of the paper deals with the connection between the two-sided beta-shiftV _β arising from a Salem numberβ and the nonhyperbolic ergodic toral automorphismα arising from the companion matrix of the minimal polynomial ofβ, and establishes an entropy-preserving correspondence between a class of shift-invariant probability measures onV _β and certainα-invariant probability measures onX. This correspondence is much weaker than, but still quite closely modelled on, the connection between the two-sided beta-shifts defined by Pisot numbers and the corresponding hyperbolic ergodic toral automorphisms.     

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.     

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

The Generalized Entropy Ergodic Theorem for Nonhomogeneous Markov Chains

Let \((\xi _n)_{n=0}^\infty \) be a nonhomogeneous Markov chain taking values in a finite state-space \(\mathbf {X}=\{1,2,\ldots ,b\}\). In this paper, we will study the generalized entropy ergodic theorem with almost-everywhere and \(\mathcal {L}_1\) convergence for nonhomogeneous Markov chains; this generalizes the corresponding classical results for Markov chains.     

Random walks on the triangular prism and other vertex-transitive graphs

In this paper we consider Markov chains of the following type: the state space is the set of vertices of a connected, regular graph, and for each vertex transitions are to the adjacent vertices, which equal probabilities. The proof is given that the mean first-passage matrix F of such a Markov chain is symmetric, when the underlying graph is vertex-transitive. Hence, we can apply results from a previous paper, in which we investigated general, finite, ergodic Markov chains, with the property F= F^T.     

Graph-theoretic and algebraic characterizations of some Markov processes

An algebraic decidable condition for a stationary Markov chain to consist of a single ergodic set, and a graph-theoretic decidable condition for a stationary Markov chain to consist of a single ergodic noncyclic set are formulated. In the third part of the paper a graph-theoretic condition for a nonstationary Markov chain to have the weakly-ergodic property is given. The paper is based on part of the author’s work towards the D. Sc. degree.     

An Ergodic Decomposition Defined by Regular Jointly Measurable Markov Semigroups on Polish Spaces

For a regular jointly measurable Markov semigroup on the space of finite Borel measures on a Polish space we give a Yosida-type decomposition of the state space, which yields a parametrisation of the ergodic probability measures associated to this semigroup in terms of subsets of the state space. In this way we extend results by Costa and Dufour (J. Appl. Probab. 43:767?C781, 2006). As a consequence we obtain an integral decomposition of every invariant probability measure in terms of the ergodic probability measures. Our approach is completely centered around the reduction to and relationship with the case of a single regular Markov operator associated to the Markov semigroup, the resolvent operator, which enables us to fully exploit results in that situation (Worm and Hille in Ergod. Theory Dyn. Syst. 31(2):571?C597, 2011).