Search

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 first main result is a necessary and sufficient condition 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. Our condition is considerably weaker than that needed for ergodic behaviour; a similar notion which demands that marginal upper and lower expectations of functions at a single time instant converge to so-called limit—or steady state—upper and lower expectations. For this reason, we refer to our notion as 'weak ergodicity'. Our second main result shows that, as far as this weakly ergodic behaviour is concerned, one should not worry about which type of independence assumption to adopt—epistemic irrelevance, complete independence or repetition independence. The characterisation of weak ergodicity as well as the limit values of upper and lower expected time averages do not depend on such a choice. Notably, this type of robustness is not exhibited by the notion of ergodicity and the related inferences of limit upper and lower expectations. Finally, though limit upper and lower expectations are often used to provide approximate information about the limit behaviour of time averages, 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. [ABSTRACT FROM AUTHOR]

We address the long-standing problem of state classification and multiclass optimization of the time-nonhomogeneous continuous-time and continuous-state Markov processes (CTCSMPs). The fundamental property required for state classification is weak ergodicity, with which the state space can be grouped into multiple classes of weak ergodic and branching states. The fundamental property for performance optimization is the state comparability. Optimality conditions are derived for long-run average problems for multiclass CTCSMPs; they take the same form as those for discrete-state Markov processes. It is shown that a stochastic diffusion process is separated by degenerate points into multiple classes. The results also cover the underselectivity issue for long-run average and optimization with nonsmooth value functions. The problem is solved by the relative optimization approach that has been successfully applied to many optimization problems that are not very amenable to dynamic programming. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM PUBLISHER]

Abstract: General nonstationary birth–death process with possible catastrophes on finite state space is studied. The approach for obtaining the bounds on the rates of convergence to the limiting characteristics is outlined. Method for construction of the limiting characteristics is proposed. We also show that, as a rule, the initial conditions quickly become irrelevant. An example of respective process is shown in details. [Copyright &y& Elsevier]

We consider the consensus problem for stochastic discrete-time linear dynamical systems. The underlying graph of such systems at a given time instance is derived from a random graph process, independent of other time instances. For such a framework, we present a necessary and sufficient condition for almost sure asymptotic consensus using simple ergodicity and probabilistic arguments. This easily verifiable condition uses the spectrum of the average weight matrix. Finally, we investigate a special case for which the linear dynamical system converges to a fixed vector with probability 1. [ABSTRACT FROM AUTHOR]