{'fraction_non_alphanumeric': 0.07485856024079597, 'fraction_numerical': 0.019202363367799114, 'mean_word_length': 3.854823433906102, 'pattern_counts': {'":': 0, '<': 22, '<?xml version=': 0, '>': 13, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 18, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Linear Stochastic Approximation Algorithms and Group Consensus over Random Signed Networks: A Technical Report with All Proofs

This paper studies linear stochastic approximation (SA) algorithms and their application to multi-agent systems in engineering and sociology. As main contribution, we provide necessary and sufficient conditions for convergence of linear SA algorithms to a deterministic or random final vector. We also characterize the system convergence rate, when the system is convergent. Moreover, differing from non-negative gain functions in traditional SA algorithms, this paper considers also the case when the gain functions are allowed to take arbitrary real numbers. Using our general treatment, we provide necessary and sufficient conditions to reach consensus and group consensus for first-order discrete-time multi-agent system over random signed networks and with state-dependent noise. Finally, we extend our results to the setting of multi-dimensional linear SA algorithms and characterize the behavior of the multi-dimensional Friedkin-Johnsen model over random interaction networks.


I. INTRODUCTION
Distributed coordination of multi-agent systems has drawn much attention from various fields over the past decades. For example, engineers control the formations of mobile robots, satellites, unmanned aircraft, and automated highway systems [9], [26]; physicists and computer scientists model the collective behavior of animals [27], [32]; sociologists investigate the evolution of opinion, belief and social power over social networks [7], [12], [17]. Many models for distributed coordination have been proposed and analyzed; a common thread in all these works is the study of a group of interacting agents trying to achieve a collective behavior by using neighborhood information allowed by the network topology.
Affine dynamical systems are basic first-order dynamical models with application to many practical problems in multiagent systems, including distributed consensus of multi-agent systems, computation of PageRank, sensor localization of wireless networks, and belief evolution on social networks [12], [25]. If the linear operator in the affine system is timeinvariant, then the study of these systems is straightforward.
However, practical systems are very often subject to random fluctuations, so that the linear operator in an affine system is time-variant and the affine system may not convergence. To overcome this deficiency and eliminate the effects of uncertainty, a feasible approach is to adopt models based on the stochastic approximation (SA) algorithm.
The main idea of the SA algorithm is as follows: each agent has a memory of its current state. At each time step, each agent updates its state according to a convex combination of its current state and the information received from its neighbors. Critically, the weight accorded to its own state tends to 1 as time grows (as a way to model the accumulation of experience). The earliest SA algorithms were proposed by Robbins and Monro [28] who aimed to solve root finding problems. SA algorithms have then attracted much interest due to many applications such as the study of reinforcement learning [30], consensus protocols in multi-agent systems [5], and fictitious play in game theory [14]. A main tool in the study of SA algorithms (see [19,Chapter 5]) is the ordinary differential equations (ODE) method, which transforms the analysis of asymptotic properties of a discrete-time stochastic process into the analysis of a continuous-time deterministic process.
In this paper, we consider the SA algorithm for a discretetime affine dynamics with random linear operator; these models are basic first-order protocols with numerous applications in engineering and sociology. A key analysis method for SA algorithms is the so-called ODE method; this method however requires (i) the state of each agent to be uniformly bounded almost surely and (ii) the limit points to be deterministic; e.g., see [19,Chapter 5]. These requirements lead to sufficient conditions for the convergence of SA affine dynamics, but not to necessary and sufficient conditions. This paper develops appropriate discrete-time analysis methods and provides necessary and sufficient conditions for the convergence of SA affine dynamics. Under our necessary and sufficient conditions, the state of the system will converge to a random vector. An additional restriction of traditional SA algorithms is that only non-negative gain schedules are considered. This paper relaxes also this requirement and provides necessary and sufficient conditions for convergence of SA affine dynamics under nonpositive gains and arbitrary gains. In addition, we analyze the convergence rate of the system when it is convergent.
Our general theoretical results are directly applicable to certain multi-agent systems. The first application is to the study of consensus problems in multi-agent systems. As it is well known, numerous works provide sufficient conditions for consensus in time-varying multi-agent systems with row-stochastic interaction matrices; an incomplete list of references is [4], [5], [8], [20], [22], [29]; see also the classic works [3], [6], [31]. Recently, motivated by the study of antagonistic interactions in social networks, novel concepts of bipartite, group, and cluster consensus have been studied over signed networks (mainly focusing on continuous-time dynamical models); see [1], [21], [24], [33]. In this paper, we apply and extend our results on SA affine dynamics to the setting of firstorder discrete-time multi-agent system over random signed networks and with state-dependent noise; for such models, we provide novel necessary and sufficient conditions to reach consensus and group consensus.
As the second application of our results, we study the Friedkin-Johnsen (FJ) model of opinion dynamics in social networks. The FJ model was first proposed in [11], where each agent is assumed to be susceptible to other agents' opinions but also to be anchored to his own initial opinion with a certain level of stubbornness. Ravazzi et al. proposed a gossip version of the FJ model in [25], whereby each link in the network is sampled uniformly and the agents associated with the link meet and update their opinions. The agents' opinions were proven to converge in mean square. Frasca et al. considered a symmetric pairwise randomization of FJ in [10], whereby a pair of agents are chosen to update their opinions. Our work, by exploiting stochastic approximation, largely relaxes the conditions for convergence when applied to FJ model over random interaction networks. The sociological meaning of stochastic approximated FJ model is that agents have cumulative memory about their previous opinions. The adoption of SA models in the study of human behavior is widely adopted in game theory and economics; e.g., see [14].
The main contributions of this paper are summarized as follows.
1) We propose a stochastic approximation version of a time-varying affine system and provide necessary and sufficient conditions to guarantee convergence by developing appropriate discrete-time methods. The convergence rate is also obtained when the system is convergent. 2) Using our results, we get the necessary and sufficient conditions to reach consensus and group consensus of the first-order discrete-time multi-agent system over random signed networks and with state-dependent noise for the first time. 3) We extend our results to the multi-dimensional SA affine dynamics and provide applications to the multidimensional FJ model over random interaction networks.
Organization: The remainder of this paper is organized as follows. We briefly review the time-varying affine dynamics and propose a stochastic approximation version of it in Section II. The main results are presented in Section III. In particular, we introduce some preliminaries and assumptions in Subsection III-A. Sufficient conditions that guarantee the convergence of the affine dynamical system are obtained in Subsection III-B. We provide the results on convergence rate in the same subsection. In Subsection III-C, we prove that the sufficient condition is also necessary. The necessary and sufficient conditions for convergence are then summarized in Subsection III-D. We generalize the results to multi-dimensional models and discuss their application to group consensus and the FJ model in Section IV. Section V concludes the paper.

A. Review of time-varying affine dynamics
In [13], [25] a time-varying affine system was considered as follows: where P (s) ∈ R n×n is a matrix associated to the communication network between agents, and u(s) ∈ R n is an input vector. Given a matrix A ∈ R n×n , let ρ(A) denote its spectral radius, i.e., ρ( For system (1), if P (s) ≡ P , u(s) ≡ u, and ρ(A) < 1, then it is immediate to see that x(s) converges to (I n − P ) −1 u. However, when P (s) or u(s) is time-varying the system (1) does not necessarily converge. As an alternative, Ravazzi et al. [25] investigate the ergodicity of system (1) as follows.
If ρ(P ) < 1, then x(s) converges to a random variable in distribution, and 1 s s−1 k=0 x(k) converges to (I n − P ) −1 u almost surely.
In a separate line of inquiry, Han et al. [13] provide some sufficient conditions for cluster consensus with some special settings on P (s) and u(s).
In this paper we adopt the stochastic approximation method to average the effect of the time-varying P (s) and u(s) to the state x(s). In this case we study the sufficient and necessary conditions for convergence of x(s), and also obtain a convergence rate.

B. SA affine dynamics over time-varying networks
In this subsection we consider the stochastic-approximation version of system (1), formulated as: where a(s) ∈ R is the gain function. Compared to system (1), each agent updates its state depending not only on the affine map P (s)x(s) + u(s) but also on its own current state. If a(s) = 1 s+1 , then x(s + 1) equals the approximate average value of the previous s affine maps because x(s) carries the information of the previous s − 1 affine maps. Such a system is a basic first-order discrete-time multi-agent system with many applications like computation of PageRank [34], sensor localization of wireless networks [18], distributed consensus of multi-agent systems, and belief evolution on social networks.
We will study the mean-square convergence of system (2) whose definition is given as follows: Definition II.1: For an n-dimensional random vector x, we say x(s) converges to x in mean square if Also, we say {x(s)} is mean-square convergent if there exists an n-dimensional random vector x such that (3) holds.

A. Informal statement of main results
We start with some notation. Given a matrix A ∈ R n×n , define ρ max (A) := max i Re(λ i (A)) and ρ min (A) := min i Re(λ i (A)) to be the maximum and minimum values of the real parts of the eigenvalues of A respectively. It is easy to show that | ρ max (A)| ≤ ρ(A).
For {P (s)} and {u(s)}, we relax the i.i.d. condition in [25] to the following assumption: (A1) Suppose there exist a matrix P ∈ R n×n and a vector u ∈ R n such that E[P (s) | x(s)] = P and E[u(s) | x(s)] = u for any s ≥ 0 and x(s) ∈ R n . Also, assume E[ P (s) 2 2 | x(s)] and E[ u(s) 2 2 | x(s)] are uniformly bounded. For {a(s)}, generally SA algorithms use the following assumption: (A2) Assume {a(s)} are non-negative real numbers independent with {x(s)}, and satisfying ∞ s=0 a(s) = ∞ and ∞ s=0 a 2 (s) < ∞. We will consider the following alternative assumption.  Under the assumptions (A1) and (A2), we later show the necessary and sufficient condition for the convergence of x(s) in system (2) is ρ max (P ) < 1, or ρ max (P ) = 1 together with the following condition for P and u: (A3) Assume any eigenvalue of P whose real part is 1 equals 1, and the eigenvalue 1 has the same algebraic and geometric multiplicities, and ξu = 0 for any left eigenvector ξ (row vector) of P corresponding to the eigenvalue 1.
Also, we will study the convergence rates when x(s) is convergent, and the convergence conditions when {a(s)} are arbitrary real numbers.

B. Sufficient convergence conditions and convergence rates
Recall that P and u are the expectations of P (s) and u(s) respectively. Let where H ∈ C n×n is an invertible matrix, and D is the Jordan normal form of P with Let r be the algebraic multiplicity of the eigenvalue 1 of P . We first consider the case ρ max (P ) = 1 (or ρ min (P ) = 1) with (A3), which implies that r ≥ 1 and that the geometric multiplicity of the eigenvalue 1 is equal to r. We choose a suitable H such that λ 1 (P ) = · · · = λ r (P ) = 1. Then the Jordan normal form D can be written as where D := diag(J r+1 , . . . , J K ) ∈ C (n−r)×(n−r) . For any vector y ∈ C n , throughout this subsection we setȳ := (y 1 , . . . , y r ) ⊤ and y := (y r+1 , . . . , y n ) ⊤ .
Theorem III.1: (Convergence of SA affine system at critical point) Consider the system (2) satisfying (A1), (A2), and (A3) with ρ max (P ) = 1, or satisfying (A1), (A2'), and (A3) with ρ min (P ) = 1. Let H be the matrix defined by (4) such that the Jordan normal form D has the form of (5). Then, for any initial state, x(s) converges to H −1 y in mean square, whereȳ is a random vector satisfying Eȳ = Hx(0) and Let v := Ev(s) = Hu. From (4) we have HP = DH, which implies H i P = H i for 1 ≤ i ≤ r, where H i is the i-th row of the matrix H. Thus, H i , 1 ≤ i ≤ r, is a left eigenvector corresponding to the eigenvalue 1. By (A3) we have Recall that v = (v r+1 , . . . , v n ) ⊤ . Also, I n−r − D is an invertible matrix, so we can set From (5) and (8) we have Set θ(s) := y(s) − z. From (7) we obtain We first consider the case when ρ max (P ) = 1, which implies that D − I n−r is a Hurwitz matrix. Thus, by the stability theory of continuous Lyapunov equation (see [15,Corollary 2.2.4]), there exists a Hermitian positive definite matrix A ∈ C (n−r)×(n−r) such that where (·) * denotes the conjugate transpose of the matrix or vector. Set then A 1 is still a Hermitian positive definite matrix. Define the Lyapunov function V 1 (θ) := θ * A 1 θ. By (10), (A1) and (11), for any θ(s) we have (5) and (11), we obtain so (12) implies where c 1 and c 2 are two positive constants. Using (14) repeatedly we get where the last inequality uses the condition that ∞ s=0 a 2 (s) < ∞. Also, because A 1 is a Hermitian positive definite matrix, Combining (15) and (16) yields Inequality (17) shows that θ(s) will not diverge, however we need to prove its convergence. We first consider the convergence of θ(s). Set where the forth line uses (13) and (17), and the last inequality does a similar computation as (16). By (18) and Lemma A.1 1 Given two sequences of positive numbers in Appendix A, we obtain lim s→∞ E[V 2 (θ(s))] = 0, which implies It remains to consider the convergence ofθ(s). Set (5) and (8) we get Similarly, the equation (20) still holds for i > j. From these and (10) we get for any s 2 > s ≥ 0, where the last line uses (A1) and (17).
Proof. We can set r = 0 in the proof of Theorem III.1, then we obtain that x(s) converges to H −1 (I n − D) −1 Hu = (I n − P ) −1 u in mean square.
Remark 1: If x(s) is uniformly bounded a.s. in addition to the conditions of Proposition III.1, then we can obtain that x(s) converges to (I n − P ) −1 u almost surely by the ODE method in stochastic approximation (Theorem 5.2.1 in [19] or Theorem 2.2 in [2]).
Next, we give the convergence rate when x(s) is meansquare convergent.
The proof of this theorem is postponed to Appendix B.
The proof of this theorem is postponed to Appendix C. The condition of non-convergence in Theorem III.3 has a constraint that the gain function {a(s)} must satisfy the assumption (A2) or (A2'). An interesting problem is to understand what happens if {a(s)} are chosen as arbitrary real numbers. Obviously, from protocol (2) if {a(s)} has only finite non-zero elements, then x(s) will converge to a random variable. Thus, we only consider the setting whereby x(s) does not converge to a deterministic vector for arbitrary gains.
Recall that where H ∈ C n×n is an invertible matrix, and D is the Jordan normal form of P . For 1 ≤ i ≤ K, define which corresponds to the Jordan block J i and then D I i = diag(0, . . . , J i , . . . , 0). To study the condition for nonconvergence of system (2), we need the following two assumptions: (A4) Assume there is a Jordan block J j in D associated with the eigenvalue λ j ′ (P ) such that Re(λ j ′ (P )) = 1 and for any s ≥ 0 and x(s) ∈ R n , where P , u, H, D and I j are defined by (A1), (4), and (25), and c 1 and c 2 are constants satisfying c 1 ≥ 0, c 2 ≥ 0, and c 1 + c 2 > 0. (A4') Assume there are two Jordan blocks J j1 and J j2 associated with the eigenvalues λ j ′ 1 (P ) and λ j ′ 2 (P ) respectively such that Re(λ j ′ 1 (P )) < 1 < Re(λ j ′ 2 (P )) and (26) holds for j = j 1 , j 2 .
Theorem III.4: Consider the system (2) satisfying (A1) and (A4) or (A4'). In addition, assume there exists a constant c 3 > 0 such that for any s ≥ 0 and x(s) ∈ R n , Then for any deterministic vector b ∈ R n , any initial state The proof of this theorem is postponed to Appendix D.
If u(s) is a degenerate random vector which means that E u(s)−u 2 2 = 0, then the condition (27) may not be satisfied. Theorem III.5: Consider the system (2) satisfying (A1), and E[ u(s) − u 2 2 | x(s)] = 0 for any s ≥ 0 and x(s) ∈ R n . Assume (A4) or (A4') holds but using instead of (26). For any deterministic vector b ∈ R n and any initial state x(0) = b, if one of the following three conditions holds: and λ j ′ 2 (P ) in (A4') are not real numbers, then x(s) cannot converge to b in mean square for any real number sequence {a(s)} s≥0 independent with {x(s)} s≥0 .
The proof of this theorem is postponed to Appendix E.

D. Necessary and sufficient conditions for convergence
From Theorems III.1 and III.3 and Proposition III.1, the following necessary and sufficient conditions for convergence with non-negative and non-positive gains are obtained immediately.
Theorem III.6: (Necessary and sufficient condition for convergence of SA affine system with non-negative gains) Consider the system (2) satisfying (A1) and (A2). Then x(s) is mean-square convergent for any initial state if and only if ρ max (P ) < 1, or ρ max (P ) = 1 with (A3).
Theorem III.7: (Necessary and sufficient condition for convergence of SA affine system with non-positive gains) Consider the system (2) satisfying (A1) and (A2'). Then x(s) is mean-square convergent for any initial state if and only if ρ min (P ) > 1, or ρ min (P ) = 1 with (A3).
Remark 2: Theorem III.6 cannot be obtained by the general tool of the ODE method in SA theory due to two reasons. First, the ODE method requires the limit points to be deterministic, but, by Theorem III.1, our sequence x(s) may converge to a random vector when ρ max (P ) = 1. Second, the ODE method requires the state of each agent to be uniformly bounded almost surely. This assumption makes it impossible to establish the necessary condition for convergence Remark 3: Compared to Theorem 1 in [25], Theorem III.6 extends the convergence condition from ρ(P ) < 1 to the sufficient and necessary condition. In fact, for the basic affine protocol x(s + 1) = P x(s) + u, x(s) converges if and only if ρ(P ) < 1. However, if we consider the timevarying affine maps and adopt the SA method to eliminate the effect of fluctuation, then the convergence condition can be substantially weakened.
Theorems III.6 and III.7 have a constraint that the gain function {a(s)} must satisfy the assumption (A2) or (A2'). Without this constraint we can get the following necessary and sufficient condition for convergence to a deterministic vector, but with some additional conditions on {u(s)} or {P (s)}.
Theorem III.8 (Necessary and sufficient condition for convergence of SA affine dynamics with arbitrary gains): Consider the SA affine system (2) which satisfies (A1). Suppose there exists a constant c ∈ (0, 1) such that for any s ≥ 0, x(s) ∈ R n , ξ 1 , . . . , ξ m ∈ {P ij (s), 1 ≤ i, j ≤ n; u i (s), 1 ≤ i ≤ n} and c 1 , . . . , c m ∈ C, In addition, assume one of the following two conditions holds: Then we can choose real number sequence {a(s)} s≥0 independent with {x(s)} s≥0 such that x(s) converges to a deterministic vector different from x(0) in mean square if and only if ρ max (P ) < 1 or ρ min (P ) > 1.
For ρ min (P ) ≤ 1 ≤ ρ max (P ), we set P (s) := P (s) − P and u(s) := u(s) − u. Define H and K by (4), and define I i by (25). For any j ∈ {1, . . . , K}, since H is an invertible matrix, I j H contains at least one non-zero row H j ′ . Thus, for any x(s) ∈ R n we have where the last inequality uses (29).
Combing this with (30) and the assumption ρ min (P ) ≤ 1 ≤ ρ max (P ), we obtain that (27) which is followed by (28). By Theorem III.5 i) x(s) cannot converge to a deterministic vector different from x(0) in mean square.

IV. SOME APPLICATIONS AND EXTENSION
A. Necessary and sufficient conditions for group consensus over random signed networks and with state-dependent noise As we discuss in the Introduction, consensus problems in multi-agent systems have drawn a lot of attention from various fields including physics, biology, engineering and mathematics in the past two decades. Typically, a general assumption is adopted that the interaction matrix associated with the network is row-stochastic at every time. Recently, motivated by the possible antagonistic interaction in social networks, bipartite/group/cluster consensus problems have been studied over signed networks (focusing on continuous-time dynamic models), e.g., see [1], [21], [24], [33]. Interestingly, from Theorems III.1, III.6 and III.7 we can obtain some results for the group consensus of the discrete-time system over random signed networks and with state-dependent noise.
Consider a discrete-time first-order system containing n agents. Each agent i has a state x i (s) ∈ R at time s which can represent the opinion, social power or others, and is updated according to the current state and the interaction from the others. In detail, for 1 ≤ i ≤ n and s ≥ 0, the state of agent i is updated by where a(s) ≥ 0 is the gain at time s, N i (s) is the neighbors of node i at time s, P ij (s) is the weight of the edge (j, i) at time s, and f ji (x(s))w ji (s) is the noise of agent i receiving information from agent j at time s. Here we consider the noise may be state-dependent which means that f ji (x(s)) is a function of the state vector x(s). Let P ij (s) = 0 if j / ∈ N i (s), and set then system (31) can be rewritten as If P ij (s) is a stationary stochastic process with uniformly bounded variance, and w ji (s) is a zero-mean noise with uniformly bounded variance for any x(s), P ji (s), and j ∈ N i (s), then (A1) is satisfied with u = 0 n×1 .
From Definition IV.1 we can know that consensus is a special case of the {S i } r ′ i=1 -group consensus with r ′ = 1. Before the statement of our results, we need to introduce some notations and an assumption: For a partition S 1 , . . . , S r ′ of {1, . . . , n}, let 1 i ∈ R n (1 ≤ i ≤ r ′ ) denote the column vector satisfying . . , c r ′ ∈ C being constants.
(A5) Assume any eigenvalue of P whose real part is 1 equals 1, and the algebraic and geometric multiplicities of the eigenvalue 1 equal r ∈ [1, r ′ ], and any right eigenvector of P corresponding to the eigenvalue 1 can be written as a linear combination of {1 i } r ′ i=1 . With Theorems III.1, III.6 and Proposition III.1 we obtain the following result: Theorem IV.1: (Necessary and sufficient condition for group consensus with non-negative gains) Consider the system (2) or (31) satisfying (A1) with u = 0 n×1 and (A2). Let S 1 , . . . , S r ′ be a partition of {1, . . . , n}. Then x(s) asymptotically reaches {S i } r ′ i=1 -group consensus in mean square for any initial state if and only if ρ max (P ) < 1, or (A5) holds with ρ max (P ) = 1.
Proof. Before proving our result, we introduce some notes first. For any matrix A ∈ C n×n , let A i and A i denote the i-th row and i-th column of A respectively. Set We first consider the sufficient part. If ρ max (P ) < 1, by Proposition III.1 and the fact u = 0 n×1 we obtain that x(s) converges to 0 n×1 in mean square for all initial states. Hence, the {S i }-group consensus can be reached.
If (A5) holds with ρ max (P ) = 1, which implies that (A3) holds together with the fact u = 0 n×1 . Let P = H −1 DH, where H is an invertible matrix, and D is the Jordan normal form of P with the same expression as (5). Then, by Theorem III.1, for any initial state there exist random variables y 1 , . . . , y r such that in mean square Also, from P H −1 = DH −1 and (5) we have Hence, by (32) and (A5), there exist random variables z 1 , . . . , z r ′ such that in mean square x(s) → z 1 1 1 + · · · + z r ′ 1 r ′ as s → ∞, which implies that x(s) asymptotically reaches {S i } r ′ i=1 -group consensus in mean square for any initial state.
Next we prove the necessary part. Since x(s) asymptotically reaches {S i } r ′ i=1 -group consensus in mean square for any initial state, then, by Definition IV.1, x(s) is mean-square convergent for any initial state. Hence, by Theorem III.6, we obtain that ρ max (P ) < 1, or (A3) holds with ρ max (P ) = 1.
It remains to show (A5) holds for the case when (A3) holds. For any complex eigenvector a + bi ∈ C n of P corresponding to eigenvalue 1, we have P a = a and P b = b, which implies that a and b are real eigenvectors of P corresponding to eigenvalue 1. Thus, any complex eigenvector of P corresponding to the eigenvalue 1 can be written as a linear combination of real eigenvectors. Also, from (5)   Similar to Theorem IV.1 we have the following theorem: Theorem IV.2: (Necessary and sufficient condition for group consensus with non-positive gains) Consider the system (2) or (31) satisfying (A1) with u = 0 n×1 and (A2'). Let S 1 , . . . , S r ′ be a partition of {1, . . . , n}. Then x(s) asymptotically reaches {S i } r ′ i=1 -group consensus in mean square for any initial state if and only if ρ min (P ) > 1, or (A5) holds with ρ min (P ) = 1.
By Theorems IV.1 and IV.2 with r ′ = 1, we immediately obtain the following two corollaries for consensus: Corollary IV.1: Consider the system (2) or (31) satisfying (A1) with u = 0 n×1 and (A2). Then x(s) asymptotically reaches consensus in mean square for any initial state if and only if one of the following condition holds: i) ρ max (P ) < 1; ii) The sum of of each row of P equals 1, and P has n − 1 eigenvalues whose real parts are all less than 1.
Corollary IV.2: Consider the system (2) or (31) satisfying (A1) with u = 0 n×1 and (A2'). Then x(s) asymptotically reaches consensus in mean square for any initial state if and only if one of the following condition holds: i) ρ min (P ) > 1; ii) The sum of of each row of P equals 1, and P has n − 1 eigenvalues whose real parts are all bigger than 1.
We give the following two examples for consensus and group consensus respectively over signed networks.
Example 1: By the Perron-Frobenius Theorem, if P is an irreducible row-stochastic matrix then P satisfies the condition ii) in Corollary IV.1, which implies that x(s) asymptotically reaches mean-square consensus. However, the reverse is not always true. For example, let The eigenvalues of P are 1, 0.9772, 0.1228, which can guarantee consensus of x(s) but P is not a row-stochastic matrix.

B. An extension to multidimensional affine dynamics
Our results in Section III can be extended to multidimensional affine dynamics in which the state of each agent is a m-dimensional vector. The dynamics is where X(s) ∈ R n×m is the state matrix, P (s) ∈ R n×n is still an interaction matrix, C ∈ R m×m is an interdependency matrix, and U (s) ∈ R n×m is an input vector.
The system (35) seems complex, however it can be transformed to one dimensional system (2) by the following way: Given a pair of matrices A ∈ R n×m , B ∈ R p×q , their Kronecker product is defined by for any s ≥ 0, 1 ≤ i ≤ n, and 1 ≤ j ≤ m. Let be the vector in R nm transformed from the matrices X(s) and U (s) respectively. By (36) we have which implies y(s + 1) = (1 − a(s))y(s) + a(s)[Q(s)y(s) + v(s)].
The system (37) has the same form as the system (2), so the results in Section III can be applied to the multidimensional affine dynamics.

C. SA Friedkin-Johnsen model over time-varying interaction network
The Friedkin-Johnsen (FJ) model proposed by [11] considers a community of n social actors (or agents) whose opinion column vector is x(s) = (x 1 (s), . . . , x n (s)) ⊤ ∈ R n at time s. The FJ model also contains a row-stochastic matrix of interpersonal influences P ∈ R n×n and a diagonal matrix of actors' susceptibilities to the social influence Λ ∈ R n×n with 0 n×n ≤ Λ ≤ I n . The state of the FJ model is updated by By [23], if 0 n×n ≤ Λ < I n , then However, if the interpersonal influences are affected by noise, then the system (37) may not converge. The FJ model (37) was extended to the multidimensional case in [12], [23]. The multidimensional FJ model still contains n individuals, but each individuals has beliefs on m truth statements. Let X(s) ∈ R n×m be the matrix of n individuals' beliefs on m truth statements at time s. Following [12], it is updated by for s = 0, 1, . . . , where Λ, P ∈ R n×n are the same matrices in (37), and C ∈ R m×m is a row-stochastic matrix of interdependencies among the m truth statements. The convergence of system (39) has been analyzed in [23]. Similar to (37) it is easy to see that if system (39) is affected by noise, then it will not converge. We will adopt the stochastic-approximation method to smooth the effects of the noise.
Proposition IV.1: Consider the system X(s + 1) = (1 − a(s))X(s) + a(s)[Λ(s)P (s)X(s)C(s) ⊤ + (I n − Λ(s))X(0)], (40) for s = 0, 1, . . ., where Λ(s) ∈ R n×n , P (s) ∈ R n×n and C(s) ∈ R m×m are independent matrix sequence with invariant expectation Λ, P , and C respectively. Suppose P and C are row-stochastic matrix, and 0 n×n ≤ Λ < I n , and the gain function a(s) satisfies (A2). Then for any initial state, X(s) converges to X * in mean square, where X * is the unique solution of the equation Proof. Since P and C are row-stochastic matrices, P ⊗ C is still a row-stochastic matrix. Together with the condition that 0 n×n ≤ Λ < I n , we have that the sum of each row of (ΛP ) ⊗ C is less than 1. Thus, using the Gershgorin disk theorem we obtain ρ max ((ΛP )⊗C) < 1. and v := Ev(s). By Proposition III.1 and the transformation from (35) to (37), we obtain that y(s) converges to (I mn − Q) −1 v in mean square. It remains to discuss the relation between (I mn − Q) −1 v and X * . Let y * := (X * 11 , . . . , X * 1m , . . . , X * n1 , . . . , X * nm ) ⊤ ∈ R nm .
By (41), similar to (37) we have y * = Qy * + v, which has a unique solution y * = (I mn − Q) −1 v since I mn − Q is an invertible matrix by ρ max (Q) < 1. Thus, with the fact that y(s) converges to (I mn − Q) −1 v in mean square we obtain that X(s) converges to X * in mean square.
Remark 4: According to Theorem III.1 and Proposition III.1, the conditions of Λ(s), P (s) and C(s) in Proposition IV.1 can be further relaxed for convergence, such as P and C are not row-stochastic matrices, and 0 n×n ≤ Λ < I n may be extended to Λ < 0 n×n or Λ ≥ I n .

V. CONCLUSION
In this paper, we consider a time-varying affine dynamical system, where the state of the system features persistent oscillation and does not converge. We propose a stochastic approximation-based approach and obtain necessary and sufficient conditions to guarantee mean-square convergence. Our theoretical results largely extend the conditions on the spectrum of the expectation of the system matrix and thus can be applied in a much broader range of applications. We also derived the convergence rate of the system. To illustrate the theoretical results, we applied them in two different applications: group consensus in multi-agent systems and FJ model with time-varying interactions in social networks.
This work leaves various problems for future research. First, the system matrix and input are assumed to have constant expectations in this paper. However, it would be more interesting, yet challenging, to study systems with timevarying expectation of the system matrix and input. Second, we only considered basic affine systems in this paper. How and whether the proposed framework can be extended to nonlinear system are important and intriguing questions. Finally, we have illustrated our results in two different application scenarios; there are other possible applications such as gossip algorithms for consensus.
where b s ≥ 0 and a s ∈ [0, 1) are real numbers. If ∞ s=1 a s = ∞ and lim s→∞ b s /a s = 0, then lim s→∞ y s = 0 for any y 1 ≥ 0.
Proof: Repeating (42) we obtain Here we define s t=i (·) := 1 when i > s. Since ∞ t=1 a t = ∞, we have ∞ t=1 (1 − a t ). To obtain our result, we just need to prove that Since lim s→∞ b s /a s = 0, for any real number ε > 0, there exists an integer s * > 0 such that b s ≤ εa s when s ≥ s * . Thus, where the first equality uses the equality (54). Let ε decrease to 0, then (44) is followed by (43).
Then by (51) where the last equality uses the classical equality with {c t } being any complex numbers, which can be obtained by induction. Here we define s2 Hence, from (53), if y m1 (0) = which implies lim s→∞ E x(s) 2 2 = ∞. Case II: ρ max (P ) = 1. Under this case we consider the following three situations: (a) There is an eigenvalue λ j (P ) = 1 + Im(λ j (P ))i with Im(λ j (P )) = 0, where Im(λ j (P )) denotes the imaginary part of λ j (P ). Similar to (52), we can choose a row D j ′ of D which is equal to (0, . . . , 0, λ j (P ), 0, . . . , 0). Similar to (53), we have We write where r t = 1 + a 2 (t)Im 2 (λ j (P )) and Assume y j ′ (0) = v j ′ 1−λj (P ) . Since ∞ t=0 a(t) = ∞, equations (56), (58), and (57) imply Next we consider the convergence of x(s). Because x(s) = H −1 y(s), using Jensen's inequality we have where σ n (H −1 ) = inf x 2=1 H −1 x 2 denotes the least singular value of H −1 . Because H −1 is invertible, we have σ n (H −1 ) > 0. Hence, by (59) and (60), we obtain lim s→∞ lim s2→∞ E x(s 2 ) − x(s) 2 2 > 0. By the Cauchy criterion (see [16, page 58]), x(s) is not mean square convergent. (b) The geometric multiplicity of the eigenvalue 1 is less than its algebraic multiplicity. By (a), we only need to consider the case when any eigenvalue of P with 1 as real part has zero imaginary part. Thus, the Jordan normal form D contains a Jordan block with m j ≥ 2. Let j ′ be the row index of D corresponding to the second line from the bottom of J j . It can be computed that Since ∞ k=0 a(k) = ∞, from (51), there are some initial states such that lim s→∞ |E[y j ′ (s)]| = ∞, which is followed by lim s→∞ E x(s) 2 2 = ∞. (c) There is a left eigenvector ξ (row vector) of P corresponding to the eigenvalue 1 such that ξu = 0. By (2)  = ξEx(s) + a(s)ξu ii) It can be obtained by the similar method as i).

APPENDIX D PROOF OF THEOREM III.4
We prove our result by contradiction: Suppose that there exists a real number sequence {a(s)} s≥0 independent with {x(s)} such that We assert that lim s→∞ a(s) = 0. This assertion will be proved still by contradiction: Assume that there exists a subsequence {a(s k )} k≥0 which does not converge to zero. Let P (s) := P (s) − P and u(s) = u(s) − u for any s ≥ 0, then by (2), (A1) and (27) we have E x(s k + 1) − b 2 2 | x(s k ) = E ξ + a(s k ) P (s k )x(s k ) + u(s k ) 2 2 | x(s k ) = ξ 2 2 + a 2 (s k )E P (s k )x(s k ) + u(s k ) where ξ := (1 − a(s k ))x(s k ) + a(s k )(P x(s k ) + u) − b.
From (62) we know that E x(s k + 1) − b 2 2 will not converge to 0 as k grows to infinity, which is in contradiction with (61).