Search

We apply the method of differential inequalities for the computation of upper bounds for the rate of convergence to the limiting regime for one specific class of (in)homogeneous continuous-time Markov chains. Such an approach seems very general; the corresponding description and bounds were considered earlier for finite Markov chains with analytical in time intensity functions. Now we generalize this method to locally integrable intensity functions. Special attention is paid to the situation of a countable Markov chain. To obtain these estimates, we investigate the corresponding forward system of Kolmogorov differential equations as a differential equation in the space of sequences l1.

We study the limit behaviour of upper and lower bounds on expected time averages in imprecise Markov chains; a generalised type of Markov chain where the local dynamics, traditionally characterised by transition probabilities, are now represented by sets of 'plausible' transition probabilities. Our main result is a set of necessary and sufficient conditions under which these upper and lower bounds, called upper and lower expected time averages, will converge as time progresses towards infinity to limit values that do not depend on the process' initial state. Remarkably, our conditions are considerably weaker than those needed to establish similar results for so-called limit -- or steady state -- upper and lower expectations, which are often used to provide approximate information about the limit behaviour of time averages as well. We show that such an approximation is sub-optimal and that it can be significantly improved by directly using upper and lower expected time averages.

In this paper we present a method for the computation of convergence bounds for four classes of multiserver queueing systems, described by inhomogeneous Markov chains. Specifically, we consider an inhomogeneous M/M/S queueing system with possible state-dependent arrival and service intensities, and additionally possible batch arrivals and batch service. A unified approach based on a logarithmic norm of linear operators for obtaining sharp upper and lower bounds on the rate of convergence and corresponding sharp perturbation bounds is described. As a side effect, we show, by virtue of numerical examples, that the approach based on a logarithmic norm can also be used to approximate limiting characteristics (the idle probability and the mean number of customers in the system) of the systems considered with a given approximation error.

We investigate a class of exponentially weakly ergodic inhomogeneous birth and death processes. We consider special transformations of the reduced intensity matrix of the process and obtain uniform (in time) error bounds of truncations. Our approach also guarantees that we can find limiting characteristics approximately with an arbitrarily fixed error. As an example, we obtain the respective bounds of the truncation error for an Mt/Mt/S queue for any number of servers S. Arbitrary intensity functions instead of periodic ones can be considered in the same manner.

We consider a multi-component system in which each component (node) can send/receive information to/from sets of neighboring nodes via communication links (edges) that form a fixed strongly connected, possibly directed, communication topology (digraph). We analyze a class of distributed iterative algorithms that allow the nodes to asymptotically compute the exact average of their initial values, despite a variety of challenging scenarios, including possible packet drops in the communication links, and imprecise knowledge of the network. The algorithms in this class run the two linear iterations of the so-called ratio-consensus algorithm, modified so that messages sent by one node to another are encoded as running sums. This 'convolutional' encoding allows the receiving node l to infer information about past messages that node j meant to send to node l but may have been lost due to packet drops. Imprecise knowledge of the network (unknown out-neighborhoods) can be handled, at the cost of memory and communication overhead, by also having each node track the progress of running sums of other nodes, and forward to its out-neighboring nodes the updated value of one such running sum that it randomly selects. Our analysis relies on augmenting the digraph that describes the communication topology by introducing additional (virtual) nodes, and showing that the dynamics of each of the two iterations in the augmented digraph is mathematically equivalent to a finite inhomogeneous Markov chain. Almost sure convergence to exact average consensus is then established via weak ergodicity analysis of the resulting inhomogeneous Markov chain. © 2015 IEEE. 61 6 1492 1507

Let X ( t ) be a nonhomogeneous continuous-time Markov chain. Suppose that the intensity matrices of X ( t ) and some weakly or strongly ergodic Markov chain X ( t ) are close. Some sufficient conditions for weak and strong ergodicity of X ( t ) are given and estimates of the rate of convergence are proved. Queue-length for a birth and death process in the case of asymptotically proportional intensities is considered as an example.

We consider a discrete time hidden Markov model where the signal is a stationary Markov chain. When conditioned on the observations, the signal is a Markov chain in a random environment under the conditional measure. It is shown that this conditional signal is weakly ergodic when the signal is ergodic and the observations are nondegenerate. This permits a delicate exchange of the intersection and supremum of $\sigma$-fields, which is key for the stability of the nonlinear filter and partially resolves a long-standing gap in the proof of a result of Kunita [J. Multivariate Anal. 1 (1971) 365--393]. A similar result is obtained also in the continuous time setting. The proofs are based on an ergodic theorem for Markov chains in random environments in a general state space., Comment: Published in at http://dx.doi.org/10.1214/08-AOP448 the Annals of Probability (http://www.imstat.org/aop/) by the Institute of Mathematical Statistics (http://www.imstat.org)

A representation for products of finite nonnegative matrices is given in terms of products of stochastic matrices and as a result Markov chain arguments are used to derive ratio limit properties. In particular, we obtain necessary and sufficient conditions for weak ergodicity and give a probabilistic proof of the Coale-Lopez theorem. In the general case, there are several sequences of sets of partitions of the state space corresponding to an associated nonhomogeneous Markov chain which lead to a number of ratio product limits. Asymptotic column proportionality, characteristic of weak ergodicity, may occur only inside each sequence of sets with one possible exception.

A new class of operators performing an optimization (optimization operators or, simply, optimators) which generate transition matrices with required properties such as ergodicity, recurrence etc., is considered and their fundamental features are described. Some criteria for comparing such operators by taking into account their strenght are given and sufficient conditions for both weak and strong ergodicity are derived. The nearest Markovian model with respect to a given set of observed probability vectors is then defined as a sequence of transition matrices satisfying certain constraints that express our prior knowledge about the system. Finally, sufficient conditions for the existence of such a model are given and the related algorithm is illustrated by an example.

Coupling methods are used to obtain a structure theorem for the atomic decomposition of the tail $\sigma$-algebra of an arbitrary nonhomogeneous Markov chain. Various related results are also derived by coupling.