Computing the stationary distribution for infinite Markov chains

In a situation where the unique stationary distribution vector of an infinite irreducible positive-recurrent stochastic matrix P is not analytically determinable, numerical approximations are needed. This paper partially synthesizes and extends work on finite-vector approximative solutions obtained from nxn northwest corner truncations _(n)P of P, from the standpoints of (pointwise convergence) algorithms as n→∞, and the manner of their computer implementation with a view to numerical stability and conditioning. The problem for finite n is connected with that of finding the unique stationary distribution of the finite stochastic matrix _(n)P? obtained from _(n)P by augmenting a column.     

Convergence and stability of a stabilized finite volume method for the stationary Navier-Stokes equations

In this paper, a new stabilized finite volume method is studied and developed for the stationary Navier-Stokes equations. This method is based on a local Gauss integration technique and uses the lowest equal order finite element pair P ₁–P ₁ (linear functions). Stability and convergence of the optimal order in the H ¹-norm for velocity and the L ²-norm for pressure are obtained. A new duality for the Navier-Stokes equations is introduced to establish the convergence of the optimal order in the L ²-norm for velocity. Moreover, superconvergence between the conforming mixed finite element solution and the finite volume solution using the same finite element pair is derived. Numerical results are shown to support the developed convergence theory.     

A generalization of carries processes and Eulerian numbers

We study a generalization of Holteʼs amazing matrix, the transition probability matrix of the Markov chains of the ‘carries’ in a non-standard numeration system. The stationary distributions are explicitly described by the numbers which can be regarded as a generalization of the Eulerian numbers and the MacMahon numbers. We also show that similar properties hold even for the numeration systems with the negative bases.     

On the convergence of sequences of stationary jump Markov processes

This paper presents two main results: first, a Liapunov type criterion for the existence of a stationary probability distribution for a jump Markov process; second, a Liapunov type criterion for existence and tightness of stationary probability distributions for a sequence of jump Markov processes. If the corresponding semigroups T_N(t) converge, under suitable hypotheses on the limit semigroup, this last result yields the weak convergence of the sequence of stationary processes (T_N(t), π_N) to the stationary limit one.     

A matrix perturbation method for computing the steady-state probability distributions of probabilistic Boolean networks with gene perturbations

Modeling genetic regulatory interactions is an important issue in systems biology. Probabilistic Boolean networks (PBNs) have been proved to be a useful tool for the task. The steady-state probability distribution of a PBN gives important information about the captured genetic network. The computation of the steady-state probability distribution involves the construction of the transition probability matrix of the PBN. The size of the transition probability matrix is 2ⁿ×2ⁿ where n is the number of genes. Although given the number of genes and the perturbation probability in a perturbed PBN, the perturbation matrix is the same for different PBNs, the storage requirement for this matrix is huge if the number of genes is large. Thus an important issue is developing computational methods from the perturbation point of view. In this paper, we analyze and estimate the steady-state probability distribution of a PBN with gene perturbations. We first analyze the perturbation matrix. We then give a perturbation matrix analysis for the captured PBN problem and propose a method for computing the steady-state probability distribution. An approximation method with error analysis is then given for further reducing the computational complexity. Numerical experiments are given to demonstrate the efficiency of the proposed methods.     

The convergence of Cesaro averages for certain nonstationary Markov chains

If P is a stochastic matrix corresponding to a stationary, irreducible, positive persistent Markov chain of period d>1, the powers Pⁿ will not converge as n → ∞. However, the subsequences P^nd+k for k=0,1,...d-1, and hence Cesaro averages Σⁿ_k-1 P^k/n, will converge. In this paper we determine classes of nonstationary Markov chains for which the analogous subsequences and/or Cesaro averages converge and consider the rates of convergence. The results obtained are then applied to the analysis of expected average cost.     

Stable Stationary Harmonic Maps to Spheres

For k ≥ 3, we establish new estimate on Hausdorff dimensions of the singular set of stable-stationary harmonic maps to the sphere S^k. We show that the singular set of stable-stationary harmonic maps from B5 to 83 is the union of finitely many isolated singular points and finitely many HSlder continuous curves. We also discuss the minimization problem among continuous maps from B^n to S^2.     

Generalized inverses and their application to applied probability problems

The main aim of this paper is to examine the applicability of generalized inverses to a wide variety of problems in applied probability where a Markov chain is present either directly or indirectly through some form of imbedding. By characterizing all generalized inverses of I—P, where P is the transition matrix of a finite irreducible discrete time Markov chain, we are able to obtain general procedures for finding stationary distributions, moments of the first passage time distributions, and asymptotic forms for the moments of the occupation-time random variables. It is shown that all known explicit methods for examining these problems can be expressed in this generalized inverse framework. More generally, in the context of a Markov renewal process setting the aforementioned problems are also examined using generalized inverses of I—P. As a special case, Markov chains in continuous time are considered, and we show that the generalized inverse technique can be applied directly to the infinitesimal generator of the process, instead of to I—P, where P is the transition matrix of the discrete time jump Markov chain.     

Markov chain mixing time on cycles

Mixing time quantifies the convergence speed of a Markov chain to the stationary distribution. It is an important quantity related to the performance of MCMC sampling. It is known that the mixing time of a reversible chain can be significantly improved by lifting, resulting in an irreversible chain, while changing the topology of the chain. We supplement this result by showing that if the connectivity graph of a Markov chain is a cycle, then there is an Ω(n²) lower bound for the mixing time. This is the same order of magnitude that is known for reversible chains on the cycle.     

Asymptotic properties of digit sequences of random numbers

We consider several aspects of the relationship between a [0, 1]‐valued random variable X and the random sequence of digits given by its m‐ary expansion. We present results for three cases: (a) independent and identically distributed digit sequences; (b) random variables X with smooth densities; (c) stationary digit sequences. In the case of i.i.d. an integral limit thorem is proved which applies for example to relative frequencies, yielding asymptotic moment identities. We deal with occurrence probabilities of digit groups in the case that X has an analytic Lebesgue density. In the case of stationary digits we determine the distribution of X in terms of their transition functions. We study an associated [0, 1]‐valued Markov chain, in particular its ergodicity, and give conditions for the existence of stationary digit sequences with prespecified transition functions. It is shown that all probability measures induced on [0, 1] by such sequences are purely singular except for the uniform distribution. (© 2005 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Algebraic multigrid methods for Laplacians of graphs

Classical algebraic multigrid theory relies on the fact that the system matrix is positive definite. We extend this theory to cover the positive semidefinite case as well, by formulating semiconvergence results for these singular systems. For the class of irreducible diagonal dominant singular M-matrices we show that the requirements of the developed theory hold and that the coarse level systems are still of the same class, if the C/F-splitting is good enough. An important example for matrices that are irreducible diagonal dominant M-matrices are Laplacians of graphs. Recent shape optimizing methods for graph partitioning require to solve singular linear systems involving these Laplacians. We present convergence results as well as experimental results for numerous graphs arising from finite element discretizations with up to 10⁶ vertices.     

Geometric ergodicity of Harris recurrent Marcov chains with applications to renewal theory

Let (X_n) be a positive recurrent Harris chain on a general state space, with invariant probability measure π. We give necessary and sufficient conditions for the geometric convergence of λPⁿf towards its limit π(f), and show that when such convergence happens it is, in fact, uniform over f and in L¹(π)-norm. As a corollary we obtain that, when (Xn) is geometrically ergodic, ∝ π(dx)6Pⁿ(x,·)-π6 converges to zero geometrically fast. We also characterize the geometric ergodicity of (X_n) in terms of hitting time distributions. We show that here the so-called small sets act like individual points of a countable state space chain. We give a test function criterion for geometric ergodicity and apply it to random walks on the positive half line. We apply these results to non-singular renewal processes on [0,∞) providing a probabilistic approach to the exponencial convergence of renewal measures.     

Necessary and sufficient local convergence condition of one class of iterative aggregation–disaggregation methods

This paper concludes one part of the local convergence analysis of a certain class of iterative aggregation–disaggregation methods for computing a stationary probability distribution vector of an irreducible stochastic matrix B. We show that the local convergence of the algorithm is determined only by the sparsity pattern of the matrix and by the choice of the aggregation groups. We introduce the asymptotic convergence rates of the normalized components of approximations corresponding to particular aggregation groups and we also specify an upper bound on the rates. Copyright © 2008 John Wiley & Sons, Ltd.     

Stabilization of statistics in wave and Klein-Gordon equations with mixing. Scattering theory for infinite energy solutions

We consider wave and Klein-Gordon equations in the whole space ?ⁿ with arbitraryn≥2. We assume initial data to be homogeneous random functions in ?ⁿ with zero expectation and finite mean density of energy. Moreover, we assume initial data fit mixing condition of Ibragimov-Linnik type. We consider the distributions of the random solution at the moment of timet. The main results mean the convergence of this distribution to some Gaussian measure ast→∞. This is a central limit theorem for wave and Klein-Gordon equations. The limit Gaussian measures are invariant measures for equations considered. Corresponding stationary random solutions are ergodic and mixing in time. The results are inspired by mathematical problems of statistical physics.     

Central limit asymptotics for shifts of finite type

We study the rate of convergence and asymptotic expansions in the central limit theorem for the class of Hölder continuous functions on a shift of finite type endowed with a stationary equilibrium state. It is shown that the rate of convergence in the theorem isO(n ^?1/2) and when the function defines a non-lattice distribution an asymptotic expansion to the order ofo(n ^?1/2) is given. Higher-order expansions can be obtained for a subclass of functions. We also make a remark on the central limit theorem for (closed) orbital measures.     

Convergent nonnegative matrices and iterative methods for consistent linear systems

Summary In this paper we study linear stationary iterative methods with nonnegative iteration matrices for solving singular and consistent systems of linear equationsAx=b. The iteration matrices for the schemes are obtained via regular and weak regular splittings of the coefficients matrixA. In certain cases when only some necessary, but not sufficient, conditions for the convergence of the iterations schemes exist, we consider a transformation on the iteration matrices and obtain new iterative schemes which ensure convergence to a solution toAx=b. This transformation is parameter-dependent, and in the case where all the eigenvalues of the iteration matrix are real, we show how to choose this parameter so that the asymptotic convergence rate of the new schemes is optimal. Finally, some applications to the problem of computing the stationary distribution vector for a finite homogeneous ergodic Markov chain are discussed.Research sponsored in part by US Army Research Office     

Ratio limit theorems for branching Ornstein-Uhlenbeck processes

We prove ratio limit theorems for critical ano supercritical branching Ornstein-Uhlenbeck processes. A finite first moment of the offspring distribution {p_n} assures convergence in probability for supercritical processes and conditional convergence in probability for critical processes. If even Σp_nnlog⁺log⁺n< ∞, then almost sure convergence obtains in the supercritical case.     

Characteristic properties of equivalent structures in compositional models

Compositional model theory serves as an alternative approach to multidimensional probability distribution representation and processing. Every compositional model over a finite non-empty set of variables N is uniquely defined by its generating sequence - an ordered set of low-dimensional probability distributions. A generating sequence structure induces a system of conditional independence statements over N valid for every multidimensional distribution represented by a compositional model with this structure.The equivalence problem is how to characterise whether all independence statements induced by structure P are induced by a second structure P^′ and vice versa. This problem can be solved in several ways. A partial solution of the so-called direct characterisation of an equivalence problem is represented here. We deduce and describe three properties of equivalent structures necessary for equivalence of the respective structures. We call them characteristic properties of classes of equivalent structures.     

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.     

On the Solution to QBD Processes with Finite State Space

Abstract

In this article, we present a solution to a class of Quasi-Birth-and-Death processes with finite state space and show that the stationary probability vector has a matrix geometric representation. We show that such models have a level-dependent rate matrix. The corresponding rate matrix is given explicitly in terms of the model parameters. The resulting closed-form expression is proposed as a basis for efficient calculation of the stationary probabilities. The method proposed in this article can be applied to several queueing systems.