{'fraction_non_alphanumeric': 0.05591604582231835, 'fraction_numerical': 0.009512937595129375, 'mean_word_length': 4.104058059899827, 'pattern_counts': {'":': 0, '<': 6, '<?xml version=': 0, '>': 12, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 12, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Gossip and Distributed Kalman Filtering: Weak Consensus under Weak Detectability

The paper presents the gossip interactive Kalman filter (GIKF) for distributed Kalman filtering for networked systems and sensor networks, where inter-sensor communication and observations occur at the same time-scale. The communication among sensors is random; each sensor occasionally exchanges its filtering state information with a neighbor depending on the availability of the appropriate network link. We show that under a weak distributed detectability condition: 1. the GIKF error process remains stochastically bounded, irrespective of the instability properties of the random process dynamics; and 2. the network achieves \emph{weak consensus}, i.e., the conditional estimation error covariance at a (uniformly) randomly selected sensor converges in distribution to a unique invariant measure on the space of positive semi-definite matrices (independent of the initial state.) To prove these results, we interpret the filtered states (estimates and error covariances) at each node in the GIKF as stochastic particles with local interactions. We analyze the asymptotic properties of the error process by studying as a random dynamical system the associated switched (random) Riccati equation, the switching being dictated by a non-stationary Markov chain on the network graph.


A. Background and Motivation
This paper presents the Gossip Interactive Kalman Filtering (GIKF). GIKF is a linear distributed estimator that filters noisy observations of a random process measured by a sparsely connected sensor network. Each sensor observes only a portion of the process, such that, acting alone, no sensor can resolve the signal. GIKF is fundamentally different from other distributed implementations of the Kalman filter ( [1], [2], [3], [4]) that employ some form of linear consensus on the sensor observations or estimates; in contrast, GIKF involves communication and observation sampling at the same time scale. GIKF runs at each sensor a local copy of the Kalman filter and achieves collaboration through occasional asynchronous state swaps between sensors at random time instants. At the random times when a sensor communicates with one of its randomly selected neighbors, the sensor swaps its previous state (its local Kalman filter state estimate and conditional error covariance) with the state of its neighbor, before processing the current observation. In other words, when communication is established, a sensor updates the state it receives from its neighbor with its present observation; otherwise, it updates its own previous state.
Such collaboration or information exchange through state swapping is asynchronous over the network and occurs occasionally, dictated by the random network topology. Indeed, due to inherent environmental randomness, the underlying medium access control (MAC) protocol is randomized and often not known at the local sensor level. We assume that the sensor network uses a generic random communication protocol, see Section II, that subsumes the widely used gossiping protocol for real time embedded architectures, [5], and the graph matching based communication protocols for internet architectures, [6].
The paper establishes GIKF and studies its error properties. We define a weak distributed detectability condition 1 under which we show: 1) the GIKF error process remains stochastically bounded, irrespective of the instability properties of the random process dynamics; and 2) the network achieves weak consensus, i.e., the conditional estimation error covariance at a (uniformly) randomly selected sensor converges in distribution to a unique invariant measure on the space of positive semi-definite matrices (independent of the initial state.) To prove these results, we interpret the filtered states at each node in the GIKF as stochastic particles with local interactions and analyze the asymptotic properties of the error process by studying as a random dynamical system the switched (random) Riccati equation, the switching being dictated by a non-stationary Markov chain on the network graph.
To study the information flows in the GIKF, we interpret the filtering states at each node as stochastic particles with controlled interactions. To prove the stochastic boundedness of the error process and the network weak consensus, we focus on these traveling states, which we refer to as tokens or particles, and not on the sequence of conditional error covariances at each sensor, which is not Markov. This particle point of view is reminiscent of the approach taken in fluid dynamics of studying the transport of a particle as it travels in the fluid (Lagrangian coordinates) rather than studying the transport at a fixed coordinate in space (Eulerian coordinates), [7]. We show that the sequence of traveling states or particles evolves according to a switched system of random Riccati operators, the switching being dictated by a non-stationary Markov chain on the graph. A key contribution is the analysis of the resulting random Riccati equation (RRE). In this context, we note that the RRE arises in the literature in several practical filtering and control formulations with non-classical information. Prior work ( [8], [9], [10], [11], [12], [13], [14], [15], [16], [17], [18]) mostly address qualitative properties of the RRE in terms of moment stability, whereas recent approaches focus on understanding the limit behavior in terms of weak convergence ( [19], [20], [21], [22], see also [23]). In this paper, we utilize a random dynamical systems formulation of the RRE; however, in contrast with our work in [19], [20], the switching sequence is no longer stationary.
Several approximation arguments of independent interest are developed to tackle this non-stationary behavior and to establish the asymptotic distributional properties of the RRE.
To summarize, the paper addresses two fundamental concerns in collaborative estimation in random environments. It introduces distributed observability for linear dynamical estimation and addresses the question of minimal observation pattern (i.e., what should be the minimal number of sensors and what should they observe,) so that there exists a successful filtering scheme. The weak detectability condition (introduced in Section II-A) resolves this question through the existence of a full rank network Grammian.
We show that satisfaction of the weak detectability condition leads to stochastic boundedness of the conditional filtering error at each sensor, irrespective of observability of individual sensors. The second concern addressed in the paper is that of robust information flow, which seeks to address the minimal communication required to maintain consistent (asymptotically) information dissemination in the network.
The weak connectedness assumption formulated in Section II-A quantifies the rate of information flow (in random communication environments) as the mixing time of a particle undergoing a random walk in the network with appropriate statistics. The positive recurrence of this Markov chain translates to information dissemination at a sufficient rate to cope with the (possible) instability in signal dynamics and leads to weak consensus of the filtering errors. The notion of weak consensus introduced in the paper is the best form of consensus possible in such a setup because, as opposed to familiar scenarios (average computation/static parameter estimation,) in a dynamic situation it is not possible to accomplish almost sure (pathwise) consensus of the estimate or error processes. On the contrary, the weak consensus we establish shows that the error processes at different sensors converge in distribution to the same invariant measure. We do not characterize here this invariant measure as a function of the communication and observation policies; instead, we resolve the minimal conditions for the existence of such an invariant measure and hence conditions for the stability of the filtering error processes.
We briefly summarize the organization of the rest of the paper. Subsection I-B sets up notation and background material to be used in the paper. Section II sets-up the problem and introduces the GIKF algorithm together with the observability and connectivity assumptions in Subsection II-A. An interactive particle interpretation and important preliminary results are in Subsection II-B. The main results regarding April 5, 2010 DRAFT the asymptotic properties of the GIKF are stated (without proof) and interpreted in Section III. To prove these results, we provide first in Section IV a random dynamic system (RDS) formulation of the switching iterates of the random Riccati equation arising in the GIKF. Appendix A recalls facts and results on random dynamical systems (RDS) needed in this Section. The main results of the paper are proved in Section VI. Two technical Lemmas are proven in Appendix B. Finally, Section VII concludes the paper.

B. Notation and Preliminaries
Let R be the reals; R M , the M -dimensional Euclidean space; T, the integers; T + , the non-negative integers; N, the natural numbers; and X , a generic space. For B ⊂ X , I B : X −→ {0, 1} is the indicator function, i.e., 1 when its argument is in B and zero otherwise; and id X is the identity function on X .
Cones in partially ordered Banach spaces. We summarize facts and definitions on the structure of cones in partially ordered Banach spaces. Let V be a Banach space (over the field of the reals) with a closed (w.r.t. the Banach space norm) convex cone V + and assume We focus on the separable Banach space of symmetric n × n matrices, S n , equipped with the induced 2-norm. The subset S N + of positive semidefinite matrices is a closed, convex, solid, normal, minihedral cone in S n , with non-empty interior S N ++ , the set of positive definite matrices. The conventions above denote the partial and strong ordering in S n induced by S N + . Probability measures on metric spaces: Let: (X , d X ) a complete separable metric space X with metric d X ; B(X ) its Borel algebra; B(X ) the Banach space of real-valued bounded functions on X , equipped with the sup-norm, i.e., f ∈ B(X ), f = sup x∈X |f (x)|; and C b (X ) the subspace of B(X ) of continuous functions. For x ∈ X , the open ball of radius ε > 0 centered at x is denoted by B ε (x), i.e., B ε (x) = {y ∈ X | d X (y, x) < ε}. For any set Γ ⊂ X , the open ε-neighborhood of Γ is given by Let P(X ) be the set of probability measures on X . A sequence {µ t } t∈T+ of probability measures in P(X ) converges weakly to µ ∈ P(X ) if lim t→∞ < f, µ t > = < f, µ >, ∀ f ∈ C b (X ). By Portmanteau's theorem, the above is equivalent to any one of the following: Weak convergence is denoted by µ t =⇒ µ and is also referred to as convergence in distribution. The weak topology on P(X ) generated by weak convergence can be metrized. In particular, e.g., [24], one has the Prohorov metric d p on P(X ), such that the metric space (P(X ), d p ) is complete, separable, and a sequence {µ t } t∈T+ in P(X ) converges weakly to µ in P(X ) iff lim t→∞ d p (µ t , µ) = 0. The distance between two probability measures µ 1 , µ 2 in P(X ) is computed as:

A. Problem setup
Signal/Observation Model We consider a discrete-time linear dynamical system observed by a network of N sensors. The signal model is: where x t ∈ R M is the signal (state) vector with initial state x 0 distributed as a zero mean Gaussian vector with covariance P 0 and the system noise {w t } is an uncorrelated zero mean Gaussian sequence independent of x 0 with covariance Q. The observation at the n-th sensor y n t ∈ R mn at time t is: where C n ∈ R mn×M and {v n t } is an uncorrelated zero mean Gaussian observation noise sequence with covariance R n ≫ 0. Also, the noise sequences at different sensors are independent of each other, the system noise process and the initial system state. Because of the limited capability of the sensors, typically the dimension of y n t is much smaller than that of the signal process and the observation process at each sensor is not sufficient to make the pair {x t , y n t } observable 2 . We envision a totally distributed application where a reliable estimate of the signal process is required at each sensor. 3 The sensors achieve collaboration with each other by means of occasional communication with their neighbors, whereby they exchange their filtering states (to be defined precisely.) We assume that time is slotted and inter-sensor communication and sensing (observation) take place at the same time-scale.

Communication Model
Communication among sensors is constrained by several factors including proximity, transmit power, and receiving capabilities. We model the underlying communication structure of the network in terms of an undirected graph (V, E) where V denotes the set of N sensors and E is the set of edges or allowable communication links between the sensors. The notation n ∼ l indicates that sensors n and l can communicate, i.e., E contains the undirected edge (n, l). The graph can be represented in terms of its N × N symmetric adjacency matrix A: We assume that the diagonal elements of A are identically 1, indicating that a sensor n can always communicate to itself. Note, that E is the maximal allowable set of links in the network at any time, however, at a particular instant, each sensor may choose to communicate only to a fraction of its neighbors.
The exact communication protocol is not so important for the analysis, as long as some weak connectivity assumptions are satisfied. For definiteness, we assume the following generic communication model, which subsumes the widely used gossiping protocol for real time embedded architectures ( [5]) and the graph matching based communication protocols for internet architectures ( [6]. ) We make this precise in the following, which we generalize later. Define the set M of symmetric 0-1 N × N matrices: In other words, M is the set of adjacency matrices, such that, every node is incident to exactly one edge (including self edges) and allowable edges are only those included in E. 4 Let D be a probability distribution on the space M. The sequence of time-varying adjacency matrices, {A(t)} t∈N , governing the inter-sensor communication, is then an i.i.d. sequence in M with distribution D and independent of the signal and observation processes. 5 We make the following assumption of connectivity on the average: Assumption C.1: Define the symmetric stochastic matrix A as The matrix A is assumed to be irreducible and aperiodic.

Remark 1
The stochasticity of A is inherited from that of the elements of M. We are not concerned with the properties of the distribution D as long as the weak connectivity assumption above is satisfied. The issue of A being irreducible depends both on the set of allowable edges E and the distribution D. We do not pursue that question in detail here. However, to show the applicability of Assumption C.1 and justify the notion of weak connectivity, we note that such a distribution D always exists if the graph (V, E) is connected. We give a Markov chain interpretation of the mean adjacency matrix A, which will be helpful for the analysis to follow. The matrix A can be associated to the transition kernel of a time-homogeneous Markov chain on the state space V . Since the state space V is finite, the irreducibility of A suggests that the resulting Markov chain is positive recurrent. Due to symmetricity, the Markov chain is reversible with unique invariant distribution π on V , where π is the discrete uniform distribution on V . 4 The set M is always non-empty, in particular the N × N identity matrix IN ∈ M. For distributed detectability, we assume the following: Weak Detectability: Assumption D.1 There exists a walk 6 of length ℓ ≥ 1, (n 1 , n 2 , · · · , n ℓ ), covering the N nodes, such that, the matrix Remark 2 Note, as permitted by the general definition of a walk, the sequence (n 1 , n 2 , · · · , n ℓ ) may consist of repeated vertices and, in particular, self-loops (if permitted by A.)

Remark 3
When F is invertible, D.1 may be replaced by the full rank of Indeed, by the irreducibility of A (equivalently, by the connectivity of the graph induced by A,) we can find a walk (n 1 , n 2 , · · · , n ℓ ) of length ℓ ≥ N , which covers the network, i.e., visits each node at least once. Hence, if F is invertible and (7) holds, it follows that the matrix ℓ i=1 F i−1 T C T ni C ni F i−1 corresponding to this walk is invertible leading to Assumption D.1.

Remark 4
From the positive definiteness of the measurement noise matrices R n , it follows that under D.1, Remark 5 Assumption D.1 is minimal, in the sense, that, even in a centralized setting (a center has access to all the sensor observations over all time,) it is required to ensure detectability for arbitrary choice of the matrix F governing the signal dynamics. This justifies the nomenclature weak detectability.
Algorithm GIKF We now present the algorithm GIKF (gossip based interacting Kalman filter) for distributed estimation of the signal process x t over time. We start by introducing notation. Let the filter at sensor n be initialized with the pair x 0|−1 , P 0 , where x 0|−1 denotes the prior estimate of x 0 (with no observation information) and P 0 the corresponding error covariance. Also, by ( x n t|t−1 , P n t ) denote the estimate at sensor n of x t based on information 7 till time t − 1 and the corresponding conditional error covariance, respectively. The pair x n t|t−1 , P n t is also referred to as the state of sensor n at time t − 1. To define the estimate update rule for the GIKF, let → (n, t) be the neighbor of sensor n at time t 6 A walk in this context is defined w.r.t. the graph induced by the non-zero entries of the matrix A. 7 The information at sensor n till (and including) time t corresponds to the sequence of observations {y n s } 0≤s≤t obtained at the sensor and the information received by data exchange between its neighboring senors. w.r.t. the adjacency matrix 8 A(t). We assume that all inter-sensor communication for time t occurs at the beginning of the slot, whereby communicating sensors swap their previous states, i.e., if at time t, → (n, t) = l, sensor n replaces its previous state x n t|t−1 , P n t by x l t|t−1 , P l t and sensor l replaces its previous state x l t|t−1 , P l t by x n t|t−1 , P n t . The estimate update at sensor n at the end of the slot (after the communication and observation tasks have been completed) is: , y n t (9) Due to conditional Gaussianity, the filtering steps above can be implemented through the time-varying Kalman filter recursions, and it follows that the sequence P n t of conditional predicted error covariance matrices at sensor n satisfies the Riccati recursion: Note that the sequence P n t is random, due to the random neighborhood selection function → (n, t).
The goal of the paper is to study asymptotic properties of the sequence of random conditional error covariance matrices P n t at every sensor n and show in what sense they reach consensus, so that, in the limit of large time, every sensor provides an equally good (stable in the sense of estimation error) estimate of the signal process.

B. An Interacting Particle Representation
To compactify the notation in eqn. (10), we define the functions f n : S N + −→ S N + for n = 1, · · · , N defining the respective Riccati operators 9 : Recall the sequence {→ (n, t)} t∈T+ of neighborhoods of sensor n. The sequence of conditional error covariance matrices {P n t } t∈T+ at sensor n then evolves according to The sequence P n t is non-Markov (not even semi-Markov given the random adjacency matrix sequence {A(t)},) as P n t+1 at time t is a random functional of the conditional error covariance at time t − 1 of the sensor → (n, t), which, in general, is different from sensor n. This makes the evolution of the sequence P n t difficult to track. To overcome this, we give the following interacting particle interpretation of the conditional error covariance evolution, which naturally leads us to track semi-Markov sequences of conditional error covariance matrices from which we can completely characterize the evolution of the desired covariance sequences P n t for n = 1, · · · , N .
To this end, we note that the link formation process given by the sequence {A(t)} can be represented in terms of N particles moving on the graph as identical Markov chains. The state of the n-th particle is denoted by p n (t), and the sequence {p n (t)} t∈T+ takes values in [1, · · · , N ]. The evolution of the n-th particle is given as follows: Recall the (random) neighborhood selection → (n, t). Thus, the n-th particle can be viewed as originating from node n at time 0 and then traveling on the graph (possibly changing its location at each time) according to the link formation process {A(t)}. The following proposition establishes important statistical properties of the sequence {p n (t)} t∈T+ :

Proposition 6
[i] For each n, the process {p n (t)} t∈T+ is a Markov chain on V = [1, · · · , N ] with transition probability matrix A.
[ii] The Markov chain {p n (t)} t∈T+ is ergodic with the uniform distribution on V being the attracting invariant measure.
Proof: For part [i], we note that, by the independence of {A(t)}, for any t ∈ T + and l t , · · · , l 0 ∈ V , where the last step follows from the fact, that the entries of A(t − 1) are binary. This establishes the desired Markovianity of the sequence {p n (t)} t∈T+ .
For part [ii], since the state space V is finite, the irreducibility of A implies its positive recurrence and hence the invariant measure (the uniform distribution on V ) is unique. That this measure is attracting follows from the aperiodicity of A.
For each of the Markov chains {p n (t)} t∈T+ , we define a sequence of switched Riccati iterates {P n (t)}: The sequence {P n (t)} t∈T+ can be viewed as an iterated system of Riccati maps, the random switching sequence being governed by the Markov chain {p n (t)} t∈T+ . A more intuitive explanation comes from the particle interpretation, precisely the n-th sequence may be viewed as a particle originating at node n and hopping around the network as a Markov chain with transition probability A whose instantaneous April 5, 2010 DRAFT state P n (t) evolves by the application of the Riccati operator corresponding to its current location. In particular, in contrary to the sequence of conditional error covariances at sensor n, P n (t) t∈T+ , the sequence {P n (t)} t∈T+ does not correspond to the error evolution at a particular sensor. The following proposition shows that the sequence {P n (t)} t∈T+ is semi-Markov and establishes its relation to the sequence P n (t) t∈T+ of interest.

Proposition 7
[i] The sequence {P n (t)} t∈T+ is semi-Markov, given the Markov switching sequence, i.e., [ii] Consider the sequence of random permutations {π t } t∈T+ on V , given by with initial condition (Note that π t (n) = p n (t) for every n, where p n (t) is defined in eqn. (13).) Then, for t ∈ T + , Part [ii] of the above proposition suggests that the asymptotics of the desired sequence P n (t) t∈T+ for every n can be obtained by studying the same for the sequences {P n (t)} t∈T+ . Also, part [i] of Proposition 7 demonstrates the nice structure of the sequence {P n (t)} t∈T+ . In the following, in particular, we will show that the sequences {P n (t)} t∈T+ reach consensus in a weak sense, which by part [ii] will establish weak consensus for the sequences P n (t) t∈T+ of interest. Hence, in the subsequent sections, we will study the sequences {P n (t)} t∈T+ , rather than working directly on the sequences P n (t) t∈T+ of interest, which involve a much more complicated statistical dependence.

III. MAIN RESULTS
In this section, we present and discuss the main results of the paper under Assumptions C.1, S.1, D.1, see page 7. The first result does not directly concern the sequences P n (t) for n = 1, · · · , N , but sets the stage for presenting the key result regarding the convergence of these sequences and is of independent interest.
Theorem 8 For a given A, let { p(t)} t∈T+ be a stationary Markov chain on V with transition probability matrix A, i.e., p(0) is distributed uniformly on V . Let ν be a probability measure on S N + and consider the random process P (t) t∈T+ given by where P (0) is distributed as ν and independent of the Markov chain { p(t)}. Then, there exists a probability measure (unique) µ A (depending on A only,) such that, for every ν, the process P (t) constructed above converges weakly to µ A . In other words, for any ν if P (0) ∼ ν and independent of { p(t)}, we have as t → ∞ that the composition of Riccati operators converges in distribution Remark 9 We stress here that the dependence of the invariant measure µ A on the communication policy D manifests only through the mean matrix A.
We now state the key result characterizing the convergence properties of the sequences P n (t) .
Theorem 10 [i] Let q be a uniformly distributed random variable on V and independent of the sequence of adjacency matrices {A(t)} t∈T+ . Then, the sequence P q (t) t∈T+ converges weakly to µ A (the latter being defined in Theorem 8), i.e., In other words, the conditional error covariance P q (t) of any randomly selected sensor (estimator) is stochastically dominated by the distribution µ A as t → ∞, i.e., for every α > 0, we have More generally, for a closed set F preserving monotonicity, i.e., In words, ∀n, the pathwise error associated with x πt(n) (t) is stochastically dominated by µ A .
[iii] For each n, the sequence of error covariances P n (t) Specifically, for all closed F , we have We discuss the consequences of Theorem 10. The first part of the theorem reinforces the weak consensus achieved by the GIKF algorithm, i.e., the conditional error covariance at a randomly selected sensor converges in distribution to the invariant measure µ A . Reinterpreted, it provides an estimate { x q (t)} (in practice, obtained by uniformly selecting a sensor q independent of the random gossip protocol {A(t)} and using its estimate x q (t) for all time t) with stochastically bounded conditional error covariance under the weak detectability and connectivity assumptions. Note that the results provided in this paper pertain to the limiting distribution of the conditional error covariance and, hence, the pathwise filtering error. This is a much stronger result than providing moment estimates of the conditional error covariance, which does not provide much insight into the pathwise instantiations of the filter. In this paper, we do not provide analytic characterizations of the resulting invariant measure µ A . However, Theorem 8 also provides an efficient numerical characterization of µ A . In particular, the weak convergence in eqn. (21) shows that the empirical distribution obtained by plotting repeated instantiations of the process P (t) (eqn. (20)) would converge to µ A .
Another class of estimates obtained by the GIKF algorithm is demonstrated in the second part of Theorem 10. For each n, the estimate x πt(n) (t) is obtained in practice by starting at the node n and then performing a random walk, π t (n), through the graph and collecting the estimates on the way.
Eqns. (23)(24)(25) show that, in the limit as t → ∞, these estimates are at least as good as the estimate { x q (t)} obtained by probing a randomly selected node and using its estimate throughout. For some n, whether the estimate x πt(n) (t) is strictly better than the estimate { x q (t)} asymptotically is an interesting technical question and not resolved in this paper. On the contrary, another possibility may be an extension of eqn. (25) to all closed F leading to the weak convergence of P πt(n) (t) to µ A by Portmanteau's theorem. However, the inequality in eqn. (25) cannot be strict for all n, as we have for all closed F and ε > 0 (see Subsection VI-B,) The last part of Theorem 10 shows that weak detectability (which is necessary for the error of a consider an auxiliary process P (t) whose evolution is governed by similar random Riccati iterates, the difference being that the switching Markov chain is stationary i.e., the switching Markov chain { p(t)} is initialized with the uniform invariant measure on V . We analyze the asymptotic properties of April 5, 2010 DRAFT the auxiliary sequence P (t) by formulating it as a RDS on the space S N + and then in subsequent sections we derive the asymptotics of the sequences {P n (t)} for n = 1, · · · , N through comparison arguments. We start by formally defining the sequence P (t) 10 : Consider a Markov chain on the graph V , { p(t)} t∈T+ , with transition matrix A and uniform initial distribution, i.e., By Proposition 6, the Markov chain { p(t)} is stationary.
We now define the auxiliary process P (t) as follows: with (possibly random) initial condition P (0). 11 Before reading the next two Sections, we refer the reader to Appendix A where we review preliminary facts and results from the theory of monotone, sublinear random dynamical systems (RDS) ( [27]) tailored to our needs. We then show in Subsection IV-A that the sequence P (t) , for each n, admits an ergodic RDS formulation evolving on S N + and establish some of its properties in Subsection IV-B.

A. RDS formulation of P (t)
In this subsection, we construct a RDS (θ R , ϕ R ) on S N + , which is equivalent to the auxiliary sequence P (t) in distribution. To this end, we construct the Markov chain { p(t)} (in a distributional sense) on the canonical path space. Let Ω denote the set {1, · · · , N } with F denoting the corresponding Borel algebra on Ω, which coincides with the power set of {1, · · · , N }. Denote by Ω R the two-sided infinite product of sets Ω, Ω R = ∞ t=−∞ Ω, i.e., Ω R is the space of double-sided sequences of entries in {1, · · · , N }, i.e., We equip Ω R with the corresponding product Borel algebra F R = ∞ t=−∞ F generated by the cylinder sets. Note that {ω t } t∈T+ for all ω ∈ Ω R denotes the canonical path space (trajectory) of the Markov chain { p(t)} t∈T+ . The reason for introducing two-sided sequences is a matter of technical convenience and will be evident soon. Consider the unique probability measure P R on F R , under which the stochastic process (two-sided) {ω t } t∈T is a stationary Markov chain on the finite state space {1, · · · , N } with transition probability matrix A. By the assumption of stationarity and Proposition 6, the distribution of ω t for each t ∈ T is necessarily the uniform distribution on {1, · · · , N }. In particular, we note that the stochastic 10 We are interested in the distributional properties of the various processes of concern. The actual pathwise construction is not of importance as long as the required distributional equivalence holds. We assume that the measure space (Ω, F, P) is rich enough (or suitably extended) to carry out constructions of the various auxiliary random variables. 11 Although the sequences {Pn(t)} of interest have deterministic initial conditions, it is required for technical reasons (to be made precise later) to allow random initial states P (0), when studying the auxiliary sequence P (t) . processes { p(t)} t∈T and {ω t } t∈T are equivalent in terms of the distribution induced on path space. Define the family of transformations θ R t t∈T on Ω as the family of left-shifts, i.e, With this, the space Ω R , F R , P R , θ R t , t ∈ T becomes the canonical path space of a two-sided stationary sequence equipped with the left-shift operator and hence (see, for example, [28]) satisfies the Assumptions A.1)-A.3) in Definition 17 to be a metric dynamical system and, in fact, is also ergodic.
We now set to define the cocycle ϕ R , see also Definition 17, over S N + , which gives the RDS of interest. We define ϕ R : (Note that, by property of the left shift θ R , we have θ R t−1 ω(0) = ω t , which explains the equality in eqn. (36).) The cocycle ϕ R defined satisfies the assumptions of measurability jointly in its arguments, and the continuity of the map ϕ R (t, ω, ·) : S N + −→ S N + w.r.t. the phase variable X for each fixed t, ω follows from the continuity of the corresponding Riccati operator. The pair θ R , ϕ R thus forms a well-defined RDS on the phase space S N + . Now consider the sequence of random variables ϕ R (t, ω, P n (0)) t∈T+ (as explained earlier, the randomness is induced by ω,) which can be viewed as successive (random) iterates of the RDS θ R , ϕ R starting with the initial state P n (0). By construction, it follows that the sequence ϕ R (t, ω, P n (0)) t∈T+ is distributionally equivalent to the sequence P (t) t∈T+ . In particular, ϕ R (t, ω, P n (0)) d P (t), ∀t ∈ T + Thus, analyzing the asymptotic distributional properties of the sequence P (t) t∈T+ is equivalent to studying the sequence ϕ R (t, ω, P n (0)) t∈T+ , which we undertake in the next subsection.

B. Properties of the RDS (θ R , ϕ R )
We establish some basic properties of the RDS θ R , ϕ R representing the auxiliary sequence P (t) .
[ii] The RDS θ R , ϕ R is order preserving.
[iii] If in addition Q is positive definite, i.e., Q ≫ 0, then θ R , ϕ R is strongly sublinear. The strong sublinearity uses the concavity of the Riccati operators and their monotone nature and is a routine extension to an arbitrary number N of Riccati operators, given the development in [19] (see Lemma 21 in [19]) for the case of two Riccati operators.

V. ASYMPTOTICS OF P (t)
The main result here concerns the asymptotic properties of the auxiliary sequences P (t) t∈T+ for each n ∈ [1, · · · , N ]. We have the following: Theorem 12 Under the assumptions C.1,S.1,D.1, see page 7, there exists a unique equilibrium probability measure µ A on the space of positive semidefinite matrices S N + , such that, for each n ∈ [1, · · · , N ], the sequence P (t) t∈T+ converges weakly (in distribution) to µ A from every initial condition P n (0): The rest of the subsection is devoted to the proof of the above result. But, before that, we highlight some consequences of Theorem 12.

Remark 13
It is important to note, as stated in Theorem 12, that the equilibrium measure µ A does not depend on the index n and the initial state P (0) of the sequence P (t) , but is a functional of the network topology and the particular (randomized) communication protocol captured by the matrix A.
Theorem 12, thus concludes that the sequences P (t) reach consensus in the weak sense to the same equilibrium measure irrespective of the initial states.
The proof of Theorem 12 is rather long and technical, which we accomplish in steps.

Lemma 14
Recall Assumption D.1, page 7, and let, in particular, w 0 = (n 1 , · · · , n ℓ ) be a walk such that, the Grammian is invertible, where ℓ ≥ 1. Define the function g w0 : Then, there exists a constant α 0 > 0 such that the following uniformity condition holds: In other words the iterate g w0 (·) is uniformly bounded irrespective of the value of the argument.
We now complete the proof of Theorem 12.
From Lemma IV-A we note that θ R , ϕ R is strongly sublinear, conditionally compact and orderpreserving. Also, the cone S N + satisfies the conditions required in the hypothesis of Theorem 26. We note for t > 0 Thus the hypotheses of Theorem 26 are satisfied, and precisely one of the assertions a) and b) holds.
By an argument similar to Lemma 23 in [19], we can show that assertion a) cannot hold in the face of stochastic boundedness of the sequence P (t) t∈T+ (Lemma 15). Thus assertion b) holds, and, as a direct consequence of Theorem 26, we establish the existence of a unique almost equilibrium u A (ω) ≫ 0 defined on a θ R -invariant set Ω * ∈ F R with P (Ω * ) = 1 such that, for any random variable v(ω) possessing the property 0 v(ω) αu A (ω) for all ω ∈ Ω * and deterministic α > 0, the following holds: From the distributional equivalence of pull-back and forward orbits, Lemma 23 establishes the existence of a unique almost equilibrium u A , i.e., a unique equilibrium measure for the process P (t) from the distributional equivalence of pull-back and forward orbits. However, to show that the measure induced by u A on S N + is attracting for P (t) , eqn. (44) must hold for all initial v, whereas Lemma 23 establishes convergence for a restricted class of initial conditions v. We need the following result to extend it to general initial conditions.

Lemma 16
Under the assumptions of Theorem 12, let u A be the unique almost equilibrium of the RDS θ R , ϕ R . Then Proof: The proof uses the fact that, for all n, f n (X) Q, and is routine given the corresponding development in Lemma 24 of [19].
We now complete the proof of Theorem 12.
Proof of Theorem 12: : Let µ A be the distribution of the unique almost equilibrium in eqn. (44).

A. Proof of Theorem 8
Proof: By Theorem 12 we know that such a sequence P (t) converges weakly to µ A when started from a deterministic initial condition. In the case, P (0) is distributed as ν, we note that, by the independence of P (0) and the Markov chain {q(t)}, for any g ∈ C b (S N + ). Now, the distribution of the sequence P (t) conditioned on the event P (0) = X is the same as that when the sequence starts with the deterministic initial condition X (this is true because for all X. Since g is bounded, the dominated convergence theorem and eqn. (57) lead to for all g ∈ C b (X), and hence the required weak convergence follows.
Consider any Γ ∈ B(S N + ). We estimate the probability P P q (t) ∈ Γ . To this end, we note that The first step holds because q is independent of the sequences P n (t) for all n and subsequently we use that q is uniformly distributed on V . Denoting by π −1 t the inverse of the permutation π t , we have Note, here, unlike in eqn. (60), we may not gain much by splitting the probabilities in the last step as the events {P l (t) ∈ Γ} and π −1 t (n) = l are not independent. Combining eqns. (60,61), we have Note the last step follows from the fact that because the events π −1 t (n) = l , n = 1, · · · , N are mutually exclusive and exhaustive, π −1 (t) being a permutation. Now consider a stationary Markov chain { p(t)} on V with transition probability A and let P (t) be the sequence defined by with initial condition P (0) = P (0). Then, By construction, the distribution of the sequence P (t) conditioned on the event { p(0) = l} is equivalent to that of the sequence {P l (t)} and hence Hence by eqns. (62,66) we obtain Thus, for all t, P q (t) d P (t). By Theorem 12, we then have the weak convergence of the sequence For the third part, we note that for any Γ ∈ B(S N + ) due to the independence of q from {A(t)}. Taking the lim sup and noting the non-negativity of the terms, we have for closed F , The proof of the second part involves an auxiliary construction and approximation arguments to relate the limit properties of the sequences {P n (t)} to similar processes, where the underlying switching Markov chain is stationary. To this end consider any strictly positive s ∈ T + . Recall the Markov chains {p n (t)} April 5, 2010 DRAFT for n = 1, · · · , N with transition probability matrix A and initial state p n (0) = n. The corresponding sequence of interacting particle processes {P n (t)} are constructed, for each n as: with initial condition P n (0) = P (0). Let f 0 : S N + −→ S N + denote the Lyapunov operator and note that the following ordering holds: For a given s > 0 chosen above and for all n, define the processes {P s n (t)} t≥s by P s n (t + 1) = f pn(t) (P s n (t)) (72) with deterministic initial value P s n (s) = f s 0 P (0) . By eqn. (71), for any s tuple (i 0 , i 1 , · · · , i s−1 ) with i r ∈ [1, · · · , N ] for r = 0, · · · , s − 1, we note that and, hence, by the monotonicity of the Riccati operators, we conclude that for all n P n (t) P s n (t), t ≥ s Also consider a stationary Markov chain {q(t)} t≥s with transition probability A, i.e., q(0) is uniformly distributed on V , and define the process {Q s (t)} t≥s by with deterministic initial value It is to be noted that by Theorem 12, the process {Q s (t)} converges weakly to µ A , i.e., where d P denotes the Prohorov metric. We now set to relate the limit properties of {P s n (t)} to those of {Q s (t)}. For t ≥ s define the total variation distance between P s n (t) and Q s (t) by d v (P s n (t), Q s (t)) = sup Since for any t, the two sequences considered above assume values in a finite set, we define a set of (t − s) tuples Λ(Γ) by Λ(Γ) = (i 1 , · · · , i t−s ) | i r ∈ [1, · · · , N ] for all r and f it−s • · · · • f i1 f s 0 ( P (0)) (79) It is clear that We then have and hence where we have used the fact that A irir+1 = P ((p n (s + 1), · · · , p n (t − 1)) = (i 2 , · · · , i t−s ) |p n (s) = i 1 ) ≤ 1 We thus obtain It is well known that the finite state Markov chain {p n (s)} converges weakly at a geometric rate to the uniform measure, i.e., the measure induced by q(s) for each s and hence in variation. In other words, and, since convergence in total variation implies weak convergence ( [29]), we have lim s→∞ sup t≥s d P (P n s (t), Q s (t)) = 0 (85) Now consider ε > 0. Then there exists s(ε), such that, Since the sequence {Q s (t)} converges weakly to µ A for all s (in particular for s = s(ε),) there exists t(ε) ≥ s(ε) sufficiently large, such that, Then, an application of the triangle inequality for the metric d P leads to for all t ≥ t(ε). Now, by definition, where F δ is defined as Since, by eqn. (88), d P P s(ε) n (t), µ A ≤ ε for all t ≥ t(ε), we have, for any closed set F , In addition to F being closed, let us assume that F satisfies monotonicity, i.e., X ∈ F implies Y ∈ F for all Y X. By eqn. (74) we have and hence We then have from eqn. (91) for all t ≥ t(ε) Taking the limit as t → ∞, we have The L.H.S. above is now independent of t and, hence, ε through t(ε). Since the above holds for arbitrary ε > 0, moving to the limit as ε → 0 yields The last step follows from the continuity of the probability measure µ A and the fact that for closed F . This establishes the result for general order preserving F . The result for sets of the form We start by defining a random dynamical system (RDS). In the sequel, we follow the notation in [30], [27].

Definition 17 (RDS)
A RDS with (one-sided) time T + and state space X is a pair (θ, ϕ) with the following properties: A) A metric dynamical system θ = (Ω, F , P, {θ t , t ∈ T}) with two-sided time T, i.e., a probability space (Ω, F , P) with a family of transformations {θ t : Ω −→ Ω} t∈T such that 3) θ t P = P ∀t ∈ T, i.e., P (θ t B) = P for all B ∈ F and all t ∈ T.

B)
A cocycle ϕ over θ of continuous mappings of X with time T + , i.e., a measurable mapping such that
Although we consider in this paper discrete time RDS, the general notion of RDS, as defined in [27], applies equally well to dynamical systems with continuous time. In the above definition, the randomness is captured by the probability space (Ω, F , P) and iterates indexed by ω indicates pathwise construction. For example, if X 0 is the deterministic initial state of the system of interest at time t = 0, the random state at time t ∈ T + is given by The measurability assumptions in the definition above, guarantee that the random state X t is a well-defined random variable. Also, note that the iterates are defined for non-negative (one-sided) time, however, the family of transformations {θ t } is two-sided, which is purely for technical convenience, as will be seen later. Some results from RDS theory We summarize terminology and notions used in the RDS literature (see [26], [27] for details.) Consider a generic RDS (θ, ϕ) with state space X as in Definition 17. In the following we assume that X is a non-empty subset of a real Banach space V with a closed, convex, solid, normal (w.r.t. the Banach space norm,) minihedral cone V + . We denote by the partial order induced by V + in X and << denotes the corresponding strong order. Although the development that follows may hold for arbitrary X ⊂ V , in the sequel we assume X = V + (which is true for the RDS θ R , ϕ R modeling the RARE.)
Since, the transformations {θ t } are measure-preserving, i.e., θ t P = P, ∀t, we have Thus eqn. (105), in particular, implies that, for an almost equilibrium u, the sequence of iterates {ϕ (t, ω, u(ω))} t∈T+ have the same distribution, which is the distribution of u.

Definition 21 (Part)
The equivalence classes in V + under the equivalence relation defined by X ∼ Y if there exists α 0 ≥ 1 such that α −1 0 X Y α 0 X are called parts of V + . We call the part C v generated by a random variable v : Ω −→ V + as the collection of random variables u : Ω −→ V + such that there exists deterministic α u ≥ 1 with Definition 22 (Orbit) For a random variable u : Ω −→ V + we define the forward orbit η f u (ω) emanating from u(ω) as the random set {ϕ (t, ω, u(ω))} t∈T+ . The forward orbit gives the sequence of iterates of the RDS starting at u.
Although η f u is the object of practical interest, for technical convenience (will be seen later,) we also define the pull-back orbit η b u (ω) emanating from u as the random set {ϕ (t, θ −t ω, u(θ −t ω))} t∈T+ .
The reason for defining the pull-back orbit is that it is comparatively convenient to establish asymptotic properties for η b u . However, analyzing η b u leads to understanding asymptotic distributional properties for η f u , because the random sequences {ϕ (t, ω, u(ω))} t∈T+ and {ϕ (t, θ −t ω, u(θ −t ω))} t∈T+ are equivalent in distribution. In other words, This follows from the fact that θ t P = P, ∀t ∈ T. Thus, in particular, we have the following assertion.
We now introduce notions of boundedness of RDS, which will be used in the sequel.
Definition 24 (Boundedness) Let a : Ω −→ V + be a random variable. The pull-back orbit η b a (ω) emanating from a is said to be bounded on U ∈ F is there exists a random variable C on U such that Definition 25 (Conditionally Compact RDS) An RDS (θ, ϕ) in V + is said to be conditionally compact if for any U ∈ F and pull-back orbit η b a (ω) which is bounded on U there exists a family of compact sets {K(ω)} ω∈U such that lim t→∞ dist (ϕ (t, θ −t ω, a (θ −t ω)) , K(ω)) = 0, ω ∈ U It is to be noted that conditionally compact is a topological property of the space V + . We now state a limit set dichotomy result for a class of sublinear, order-preserving RDS.

Proof of Lemma 14
The proof is obtained by constructing an approximate filter with suboptimal performance, and then bounding its error by using the rank condition on the Grammian G w0 . We detail such a construction now.
Consider ℓ steps t = 1, · · · , ℓ of the linear time-varying signal/observation model given by 2 and 3, where in 3 we index the observation matrix as C nt where n(t) indicates the current state of the walk w 0 . The signal vector x t ∈ R M with initial state x 1 is a Gaussian random variable with known mean x 1 and variance X ∈ S N + . The system noise process {w t } is uncorrelated zero mean Gaussian with covariance Q. The observation noise process {v t } ℓ t=1 is uncorrelated zero mean Gaussian with time varying error covariance R nt and independent of the initial signal state and the system noise process. By the above construction, the optimal estimate of the signal state x t at time t, based on observations till that time, is given by the Kalman filter initialized with X as the predicted conditional error covariance at time t = 1. In other words, the optimal m.m.s.e. state estimator (predictor form) of x t based on observations {y s } 1≤s<t for 1 ≤ t ≤ ℓ + 1 can be recursively constructed through the Kalman filter and the corresponding predicted conditional error covariance sequence {P w0 (t)} 1≤t≤ℓ+1 satisfies the recursion: with initial condition P w0 (1) = X. We then have the R.H.S. being the desired functional form in eqn. (40), i.e., P w0 (ℓ + 1) = g w0 (X). Since for a Kalman filter with deterministic system/observation matrices, the conditional error covariance is equal to the unconditional one and the fact that the Kalman filter minimizes any positive definite form of the estimation error, for a generic estimator h of x ℓ+1 based on {y s } 1≤s≤ℓ we have where refers to the partial order on S N + . In order to upper bound the functional g w0 , we now construct a suboptimal state estimator with a guaranteed estimation performance. To this end, define the modified Grammian We note that G w0 is invertible by the invertibility of G w0 and the noise covariances R nt . Define the suboptimal estimator of x ℓ+1 by: based on observations {y s } 1≤s≤ℓ . Using the fact, that, we have from eqn. (118) The filtering error is then given by e w0 (ℓ + 1) = x ℓ+1 − x w0 (ℓ + 1) We note that the error above is independent of the initial state x 1 (and hence the covariance X) of the system, and the mean square boundedness of the process noise {w t } and observation noise {v t } imply the existence of a constant α 0 > 0, such that, E e w0 (ℓ + 1)e w0 (ℓ + 1) T α 0 I The Lemma then follows by the optimality of the Kalman filter, as stated in eqn. (116).

Proof of Lemma 15
In case F is stable, the claim is obvious, as the suboptimal estimate of 0 at each sensor for all time is stochastically bounded. So, in the sequel we assume F is unstable.
The proof is somewhat technical and mainly uses the uniform boundedness of the composition of Riccati operators in Lemma 14 and the ergodicity of the underlying switching Markov chain { p(t)} t∈T+ . From Lemma 14 it follows that a successive application of ℓ Riccati maps (in the composition order f n l • · · · • f n1 ) reduces the iterate in the conic interval [0, α 0 I] irrespective of its initial value. The approach is to relate the probability of large exceedance of P t to the hitting time statistics of a modified Markov chain. We detail it below.