Paper deep dive
Robustness and Leadership in Markov-switching Consensus Networks
Sarah H. Cen, Vaibhav Srivastava, Naomi Ehrich Leonard
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 89%
Last extracted: 7/9/2026, 7:55:54 AM
Summary
This paper investigates the robustness and leadership properties of multi-agent consensus networks under time-varying interactions modeled by Markov switching graphs (MSGs). Using Markov jump linear systems (MJLS), the authors derive steady-state performance metrics for noisy consensus and leader-follower tracking in both continuous- and discrete-time settings. They extend static graph robustness, certainty, and centrality measures to MSGs, analyze switching between two topologies, and demonstrate that dynamic graphs can sometimes outperform static ones in system robustness.
Entities (8)
Relation Signals (6)
Markov switching graph → models → time-varying interactions
confidence 95% · We model the time-varying interaction by a Markov switching graph (MSG), defined by a set of static graphs and a Markov chain that describes the transitions among these graphs.
Stochastic noise → affects → tracking error
confidence 90% · Our focus is on the steady-state performance of consensus and leader-follower tracking dynamics subject to stochastic noise.
Markov jump linear systems → usedtoanalyze → MSG dynamics
confidence 90% · Our results leverage the theory of Markov jump linear systems (MJLS) to characterize robustness and leadership properties in time-varying multi-agent networks.
Robustness index → extendedto → Markov switching graph
confidence 85% · We extend established notions of robustness, certainty indices, and joint centrality from static graphs to the MSG setting.
Switching topologies → influences → system robustness
confidence 85% · Numerical simulations further illustrate how switching topologies affects system robustness in both coordination tasks.
Steady-state covariance → quantifies → system performance
confidence 85% · derive expressions for the steady-state covariance... and use them to quantify individual and group performance as a function of the interaction graphs and the switching dynamics.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:We investigate how time-varying interactions, modeled via a Markov switching graph (MSG), impact the robustness of noisy multi-agent dynamics in both continuous- and discrete-time settings. Our focus is on the steady-state performance of consensus and leader-follower tracking dynamics subject to stochastic noise. Using the framework of Markov jump linear systems (MJLS), we derive expressions for the steady-state covariance of each agent's deviation from consensus and tracking error, respectively, and use them to quantify individual and group performance as a function of the interaction graphs and the switching dynamics. We extend established notions of robustness, certainty indices, and joint centrality from static graphs to the MSG setting. To gain analytical insight, we specialize our results to systems switching between two topologies and characterize how switching influences performance. Numerical simulations further illustrate how switching topologies affects system robustness in both coordination tasks.
Tags
Links
- Source: https://arxiv.org/abs/2606.25888v1
- Canonical: https://arxiv.org/abs/2606.25888v1
Trouble viewing inline? Open PDF directly →
Full Text
79,831 characters extracted from source content.
Expand or collapse full text
Robustness and Leadership in Markov-switching Consensus Networks †thanks: This is an extended version of the conference paper [1]. Beyond the results reported therein, this extended version incorporates an analysis of the discrete-time setting and derives analytical specializations of the general results for the case of switching between two graph topologies. †thanks: This research has been supported by ONR grant N00014-14-1-0635 and ARO grant W911NF-14-1-0431. Sarah H. Cen, Vaibhav Srivastava, and Naomi Ehrich Leonard S. H. Cen is with the Department of Electrical and Computer Engineering, Carnegie Mellon University, Pittsburgh, PA 15213, USA (sarahcen@andrew.cmu.edu). V. Srivastava is with the Department of Electrical and Computer Engineering, Michigan State University, East Lansing, MI 48824, USA (vaibhav@egr.msu.edu). N. E. Leonard is with the Department of Mechanical and Aerospace Engineering, Princeton University, Princeton, NJ 08544, USA (naomi@princeton.edu). Abstract We investigate how time-varying interactions, modeled via a Markov switching graph (MSG), impact the robustness of noisy multi-agent dynamics in both continuous- and discrete-time settings. Our focus is on the steady-state performance of consensus and leader-follower tracking dynamics subject to stochastic noise. Using the framework of Markov jump linear systems (MJLS), we derive expressions for the steady-state covariance of each agent’s deviation from consensus and tracking error, respectively, and use them to quantify individual and group performance as a function of the interaction graphs and the switching dynamics. We extend established notions of robustness, certainty indices, and joint centrality from static graphs to the MSG setting. To gain analytical insight, we specialize our results to systems switching between two topologies and characterize how switching influences performance. Numerical simulations further illustrate how switching topologies affects system robustness in both coordination tasks. 1 Introduction Many systems rely on the coordinated behavior of multiple agents, each performing individual tasks while interacting strategically to achieve a common objective. Such multi-agent systems appear across a wide range of domains, including biology, engineering, and economics. These systems often operate in environments characterized by stochastic disturbances and time-varying patterns of interaction. Designing effective multi-agent systems thus requires a careful understanding of how temporal variations in connectivity and the presence of noise influence both individual and collective performance. In this paper, we examine the influence of time-varying interaction among agents on the robustness of consensus dynamics [2, 3] and the related leader-follower collective tracking problem, in the presence of stochastic noise. We model the time-varying interaction by a Markov switching graph (MSG), defined by a set of static graphs and a Markov chain that describes the transitions among these graphs. The robustness of the consensus problem has been extensively studied for static interaction graphs among agents [4, 5, 6, 7, 8, 9]. Extending these results to time-varying graphs is challenging due to the limited analytic tractability of time-dependent dynamical systems. Consensus dynamics have been analyzed for deterministically time-varying graphs [10] and for stochastically time-varying graphs [11, 12, 13], but these works do not address the impact of stochastic noise. In particular, tools such as contraction analysis cannot be readily applied in the presence of stochastic disturbances. We address this gap by leveraging the structure of MSGs, a tractable subclass of stochastically time-varying graphs, to characterize the robustness properties of consensus dynamics under noise. While consensus over MSGs has been previously studied in [11], the role of noise in shaping performance within such frameworks has, to the best of our knowledge, not been examined. The noisy leader-follower collective tracking problem involves a network of agents that must track an external reference signal despite the presence of measurement and communication noise. A subset of agents, called leaders, directly observe the reference signal, while the remaining followers rely solely on information exchanged through the network. This problem has been studied primarily in the context of optimal leader selection, where the goal is to choose a leader set that optimizes collective tracking performance [14, 15, 16, 17], as well as in the context of edge modifications [18]. Prior work has addressed leader selection for time-varying graphs that evolve much more slowly than the consensus dynamics, or for stochastic time-varying graphs subject to random link failures [17]. In contrast, we study the noisy leader-follower tracking problem under MSGs, where graph switching may occur at comparable or faster timescales. Our framework does not require any time-scale separation between graph and state dynamics and accommodates a broader class of stochastic interaction models than those considered in [17]. Similar problems have been studied in the context of sensor selection [19]. Our results leverage the theory of Markov jump linear systems (MJLS) [20, 21] to characterize robustness and leadership properties in time-varying multi-agent networks. Our main contributions are fourfold. First, we derive measures of steady-state performance for noisy consensus and leader-follower tracking dynamics under MSGs, in both continuous- and discrete-time settings. These measures quantify system and node-level deviations from ideal behavior, due to noise, as a function of the network topologies and the switching process. Second, we show how these measures can be used to extend existing notions of robustness, certainty, and centrality measures for static graphs to MSGs. Third, we specialize our general results to the case of switching between two network topologies. This analysis allows us to characterize how switching topologies influences performance relative to a randomly assigned static topology. Fourth, we numerically illustrate how system performance can be different and sometimes better for the dynamic graph as compared to the static graph. The remainder of the paper is organized as follows. In Section 2, we introduce the noisy consensus and leader-follower tracking problems under Markov switching graphs (MSGs), define the performance metrics of interest, and review relevant background on continuous-time Markov jump linear systems (MJLS), which form the foundation of our analysis. In Section 3, we derive steady-state performance expressions for both coordination problems. Section 4 introduces robustness, certainty, and centrality indices for MSGs. To gain additional analytic insights, we specialize to the case of switching between two graph topologies in Section 5. Section 6 presents numerical examples that illustrate the influence of switching dynamics on system performance. We conclude in Section 7. Extension of the results to a discrete-time setting is presented in Appendix I. 1.1 Notation In this paper, matrices are denoted by upper-case letters and vectors by lower-case letters in bold. The i-th element of vector x is denoted by xix_i, and the (i,j)(i,j)-th entry of a matrix A is denoted AijA_ij. The transpose, inverse, and pseudoinverse of a matrix A are written as A⊤A , A−1A^-1, and A+A^+, respectively. The vectors n0_n and n1_n denote n×1n× 1 vectors of all zeros and ones, respectively. The n×n× n identity matrix is nI_n and the n×n× n exchange matrix is nJ_n. The matrix A⊗B∈ℝmp×nqA B ^mp× nq denotes the Kronecker product of matrices A∈ℝm×nA ^m× n and B∈ℝp×qB ^p× q. The matrix A⊕B=(A⊗n+m⊗B)∈ℝmn×mnA B=(A _n+I_m B) ^mn× mn denotes the Kronecker sum of matrices A∈ℝm×mA ^m× m and B∈ℝn×nB ^n× n. The covariance, trace, and vectorization of a matrix A are denoted by cov(A)cov(A), tr(A)tr(A), and vec(A)vec(A), respectively. Additionally, diagn(Ai)diag_n(A_i) is the block-diagonal matrix with entries (A1,A2,…,An)(A_1,A_2,…,A_n). The indicator function is denoted (E) 1(E), and the probability of an event E is denoted Pr(E) (E). The (n−1)(n-1)-dimensional probability simplex in ℝnR^n is denoted Δn _n, and the expectation of a random variable X is written as (X)E(X). 2 Two noisy distributed coordination problems under Markov switching graphs In this section, we review the noisy consensus and noisy leader-follower reference tracking coordination problems for time-varying networks. We present our definitions of system and node errors as measures of performance. Finally, we introduce MSG and MJLS. 2.1 Problem Statement Consider a network of m agents with system state (t)∈ℝmx(t) ^m, where xi(t)x_i(t) is the state of agent i at time t≥0t≥ 0. At time t, each agent i sends and receives information from its set of neighbors Ni(t)N_i(t). The resulting communication topologies are represented by the undirected, unweighted time-varying graph (t)=(,ℰ(t),Y(t))G(t)=(V,E(t),Y(t)) for the set of nodes =1,…,mV=\1,…,m\, set of edges ℰ(t)⊆×E(t) ×V, and adjacency matrix Y(t)∈ℝm×mY(t) ^m× m. Each graph node corresponds to an agent in the network, and an edge (i,j)(i,j) between nodes i and j exists at time t when j∈Ni(t)j∈N_i(t). Yij(t)=1Y_ij(t)=1 if edge (i,j)(i,j) exists at time t; otherwise, Yij(t)=0Y_ij(t)=0. Since (t)G(t) is undirected, (i,j)(i,j) implies (j,i)(j,i), and Y(t)Y(t) is thus symmetric. The degree of node i at time t is di(t)=∑j=1mYij(t)d_i(t)= _j=1^mY_ij(t), and the degree matrix D(t)=diag(d1(t),d2(t),…,dm(t))D(t)=diag(d_1(t),d_2(t),…,d_m(t)). The Laplacian matrix of the graph at time t is L(t)=D(t)−Y(t)L(t)=D(t)-Y(t). In the noisy consensus problem, a set of agents seeks to reach agreement over time. They resolve their differing opinions, which are given in x, through noisy network communication. We study the network consensus problem [2] under stochastic noise for time-varying graphs. The associated continuous-time dynamics are d(t)=−L(t)(t)dt+Fd(t), dx(t)=-L(t)x(t)dt+FdW(t), (1) where F is the system noise matrix and d(t)dW(t) is the m-dimensional standard Wiener process increment. Consensus is achieved when =αmx= 1_m, where α∈ℝα is the agreement value. In the noisy leader-follower reference tracking problem, the agents seek to track an external reference signal θ∈ℝθ such that xix_i represents agent i’s estimate of θ. A subset of agents assigned as the leaders directly measure θ, which is affected by noise, and the remaining agents are termed followers. All agents exchange information via noisy communications with their neighbors. The objective of the leaders is to drive the state of every agent to θ. The associated continuous-time dynamics are d(t)=−(L(t)(t)+K((t)−θm))dt+Fd(t), -1.0ptdx(t)=-(L(t)x(t)+K(x(t)- 1_m))dt+FdW(t), (2) where the leadership matrix K∈ℝm×mK ^m× m is a diagonal matrix with entries κ1,κ2,…,κm\ _1, _2,…, _m\. If agent i is a leader, then κi=κ>0 _i=κ>0 such that the leaders share the same gain κ. If agent i is a follower, then κi _i = 0. The cardinality of the leader set K is given by |||K|. Without loss of generality, we shift the origin of x to θm 1_m, reducing the dynamics in (2) to d(t)=−M(t)(t)dt+Fd(t), dx(t)=-M(t)x(t)dt+FdW(t), (3) where M(t)=L(t)+KM(t)=L(t)+K. We assess network performance using the following definitions of node and system errors, which apply only to systems for which the steady-state covariance exists. Define the node error EiE_i of node i as the steady-state variance of xix_i: Ei(Σs())=(Σs())ii, _i( _s(x))=( _s(x))_i, where Σs() _s(x) is the steady-state covariance of x. Define the system error E as the steady-state variance of x: E(Σs())=tr(Σs())=∑i=1mEi(Σs()). ( _s(x))=tr( _s(x))= _i=1^mE_i( _s(x)). We draw inspiration for these definitions from previous works, including [22, 14, 4, 23]. For the noisy consensus problem, the error quantifies the dispersion (or distance) from consensus and is thus inversely related to its robustness of consensus, as shown in [4]. For the noisy leader-follower reference tracking problem, the error indicates the success of the leader set in driving the agents’ states to the reference signal. 2.2 Markov Switching Graph We study the two coordination problems under the assumption that the network switches between a finite set of graphs =G1,…,GnG=\G_1,…,G_n\ according to a Markov chain (MC). The resulting time-varying graph is known as a Markov switching graph (MSG). Under a given MSG G, the linear dynamical systems (1)-(18) are Markov jump linear systems (MJLS) [24]. Recall that the total number of possible unweighted graphs for a given finite node set is also finite. Hence, the set G is assumed to be finite without loss of generality. Let S=1,…,nS=\1,…,n\ be the graph index set. The graph switching behavior of the continuous-time system is governed by a continuous-time MC (CTMC). For the graph set G, the CTMC is specified by the infinitesimal time-homogeneous generator matrix Γ∈ℝn×n ^n× n with elements: Γij=qij,i≠j,−vi,i=j, _ij= casesq_ij,&i≠ j,\\ -v_i,&i=j, cases for i,j∈Si,j∈ S. Here, vi=∑j∈S∖iqijv_i= _j∈ S iq_ij is the holding rate of graph GiG_i, and qij≥0q_ij≥ 0 is the transition rate from GiG_i to GjG_j. Intuitively, qijq_ij is the rate parameter of an exponential distribution that determines the probability that the system in graph GiG_i transitions to graph GjG_j with time [25]. Note that all rows in Γ sum to 0, and −Γ- is a Laplacian matrix. For the CTMC with the generator matrix Γ , let (t)∈Δn π(t)∈ _n be the probability distribution over G at time t. Specifically, πi(t) _i(t) is the probability that the network graph is (t)=GiG(t)=G_i, and ∑i=1nπi(t)=1 _i=1^nπ_i(t)=1. Furthermore, (t)=eΓ⊤t(0) π(t)=e t π(0) [25]. The remainder of our analysis makes the following two assumptions about the MSG. Assumption 1. The MC underlying the MSG is ergodic. Assumption 2. Every graph in the set G is unweighted, undirected, and connected. Under Assumption 1, the MC must have a unique stationary distribution ss π_s such that limt→∞(t)=s _t→∞ π(t)= π_s and limk→∞(k)=s _k→∞ π(k)= π_s for the CTMC and DTMC, respectively. An ergodic CTMC guarantees that G⊤G has exactly one eigenvalue at 0 with the right eigenvector ss π_s (i.e., ss=eG⊤ss π_s=e^G π_s), and all others in the left half-plane. An ergodic DTMC ensures that P⊤P has exactly one eigenvalue at 11 with the right eigenvector ss π_s (i.e., ss=P⊤ss π_s=P π_s), and all others strictly within the unit circle in the complex plane. Assumption 2 can be relaxed under certain conditions, but for clarity of exposition, we keep it. 2.3 Continuous-time Markov jump linear systems Consider the following continuous-time (CT) MJLS: d(t)=−Z(t)(t)dt+Fd(t), dx(t)=-Z(t)x(t)dt+FdW(t), (4) where Z(t)∈ℝm×mZ(t) ^m× m corresponds to the network graph of the MSG at time t with the generator matrix Γ . Let Z(t)=ZiZ(t)=Z_i whenever (t)=GiG(t)=G_i. Next, we obtain the dynamics of the mean and second moment of (t)x(t) evolving according to (4). For the following proposition, let the mean (t)=[(t)] μ(t)=E[x(t)]. The contribution of graph Gi∈G_i to the mean is i(t)=[(t)((t)=Gi)] μ^i(t)=E[x(t) 1(G(t)=G_i)] such that (t)=∑i=1ni(t) μ(t)= _i=1^n μ^i(t). Vertically stacking the means for all graphs gives the vector (t)=[1(t)⊤,2(t)⊤,…,n(t)⊤]⊤. ν(t)=[ μ^1(t) , μ^2(t) ,…, μ^n(t) ] . Similarly, let the second moment C(t)=[(t)(t)⊤]C(t)=E[x(t)x(t) ]. The contribution of graph Gi∈G_i to the second moment is Ci(t)=[(t)(t)⊤((t)=Gi)]C^i(t)=E[x(t)x(t) 1(G(t)=G_i)] such that C(t)=∑i=1nCi(t)C(t)= _i=1^nC^i(t). Vertically stacking the vectorized second moments for all graphs gives the vector (t)=[vec(C1(t))⊤,vec(C2(t))⊤,…,vec(Cn(t))⊤]⊤. (t)=[vec(C^1(t)) ,vec(C^2(t)) ,…,vec(C^n(t)) ] . Finally, let Q=FF⊤Q=F , =diagn(Zi)−ΓT⊗mN=diag_n(Z_i)- ^T _m and ℳ=diagn(Zi⊕Zi)−Γ⊤⊗m2M=diag_n(Z_i Z_i)- _m^2. Proposition 1. The following statements hold for the CT MJLS (4) with an MSG satisfying Assumptions 1 and 2: (i). The dynamics of the mean term (t) ν(t) are ˙(t)=−(t); ν(t)=-N ν(t); (5) (i). The dynamics of the second moment term (t)c(t) are ˙(t) c(t) =−ℳ(t)+(t)⊗vec(Q). =-Mc(t)+ π(t) (Q). (6) Proof. This result is standard in MJLS literature. See, for example, [26, Proposition 3.5]. For completeness, we have included a short proof in Appendix I. ∎ 3 Performance of distributed coordination under Markov switching graphs In this section, we study and interpret the performance of the two noisy coordination problems described in Section 2 under MSGs. Let S,1=vec(m)⊤h_S,1=vec(I_m) and S=n⊤⊗S,1h_S=1_n _S,1. Furthermore, let N,1i=vec(mi))⊤h_N,1^i=vec(O^i_m)) and Ni=n⊤⊗N,1ih_N^i=1_n _N,1^i, where miO^i_m is the m×m× m matrix containing all zeros except at element (i,i)(i,i), which takes the value 11. Then, Sh_Sc is the trace of second moment [⊤]E[xx ], and Nih_N^ic is its diagonal element (i,i)(i,i) corresponding to node i. At steady state, these expressions are the contribution of the second moment to the system and node errors, respectively. 3.1 Noisy consensus under MSGs Let cN_c and ℳcM_c be the system matrices in (5) and (6) after specializing Proposition 1 to the CT MJLS (1). Lemma 1. For the continuous-time noisy consensus dynamics (1) under Assumptions 1 and 2, both cN_c and ℳcM_c have exactly one eigenvalue at 0 each; all other eigenvalues lie strictly in the right half-plane. Proof. When specializing Proposition 1 to the CT MJLS (1), Zi=LiZ_i=L_i, and (4) reduces to (1). Consequently, c=diagn(Li)−Γ⊤⊗mN_c=diag_n(L_i)- _m and ℳc=diagn(Li⊕Li)−Γ⊤⊗m2M_c=diag_n(L_i L_i)- _m^2. We seek to show that c⊤N_c and ℳc⊤M_c are effectively the Laplacian matrices of two large graphs that contain nmnm and nm2nm^2 nodes, respectively, and each has exactly one eigenvalue at 0. For c⊤N_c , diagn(Li)diag_n(L_i) is the Laplacian of a disconnected graph with n clusters, each of which is a connected subgraph as required. Therefore, the null space of diagn(Li)diag_n(L_i) is spanned by vectors of the form ⊗ma 1_m for any ∈ℝna ^n. Because Γ describes an ergodic CTMC, −Γ⊗m- _m is the Laplacian of a connected graph, and the null space of −Γ⊗m- _m is spanned by vectors of the form n⊗ 1_n for any ∈ℝmb ^m. The sum of two Laplacians is also a Laplacian. Furthermore, by Lemma 3.5 in [11], for two Laplacian matrices A and B, Null(A+B)=Null(A)∩Null(B)Null(A+B)=Null(A)\;∩\;Null(B). Therefore, Null(c⊤)Null(N _c) is the intersection of space spanned by ⊗ma 1_m and n⊗ 1_n , which is the space spanned by mn1_mn. Since the eigenvalues of a Laplacian are either at 0 or lie strictly in the right half-plane [27] and the nullity of c⊤N_c is 11, the transpose N, which shares its eigenvalues, has exactly one eigenvalue at 0. It can be verified that the corresponding right eigenvector is s⊗m π_s 1_m. It can be shown similarly that ℳcM_c has the unique right eigenvector s⊗m2 π_s 1_m^2 corresponding to the eigenvalue at 0.∎ Due to the eigenvalues of cN_c and ℳcM_c at 0, the second moment of x for the CT MJLS (1) diverges. However, the diverging part corresponds to the fully correlated component of agents’ states. It therefore does not contribute to the deviation from consensus, and consequently should not affect the system and node errors. We thus seek to isolate and disregard this component of the second moment attributed to network consensus. Borrowing terminology from [28], we label the subspace of ℝmR^m spanned by m1_m the consensus subspace and its orthogonal complement the disagreement subspace. We show that, as with the static graph [4], the second moments of x in (1) achieve bounded steady-state values when projected onto the disagreement subspace and, importantly, measure the distance from consensus as required for the calculation of the system and node errors. For the following propositions, let ⟂∈ℝm−1x ^m-1 represent the orthogonal projection of x onto the (m−1)(m-1)-dimensional disagreement subspace m⟂1 _m. We pick V∈ℝ(m−1)×mV ^(m-1)× m such that its rows form the orthonormal basis of m⟂1_m and let =V⊤V=−1mmm⊤V=V V=I- 1m1_m1_m . Then, as in [4], let ⟂=Vx =Vx and ¯=V⊤⟂ x=V x such that =1mmm⊤+¯x= 1m1_m1_m x+ x. The vector ¯∈ℝm x ^m is the component of x orthogonal to the consensus subspace, and we refer to it as the disagreement vector. In addition, note that m1_m is the right eigenvector of L(t)L(t) and B(k)B(k) associated with the eigenvalues 0 and 11, respectively. From (1), the continuous-time disagreement dynamics is d¯(t)=−L(t)¯(t)dt+Fd(t). d x(t)=-VL(t) x(t)dt+VFdW(t). (7) Lastly, mimicking the notation in Section 2.3, let ¯(t)=[¯(t)] μ(t)=E[ x(t)], ¯i(t)=[¯(t)((t)=Gi)] μ^i(t)=E[ x(t) 1(G(t)=G_i)], for each i∈Si∈ S, and ¯(t)=[¯1(t)⊤,…,¯n(t)⊤]⊤. ν(t)=[ μ^1(t) ,…, μ^n(t) ] . Let C¯(t) C(t), C¯i(t) C^i(t) and ¯(t) c(t), the second moment terms of ¯ x, be defined analogously. Proposition 2. For the disagreement dynamics (7) under Assumptions 1 and 2, the following statements hold: (i). the steady-state mean disagreement vector is zero, i.e., ¯s=nm, ν_s=0_nm, (8) where nm0_nm is the nm×1nm× 1 vector of all zeros; (i). the steady-state second moment of the disagreement vector is ¯s=ℳ¯c+(s⊗vec(Q)), c_s= M_c^+( π_s (VQV)), (9) where ℳ¯c=diagn(Li⊕Li)−Γ⊤⊗ M_c=diag_n(VL_iV _iV)- . Proof. Recall that ¯= x=Vx and =2V=V^2. Therefore, ¯i=¯i ν^i=V ν^i and ¯i=(⊗)¯i c^i=(V ) c^i. Specializing Proposition 1(i) to (7) gives ¯˙(t)=−¯c¯(t), ν(t)=- N_c ν(t), where ¯c=diagn(Li)−Γ⊤⊗ N_c=diag_n(VL_iV)- . First, note that LiVL_iV is also a Laplacian matrix and =m−1mmm⊤V=I_m- 1m1_m1_m . Then, by the same logic used in the proof of Lemma 1, X=diagn(Li)−Γ⊤⊗mX=diag_n(VL_iV)- _m has exactly one eigenvalue at 0 with the eigenvector s⊗m π_s 1_m and all others in the right half-plane. Since the CTMC is ergodic, the remaining term in ¯c N_c, which is Γ⊤⊗(1mmm⊤) ( 1m1_m1_m ), has exactly n−1n-1 non-zero eigenvalues, all of which are positive and map to the null space of X. This result means that the null space of ¯c N_c is equivalent to that of X, i.e., s⊗m π_s 1_m, and its non-zero eigenvalues lie in the right half-plane. Second, recall that ¯=(m−1mmm⊤) x=(I_m- 1m1_m1_m )x. Since any component of x along the direction m1_m is removed to get ¯ x, by its definition, ¯ ν has no component along s⊗m π_s 1_m. Thus, the eigenvalue at 0 is inconsequential, and ¯ ν has a steady-state solution. As all other eigenvalues lie in the right half-plane, the steady-state solution is ¯s=nm ν_s=0_nm, as stated in Proposition 2(i). Similarly, specializing Proposition 1(i) to (7) gives ¯˙(t)=−ℳ¯c¯(t)+(t)⊗vec(Q). c(t)=- M_c c(t)+ π(t) (VQV). where ℳ¯c=diagn(Li⊕Li)−Γ⊤⊗ M_c=diag_n(VL_iV _iV)- . It can be shown analogously to ¯c N_c that ℳ¯c M_c has exactly one eigenvalue at 0 with eigenvector s⊗m2 π_s 1_m^2 that is inconsequential to the evolution of ¯ c and that all other eigenvalues of ℳ¯c M_c lie in the right half-plane, meaning that there is a steady-state solution for ¯(t) c(t). At steady state, ¯˙s=nm2 c_s=0_nm^2 and (t)=s π(t)= π_s. Solving for ¯s c_s gives the result that is stated in Proposition 2(i). ∎ These results imply that the steady-state second moment of the disagreement vector is equal to the steady-state covariance. As a result, the system and i-th node errors of (1) computed on the disagreement subspace are S¯sh_S c_s and Ni¯sh_N^i c_s, respectively. 3.2 Noisy leader-follower reference tracking under MSGs Let kN_k and ℳkM_k be the system matrices in (5) and (6) after specializing Proposition 1 to the CT MJLS (3). Lemma 2. For the continuous-time noisy leader-follower reference tracking dynamics (3) under Assumptions 1 and 2, all eigenvalues of matrices kN_k and ℳkM_k lie strictly in the right half-plane. Proof. When specializing Proposition 1 to the CT MJLS (3), Zi=Li+K=MiZ_i=L_i+K=M_i, and (4) reduces to (1). Consequently, k=diagn(Mi)−Γ⊤⊗mN_k=diag_n(M_i)- _m and ℳk=diagn(Mi⊕Mi)−Γ⊤⊗m2M_k=diag_n(M_i M_i)- _m^2. It follows that k=c+In⊗KN_k=N_c+I_n K. From Lemma 1, c⊤N_c is a Laplacian matrix with the one-dimensional null space nm 1_nm. Thus, kN_k is a diagonal perturbation of cN_c and has all eigenvalues strictly in the right half-plane as long as ||>0|K|>0. It can be shown analogously that all eigenvalues of ℳkM_k also lie strictly in the right half-plane. ∎ Thus, in contrast to the noisy consensus problem, the noisy leader-follower reference tracking problem does not require the separation of consensus and disagreement subspaces since the presence of leaders removes the eigenvalue at 0 from kN_k and ℳkM_k as well as that at 11 from ℋkH_k and kA_k. For the following propositions, let the specialization of (t) ν(t) and (t)c(t) in (5) and (6) to the CT MJLS (3) be ^(t) ν(t) and ^(t) c(t), respectively; let the specialization of (k) ν(k) and (k)c(k) in (20) and (21) to the DT MJLS (18) be ^(k) ν(k) and ^(k) c(k), respectively. Proposition 3. For the leader-follower reference tracking dynamics (3) with ||>0|K|>0 and under Assumptions 1 and 2, the following statements hold: (i). the steady-state mean of the state vector is zero, i.e., ^s=nm; ν_s=0_nm; (10) (i). the steady-state second moment of the state vector is ^s=ℳk−1(s⊗vec(Q)), c_s=M_k^-1( π_s (Q)), (11) where ℳk=diagn(Mi⊕Mi)−Γ⊤⊗m2M_k=diag_n(M_i M_i)- _m^2. Proof. For the CT MJLS (3), all eigenvalues of kN_k lie strictly in the right half-plane, meaning that there is a steady-state solution for ^(t) ν(t). Since ^˙(t)=nm ν(t)=0_nm at steady state, it must be true that ^s=nm ν_s=0_nm as stated in in Proposition 3(i). Similarly, since the eigenvalues of ℳkM_k also lie strictly in the right half-plane, there exists a steady-state solution for ^(t) c(t). At steady state, ^˙(t)=nm2 c(t)=0_nm^2 and (t)=s π(t)= π_s. Solving for ^(t) c(t) under these conditions yields the result for ^s c_s stated in Proposition 3(i). ∎ As in the previous subsection, only the steady-state second moment is needed to determine the system and i-th node errors of (3), which are given by S^sh_S c_s and Ni^sh_N^i c_s, respectively. Equations (9) and (11) express the relationship between performance and graph structure. Understanding these results can reveal how the graph topologies and switching behavior, which are encoded in ℳM and A, affect how well the MSG propagates information. However, unlike s π_s and Q, the effects of ℳM and A on error are difficult to interpret due to the inverse matrices in (9) and (11). Intuitively, these matrices contain the most information since it is the inverse operation that, in effect, performs the mixing of graphs in G according to Γ and P. 4 Robustness and leadership indices for MSGs The robustness of a system is measured by its deviation from the desired result. The deviation from consensus is isolated by projecting the system state onto the disagreement subspace. Proposition 2 shows that for noisy consensus under MSGs, this disagreement state is a stochastic process that, in the limit t→+∞t→+∞, has zero mean and finite covariance. The component of covariance along consensus subspace is disregarded because it is completely correlated and thus does not correspond to deviation from consensus (i.e., the covariance of (t)x(t) along the consensus subspace is spanned by mm⊤ 1_m 1_m ). As discussed in [4], the trace of the steady-state disagreement covariance, which we define as the system error, measures the mean squared distance of the system state from consensus and, for a fixed undirected graph, corresponds to the ℋ2H_2 norm of (7) [29, 30]. For a fixed graph, this value has been linked to graph resistances and used to assess the robustness of consensus. In a similar spirit, we propose a new notion of robustness of consensus for Markov switching graphs defined by 1/(S¯s)1/(h_S c_s) and call it the system certainty index. This measure quantifies the efficacy of the MSGs in achieving consensus and allows for the ordering of MSGs by performance. As in [31], it can help in designing or dynamically rearranging MSG topologies for improved performance. The noisy consensus dynamics (1) is a continuum approximation to evidence aggregation in fixed-sample and sequential decision-making. Furthermore, the variance of each agent’s disagreement state, given by x¯i x_i, reflects its decision-making accuracy [32] and illustrates the speed-accuracy trade-off [33]. Accordingly, the inverse of the steady-state variance of x¯i x_i is described as the node certainty index in [32]. For a fixed graph, it was shown in [32] that the node certainty index is a monotone function of the node’s information centrality [34]. In a similar spirit, we introduce a novel notion of node certainty index for MSGs defined by 1/(Ni¯s)1/(h_N^i c_s) for the node i. The node certainty index can be used to order the nodes in an MSG based on their accuracy in decision-making. The system error in the noisy leader-follower tracking is the mean squared tracking error for all agents. Thus, the system error is a measure of the robustness of tracking in the presence of noise. The choice of nodes selected as leaders largely dictates the tracking performance. Consequently, the leader selection problem has received significant attention for fixed noisy consensus networks [14, 15, 17, 16, 35]. For the fixed graph with ||=1|K|=1, [16] shows that the most information-central node minimizes the system error when assigned as the leader. The system error due to multiple leaders was used to define the notion of joint centrality for multiple nodes, and its relation to network resistances is explored in [16]. The system error is used to define centrality measures for fixed consensus networks in [36]. In a similar spirit, we define joint robustness centrality of a set of leaders K in MSGs as the inverse of the system error for (3) with leader set K and in the limit κ→+∞κ→+∞, i.e., limκ→+∞1/(S^s) _κ→+∞1/(h_S c_s). 5 Analysis of the Two-Topology MSG In this section, we dissect the results for the simple two-topology continuous-time MSG in order to understand the mechanisms affecting the performance of a switching network. Let n=2n=2. Then, the generator matrix is Γ=[−v1v1v2−v2]=β[−πs,2πs,2πs,1−πs,1], = bmatrix-v_1&v_1\\ v_2&-v_2 bmatrix=β bmatrix-π_s,2&π_s,2\\ π_s,1&-π_s,1 bmatrix, (12) where β=v1+v2β=v_1+v_2 and s=1β[v2v1]⊤ π_s= 1β[v_2 5.0ptv_1] is the stationary distribution. Let α=βπs,1πs,2α=βπ_s,1π_s,2. Furthermore, let i=(Li⊕Li)+L_i=(VL_iV _iV)^+. Then, by Proposition 2, ¯s,i=ivec(Q) c_s,i=L_ivec(VQV) is the vectorized disagreement covariance for the single-topology static graph GiG_i with dynamics (1). Lastly, we define: E¯static E_static =S,1(πs,1¯s,1+πs,2¯s,2) =h_S,1(π_s,1 c_s,1+π_s,2 c_s,2) Ω¯ =(⊗)(πs,21+πs,12) =(V )(π_s,2L_1+π_s,1L_2) ¯diff c_diff =(⊗)(¯s,2−¯s,1) =(V )( c_s,2- c_s,1) ¯S,diff h_S,diff =,(2−1). =h_S,1(L_2-L_1). Proposition 4. For n=2n=2, β sufficiently small, and under Assumptions 1 and 2, the system error of the noisy consensus CT MJLS (1) computed on the disagreement subspace is E =E¯static−α¯S,diff(m2+βΩ¯)−1¯diff. = E_static-α h_S,diff(I_m^2+β )^-1 c_diff. (13) Substituting Nih_N^i for Sh_S yields an equivalent equation for the i-th node error. These results follow from Proposition 2. Proof. We begin by writing ℳ¯c=R1−βR2 M_c=R_1-β R_2, where R1=diagn(Li⊕Li),R2=[−πs,2πs,1πs,2−πs,1]⊗.R_1=diag_n(VL_iV _iV),R_2= bmatrix-π_s,2&π_s,1\\ π_s,2&-π_s,1 bmatrix . Recall the system error is E=Sℳ¯c+TE=h_S M_c^+T, where T=s⊗vec(Q)T= π_s (VQV). We choose to represent ℳ¯c+=∑p=0∞βpUp M_c^+= _p=0^∞β^pU_p. Noting that ℳ¯cℳ¯c+=Π M_c M_c^+= , where Π=nm2−1nm2nm2nm2⊤ =I_nm^2- 1nm^21_nm^21_nm^2 , we expand the series and solve for the matrices UrU_r by matching terms with the same power of β with the result that Up=(R1+R2)pR1+U_p=(R_1^+R_2)^pR_1^+. Note that R1+T=[πs,1¯s,1πs,2¯s,2] and SR1+T=E¯static.R_1^+T= bmatrixπ_s,1 c_s,1\\ π_s,2 c_s,2 bmatrix and h_SR_1^+T= E_static. Some detailed calculations yield S(R1+R2)p=(−1)p−1S[−πs,2(2−1)Ωp−1(⊗)πs,1(2−1)Ωp−1(⊗)],h_S(R_1^+R_2)^p=(-1)^p-1h_S\\ bmatrix-π_s,2(L_2-L_1) ^p-1(V )&\\ &π_s,1(L_2-L_1) ^p-1(V ) bmatrix, and Sβ(R1+R2)pR1+T=(−1)p−1α¯S,diffΩp−1¯diff.h_Sβ(R_1^+R_2)^pR_1^+T=(-1)^p-1α h_S,diff ^p-1 c_diff. Collecting the terms and using the Neumann series, which is guaranteed to converge for small β, we have E =E¯static−α¯S,diff(m2+βΩ¯)−1¯diff, = E_static-α h_S,diff(I_m^2+β )^-1 c_diff, ∎ For the next proposition, we define i=(Mi⊕Mi)+M_i=(M_i M_i)^+, s,i=ivec(Q)c_s,i=M_ivec(Q), and: Estatic E_static =S,1(πs,1s,1+πs,2s,2) =h_S,1(π_s,1c_s,1+π_s,2c_s,2) Ω =πs,21+πs,12 =π_s,2M_1+π_s,1M_2 diff c_diff =s,2−s,1 =c_s,2-c_s,1 S,diff h_S,diff =,(2−1). =h_S,1(M_2-M_1). Proposition 5. For n=2n=2, β sufficiently small, and under Assumptions 1 and 2, the system error of the noisy leader-follower reference tracking CT MJLS (3) is E =Estatic−α,diff(m2+βΩ)+diff. =E_static- _S, diff(I_m^2+β )^+c_diff. (14) Substituting Nih_N^i for Sh_S yields an equivalent equation for the i-th node error. These results follow from Proposition 3. Proof. Repeat the proof of Proposition 4 substituting ℳkM_k for ℳ¯c M_c, mI_m for V, nm2I_nm^2 for Π , iM_i for iL_i, s,ic_s,i for ¯s,i c_s,i, and so on. ∎ We now focus our discussion on the noisy consensus problem and Proposition 4. However, our conclusions straightforwardly apply to Proposition 5 as well. The error for the two-topology MSG consists of two main components. The first is E¯static E_static, which represents the baseline error incurred for the simplest MSG: the non-switching network. In other words, suppose the system initially enters into graph GiG_i with probability πs,i _s,i and remains in GiG_i thereafter. Then, the error, which is averaged over an infinite number of instances of the MSG, would be E¯static E_static. Consequently, the second term reflects the effect of graph switching on the error. It is helpful to note that it resembles the expression for system error: Sℳ¯c+vec(Q)h_S M_c^+vec(VQV). In that case, the elements of vec(Q)vec(VQV) scale with the level of noise experienced by the agents, and Sh_S is used to extract the elements that contribute to the system error; for both, greater values mean greater error. This comparison suggests that the impact of graph switching on performance is directly related to the dissimilarity of the two topologies. Not only do greater values in ¯S,diff h_S,diff and ¯diff c_diff increase the magnitude of the second term, but they do so by selectively scaling the elements of (m2+βΩ)+(I_m^2+β )^+ corresponding to the largest differences. Extending the analogy further, (m2+βΩ)(I_m^2+β ), which mirrors ℳ¯c M_c in the system error expression, encodes the topologies and generator matrix of some network. Although this network is difficult to interpret, it is clear that (m2+βΩ)(I_m^2+β ) and its pseudoinverse are positive semi-definite. If we make the reasonable assumption that each agent is independently affected by noise such that F=Q=F=Q=I, then ¯S,diff⊤=¯diff h_S,diff = c_diff. By the definition of positive semi-definite matrices, ¯S,diff(m2+βΩ¯)+¯diff≥0 h_S,diff(I_m^2+β )^+ c_diff≥ 0. Due to the negative sign before the second term, this finding means that, given two graphs and the proportion of time the system must spend in each, allowing the network to switch between them cannot hurt its performance. In short, graph switching is favorable. We hypothesize that this holds true for any reasonable system noise matrix F (e.g. positive diagonal elements), and we have not encountered evidence to the contrary. Furthermore, α>0α>0 scales with the sum q12+q21q_12+q_21. As qijq_ij indicates the propensity of the system to switch out of GiG_i into GjG_j, larger values of α correspond to more frequent graph switching. Since α scales the non-negative expression ¯S,diff(m2+βΩ¯)+¯diff h_S,diff(I_m^2+β )^+ c_diff, more frequent switching gives lower error. We conclude that, for the two-topology MSG, the act of switching between graphs lowers or does not change the error. In the former case, increasing the rate of switching further improves performance; we prove this for F=F=I and speculate that it is generally true. Moreover, we find that more dissimilar topologies produce better MSGs. This result applies analogously to Proposition 5. We believe that the intuitions developed in this section apply for arbitrarily large MSGs. 6 Numerical Illustrations In this section, we illustrate the results of the previous sections by simulating simple MSGs. For all examples, F=F=I. First, we examine the noisy consensus dynamics (1) under MSGs with the state space G comprising the line and ring graphs shown in Figs. 1(a)-(b) and the generator matrix Γ=ϵ[−r12r12r21−r21], =ε bmatrix-r_12&r_12\\ r_21&-r_21 bmatrix, (15) where qij=vi=ϵrijq_ij=v_i=εr_ij. Recall that Γ ’s off-diagonal elements qijq_ij scale with the MSG’s propensity to switch from GiG_i to GjG_j. Accordingly, ϵε controls the network’s overall rate of graph switching. We fix ϵ=0.5ε=0.5 and study the system and node certainty indices as functions of r12r_12 and r21r_21 in Fig. 1(c)-(d). Fig. 1 illustrates that, in general, the MSG benefits from spending more time in the more connected topology. In this case, the performance improves when the MSG lingers in the ring topology (low r21r_21) and/or transitions to the ring more frequently (high r12r_12). Fig. 1(c) also suggests that if r12r_12 is sufficiently high compared to r21r_21, the performance only improves marginally for rising r12r_12, which reveals that lengthening the time the system spends as a ring has diminishing returns. Fig. 1(d) demonstrates that the nodes do not benefit equally from the addition of edge (1,5)(1,5). In addition, the certainty curve of node 3 shows that, for this MSG, only the shortest paths between nodes affects success as node 3 does not benefit from additional longer routes to previously accessible nodes (e.g. the extra path 3-4-5-1 in the ring does not improve node 3’s certainty since the shorter path 3-2-1 already exists in the line). (a) (b) (c) (d) Figure 1: Noisy consensus dynamics (1) under MSG with state space comprising a line graph G1G_1 shown in panel (a) and a ring graph G2G_2 shown in panel (b), and defined by the parametrized generator matrix (15). For fixed ϵ=0.5ε=0.5, panels (c) and (d) chart the system and node certainty indices, respectively, across various r12r_12 and r21r_21 values. Second, we investigate the noisy consensus dynamics (1) under the MSGs with G comprising graphs G1,G2G_1,G_2, G3G_3, shown in Figs. 2(a), (b), (c), respectively, and the generator matrix Γ=ϵ[−r12r120r2j−2r2jr2j0r32−r32], =ε bmatrix-r_12&r_12&0\\ r_2j&-2r_2j&r_2j\\ 0&r_32&-r_32 bmatrix, (16) where we set r12=r32r_12=r_32 and r2j=0.05r_2j=0.05. The system cannot transition directly between G1G_1 and G3G_3. Unlike in the previous case, this MSG comprises three equally connected topologies that would individually produce identical system errors. We illustrate system and node certainty indices as a function of q12q_12 and ϵε in Figs. 2(d)-(e). The system certainty curves in Fig. 2(d) are concave and contain finite non-zero global maxima, which indicates that, unlike in the simpler line-graph case, the optimal MSG prefers to switch between graphs in order to balance the information flow across the nodes. Fig. 2(e) shows three revealing facts. First, some nodes gain from increasing q12q_12 while others worsen, which causes the maxima in system certainty. Second, node 3 clearly does best with increasing q12q_12. Interestingly, node 2 also benefits from spending more time in G2G_2 despite its central placement in G3G_3, suggesting that obtaining a highly central position is less crucial than avoiding the least central ones. Finally, as ϵε increases, the certainty indices rise, meaning that, for the same stationary distribution, performance improves when switching occurs more often. (a) (b) (c) (d) (e) Figure 2: Noisy consensus dynamics (1) under MSG with state space comprising G1,G2G_1,G_2 and G3G_3 shown in panels (a), (b), and (c), respectively, and defined by the parametrized generator matrix (16) with v2=0.1v_2=0.1. Panels (d) and (e) chart the system and node certainty indices, respectively, for various v1v_1 and ϵε values. (a) (b) Figure 3: Two topologies of a five-node MSG. Lastly, we study the noisy leader-follower reference tracking problem (3) and the robustness centrality index. Consider the MSG comprising the two graphs in Fig. 3 and defined by the generator matrix (15) with q12=q21=1q_12=q_21=1. Then, for κ=∞κ=∞, ϵε small, and ||=1|K|=1, the nodes listed in order of decreasing robustness centrality (i.e., leader potential) are 1-3-4-5-2. However, for ϵ=1ε=1, the nodes listed in order of decreasing node certainty are 3-1-4-5-2; interestingly, for ϵ=10ε=10, the ordering again becomes 1-3-4-5-2. Thus, the set of agents with the greatest combined node certainty does not reliably predict the optimal leader set. This result contrasts with the static graph, for which it always holds true [16]. 7 Conclusion and Future Work In this paper, we studied the noisy distributed consensus and noisy leader-follower reference tracking problems under Markov switching graphs (MSGs). We derived performance measures that quantify robustness of consensus, node certainty, and joint centrality in both continuous- and discrete-time settings. By specializing to the case of switching between two graph topologies, we obtained analytical insights into how switching rates and network structure influence system performance. Through numerical examples, we further illustrated how both the topology and switching dynamics affect consensus and tracking behavior. Notably, we observed that the optimal leader set for reference tracking does not necessarily correspond to the agents with the highest combined node certainty for the static graphs. This work opens several promising directions for future research. One is to better understand and characterize the structure of the matrix ℳM that governs steady-state performance. Another is to develop efficient algorithms for optimal leader selection in noisy, Markov-switching networks. Additional extensions include relaxing our current assumptions to accommodate directed, weighted, or disconnected graphs. Appendix I Discrete Time Consensus Networks For the analogous discrete-time systems, each time step is denoted by k≥0k≥ 0. At some time step k, the network graph is given by (k)=(,ℰ(k),Y(k))G(k)=(V,E(k),Y(k)) and parallels the continuous-time system described at the beginning of this subsection. The discrete-time dynamics for the noisy consensus problem are (k+1)=B(k)(k)+F(k), (k+1)=B(k)x(k)+Fv(k), (17) where (k)x(k) is the system state at time step k, B(k)=e−L(k)B(k)=e^-L(k) is the averaging matrix, and F is the covariance matrix for the system noise (k)∈(m,m)v(k) (0_m,I_m). Similarly, the discrete-time dynamics for the leader-follower reference tracking problem are (k+1)=A(k)(k)+F(k), (k+1)=A(k)x(k)+Fv(k), (18) where A(k)=e−(L(k)+K)=e−M(k)A(k)=e^-(L(k)+K)=e^-M(k). We first recall some results for a general discrete-time MJLS. Consider the following discrete-time (DT) MJLS: (k+1)=W(k)(k)+F(k), (k+1)=W(k)x(k)+Fv(k), (19) where W(k)∈ℝm×mW(k) ^m× m maps to the network graph of the MSG at time step k with transition probability matrix P. Specifically, W(k)=WiW(k)=W_i whenever (k)=GiG(k)=G_i. Next, we obtain the dynamics of the moments of (k)x(k) evolving according to (19). The following notation aligns with that of Section 2.3. Let the mean (k)=[(k)] μ(k)=E[x(k)] and i(k)=[(k)((k)=Gi)] μ^i(k)=E[x(k) 1(G(k)=G_i)] such that (k)=∑i=1ni(k) μ(k)= _i=1^n μ^i(k). As for the CT MJLS, vertically stacking the means for all graphs gives the vector (k) ν(k). Furthermore, let the second moment C(k)=[(k)(k)⊤]C(k)=E[x(k)x(k) ] and Ci(k)=[(k)(k)⊤((k)=Gi)]C^i(k)=E[x(k)x(k) 1(G(k)=G_i)] such that C(k)=∑i=1nCi(k)C(k)= _i=1^nC^i(k). Vertically stacking the vectorized second moments for all graphs gives the vector (k)c(k). Finally, let ℋ=(PT⊗m)diagn(Wi)H=(P^T _m) 1.0ptdiag_n(W_i) and =(P⊤⊗m2)diagn(Wi⊗Wi)A=(P _m^2) 1.0ptdiag_n(W_i W_i). Proposition 6. The following statements hold for the DT MJLS (19) with an MSG satisfying Assumptions 1 and 2: (i). The dynamics of the mean term (k) ν(k) is (k+1)=ℋ(k); ν(k+1)=H ν(k); (20) (i). The dynamics of the second moment term (k)c(k) is (k+1) c(k+1) =(k)+(k+1)⊗vec(Q). =Ac(k)+ π(k+1) (Q). (21) Proof. This result is standard in MJLS literature. See, for example, [24, Chapter 4]. For completeness, we have included a short proof in Appendix I. ∎ We now establish the discrete-time equivalents of Lemma 1 and Proposition 2. Let ℋcH_c and cA_c be the system matrices in (20) and (21) after specializing Proposition 6 to the DT MJLS (17). In the following, the time t in the notation in Section 3.1 is substituted with the time step k for the discrete-time notation of ¯(k) μ(k), and so on. Lemma 3. For the discrete-time noisy consensus dynamics (17) under Assumptions 1 and 2, both ℋcH_c and cA_c have exactly one eigenvalue at 11 each; all other eigenvalues lie strictly within the unit circle of the complex plane. Proof. When specializing Proposition 6 to the DT MJLS (17), Wi=BiW_i=B_i, and (19) reduces to (17). Consequently, ℋc=(P⊤⊗m)diagn(Bi)H_c=(P _m)diag_n(B_i) and c=(P⊤⊗m2)diagn(Bi⊗Bi)A_c=(P _m^2)diag_n(B_i B_i). Let Λ1(X) _1(X) be the eigenspace of 11 for matrix X, and |λ∖1(X)|<1| _ 1(X)|<1 means that all eigenvalues of X other than those at 11 lie strictly within the unit circle of the complex plane. For an ergodic DTMC, Λ1(P)=n _1(P)=\1_n\, and |λ∖1(P)|<1| _ 1(P)|<1. Therefore, Λ1(P⊗m)=(n⊗)∀∈ℝm _1(P _m)=\(1_n ) ^m\. In addition, since all graphs in G are connected, Λ1(Bi)=m _1(B_i)=\1_m\, and |λ∖1(Bi)|<1| _ 1(B_i)|<1 for all i∈Si∈ S. As a result, Λ1(diagn(Bi))=(⊗m)∀∈ℝn _1(diag_n(B_i))=\(b 1_m) ^n\. As |λ∖1(P⊗m)|<1| _ 1(P _m)|<1 and |λ∖1(diagn(Bi))|<1| _ 1(diag_n(B_i))|<1, it must be true that Λ1(ℋc⊤)=Λ1(P⊗m)∩Λ1(diagn(Bi))=mn _1(H_c 1.0pt )= _1(P _m)∩ _1(diag_n(B_i))=\1_mn\. Its transpose ℋcH_c must also have exactly one eigenvalue at 11. It is straightforward to verify that the associated right eigenvector is s⊗m π_s 1_m. By the Perron-Frobenius theorem, |λ∖1(ℋc)|<1| _ 1(H_c)|<1. It follows similarly that cA_c has a unique eigenvector s⊗m2 π_s 1_m^2 corresponding to the eigenvalue at 11 and |λ∖1(c)|<1| _ 1(A_c)|<1. ∎ From (17), the discrete-time disagreement dynamics is ¯(k+1)=B(k)¯(k)+F(k). x(k+1)=VB(k) x(k)+VFv(k). (22) Proposition 7. For the disagreement dynamics (22) under Assumptions 1 and 2, the following statements hold: (i). the steady-state mean disagreement vector is zero, i.e., ¯s=nm; ν_s=0_nm; (23) (i). the steady-state second moment of the disagreement vector is ¯s=(nm2−¯c)+(s⊗vec(Q)), c_s=(I_nm^2- A_c)^+( π_s (VQV)), (24) where ¯c=(P⊤⊗)diagn(Bi⊗Bi) A_c=(P )diag_n(VB_iV _iV). Proof. For the following proof parallels, refer to the proofs of Proposition 2 and Lemma 3 for details when needed. Specializing Proposition 6(i) to (7) gives ¯(k+1)=−ℋ¯c¯(k), ν(k+1)=- H_c ν(k), where ℋ¯c=(P⊤⊗m)diagn(Bi) H_c=(P _m)diag_n(VB_i). Since V is the projector onto the disagreement subspace, BiVB_i removes the eigenvalue of BiB_i at 11 and replaces it with an eigenvalue at 0. As a result, all eigenvalues of diagn(Bi)diag_n(VB_i) lie strictly within the unit circle of the complex plane. From the proof of Lemma 3, we conclude that all eigenvalues of ℋ¯c H_c also lie strictly within the unit circle as well, meaning that the solution at steady state is ¯s=nm ν_s=0_nm, as stated in Proposition 7(i). Similarly, specializing Proposition 6(i) to (22) gives ¯(k+1)=¯c¯(k)+(k+1)⊗vec(Q). c(k+1)= A_c c(k)+ π(k+1) (VQV). where ¯c=(P⊤⊗m2)diagn(Bi⊕Bi) A_c=(P _m^2)diag_n(VB_i _i). It can be shown analogously to ℋ¯c H_c that all eigenvalues of ¯c A_c fall inside the unit circle, and a steady solution for ¯(k) c(k) exists. At steady state, ¯s=¯(k+1)=¯(k) c_s= c(k+1)= c(k) and (k)=s π(k)= π_s. Solving for ¯s c_s gives the result that is stated in Proposition 7(i). ∎ We now extend Lemma 2 and Proposition 3 to the discrete-time setting. Let ℋkH_k and kA_k be the system matrices in (20) and (21) after specializing Proposition 6 to the DT MJLS (18). Lemma 4. For the discrete-time noisy leader-follower reference tracking dynamics (18) under Assumptions 1 and 2, all eigenvalues of matrices kN_k and ℳkM_k lie strictly within the unit circle of the complex plane. Proof. When specializing Proposition 6 to the DT MJLS (18), Wi=e−(Li+K)=AiW_i=e^-(L_i+K)=A_i, and (19) reduces to (17). Consequently, ℋk=(P⊤⊗m)diagn(Ai)H_k=(P _m)diag_n(A_i) and k=(P⊤⊗m2)diagn(Ai⊗Ai)A_k=(P _m^2)diag_n(A_i A_i). For ||>0|K|>0, the eigenvalues of Li+KL_i+K lie strictly in the right half-plane, meaning that those of AiA_i lie strictly within the unit circle. Using the same logic as in the proof of Lemma 3, all eigenvalues of ℋkH_k also lie strictly within the unit circle. It can be shown analogously that all eigenvalues of kA_k lie strictly within the unit circle. ∎ Proposition 8. For the leader-follower reference tracking dynamics (18) with ||>0|K|>0 and under Assumptions 1 and 2, the following statements hold: (i). the steady-state mean of the state vector is zero, i.e., ^s=nm; ν_s=0_nm; (25) (i). the steady-state second moment of the state vector is ^s=(nm2−k)−1(s⊗vec(Q)), c_s=(I_nm^2-A_k)^-1( π_s (Q)), (26) where k=(P⊤⊗m2)diagn(Ai⊗Ai)A_k=(P _m^2)diag_n(A_i A_i). Proof. For the DT MJLS (18), all eigenvalues of ℋkH_k and kA_k lie strictly within the unit circle, meaning that there are steady-state solutions for ^(k) ν(k) and ^(k) c(k). Since ^(k+1)=^(k) ν(k+1)= ν(k) at steady state, it must be true that ^s=nm ν_s=0_nm as stated in in Proposition 8(i). Similarly, at steady state, ^(k+1)=^(k) c(k+1)= c(k) and (k)=s π(k)= π_s. Solving for ^(k) c(k) under these conditions yields the result for ^s c_s stated in Proposition 8(i). ∎ Remark 1. The results of Propositions 4 and 5 can be easily extended to the discrete time case. Specifically, let the state transition matrix be P=[1−v1v1v21−v2]=[1−βπs,2βπs,2βπs,11−βπs,1],P= bmatrix1-v_1&v_1\\ v_2&1-v_2 bmatrix= bmatrix1-βπ_s,2&βπ_s,2\\ βπ_s,1&1-βπ_s,1 bmatrix, where β=v1+v2β=v_1+v_2 and s=1β[v2v1]⊤ π_s= 1β[v_2 5.0ptv_1] is the stationary distribution. The system error is E=Sℳ¯d+TE=h_S M_d^+T, where ℳ¯d=R1−βR2 M_d=R_1-β R_2 with R1 R_1 =(nm2−(2⊗)diagn(Bi⊗Bi), =(I_nm^2-(I_2 )diag_n(VB_iV _iV), R2 R_2 =([−πs,2πs,2πs,1−πs,1]⊗)diagn(Bi⊗Bi). = ( bmatrix-π_s,2&π_s,2\\ π_s,1&-π_s,1 bmatrix )diag_n(VB_iV _iV). Analogous steps to the proof of Proposition 4 can be employed to derive similar expressions. □ References [1] S. H. Cen, V. Srivastava, and N. E. Leonard, “On robustness and leadership in Markov switching consensus networks,” in IEEE Conf. on Decision and Control, (Melbourne, Australia), p. 1701–1706, Dec. 2017. [2] R. Olfati-Saber, J. A. Fax, and R. M. Murray, “Consensus and cooperation in networked multi-agent systems,” Proceedings of the IEEE, vol. 95, no. 1, p. 215–233, 2007. [3] W. Ren, R. W. Beard, and E. M. Atkins, “A survey of consensus problems in multi-agent coordination,” in American Control Conference, p. 1859–1864, IEEE, 2005. [4] G. F. Young, L. Scardovi, and N. E. Leonard, “Robustness of noisy consensus dynamics with directed communication,” in American Control Conference, p. 6312–6317, IEEE, 2010. [5] D. Zelazo and M. Burger, “On the robustness of uncertain consensus networks,” IEEE Transactions on Control of Network Systems, 2015. [6] M. Siami and N. Motee, “Fundamental limits and tradeoffs on disturbance propagation in linear dynamical networks,” IEEE Transactions on Automatic Control, vol. 61, no. 12, p. 4055–4062, 2016. [7] B. Bamieh, M. R. Jovanovic, P. Mitra, and S. Patterson, “Coherence in large-scale networks: Dimension-dependent limitations of local feedback,” IEEE Transactions on Automatic Control, vol. 57, no. 9, p. 2235–2249, 2012. [8] L. Xiao, S. Boyd, and S.-J. Kim, “Distributed average consensus with least-mean-square deviation,” Journal of Parallel and Distributed Computing, vol. 67, no. 1, p. 33–46, 2007. [9] M. Pirani, A. Mitra, and S. Sundaram, “Graph-theoretic approaches for analyzing the resilience of distributed control systems: A tutorial and survey,” Automatica, vol. 157, p. 111264, 2023. [10] L. Moreau, “Stability of multiagent systems with time-dependent communication links,” IEEE Transactions on Automatic Control, vol. 50, no. 2, p. 169–182, 2005. [11] I. Matei, J. S. Baras, and C. Somarakis, “Convergence results for the linear consensus problem under Markovian random graphs,” SIAM Journal on Control and Optimization, vol. 51, no. 2, p. 1574–1591, 2013. [12] A. Tahbaz-Salehi and A. Jadbabaie, “Consensus over ergodic stationary graph processes,” IEEE Transactions on Automatic Control, vol. 55, no. 1, p. 225–230, 2010. [13] B. Touri and A. Nedic, “On ergodicity, infinite flow, and consensus in random models,” IEEE Transactions on Automatic Control, vol. 56, no. 7, p. 1593–1605, 2011. [14] S. Patterson and B. Bamieh, “Leader selection for optimal network coherence,” in IEEE Conference on Decision and Control, p. 2692–2697, IEEE, 2010. [15] F. Lin, M. Fardad, and M. R. Jovanovic, “Algorithms for leader selection in stochastically forced consensus networks,” IEEE Transactions on Automatic Control, vol. 59, no. 7, p. 1789–1802, 2014. [16] K. Fitch and N. E. Leonard, “Joint centrality distinguishes optimal leaders in noisy networks,” IEEE Transactions on Control of Network Systems, vol. 3, no. 4, p. 366–378, 2015. [17] A. Clark, L. Bushnell, and R. Poovendran, “A supermodular optimization framework for leader selection under link noise in linear multi-agent systems,” IEEE Transactions on Automatic Control, vol. 59, no. 2, p. 283–296, 2014. [18] A. Shrinate and T. Tripathy, “Towards influence centrality: where to not add an edge in the network?,” in European Control Conference, (Thessaloniki, Greece), June 2025. available at: arXiv:2412.20112. [19] R. Vafaee and M. Siami, “Real-time sensor selection for time-varying networks with guaranteed performance,” Automatica, vol. 163, p. 111550, 2024. [20] O. L. do Valle Costa, M. D. Fragoso, and M. G. Todorov, Continuous-time Markov Jump Linear Systems. Springer Science & Business Media, 2012. [21] O. L. V. Do Costa, R. P. Marques, and M. D. Fragoso, Discrete-time Markov Jump Linear Systems. Springer, 2005. [22] K. Fitch and N. E. Leonard, “Information centrality and optimal leader selection in noisy networks,” in IEEE Conference on Decision and Control, p. 7510–7515, IEEE, 2013. [23] I. Poulakakis, L. Scardovi, and N. E. Leonard, “Node certainty in collective decision making,” in Decision and Control (CDC), 2012 IEEE 51st Annual Conference on, p. 4648–4653, IEEE, 2012. [24] V. Gupta, R. M. Murray, L. Shi, and B. Sinopoli, “Networked sensing, estimation and control systems,” California Institute of Technology Report, 2009. [25] G. Grimmett and D. Stirzaker, Probability and Random Processes. Probability and Random Processes, OUP Oxford, 2001. [26] X. Feng, K. A. Loparo, Y. Ji, and H. J. Chizeck, “Stochastic stability properties of jump linear systems,” IEEE Transactions on Automatic Control, vol. 37, no. 1, p. 38–53, 1992. [27] R. Agaev and P. Chebotarev, “On the spectra of nonsymmetric Laplacian matrices,” Linear Algebra and its Applications, vol. 399, p. 157–168, 2005. [28] G. F. Young, Optimising robustness of consensus to noise on directed networks. PhD thesis, Princeton University, 2014. [29] P. Barooah and J. P. Hespanha, “Estimation from relative measurements: Electrical analogy and large graphs,” IEEE Transactions on Signal Processing, vol. 56, no. 6, p. 2181–2193, 2008. [30] G. F. Young, L. Scardovi, and N. E. Leonard, “A new notion of effective resistance for directed graphs-part I: Definition and properties,” IEEE Transactions on Automatic Control, vol. 61, no. 7, p. 1727–1736, 2016. [31] G. F. Young, L. Scardovi, and N. E. Leonard, “Rearranging trees for robust consensus,” in IEEE Conference on Decision and Control and European Control Conference, p. 1000–1005, 2011. [32] I. Poulakakis, G. F. Young, L. Scardovi, and N. E. Leonard, “Information centrality and ordering of nodes for accuracy in noisy decision-making networks,” IEEE Transactions on Automatic Control, vol. 61, no. 4, p. 1040–1045, 2016. [33] V. Srivastava and N. E. Leonard, “Collective decision-making in ideal networks: The speed-accuracy trade-off,” IEEE Transactions on Control of Network Systems, vol. 1, no. 1, p. 121–132, 2014. [34] K. Stephenson and M. Zelen, “Rethinking centrality: Methods and examples,” Social Networks, vol. 11, no. 1, p. 1–37, 1989. [35] S. Patterson, N. McGlohon, and K. Dyagilev, “Optimal k-leader selection for coherence and convergence rate in one-dimensional networks,” IEEE Transactions on Control of Network Systems, 2016. [36] M. Siami, S. Bolouki, B. Bamieh, and N. Motee, “Centrality measures in linear consensus networks with structured network uncertainties,” IEEE Transactions on Control of Network Systems, 2017. [37] R. Horn and C. Johnson, Topics in Matrix Analysis. Cambridge University Press, 1994. Appendix I Proof of Proposition 1 To prove Proposition 1, we require the following lemma. Lemma 5. Let event B⊂B , where J is a finite sample space. Then, for a random variable Y and another event A, [Y(A)]=∑j∈[Y|A∩B=j]Pr(A|B=j)Pr(B=j), [Y 1(A)]= _j E[Y|A∩ B=j] (A|B=j) (B=j), where j is an outcome of J. Proof. (Lemma 5) For the probability density function f(y)f(y) and some event C, [Y(C)]=∫yf(y|C)Pr(C)y=[Y|C]Pr(C)E[Y 1(C)]= yf(y|C) (C)dy=E[Y|C] (C). Let [Y(A)]=∑j∈[Y(A∩B=j)]E[Y 1(A)]= _j E[Y 1(A∩ B=j)]. We complete the proof by letting C=A∩(B=j)C=A∩(B=j). ∎ Proof. (Proposition 1) Within this proof, we abbreviate a(t)=ata(t)=a_t and bi(t)=bi,tb_i(t)=b_i,t. Then, for some small time increment h, we rewrite (4) as t+h=(m−hZt)t+Fd(h)x_t+h=(I_m-hZ_t)x_t+FdW(h) where Zt=ZiZ_t=Z_i if t=Gi∈G_t=G_i is the network graph at time t. For j≠ij≠ i, let pii(h)=Pr(t+h=Gi|t=Gi)≈1−vih+O(h2) _i(h)= (G_t+h=G_i|G_t=G_i)≈ 1-v_ih+O(h^2) pji(h)=Pr(t+h=Gi|t=Gj)≈qjih+O(h2), _ji(h)= (G_t+h=G_i|G_t=G_j)≈ q_jih+O(h^2), where i,j∈Si,j∈ S. Then, from Lemma 5, t+hi μ_t+h^i =∑j∈S[t+h|t=Gj]pji(h)πj,t = _j∈ SE[x_t+h|G_t=G_j]p_ji(h) _j,t =(m−hZi)ti(1−vih)+∑j∈S∖ihqji(m−hZj)tj. =(I_m-hZ_i) μ_t^i(1-v_ih)+ _j∈ S ihq_ji(I_m-hZ_j) μ_t^j. We take the derivative ˙ti=limh→0(t+hi−ti)/h μ_t^i= _h→ 0( μ_t+h^i- μ_t^i)/h: ˙ti μ_t^i =−(Zi+vim)ti+∑j∈S∖ivjpjitj = -1.0pt-(Z_i+v_iI_m) μ_t^i+ -1.0pt _j∈ S iv_jp_ji μ_t^j =−Ziti+∑j∈SΓjitj, = -1.0pt-Z_i μ_t^i+ -1.0pt _j∈ S _ji μ_t^j, Vertically stacking ˙ti μ_t^i for all i∈Si∈ S into an mn×1mn× 1 vector gives the result that is stated in Proposition 1(i). Similarly, Ct+hi C^i_t+h =∑j∈S[t+ht+h⊤|t+h=Gi,t=Gj]pji(h)πj,t = _j∈ SE[x_t+hx_t+h |G_t+h=G_i,G_t=G_j]p_ji(h) _j,t =(Cti−hZiCti−hCtiZi⊤−vihCti) =(C^i_t-hZ_iC^i_t-hC^i_tZ_i -v_ihC^i_t) +∑j∈S∖iCtjhqji+πi,t+hhQ+O(h2). 50.0pt+ _j∈ S iC^j_thq_ji+ _i,t+hhQ+O(h^2). We take the derivative C˙ti=limh→0(Ct+hi−Cti)/h C^i_t= _h→ 0(C^i_t+h-C^i_t)/h: C˙ti C^i_t =−(ZiCti+CtiZi⊤+viCti)+∑j∈S∖iCtjqji+πi,tQ =-(Z_iC^i_t+C^i_tZ_i +v_iC^i_t)+ -2.0pt _j∈ S iC^j_tq_ji+ _i,tQ =−(ZiCti+CtiZi⊤)+∑j∈SCtjΓji+πi,tQ. =-(Z_iC^i_t+C^i_tZ_i )+ _j∈ SC^j_t _ji+ _i,tQ. Then, let ti=vec(Cti)c_t^i=vec(C^i_t) and vectorize the previous equation with the help of the rule vec(AXB)=(B⊤⊗A)vec(X)vec(AXB)=(B A)vec(X) for matrices A, X, and B [37]. As a result, ˙ti c_t^i =−(Zi⊕Zi)cti+∑j∈SΓjictj+πi,tvec(Q), =-(Z_i Z_i)c_t^i+ _j∈ S _jic_t^j+ _i,tvec(Q), which, when stacked vertically for all i∈Si∈ S into an nm2×1nm^2× 1 vector, gives the result that is stated in Proposition 1(i). ∎ Appendix I Proof of Proposition 6 This proof parallels that in Appendix I, which may contain information relevant to this section. First, let Wk=WiW_k=W_i if k=Gi∈G_k=G_i is the network graph at time step k. From 5, ki μ_k^i =∑j∈S[k|k−1=Gj]Pjiπj,k−1=∑j∈SWjk−1jPji. = _j∈ SE[x_k|G_k-1=G_j]P_ji _j,k-1= _j∈ SW_j μ_k-1^jP_ji. Then, vertically stacking ki μ_k^i for all i∈Si∈ S into an mn×1mn× 1 vector gives the result stated in 6(i). Similarly, Cki C^i_k =∑j∈S[kk⊤|k=Gi,k−1=Gj]Pjiπj,k−1 = _j∈ SE[x_kx_k |G_k=G_i,G_k-1=G_j]P_ji _j,k-1 =∑j∈SWjCk−1jWj⊤Pji+πi,kQ. = _j∈ SW_jC^j_k-1W_j P_ji+ _i,kQ. Vectorizing this equation yields: ki c_k^i =∑j∈SPji(Wj⊗Wj)k−1i+πi,kvec(Q), = _j∈ SP_ji(W_j W_j)c_k-1^i+ _i,kvec(Q), which, when stacked vertically for all i∈Si∈ S into an nm2×1nm^2× 1 vector, gives the result that is stated in Proposition 6(i). Similarly, the graph switching behavior of the discrete-time MSG with the graph set G is determined by a discrete-time MC (DTMC). The DTMC is described by the transition probability matrix P∈ℝn×nP ^n× n containing the elements: Pij(k)=Pr(r(k)=j|r(k−1)=i), P_ij(k)= (r(k)=j|r(k-1)=i), for i,j∈Si,j∈ S. Additionally, P is time-homogeneous, meaning that it is independent of k, and row-stochastic. As for the CTMC, the probability distribution of the DTMC at time step k is given by (k)∈Δn π(k)∈ _n. In this case, (k)=(P⊤)k(0) π(k)=(P )^k π(0).