# A Random Adaptation Perspective on Distributed Averaging

Rohit Parasnis  Department of Electrical and Computer Engineering, University
of California San Diego  Ashwin Verma  Department of Electrical and Computer
Engineering, University of California San Diego  Massimo Franceschetti
Department of Electrical and Computer Engineering, University of California
San Diego  Behrouz Touri Email:
<EMAIL_ADDRESS>Department of Electrical and
Computer Engineering, University of California San Diego

###### Abstract

We propose a random adaptation variant of time-varying distributed averaging
dynamics in discrete time. We show that this leads to novel interpretations of
fundamental concepts in distributed averaging, opinion dynamics, and
distributed learning. Namely, we show that the ergodicity of a stochastic
chain is equivalent to the almost sure (a.s.) finite-time agreement attainment
in the proposed random adaptation dynamics. Using this result, we provide a
new interpretation for the absolute probability sequence of an ergodic chain.
We then modify the base-case dynamics into a time-reversed inhomogeneous
Markov chain, and we show that in this case ergodicity is equivalent to the
uniqueness of the limiting distributions of the Markov chain. Finally, we
introduce and study a time-varying random adaptation version of the Friedkin-
Johnsen model and a rank-one perturbation of the base-case dynamics.

##  1 INTRODUCTION

Distributed averaging is a central mechanism to information mixing in
distributed optimization [1, 2], distributed parameter estimation and signal
processing [3, 4, 5, 6, 7, 8, 9], decentralized control of robotic networks
[10], and opinion dynamics [11, 12, 13, 14, 15, 16]. Hence, a variety of
distributed averaging dynamics have been studied till date within different
mathematical frameworks [17, 18, 19].

In particular, distributed averaging algorithms over time-varying networks are
often analyzed using chains/sequences of stochastic matrices (a class of non-
negative matrices). Several properties of such chains, such as ergodicity and
reciprocity, have been studied in detail [20, 21, 22, 23, 24, 25, 26, 27].
Despite this abundance of literature, interpretations of some key concepts in
this area, such as Kolmogorov’s absolute probability sequences, have remained
elusive.

On the other hand, stochastic matrices can be interpreted by noting that every
row of such matrices gives the probability mass function of a discrete random
variable. Thus motivated, we introduce a random adaptation framework in which
each entry of a stochastic matrix denotes the probability that a node $i$
adapts to the state of a node $j$, rather than the weight assigned by $i$ to
$j$. That is, we propose random adaptation variants of some classical
discrete-time distributed averaging dynamics. We then study the proposed
dynamics to interpret in a new light certain concepts that are central to the
study of stochastic chains and averaging dynamics. Our contributions are as
follows:

  1. 1.

An Interpretation of Ergodicity:

We show that the classical notion of ergodicity is equivalent to an intuitive
condition of agreement in finite time in the random adaptation dynamics. This
differs from the classical scenario of distributed averaging dynamics, where
ergodicity does not necessarily ensure finite-time agreement.

  2. 2.

An Interpretation of Absolute Probability Sequence: Using the above
characterization of ergodicity, we interpret the absolute probability sequence
of an ergodic chain as the limiting probability distribution of the common
value attained by all the nodes in the proposed dynamics.

  3. 3.

Ergodicity vis-a-vis Uniqueness of the Limiting Distribution: We propose a
time-reversed, transposed variant of the aforementioned dynamics and use it to
show that the limiting distribution of the state vector is unique if and only
if the given stochastic chain is ergodic. This leads to a new insight:
absolute probability sequences are to ergodic chains what stationary
distributions are to regular stochastic matrices.

  4. 4.

Asymptotic Behaviors of Variants: Finally, we discuss the random adaptation
interpretation of the well-known Friedkin-Johnsen model of opinion dynamics
[28] as well as rank-one perturbations of the base-case dynamics. In both the
cases, we study the limiting probability distributions of the agents’
states/opinions.

In addition, in Section 5 we provide numerical examples to illustrate and
interpret some of our results on the base-case dynamics as well as on our
random adaptation variants of the Friedkin-Johnsen model.

Related works: This paper is closely related to the voter model [29, 30] and
its many extensions (e.g., [31, 32, 33, 34, 35, 36]), which apply to social
networks and describe the processes of individuals randomly adapting to their
neighbors’ political preferences. However, our work differs from these prior
works in at least two fundamental ways. First, the voter model and most of its
variants assume a limit on the number of agents that update their opinions
synchronously, whereas our model does not make any assumptions on the level of
synchrony among the agents’ updates (note that our update rules can be used to
prevent an arbitrary set of agents from updating their opinions by simply
setting the corresponding diagonal entries of the associated stochastic
matrices to 1). For instance, the voter model with zealots [37] differs from
our random adaptation variant of the Friedkin-Johnsen model in that, in the
former, at most one agent updates its state in any given update period.
Second, unlike this paper, none of the prior works aims to unravel the
properties of the stochastic chains or matrices associated with the random
dynamics proposed therein.

Besides, some of our results may be related to the well-studied duality
between coalescing random walks and voter dynamics [38, 39].

Notation:  In this paper $\mathbb{N}:=\\{1,2,\ldots\\}$,
$\mathbb{N}_{0}:=\mathbb{N}\cup\\{0\\}$, $\mathbb{R}$ denotes the set of real
numbers, $\mathbb{R}^{n}$ denotes the set of $n$-dimensional real-valued
column vectors, and $\mathbb{R}^{n\times n}$ denotes the set of $n\times n$
real-valued matrices. For $n\in\mathbb{N}$, we let
${[n]:=\\{1,2,\ldots,n\\}}$. For a vector
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{v}}\in\mathbb{R}^{n}$,
$v_{i}$ denotes its $i$th entry, and $b_{ij}$ denotes the $(i,j)$th entry of a
matrix ${B\in\mathbb{R}^{n\times n}}$. All matrix and vector inequalities are
assumed to hold entry-wise.

For a given $n\in\mathbb{N}$ whose value is clear from the context, let $O,I$
denote the $n\times n$ matrix with all zero entries and the identity matrix,
respectively. We denote the column vectors with all zero entries and all one
entries in $\mathbb{R}^{n}$ by $\mathbf{0}$ and $\mathbf{1}$, respectively.
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{e}}^{(i)}\in\mathbb{R}^{n}$
denotes the $i$th canonical basis vector.

For a matrix $A\in\mathbb{R}^{n\times n}$ and a set $S\subseteq[n]$, let
$A_{S}$ be the principal sub-matrix of $A$ corresponding to the rows and
columns indexed by $S$. Let $\bar{S}:=[n]\setminus S$ be the complement of $S$
with respect to $[n]$, and for sets $S,T\subseteq[n]$, let $A_{ST}$ denote the
sub-matrix of $A$ corresponding to the rows indexed by $S$ and the columns
indexed by $T$.

We say
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{v}}\in\mathbb{R}^{n}$
is stochastic if $\mathbf{v}\geq\mathbf{0}$ and $\mathbf{1}^{T}\mathbf{v}=1$,
where the superscript T denotes transposition. A matrix
$A\in\mathbb{R}^{n\times n}$ is called row-stochastic or simply stochastic if
each row of $A$ is stochastic. We let $\mathcal{P}_{n}$ (respectively,
$\mathcal{P}_{n\times n}$) denote the set of all stochastic vectors
(respectively, matrices) in $\mathbb{R}^{n}$ (respectively,
$\mathbb{R}^{n\times n}$). For a sequence $\\{A(t)\\}_{t=0}^{\infty}$ and
indices $t_{1}<t_{2}$, we let ${A(t_{2}:t_{1}):=A(t_{2}-1)A(t_{2}-2)\cdots
A(t_{1})}$ with the convention that $A(t:t):=I$ for all $t\in\mathbb{N}_{0}$.

All random objects in this work are defined with respect to an underlying
probability space $(\Omega,\mathcal{B},\text{Pr})$. With an abuse of
terminology, by
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}Z}(t)\in\mathbb{R}^{n}$
for a random process
$\\{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}Z}(t)\\}$
we mean
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}Z}(t,\omega)\in\mathbb{R}^{n}$
for all $t\in\mathbb{N}_{0}$ and $\omega\in\Omega$. We use $\mathbb{E}[\cdot]$
to denote the expectation operator with respect to this probability space. We
use the notation $\widehat{Z}$ to denote the expectation of a random
variable/matrix/vector $Z$.

##  2 RANDOM ADAPTATION DYNAMICS

In distributed averaging dynamics, we are given a sequence of stochastic
matrices
$\\{{Q}(t)\\}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}_{t=0}^{\infty}}$,
and we are interested in studying the dynamics

$\displaystyle{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{x}}(t+1)=Q(t){\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{x}}(t),$
(1)

for some initial time $t_{0}\in\mathbb{N}_{0}$ and initial state
$\mathbf{x}(t_{0})\in\mathbb{R}^{n}$. As mentioned in the introduction, each
row of $Q(t)$ is a stochastic vector that can be viewed as the probability
mass function of a certain random variable taking $n$ values. Our random
adaptation viewpoint formulates a very natural sequence of random variables
that exhibits this behavior. Consider $n$ agents assuming a random state
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}x}_{i}(t)\in\mathbb{R}$
(more precisely,
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}x}_{i}(t,\omega)\in\mathbb{R}$
where $\omega\in\Omega$) evolving over discrete time $t\in\mathbb{N}_{0}$. Let
the starting time $t_{0}\in\mathbb{N}_{0}$ and the initial states
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{x}}(t_{0})\in\mathbb{R}^{n}$
be an arbitrary deterministic vector. For a given sequence $\\{Q(t)\\}$ of
stochastic matrices, the random adaptation scheme is defined as follows: At
time $t\geq t_{0}$, agent $i$ adopts agent $j$’s state with probability
$q_{ij}(t)$ independently of other agents as well as every agent’s past
choices and states, i.e.,
${\text{Pr}({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}x}_{i}(t+1)={\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}x}_{j}(t)\mid{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{x}}(t),\ldots,{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{x}}(t_{0}))=q_{ij}(t)}$
for all $i,j\in[n]$. Therefore, we can write

$\displaystyle{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{x}}(t+1)=A(t){\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{x}}(t),$
(2)

where
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{x}}(t)\in\mathbb{R}^{n}$
is the random state vector (whose $i$-th entry is
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}x}_{i}(t)$)
and $A(t)\in\mathbb{R}^{n\times n}$ is a binary random stochastic matrix,
i.e., $\\{a_{ij}(t):i,j\in[n]\\}$ are Bernoulli random variables with
parameters $\widehat{a}_{ij}(t)=q_{ij}(t)$ for all $i,j\in[n]$.

We now observe a few important properties of (2): (i) The random process
$\\{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{x}}(t)\\}_{t=0}^{\infty}$
is a non-homogeneous Markov chain with state space size at most $n^{n}$ as the
state of each agent at every time instant is in $\\{x_{i}(t_{0})\mid
i\in[n]\\}$. (ii) For each $t\in\mathbb{N}_{0}$, the rows of $A(t)$ are
independent random vectors. (iii) The random matrices
$\\{A(t)\\}_{t=0}^{\infty}$ are independent and hence, for each
$t\in\mathbb{N}$, $A(t)$ is independent of
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{x}}(t)$.

##  3 MAIN RESULTS

We first define two properties that will be shown to be closely related. The
first property relates to stochastic chains.

######  Definition 1 (Ergodicity [21, 23]).

A deterministic (non-random) stochastic chain $\\{Q(t)\\}_{t=0}^{\infty}$ is
said to be ergodic if, for every $t_{0}\in\mathbb{N}_{0}$, there exists a
vector
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\boldsymbol{\psi}}(t_{0})\in\mathcal{P}_{n}$
such that
$\lim_{t\to\infty}Q(t:t_{0})=\mathbf{1}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\boldsymbol{\psi}}^{T}(t_{0})$.

Put differently, a stochastic chain $\\{Q(t)\\}_{t=0}^{\infty}$ is called
ergodic if every backward matrix product $Q(t:t_{0})$ converges to a rank-one
matrix that has identical rows.

The second property relates to the random adaptation dynamics (2).

######  Definition 2 (Finite Agreement).

We say that the adaptation dynamics (2) has an a.s. finite agreement property
if for all initial times $t_{0}\in\mathbb{N}_{0}$ and initial states
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{x}}(t_{0})\in\mathbb{R}^{n}$,
there exist a random scalar $y=y(t_{0},\mathbf{x}(t_{0}))$ and a random
(stopping) time $T\geq t_{0}$ such that $\mathbf{x}(t)=y\mathbf{1}$ for all
$t\geq T$.

In other words, the random adaptation dynamics (2) has the finite agreement
property if at some time after the initiation of the dynamics, all the agents
adopt the same state.

Note that the ergodicity of $\\{Q(t)\\}$ does not imply finite agreement for
the deterministic dynamics (1). For example, suppose $n=2$, let
$\mathbf{x}(0)={\mathbf{e}}^{(1)}$, and consider the static chain defined by
$Q(t)=\begin{pmatrix}p&1-p\\\ 1-q&q\\\ \end{pmatrix}$ for all
$t\in\mathbb{N}_{0}$, where $p,q\in(0,1)$. Then it can be verified that
$\\{Q(t)\\}_{t=0}^{\infty}$ is ergodic. However, we also have
${x_{1}(t)-x_{2}(t)=(p+q-1)^{t}}$ for all $t\in\mathbb{N}$, which implies that
no agreement is reached in finite time unless $p+q=1$.

On the contrary, if
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{x}}(t_{0})\in\\{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{e}}^{(1)},{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{e}}^{(2)}\\}$
the random adaptation variation (2) of the same static chain ensures that the
two agents reach an agreement at time ${T:=\inf\\{t\geq t_{0}:x_{1}(t)\oplus
x_{2}(t)=0\\}}$, where $\oplus$ denotes the exclusive OR operation. Since $T$
is a geometric random variable with the parameter ${p(1-p)+q(1-q)>0}$, it is
finite a.s. In fact, even for $n\neq 2$, every ergodic chain guarantees finite
agreement for all initial conditions, as we now show.

######  Theorem 1.

The random adaptation dynamics (2) has the finite agreement property if and
only if ${\\{\widehat{A}(t)\\}_{t=0}^{\infty}=\\{Q(t)\\}_{t=0}^{\infty}}$ is
an ergodic chain.

###### Proof.

We establish ergodicity first as a sufficient condition and then as a
necessary condition for a.s. finite agreement with an arbitrary initial
condition
$(t_{0},{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{x}}(t_{0}))$.

#### Proof of Sufficiency

It suffices to show that an agreement occurs in the network infinitely often
a.s., because once an agreement is reached, the state vector stops evolving in
time.

We first note that by Definition 1, there exists a
${{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\boldsymbol{\psi}}(t_{0})\in\mathcal{P}_{n}}$
such that
${\lim_{t\to\infty}Q(t:t_{0})=\mathbf{1}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\boldsymbol{\psi}}^{T}(t_{0})}$
a.s. As
${{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\boldsymbol{\psi}}^{T}(t_{0})\mathbf{1}=1}$,
there exists an index $\ell(t_{0})\in[n]$ such that
${{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\psi}_{\ell(t_{0})}(t_{0})\geq\frac{1}{n}}$,
which implies that
${\lim_{t\to\infty}Q_{i\ell(t_{0})}(t:t_{0})\geq\frac{1}{n}}$ for all
$i\in[n]$. Consequently, there exists a time $t_{1}\geq t_{0}$ such that
$Q_{i\ell(t_{0})}(t_{1}:t_{0})\geq\frac{1}{2n}$ for all $i\in[n]$. By Lemma 1,
this implies that
$\text{Pr}\left(A_{[n]\\{\ell(t_{0})\\}}(t_{1}:t_{0})=\mathbf{1}\right)\geq\left(\frac{1}{2n}\right)^{n}$.
Since $A(t_{1}:t_{0})\in\mathcal{P}_{n\times n}$ is binary, it follows that
${\text{Pr}(A(t_{1}:t_{0})=\mathbf{1}({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{e}}^{\ell(t_{0})})^{T})\geq\left(\frac{1}{2n}\right)^{n}}$.

As $t_{0}$ is arbitrary, we can repeat the above analysis with different
starting times and obtain an increasing sequence of times
$\\{t_{k}\\}_{k=0}^{\infty}$ such that
${\text{Pr}(A(t_{k+1}:t_{k})=\mathbf{1}({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{e}}^{\ell(t_{k})})^{T})\geq\left(\frac{1}{2n}\right)^{n}}$.
Since
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{x}}(t_{k+1})=A(t_{k+1}:t_{k}){\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{x}}(t_{k})$,
this further implies that
$\text{Pr}({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{x}}(t_{k+1})={\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}x}_{\ell}(t_{k})\mathbf{1})\geq\left(\frac{1}{2n}\right)^{n}$.
As a result, letting $C_{k}$ denote the event that an agreement exists in the
network at time $t_{k}\geq t_{0}$, we have
$\sum_{k=0}^{\infty}\text{Pr}(C_{k})=\infty$. Now,
$\\{C_{k}\\}_{k=0}^{\infty}$ are independent events because
$\\{A(t)\\}_{t=0}^{\infty}$ are independent and
$\\{[t_{k},t_{k+1}-1]:k\in\mathbb{N}_{0}\\}$ are disjoint intervals.
Therefore, by the Second Borel-Cantelli Lemma [40, Theorem 2.3.6], infinitely
many events among $\\{C_{k}\\}_{k=0}^{\infty}$ occur a.s., which proves the
assertion.

#### Proof of Necessity

Suppose there exist
${T=T(t_{0},{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{x}}(t_{0}))<\infty}$
and
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}y}={\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}y}(t_{0},x(t_{0}))\in\mathbb{R}$
such that
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{x}}(t)={\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}y}\mathbf{1}$
a.s. for all $t\geq T$. Then
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{x}}(t)=A(t:t_{0}){\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{x}}(t_{0})$
implies that
${\lim_{t\to\infty}A(t:t_{0}){\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{x}}(t_{0})={\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}y}\mathbf{1}}$
a.s.

Besides, we know that
$\|{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{x}}(t)\|_{\infty}\leq\|{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{x}}(t_{0})\|_{\infty}$
for all ${t\geq t_{0}}$. Therefore, by the Dominated Convergence Theorem [40,
Theorem 1.6.7], we have

$\displaystyle\mathbb{E}\left[{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}y}\right]\mathbf{1}=\mathbb{E}\left[\lim_{t\to\infty}A(t:t_{0}){\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{x}}(t_{0})\right]$
(3)
$\displaystyle=\lim_{t\to\infty}\mathbb{E}[A(t:t_{0}){\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{x}}(t_{0})]=\lim_{t\to\infty}\widehat{A}(t:t_{0}){\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{x}}(t_{0}),$
(4)

where the last equality follows from the independence of
$\\{A(t)\\}_{t=0}^{\infty}$. As a result,
${\lim_{t\to\infty}Q(t:t_{0}){\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{x}}(t_{0})=\widehat{y}\mathbf{1}}$.
For the initial condition
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{x}}(t_{0})={\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{e}}^{(i)}$,
this implies that the $i$th column of $Q(t:t_{0})$ converges to
$\psi_{i}\mathbf{1}$ for some scalar $\psi_{i}\in\mathbb{R}$ and hence,
$\lim_{t\to\infty}Q(t:t_{0})=\mathbf{1}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\boldsymbol{\psi}}^{T}$
for some vector
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\boldsymbol{\psi}}={\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\boldsymbol{\psi}}(t_{0})\in\mathcal{P}_{n}$.
The latter step follows from the fact that the set of row-stochastic matrices
is a closed semigroup (under matrix multiplication).

######  Remark 1.

Theorem 1 enables us to comment further on ergodic chains. To elaborate, we
can repeat some of the arguments used in the proof above to show that if
$\\{Q(t)\\}_{t=0}^{\infty}$ is ergodic, then for all
${(t_{0},{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{x}}(t_{0}))\in\mathbb{N}_{0}\times\mathbb{R}^{n}}$,
there a.s. exists a
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\boldsymbol{\pi}}(t_{0})\in\mathcal{P}^{n}$
such that
$\lim_{t\to\infty}A(t:t_{0})=\mathbf{1}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\boldsymbol{\pi}}^{T}(t_{0})$
for all $t_{0}\in\mathbb{N}_{0}$. Moreover,
$\\{A(t)\\}_{t=0}^{\infty}\in\mathcal{P}_{n\times n}$ being binary implies
that
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\boldsymbol{\pi}}(t_{0})$
is binary, i.e.,
${{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\boldsymbol{\pi}}(t_{0})\in\\{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{e}}^{(i)}:i\in[n]\\}}$.
Finally, taking expectations on both sides yields
${\lim_{t\to\infty}\widehat{A}(t:t_{0})=\mathbf{1}\widehat{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\boldsymbol{\pi}}}^{T}(t_{0})}$,
i.e.,
${\lim_{t\to\infty}Q(t:t_{0})=\mathbf{1}\widehat{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\boldsymbol{\pi}}}^{T}(t_{0})}$
where
${\widehat{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\boldsymbol{\pi}}}^{T}(t_{0})\in\mathcal{P}_{n}}$.
Interestingly, for the chain $\\{Q(t)\\}_{t=0}^{\infty}$, one can verify that
$\\{\widehat{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\boldsymbol{\pi}}}(t)\\}_{t=0}^{\infty}$
forms what we call an absolute probability sequence, a concept defined below
and introduced by Kolmogorov in [41].

######  Definition 3 (Absolute Probability Sequence).

For a deterministic stochastic chain $\\{Q(t)\\}_{t=0}^{\infty}$, a sequence
of stochastic vectors
$\\{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\boldsymbol{\psi}}(t)\\}_{t=0}^{\infty}$
is said to be an absolute probability sequence if
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\boldsymbol{\psi}}^{T}(t+1)Q(t)={\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\boldsymbol{\psi}}^{T}(t)$
for all $t\geq 0$.

We now connect this novel concept with the dynamics (2).

######  Theorem 2.

Suppose that $\\{Q(t)\\}_{t=0}^{\infty}=\\{\widehat{A}(t)\\}_{t=0}^{\infty}$
is ergodic for the dynamics (2), with an absolute probability sequence
$\\{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\boldsymbol{\psi}}(t)\\}_{t=0}^{\infty}=\\{\widehat{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\boldsymbol{\pi}}}(t)\\}_{t=0}^{\infty}$,
where
$\\{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\boldsymbol{\pi}}(t)\\}_{t=0}^{\infty}$
is an absolute probability sequence for $\\{A(t)\\}_{t=0}^{\infty}$. Let
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}y}={\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}y}(t_{0},{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{x}}(t_{0}))$
be the agreed value of all the agents, i.e.,
$\lim_{t\to\infty}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{x}}(t)={\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}y}\mathbf{1}$
a.s for initial conditions
${(t_{0},{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{x}}(t_{0}))\in\mathbb{N}_{0}\times\mathbb{R}^{n}}$
such that
$\\{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}x}_{i}(t_{0})\\}_{i=1}^{n}$
are all distinct. Then the probability distribution of
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}y}$
is given by
${p_{i}(t_{0}):=\text{Pr}({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}y}={\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}x}_{i}(t_{0}))=\psi_{i}(t_{0})}$
for all ${i\in[n]}$.

###### Proof.

By Remark 1, we almost surely have
${\lim_{t\to\infty}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{x}}(t)=\lim_{t\to\infty}A(t:t_{0}){\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{x}}(t_{0})=\mathbf{1}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\boldsymbol{\pi}}^{T}(t_{0}){\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{x}}(t_{0})}$.
Thus,
${{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}y}={\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\boldsymbol{\pi}}^{T}(t_{0}){\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{x}}(t_{0})}$,
which implies that
${\widehat{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}y}}={\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\widehat{\boldsymbol{\pi}}}^{T}(t_{0}){\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{x}}(t_{0})}=\sum_{i=1}^{n}\psi_{i}(t_{0})x_{i}(t_{0})$.

On the other hand, the definition of expectation implies that
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\widehat{y}}=\sum_{i=1}^{n}p_{i}(t_{0})x_{i}(t_{0})$.

Hence,
${\sum_{i=1}^{n}\psi_{i}(t_{0}){\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}x}_{i}(t_{0})=\sum_{i=1}^{n}p_{i}(t_{0}){\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}x}_{i}(t_{0})}$.
Since this holds for all
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{x}}(t_{0})\in\mathbb{R}^{n}$,
we must have $p_{i}(t_{0})=\psi_{i}(t_{0})$ for all $i\in[n]$.

##  4 VARIANTS AND EXTENSIONS

###  4.1 Time-Reversed Non-homogeneous Markov Chains

Let $\\{A(t)\\}_{t=0}^{\infty}$ be a random sequence of independent binary
matrices, and let
${\\{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{e}}^{(i)}:i\in[n]\\}}$
be the state space of a time-reversed Markov chain whose probability
transition matrix is $Q(t):=\widehat{A}(t)$ at time $t$. To be precise, the
Markov chain is a random process
$\\{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{z}}(t)\\}$
that starts at an arbitrary time instant $t_{\infty}\in\mathbb{N}$ with an
arbitrary probability distribution given by
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{p}}_{\infty}\in\mathcal{P}_{n}$
(where
${({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{p}}_{\infty})_{i}:=\text{Pr}({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{z}}(t_{\infty})={\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{e}}^{(i)})}$
and evolves backwards in time with
${\text{Pr}({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{z}}(t)={\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{e}}^{(j)}\mid{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{z}}(t+1)={\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{e}}^{(i)})=q_{ij}(t)}$
for all ${t<t_{\infty}}$. Equivalently,

$\displaystyle{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{z}}^{T}(t)={\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{z}}^{T}(t+1)A(t)$
(5)

for all $t\in\\{t_{\infty}-1,t_{\infty}-2,\ldots,0\\}$. Note that (5) is
nothing but a time-reversed, transposed variant of (2).

To relate these dynamics to time-homogeneous chains, recall that the limiting
probability distribution of a regular Markov chain is a stationary
distribution independent of the initial distribution [42]. Analogously, we
ask, is the limiting distribution of a time-reversed inhomogeneous Markov
chain an absolute probability sequence of the associated stochastic chain that
is independent of
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{p}}_{\infty}$?
As we show, the answer is yes if and only if the stochastic chain is ergodic.

######  Theorem 3.

Consider the dynamics (5) with a variable starting time $t_{\infty}$. Let
$\\{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\boldsymbol{\psi}}(t)\\}_{t=0}^{\infty}$
be an absolute probability sequence for $\\{Q(t)\\}_{t=0}^{\infty}$. Then the
limiting distribution
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{p}}(t):=\sum_{i=1}^{n}p_{i}(t){\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{e}}^{(i)}\in\mathcal{P}_{n}$
with
$p_{i}(t):=\lim_{t_{\infty}\to\infty}\text{Pr}({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{z}}(t)={\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{e}}^{(i)})$
exists and is invariant w.r.t. the initial distribution
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{p}}_{\infty}$
for all $t\in\mathbb{N}_{0}$ if and only if $\\{Q(t)\\}_{t=0}^{\infty}$ is
ergodic, in which case
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{p}}(t)={\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\boldsymbol{\psi}}(t)$
for all $t\in\mathbb{N}_{0}$.

###### Proof.

We first note that for all $t\leq t_{\infty}$, we have
$\text{Pr}({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{z}}(t)={\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{e}}^{(i)})=\mathbb{E}[{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}z}_{i}(t)]={\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\widehat{z}}_{i}(t)$
for all ${i\in[n]}$, which means that
$p_{\infty}={\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\widehat{\mathbf{z}}}(t_{\infty})$
and more generally that the probability distribution of
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{z}}(t)$
is determined by
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\widehat{\mathbf{z}}}^{T}(t)={\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\widehat{\mathbf{z}}}^{T}(t_{\infty})\widehat{A}(t_{\infty}:t)={\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{p}}_{\infty}^{T}Q(t_{\infty}:t)$
for all $t\leq t_{\infty}$. Thus,
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{p}}^{T}(t)={\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{p}}_{\infty}^{T}\lim_{t_{\infty}\to\infty}Q(t_{\infty}:t)$
(if the limit exists). Using this, we first establish the sufficiency of
ergodicity and then its necessity for the invariance assertion to hold.

If $\\{Q(t)\\}_{t=0}^{\infty}$ is ergodic, then
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{p}}^{T}(t)$
is given by
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{p}}_{\infty}^{T}\lim_{t_{\infty}\to\infty}Q(t_{\infty}:t)\stackrel{{\scriptstyle(a)}}{{=}}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{p}}_{\infty}^{T}\mathbf{1}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\boldsymbol{\psi}}^{T}(t)\stackrel{{\scriptstyle(b)}}{{=}}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\boldsymbol{\psi}}^{T}(t)$,
where $(a)$ follows from Remark 1 and $(b)$ holds because
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{p}}_{\infty}\in\mathcal{P}_{n}$.
Since
$\\{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\boldsymbol{\psi}}(t)\\}_{t=0}^{\infty}$
are unique (see [20], Theorem 1), it follows that
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{p}}(t)={\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\boldsymbol{\psi}}(t)$
a.s. does not vary with
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{p}}_{\infty}$.

On the other hand, if $\\{Q(t)\\}_{t=0}^{\infty}$ is not ergodic, then there
exists a $t_{0}\in\mathbb{N}_{0}$ such that either
${\lim_{t_{\infty}\to\infty}Q(t_{\infty}:t_{0})}$ does not exist (in which
case there is nothing to prove), or there exists an index $\ell\in[n]$ such
that the column vector
${{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{v}}:=\lim_{t_{\infty}\to\infty}Q_{[n]\,\\{\ell\\}}(t_{\infty}:t_{0})}$
satisfies
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{v}}\neq\alpha\mathbf{1}$
for all ${\alpha\in\mathbb{R}}$. Therefore, we can write
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{v}}=\alpha\mathbf{1}+\beta{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{w}}$
for some $\alpha,\beta>0$ and some
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{w}}$
with
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{w}}^{T}\mathbf{1}=0$.
Note that
${{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{w}}^{T}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{v}}\not=0}$.
Note also that for small enough $\tilde{\beta}>0$,
$\tilde{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{w}}}={\frac{1}{n}\mathbf{1}+\tilde{\beta}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{w}}\in\mathcal{P}_{n}}$.
Now, for
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{p}}_{\infty}=\frac{1}{n}\mathbf{1}$
and
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{p}}_{\infty}=\tilde{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{w}}}$,
the value of
${p}_{\ell}(t_{0})=\left({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{p}}_{\infty}^{T}\lim_{t_{\infty}\to\infty}A(t_{\infty}:t_{0})\right)_{\ell}$
would be
$\frac{1}{n}\mathbf{1}^{T}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{v}}$
and
$\frac{1}{n}\mathbf{1}^{T}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{v}}+\tilde{\beta}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{w}}^{T}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{v}}$,
respectively, which along with
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{w}}^{T}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{v}}\neq
0$ violates the invariance condition.

Theorem 3 also shows that, just as stationary distributions are the limiting
probability distributions of Markov chains defined by regular matrices,
absolute probability sequences can be interpreted as the limiting
distributions of time-reversed Markov chains defined by ergodic stochastic
chains.

###  4.2 Random Adaptation Approach to Friedkin-Johnsen Model

The dynamics (1) can be viewed as a time-varying version of the French-Degroot
opinion dynamics model where agent opinions move towards convex combinations
of other agents’ opinions. The Friedkin-Johnsen model, in addition to being
partly influenced by neighbors, introduces a prejudice that affects the
agents’ opinions. Mathematically,

$\displaystyle{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{x}}(t+1)=\Lambda
W(t){\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{x}}(t)+(I-\Lambda){\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{u}},$
(6)

where
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{x}}(t)\in\mathbb{R}^{n}$
denotes the vector of opinions,
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{u}}\in\mathbb{R}^{n}$
is the vector of the agents’ prejudices, $W(t)\in\mathbb{R}^{n\times n}$
denotes the influence matrix, which describes how the agents influence each
other, and $\Lambda\in\mathbb{R}^{n\times n}$ is a diagonal matrix whose $i$th
diagonal entry, $\lambda_{i}\in[0,1]$, denotes the susceptibility of agent $i$
to social influence and $1-\lambda_{i}$ denotes the susceptibility of agent
$i$ to her prejudice
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}u}_{i}$.

Similar to (6), we can provide a random adaptation variation of the Friedkin-
Johnsen model as follows. In the $t$-th time period, agent $i$ decides between
adapting to her neighbor’s opinion versus adapting to her prejudice. Her
choice is independent of other agents’ choices and her own past choices. With
a probability $\gamma(t)\in(0,1)$, she follows the adaptation scheme described
earlier, and with probability $1-\gamma(t)$, she resets her opinion to her
prejudice $u_{i}\in\mathbb{R}$. As before, we assume the initial state vector
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{x}}(0)\in\mathbb{R}^{n}$
to be arbitrary. This results in the update rule

$\displaystyle{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{x}}(t+1)=\Lambda(t)A(t){\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{x}}(t)+(I-\Lambda(t)){\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{u}},$
(7)

where
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{x}}(t)$
and $A(t)$ have their usual meanings,
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{u}}\in\mathbb{R}^{n}$
is a vector of external influences/prejudices, and
$\\{\Lambda(t)\\}_{t=0}^{\infty}$ is a sequence of diagonal matrices whose
diagonal entries $\\{\lambda_{i}(t):i\in[n]\\}$ are Bernoulli random variables
with $\text{Pr}(\lambda_{i}(t)=1)=\gamma_{i}(t)$.

######  Remark 2.

Observe that (7) is a special case of (2) by letting
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{y}}^{T}(t):=[{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{x}}^{T}(t)\,\,{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{u}}^{T}]$
and by noting that

$\displaystyle{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{y}}(t+1)=B(t){\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{y}}(t),$
(8)

where $B(t):=\begin{pmatrix}\Lambda(t)A(t)\,&I-\Lambda(t)\\\ O_{n\times
n}\,&I_{n\times n}\end{pmatrix}$. As a result, for any
$t,t_{0}\in\mathbb{N}_{0}$ with $t\geq t_{0}$, we have
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{y}}(t)=B(t:t_{0}){\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{y}}(t_{0})$
with $B_{[n]}(t:t_{0})=P(t:t_{0})$, where $P(t):=\Lambda(t)A(t)$. Note also
that $P(t)\leq A(t)$ because $\Lambda(t)\leq I$.

We now define two terms: dominance in expectation and simultaneously malleable
agents, and we show that, if $\\{Q(t)\\}_{t=0}^{\infty}$ is an ergodic chain
with simultaneously malleable agents that dominate in expectation, then all
the agents’ opinions will almost surely enter the prejudice set (the set of
external influences) $\mathcal{U}:=\\{u_{i}:i\in[n]\\}$ in finite time.

######  Definition 4 (Dominance in Expectation).

The agents of a set $S\subseteq[n]$ are said to dominate in expectation if
$\sum_{t=0}^{\infty}\mathbf{1}^{T}Q_{\bar{S}S}(t)\mathbf{1}=\infty$ and
$\sum_{t=0}^{\infty}\mathbf{1}^{T}Q_{S\bar{S}}(t)\mathbf{1}<\infty$.

In the the average-case scenario, if a set of agents $S\subseteq[n]$ dominate
in expectation, then the agents of $S$ significantly influence the rest of the
agents $\bar{S}$ without themselves being significantly influenced by
$\bar{S}$ in the long run.

######  Definition 5 (Simultaneously Malleable Agents).

The agents of a set $S\subseteq[n]$ are said to be simultaneously malleable if
$\sum_{t=0}^{\infty}\prod_{i\in S}(1-\gamma_{i}(t))=\infty$.

Essentially, simultaneously malleable agents are those whose probability of
simultaneously adapting to their respective external influences does not
vanish too fast with time.

######  Theorem 4.

For the dynamics (7), suppose
${\\{Q(t)\\}_{t=0}^{\infty}=\\{\widehat{A}(t)\\}_{t=0}^{\infty}}$ is ergodic,
and suppose there exists a set $S\subseteq[n]$ of simultaneously malleable
agents that dominate in expectation. Then there a.s. exists a time $T<\infty$
such that
$\\{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}x}_{i}(T)\\}_{i=1}^{n}\subseteq\mathcal{U}$.

###### Proof.

First, note that the decisions taken in the network at time $t$ are
independent across agents. As a result, $\text{Pr}\left(\bigcap_{i\in
S}\left\\{\lambda_{i}(t)=0\right\\}\right)=\prod_{i\in S}(1-\gamma_{i}(t)).$
In light of Definition 5 and the Second Borel-Cantelli Lemma, this further
implies that there exists an increasing sequence of random times
$\\{T_{k}\\}_{k=1}^{\infty}$ such that $\lambda_{i}(T_{k}-1)=0$ a.s. for all
$i\in S$ and all $k\in\mathbb{N}$. This means that
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}x}_{i}(T_{k})=u_{i}$
a.s. for all $i\in S$ and all $k\in\mathbb{N}$.

On the other hand, we can use the union bound to show that
${\text{Pr}(\bigcup_{i\in S}\bigcup_{i\in\bar{S}}\\{a_{ij}(t)=1\\})}$ is at
most
$\sum_{i\in
S}\sum_{j\in\bar{S}}q_{ij}(t)=\mathbf{1}^{T}Q_{S\bar{S}}(t)\mathbf{1}$. Since
$\sum_{t=0}^{\infty}\mathbf{1}^{T}Q_{S\bar{S}}(t)\mathbf{1}<\infty$, it
follows from the First Borel-Cantelli Lemma [40, Theorem 2.3.1] that there
exists a random time $T^{*}<\infty$ such that $a_{ij}(t)=0$ a.s. for all $i\in
S$, $j\in\bar{S}$, and $t\geq T^{*}$. This means that there a.s. exists a
point of time $T^{*}$ after which the agents in $S$ are never influenced by
those in $\bar{S}$.

Let $K:=\inf\\{k\in\mathbb{N}_{0}:T_{k}>T^{*}\\}$. Then, $T_{K}>T^{*}$ and
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}x}_{i}(T_{K})=u_{i}$
a.s. for all $i\in S$. Hence,
${\\{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}x}_{i}(t):i\in
S\\}\subseteq\mathcal{U}\bigcup\\{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}x}_{i}(T_{K}):i\in
S\\}\subseteq\mathcal{U}}$ for all ${t\geq T_{K}}$.

It remains to show the existence of a time $T\geq T_{K}$ such that
$\\{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}x}_{i}(t):i\in\bar{S}\\}\subseteq\mathcal{U}$
for all $t\geq T$. By the definition of ergodicity, the truncated chain
$\\{Q(t)\\}_{t=\tau}^{\infty}$ is ergodic for all $\tau\in\mathbb{N}_{0}$. It
follows from Remark 1 that there exists a random vector
${{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\boldsymbol{\pi}}(\tau)\in\\{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{e}}^{(i)}:i\in[n]\\}}$
such that
$\lim_{t\to\infty}A(t:\tau)=\mathbf{1}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\boldsymbol{\pi}}^{T}(\tau)$
a.s. Thus,
${\lim_{t\to\infty}A(t:T_{K})=\mathbf{1}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\boldsymbol{\pi}}^{T}(T_{K})}$
a.s. On the other hand, for $t\geq T_{K}\geq T^{*}$, we have $a_{ij}(t)=0$
a.s. for all $i\in S$ and ${j\in\bar{S}}$. Hence, $A_{S\bar{S}}(t:T_{K})=O$
a.s. for all $t\geq T_{K}$. It follows that
$\lim_{t\to\infty}A_{S\bar{S}}(t:T_{K})=O$ a.s., which means that
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\boldsymbol{\pi}}^{T}(T_{K})\notin\\{e^{(i)}:i\in\bar{S}\\}$
a.s. Since
$\mathbf{1}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\boldsymbol{\pi}}^{T}(T_{K})$
has identical rows, this further implies that the columns of
${\lim_{t\to\infty}A(t:T_{K})}$ indexed by $\bar{S}$ are all zero a.s. It now
follows from Remark 2 that

$\displaystyle\limsup_{t\to\infty}B_{[n]\bar{S}}(t:T_{K})$
$\displaystyle=\limsup_{t\to\infty}P_{[n]\bar{S}}(t:T_{K})$
$\displaystyle\leq\limsup_{t\to\infty}A_{[n]\bar{S}}(t:T_{K})=O\quad a.s.$

Equivalently, for all sufficiently large $t$, the entries of
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{y}}(t)=B(t:T_{K}){\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{y}}(T_{K})$
are binary convex combinations of
${\\{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}x}_{i}(T_{K}):i\in
S\\}\bigcup\mathcal{U}=\mathcal{U}}$. This completes the proof.

We now consider a special case of (7) in which the probability distributions
of the agents’ opinions converge to limits that can be computed using closed-
form expressions.

######  Theorem 5.

Suppose the matrix pairs $\\{(\Lambda(t),A(t))\\}_{t=0}^{\infty}$ are
independent and identically distributed. Also, suppose $\Gamma<I$, where
$\Gamma:=\widehat{\Lambda}(t)$ and $Q:=\widehat{A}(t)$ for all
$t\in\mathbb{N}_{0}$. Finally, suppose that $|\mathcal{U}|=n$ and that
$\\{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}x}_{i}(0)\\}\bigcap\mathcal{U}=\emptyset$.
Then the following assertions hold.

  1. (i)

We have
${\lim_{t\to\infty}\text{Pr}({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}x}_{i}(t)=u_{j})=v_{ij}}$
for all ${i,j\in[n]}$, where $\\{v_{ij}:i,j\in[n]\\}$ are the entries of

$\displaystyle V:=\left(I-\Gamma Q\right)^{-1}\left(I-\Gamma\right).$ (9)

  2. (ii)

There a.s. exists a random time $T<\infty$ such that
${{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}x}_{i}(t)\in\mathcal{U}}$
for all $t\geq T$.

###### Proof.

We first recall from Remark 2 that
${{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{y}}(t)=B(t:0){\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{y}}(0)}$
for all $t\in\mathbb{N}_{0}$. Since $\mathcal{U}$ has $n$ distinct elements
and since
$\\{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}x}_{i}(0)\\}\bigcap\mathcal{U}=\emptyset$,
this implies that

$\displaystyle\text{Pr}({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}x}_{i}(t)=u_{j})$
$\displaystyle=\text{Pr}\left(B_{i\,n+j}(t:0)=1\right)=\mathbb{E}\left[B_{i\,n+j}(t:0)\right]$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\widehat{B}_{i\,n+j}(t:0)\stackrel{{\scriptstyle(b)}}{{=}}\left(\left(\widehat{B}(0)\right)^{t}\right)_{i\,n+j},$
(10)

where $(a)$ and $(b)$ hold because $\\{(\Lambda(t),A(t))\\}_{t=0}^{\infty}$
are i.i.d.

Thus, it suffices to evaluate $\lim_{t\to\infty}(\widehat{B}(0))^{t}$. Observe
that for the expected dynamics
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\widehat{\mathbf{x}}}(t+1)=\Gamma
Q\widehat{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{x}}}(t)+(I-\Gamma){\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{u}}$,
we have
${{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\widehat{\mathbf{y}}}(t)=(\widehat{B}(0))^{t}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{y}}(0)}$
as a consequence of Remark 2. On the other hand, we know from Theorem 21 and
Corollary 22 in [13] that
$\lim_{t\to\infty}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\widehat{\mathbf{x}}}(t)=V{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{u}}$,
which implies that

$\lim_{t\to\infty}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\widehat{\mathbf{y}}}(t)=\begin{pmatrix}O_{n\times
n}&V\\\ O_{n\times
n}&I\end{pmatrix}\begin{pmatrix}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{x}}(0)\\\
{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{u}}\end{pmatrix}=\begin{pmatrix}O_{n\times
n}&V\\\ O_{n\times
n}&I\end{pmatrix}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{y}}(0).$

That is,
$\lim_{t\to\infty}(\widehat{B}(0))^{t}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{y}}(0)=\begin{pmatrix}O_{n\times
n}&V\\\ O_{n\times
n}&I\end{pmatrix}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{y}}(0).$
As
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{y}}(0)$
(which stacks the initial states and the external influences) is arbitrary, it
follows that
${\left(\lim_{t\to\infty}(\widehat{B}(0))^{t}\right)_{i\,n+j}=v_{ij}}$ for all
$i,j\in[n]$. In light of (4.2), this proves (i).

To prove (ii), note that $\prod_{i\in[n]}(1-\gamma_{i}(t))$ is positive and
time-invariant because $\Gamma(t)=\Gamma<I$ for all $t\in\mathbb{N}_{0}$.
Hence, all the agents in the network are simultaneously malleable. Since they
also dominate in expectation trivially, (ii) follows immediately from Theorem
4.

###  4.3 Rank-One Perturbation of the Friedkin-Johnsen Variant

Another random adaptation-based variant of the Friedkin-Johnsen model can be
obtained by letting the opinion of each agent ‘mutate’ to any external
influence with a fixed probability distribution, i.e., in the $t$th time
period, agent $i$ either adapts to a neighbor’s opinion or adapts to one of
the prejudices independently of her past choices. With probability
$\gamma_{i}(t)\in(0,1)$, the agent follows the adaptation scheme described
earlier (in (2)), and with probability ${1-\gamma_{i}(t)}$, however, instead
of adapting to one fixed prejudice, she chooses an opinion from the set
${\mathcal{U}=\\{u_{i}:i\in[n]\\}}$, according to a stochastic vector
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{q}}$
on $\mathcal{U}$. That is,

$\displaystyle{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{x}}(t+1)=\Lambda(t)A(t){\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{x}}(t)+(I-\Lambda(t))C(t){\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{u}},$
(11)

where
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{x}}(t)$
and $A(t)$ are as before,
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{u}}\in\mathbb{R}^{n}$
is the vector of external influences, $\\{\Lambda(t)\\}_{t=0}^{\infty}$ is a
sequence of random binary diagonal matrices with
$\text{Pr}(\lambda_{i}(t)=1)=\gamma_{i}(t)$, and $\\{C(t)\\}_{t=0}^{\infty}$
is a sequence of i.i.d. binary stochastic random matrices. For any $i\in[n]$,
$\text{Pr}(C_{ij}(t)=1)=q_{j}$ for all $j\in[n]$, independent of the other
rows. Here
$\widehat{C}(t)=\mathbf{1}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{q}}^{T}$,
for all $t\in\mathbb{N}_{0}$, which is a rank-one matrix for all
$t\in\mathbb{N}_{0}$.

######  Theorem 6.

Consider the dynamics (11) where $|\mathcal{U}|=n$,
$\\{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}x}_{i}(0):i\in[n]\\}\bigcap\mathcal{U}={\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\emptyset}$,
and the matrix pairs $\\{(\Lambda(t),A(t))\\}_{t=0}^{\infty}$ are i.i.d. with
$Q:=\widehat{A}(t)$ and $\Gamma:=\widehat{\Lambda}(t)$ for all
$t\in\mathbb{N}_{0}$. Also, suppose that $\Gamma<I$. Then the following hold
true.

  1. (i)

We have
$\lim_{t\to\infty}\text{Pr}({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}x}_{i}(t)=u_{j})=v_{ij}$
for all ${i,j\in[n]}$, where $\\{v_{ij}:i,j\in[n]\\}$ are the entries of

$\displaystyle V$ $\displaystyle:=(I-\Gamma
Q)^{-1}(I-\Gamma)\mathbf{1}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color<EMAIL_ADDRESS>
  2. (ii)

There a.s. exists a random time $T<\infty$ such that
${{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}x}_{i}(t)\in\mathcal{U}}$
for all $t\geq T$.

###### Proof.

We can rewrite the dynamics as
${{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{y}}(t+1)=D(t){\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{y}}(t)}$,
where
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{y}^{T}}(t)=\begin{bmatrix}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{x}}^{T}(t)&{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{u}}^{T}\end{bmatrix}$
and

$\displaystyle D(t)$
$\displaystyle=\begin{bmatrix}\Lambda(t)A(t)&({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}I}-\Lambda(t))C(t)\\\
O_{n\times n}&I_{n\times n}\end{bmatrix}.$ (12)

So, we have
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{y}}(t)=D(t:0){\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{y}}(0)$,
for all $t\in\mathbb{N}_{0}$. Since the elements of $\mathcal{U}$ are distinct
and
$\\{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}x}_{i}(0)\mid
i\in[n]\\}\bigcap\mathcal{U}={\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\emptyset}$,
similar to (4.2), we have
$\text{Pr}({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}x}_{i}(t)=u_{j})=\left(\left(\widehat{D}(0)\right)^{t}\right)_{i\,n+j}$.
To compute the limiting marginal probability note that

$\displaystyle\left(\widehat{D}(0)\right)^{t}$
$\displaystyle=\begin{bmatrix}\Gamma
Q&({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}I}-\Gamma)\widehat{C}(0)\\\
O_{n\times n}&I_{n\times n}\end{bmatrix}^{t}=\begin{bmatrix}\left(\Gamma
Q\right)^{t}&R(t)\\\ O_{n\times n}&I_{n\times n}\end{bmatrix},$ (13)

where ${R(t)=\sum_{k=0}^{t-1}\left(\Gamma
Q\right)^{k}(I-\Gamma)\mathbf{1}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color<EMAIL_ADDRESS>Since ${Q\in\mathcal{P}_{n\times n}}$, we know that the maximum absolute value
of eigenvalues of $\Gamma Q$ is less than $1$ since $\Gamma
Q\leq\gamma_{\max}Q$, where $\gamma_{\max}=\max_{i\in[n]}\gamma_{i}\in(0,1)$.
Using a result on Neumann Series (Eq. (7.10.11) in [43]), we have
${\lim_{t\to\infty}R(t)=(I-\Gamma
Q)^{-1}(I-\Gamma)\mathbf{1}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{q}}^{T}}=V$,
and $\lim_{t\to\infty}\left(\Gamma Q\right)^{t}=O_{n\times n}.$

For (ii), note that the probability that all the agents adapt to an external
influence at any time is ${\prod_{i=1}^{n}(1-\gamma_{i})>0}$. Since
$\\{\Lambda(t)\\}_{t=0}^{\infty}$ are independent, it follows from the Second
Borel-Cantelli Lemma that there exists an increasing sequence of random times
$\\{T_{k}\\}_{k=1}^{\infty}$ such that $\Lambda(T_{k})=1$. This implies that
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}x}_{i}(T_{1}+1)\in\mathcal{U}$
for all $i\in[n]$. Therefore, for all
$(t_{0},{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{x}}(t_{0}))\in\mathbb{N}_{0}\times\mathbb{R}^{n}$,
there a.s. exists a random time $T<\infty$ such that
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}x}_{i}(t)\in\mathcal{U}$
for all $t\geq T$.

######  Remark 3.

Suppose, in addition to the assumptions in Theorem 6, all the agents have
identical susceptibility, i.e., $\Gamma=\gamma I$ for some $\gamma\in(0,1)$.
Then, since ${Q\in\mathcal{P}_{n\times n}}$, we have
${R(t)=\sum_{k=0}^{\infty}\gamma^{k}(1-\gamma)\mathbf{1}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{q}}^{T}}$,
and since ${\gamma\in(0,1)}$, we have
${V=\mathbf{1}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{p}}^{T}}$.
Furthermore, for this case, the result extends to all stochastic chains
$\\{Q(t)\\}_{t=0}^{\infty}$ and not just to identically distributed chains, as
${R(t)=\sum_{k=0}^{t}\gamma^{k}(1-\gamma)Q(k+1:0)\mathbf{1}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{q}}^{T}}$
with ${Q(t+1:0)\mathbf{1}=\mathbf{1}}$, for all $t\in\mathbb{N}_{0}$, which
implies that
${V=\lim_{t\to\infty}R(t)=\mathbf{1}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{q}}^{T}}$.
Therefore, in this case, the limiting marginal probability distribution is
independent of the degree of susceptibility.

######  Remark 4.

Note that the dynamics studied in Sections 4.2 and 4.3 can be obtained as
special cases of the generalized model studied in [44]. However, while the
results of [44] imply convergence in distribution and provide the expected
values of the steady states, they do not characterize the distributions of
these steady states, nor do they show the a.s. convergence of the agents’
opinions to the prejudice set.

##  5 SIMULATIONS

We now illustrate some of our main results with the help of suitable numerical
examples generated using MATLAB. These examples are aimed at facilitating the
reader’s understanding of the key ideas developed in this work.

######  Example 1 (Base Case Dynamics with Ergodicity).

Consider Equation (2), the simplest among all of the random adaptation
dynamics we have analyzed above. Suppose we have $n=10$ agents in a social
network, and for simplicity, suppose that the initial states (or opinions) of
the agents are given by $x_{i}(0)=i$ for all $i\in[n]$.

In order to simulate the case of the expected stochastic chain
$\\{Q(t)\\}_{t=0}^{\infty}$ being ergodic, we first assume a finite time
horizon of $H=1000$, use _randfixedsum.m_ [45] to randomly generate an
indefinitely long (but finite) sequence of $n\times n$ stochastic matrices,
select among the generated matrices the first $H$ matrices that are
irreducible (i.e., the first $H$ that can be expressed as the adjacency
matrices of strongly connected directed graphs), and then set the finite
sequence $\\{Q(t)\\}_{t=0}^{H-1}$ equal to the sequence of the irreducible
matrices thus obtained.

Next, we obtain $\\{A(t)\\}_{t=0}^{H-1}$ as the random matrices generated
using the probability distributions defined by $\\{Q(t)\\}_{t=0}^{H}$. We then
choose an arbitrary realization of $\\{A(t)\\}_{t=0}^{H-1}$ and plot the
corresponding dynamics (2) in Figure 1 below.

Figure 1: Simulation of the base case dynamics (2) with $\\{Q(t)\\}$ being an
ergodic chain

In the above example, observe that all the agents’ opinions reach the same
value within the first $30$ time periods. This is in agreement with Theorem 1,
which implies that finite agreement occurs almost surely when the expected
stochastic chain $\\{Q(t)\\}=\\{\widehat{A}(t)\\}$ is ergodic.

######  Example 2 (Base Case Dynamics without Ergodicity).

We again consider Equation (2) and repeat the procedure described in Example
1, except that we now generate $\\{Q(t)\\}_{t=0}^{H-1}$ as follows: we first
generate two sequences
$\\{R(t)\\}_{t=0}^{H-1},\\{S(t)\\}_{t=0}^{H-1}\subset\mathbb{R}^{\frac{n}{2}\times\frac{n}{2}}$
of irreducible matrices, we then generate two arbitrary sequences of random
non-negative matrices
$\\{\Delta_{1}(t)\\}_{t=0}^{H-1},\\{\Delta_{2}(t)\\}_{t=0}^{H-1}\subset\mathbb{R}^{\frac{n}{2}\times\frac{n}{2}}$,
we let

$\tilde{Q}(t)=\begin{pmatrix}B(t)&\frac{1}{t^{2}}\Delta_{1}(t)\\\
\frac{1}{t^{2}}\Delta_{2}(t)&C(t)\end{pmatrix},$

and we finally set
$q_{ij}(t)=\frac{\tilde{q}_{ij}(t)}{\sum_{k=1}^{n}\tilde{q}_{ik}(t)}$ for each
$i,j\in[n]$ so as to obtain $Q(t)$ as a row-stochastic matrix. The decay
factor of $\frac{1}{t^{2}}$ ensures that the influence of the agent subsets
$\\{1,2,\ldots,\frac{n}{2}\\}$ and $\\{\frac{n}{2},\frac{n}{2}+1,\ldots,n\\}$
on each other diminishes with time fast enough to make
$\\{Q(t)\\}_{t=0}^{H-1}$ a good approximation of a non-ergodic chain.

Next, we obtain $\\{A(t)\\}_{t=0}^{H-1}$ as the random matrices generated
using the probability distributions defined by $\\{Q(t)\\}_{t=0}^{H}$. We then
choose an arbitrary realization of $\\{A(t)\\}_{t=0}^{H-1}$ and plot the
corresponding dynamics (2) in Figure 2 below.

Figure 2: Simulation of the base case dynamics (2) with $\\{Q(t)\\}$ being a
non-ergodic chain

In the above example, two clusters of agents reach two distinct consensus
values within the first $15$ time periods. This is consistent with Theorem 1,
which states that finite agreement almost surely does not occur in the base
case dynamics if $\\{Q(t)\\}$ is not an ergodic chain. Moreover, it can be
shown that the principal submatrices of $\tilde{Q}(t)$ corresponding to the
coordinates $\\{1,2,\ldots,\frac{n}{2}\\}$ form an ergodic stochastic chain.
The same can be said about the principal submatrices corresponding to the
complementary set $\\{\frac{n}{2},\ldots,n-1,n\\}$, which, along with Theorem
1, explains why exactly two consensus clusters are formed in the associated
random adaptation dynamics.

######  Example 3 (Comparison of the Base Case Random Adaptation Dynamics with
the Expected Dynamics).

We now repeat the setup of Example 1 and plot in Figure 3 the evolution of
$\mathbf{x}(t)$ averaged over $1000$ different realizations of
$\\{A(t)\\}_{t=0}^{H-1}$ as a set of $n$ line plots. To compare the resulting
plots with the associated expected dynamics, i.e., the classical non-random
averaging dynamics defined by (1), we simulate (1) and plot the corresponding
state evolution of the $n$ agents using solid red square markers whose color
intensity varies with the agent index $i\in[n]$.

Figure 3: Comparison of the Empirical Mean of the Base Case Dynamics with the
Expected Dynamics (1)

In Figure 3, we observe that the line plots and the square marker plots
exhibit finite agreement and also overlap with each other almost perfectly.
This is consistent with Theorem 1 and with the observation that

$\mathbb{E}[\mathbf{x}(t)]=\mathbb{E}[A(t:t_{0})\mathbf{x}(t_{0})]=\mathbb{E}[A(t:t_{0})]\mathbf{x}(t_{0})=Q(t:t_{0})\mathbf{x}(t_{0}),$

where the last step follows from the mutual independence of
$\\{A(t)\\}_{t=0}^{\infty}$. This observation means that the distributed
averaging dynamics defined by (1) is nothing other than the expectation of the
random adaptation dynamics defined by (2). Hence, the empirical average of
$\mathbf{x}(t)$ plotted using solid lines must be a good approximation for the
averaging dynamics (1).

######  Example 4 (Random Adaptation Variant of Friedkin-Johnsen Dynamics).

Finally, we simulate (7), the random adaptation variant of the Friedkin-
Johnsen model. We first set $n=10$ and generate
$\\{Q(t)\\}_{t=0}^{H-1}=\\{\widehat{A}(t)\\}_{t=0}^{H-1}$ using the procedure
described in Example 1. We then generate $\\{\gamma_{i}(0):i\in[n]\\}$ as
random variables uniformly distributed over the set $[0,1]$, and we make sure
that $0<\gamma_{i}(0)<1$ for all $i\in[n]$. Next, we set
$\gamma_{i}(t)=\gamma_{i}(0)$ for all $i\in[n]$ and all
$t\in\\{0,1,\ldots,H-1\\}$ so as to ensure that $\\{\Lambda(t)\\}_{t=0}^{H-1}$
are i.i.d. random matrices. As the next step, we generate
$\lambda_{i}(t)=\text{Bernoulli}(\gamma_{i}(0))$ for each $i\in[n]$ and
$t\in\\{0,1,\ldots,H-1\\}$.

As for the initial opinions and prejudices, we choose $u_{i}=i+20$ and
$x_{i}(0)=i$ for all $i\in[n]$ to ensure that
$\\{x_{i}(0):i\in[n]\\}\bigcap\mathcal{U}=\emptyset$. We then plot the results
of our simulation in Figure 4 below.

Figure 4: Simulation of the Random Adaptation Variant (7) of the Friedkin-
Johnsen Model

As seen from Figure 4, although the initial opinions (states) of all the
agents lie in the set $\\{1,2,\ldots,10\\}$, all the agents eventually enter
the prejudice set $\\{21,22,\ldots,30\\}$. This happens because
$\\{\Lambda(t)\\}_{t=0}^{H-1}$ are i.i.d., which implies that $[n]$ is a set
of simultaneously malleable agents that dominate in expectation trivially.
Therefore, by Theorem 4, all the initial opinions of the agents get erased
within a finite time-span.

In summary, all of our simulation results are consistent with, and hence
validate, our main theoretical results.

##  6 CONCLUSION

We proposed and studied a random adaptation variant of time-varying
distributed averaging dynamics in discrete time. We have shown that our models
give rise to novel interpretations for the concepts of ergodicity and absolute
probability sequences, both of which are pivotal to the study of stochastic
chains. We have also proposed a time-varying, stochastic analog of the well-
known Friedkin-Johnsen opinion dynamics and analyzed the asymptotic behavior
of the probability distributions of the agents’ opinions. Finally, we have
considered a rank-one perturbation of our base-case stochastic dynamics and
studied its asymptotic behavior.

Our random adaptation interpretation of averaging (and related) dynamics opens
up many avenues avenues for further investigations including the (time-
varying) controlled variation of Friedkin-Johnsen dynamics through the lens of
random adaptation dynamics, and the connection of mutation-adaptation learning
dynamics (in game theoretic setting) and our proposed random adaptation
schemes.

## Appendix

######  Lemma 1.

For the dynamics (2)  with $Q(t)=\widehat{A}(t)$, the following holds for all
$S\subseteq[n]$, $\ell\in[n]$, $t\in\mathbb{N}_{0}$ and $\Delta\in\mathbb{N}$

$\displaystyle\text{Pr}\left(\bigcap_{i\in
S}\left(A(t+\Delta:t)\right)_{i\ell}=1\right)\geq\prod_{i\in
S}Q_{i\ell}(t+\Delta:t).$ (14)

###### Proof.

We use induction on $\Delta$. For $\Delta=1$, the assertion follows from the
independence of the rows of $A(t)$.

Assume now that the assertion holds for some $\Delta\geq 1$. Let
$S\subseteq[n]$ be a given set. W.l.o.g. we assume $S=[v]$ for some $v\in[n]$.
In addition, for each $i\in[n]$, let $\sigma_{i}(t)$ denote the random index
such that $a_{i\sigma_{i}(t)}(t)=1$, let
$\tilde{\sigma}(t):=(\sigma_{1}(t),\ldots,\sigma_{v}(t))$ and let
$\tilde{\alpha}=(\alpha_{1},\ldots,\alpha_{v})$ be a realization of
$\tilde{\sigma}(t)$. Let ${W:=\\{i\in
S:\alpha_{i}\notin\\{\alpha_{1},\ldots,\alpha_{i-1}\\}\\}}$ index all the
distinct $\alpha_{i}$s. Then, for $\Delta+1$, we have $\bigcap_{i\in
S}\left\\{A_{i\ell}(t+\Delta+1:t)=1\right\\}=\bigcap_{i\in
S}\\{A_{i\ell}(t+\Delta+1:t)=1\\}\cap\\{\sigma(t)=\tilde{\alpha}\\}$. Since,
$A(t)$ has independent rows and because
$\\{(A(t+\Delta+1:t))_{i\ell}=1\\}=\\{(A(t+\Delta:t))_{\alpha_{i}\ell}=1\\}$
conditional on the event $\\{\sigma_{i}(t)=\alpha_{i}\\}$, we have

$\displaystyle\text{Pr}\left(\bigcap_{i\in
S}\left\\{A_{i\ell}(t+\Delta+1:t)=1\right\\}\right)$
$\displaystyle{=}\sum_{\tilde{\alpha}\in[n]^{v}}\bigg{(}\text{Pr}(\bigcap_{i\in
S}\\{A_{\alpha_{i}\ell}(t+\Delta:t)=1\\}\mid\tilde{\sigma}(t)=\tilde{\alpha})$
$\displaystyle\quad\quad\quad\quad\quad\times\prod_{j\in
S}q_{j\sigma_{j}(t)}(t)\bigg{)}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\sum_{\tilde{\alpha}\in[n]^{v}}\text{Pr}(\bigcap_{i\in
S}\\{A_{\alpha_{i}\ell}(t+\Delta:t)=1\\})\cdot\prod_{j\in
S}q_{j\sigma_{j}(t)}(t)$
$\displaystyle=\sum_{\tilde{\alpha}\in[n]^{v}}\text{Pr}(\bigcap_{i\in
W}\\{A_{\alpha_{i}\ell}(t+\Delta:t)=1\\})\cdot\prod_{j\in
S}q_{j\sigma_{j}(t)}(t)$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\geq}}\sum_{\tilde{\alpha}\in[n]^{v}}\prod_{i\in
W}Q_{\alpha_{i}\ell}(t+\Delta:t)\cdot\prod_{j\in S}q_{j\sigma_{j}(t)}(t)$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{\geq}}\sum_{\tilde{\alpha}\in[n]^{v}}\prod_{i\in
S}Q_{\alpha_{i}\ell}(t+\Delta:t)\cdot\prod_{j\in S}q_{j\sigma_{j}(t)}(t)$

where $(a)$ holds because $\\{A(\tau)\\}_{\tau=0}^{\infty}$ are independent,
$(b)$ follows from our inductive hypothesis, and $(c)$ holds because
$W\subseteq V$ and because all matrix entries lie in $[0,1]$. Noting that the
last expression is simply $\prod_{i\in S}Q_{i\ell}(t+\Delta+1:t)$ completes
the proof.

## References

  * [1] A. Nedic and A. Ozdaglar, “On the Rate of Convergence of Distributed Subgradient Methods for Multi-Agent Optimization,” in 46th IEEE Conference on Decision and Control, pp. 4711–4716, IEEE, 2007.
  * [2] M. Rabbat and R. Nowak, “Distributed Optimization in Sensor Networks,” in Proceedings of the 3rd International Symposium on Information Processing in Sensor Networks, pp. 20–27, 2004.
  * [3] J. B. Predd, S. B. Kulkarni, and H. V. Poor, “Distributed learning in wireless sensor networks,” IEEE Signal Processing Magazine, vol. 23, no. 4, pp. 56–69, 2006.
  * [4] F. S. Cattivelli and A. H. Sayed, “Diffusion LMS strategies for Distributed Estimation,” IEEE Transactions on Signal Processing, vol. 58, no. 3, pp. 1035–1048, 2009.
  * [5] A. Jadbabaie, P. Molavi, A. Sandroni, and A. Tahbaz-Salehi, “Non-Bayesian social learning,” Games and Economic Behavior, vol. 76, no. 1, pp. 210–225, 2012.
  * [6] A. Lalitha, A. Sarwate, and T. Javidi, “Social Learning and Distributed Hypothesis Testing,” in 2014 IEEE International Symposium on Information Theory, pp. 551–555, IEEE, 2014.
  * [7] A. Nedić, A. Olshevsky, and C. A. Uribe, “A Tutorial on Distributed (Non-Bayesian) Learning: Problem, Algorithms and Results,” in 2016 IEEE 55th Conference on Decision and Control (CDC), pp. 6795–6801, IEEE, 2016.
  * [8] R. Parasnis, M. Franceschetti, and B. Touri, “Non-Bayesian social learning on random digraphs with aperiodically varying network connectivity,” IEEE Transactions on Control of Network Systems, 2022.
  * [9] A. Rangi and M. Franceschetti, “Multi-armed bandit algorithms for crowdsourcing systems with online estimation of workers’ ability,” in Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, pp. 1345–1352, 2018.
  * [10] F. Bullo, J. Cortés, and S. Martínez, “Distributed Control of Robotic Networks: A Mathematical Approach to Motion Coordination Algorithms,” 2008.
  * [11] M. H. DeGroot, “Reaching a Consensus,” Journal of the American Statistical Association, vol. 69, no. 345, pp. 118–121, 1974.
  * [12] D. Acemoglu and A. Ozdaglar, “Opinion dynamics and learning in social networks,” Dynamic Games and Applications, vol. 1, no. 1, pp. 3–49, 2011\.
  * [13] A. V. Proskurnikov and R. Tempo, “A Tutorial on Modeling and Analysis of Dynamic Social Networks. Part I,” Annual Reviews in Control, vol. 43, pp. 65–79, 2017.
  * [14] A. V. Proskurnikov and R. Tempo, “A Tutorial on Modeling and Analysis of Dynamic Social Networks. Part II,” Annual Reviews in Control, vol. 45, pp. 166–190, 2018.
  * [15] R. Hegselmann, U. Krause, et al., “Opinion dynamics and bounded confidence models, analysis, and simulation,” Journal of artificial societies and social simulation, vol. 5, no. 3, 2002.
  * [16] R. Parasnis, M. Franceschetti, and B. Touri, “On the convergence properties of social Hegselmann-Krause dynamics,” IEEE Transactions on Automatic Control, 2021.
  * [17] L. Xiao and S. Boyd, “Fast Linear Iterations for Distributed Averaging,” Systems & Control Letters, vol. 53, no. 1, pp. 65–78, 2004.
  * [18] L. Cao, Y. Zheng, and Q. Zhou, “A Necessary and Sufficient Condition for Consensus of Continuous-Time Agents over Undirected Time-Varying Networks,” IEEE Transactions on Automatic Control, vol. 56, no. 8, pp. 1915–1920, 2011\.
  * [19] M. El Chamie, J. Liu, and T. Başar, “Design and Analysis of Distributed Averaging with Quantized Communication,” IEEE Transactions on Automatic Control, vol. 61, no. 12, pp. 3870–3884, 2016.
  * [20] D. Blackwell, “Finite Non-Homogeneous Chains,” Annals of Mathematics, pp. 594–599, 1945.
  * [21] S. Chatterjee and E. Seneta, “Towards Consensus: Some Convergence Theorems on Repeated Averaging,” Journal of Applied Probability, vol. 14, no. 1, pp. 89–97, 1977.
  * [22] B. Touri and A. Nedić, “On Backward Product of Stochastic Matrices,” Automatica, vol. 48, no. 8, pp. 1477–1488, 2012.
  * [23] B. Touri, Product of Random Stochastic Matrices and Distributed Averaging.  Springer Science & Business Media, 2012.
  * [24] S. Martin and J. M. Hendrickx, “Continuous-Time Consensus under Non-Instantaneous Reciprocity,” IEEE Transactions on Automatic Control, vol. 61, no. 9, pp. 2484–2495, 2015.
  * [25] S. Bolouki and R. P. Malhamé, “Consensus Algorithms and the Decomposition-Separation Theorem,” IEEE Transactions on Automatic Control, vol. 61, no. 9, pp. 2357–2369, 2015.
  * [26] R. Parasnis, M. Franceschetti, and B. Touri, “Towards a Perron-Frobenius Theorem for Strongly Aperiodic Stochastic Chains,” arXiv preprint arXiv:2204.00573, 2022.
  * [27] G. De Pasquale, F. Bullo, and M. E. Valcher, “Ergodicity Coefficients are Induced Matrix Seminorms,” arXiv preprint arXiv:2201.03103, 2022.
  * [28] N. E. Friedkin and E. C. Johnsen, “Social Influence and Opinions,” Journal of Mathematical Sociology, vol. 15, no. 3-4, pp. 193–206, 1990.
  * [29] P. Clifford and A. Sudbury, “A model for spatial conflict,” Biometrika, vol. 60, no. 3, pp. 581–588, 1973.
  * [30] R. A. Holley and T. M. Liggett, “Ergodic theorems for weakly interacting infinite systems and the voter model,” The annals of probability, pp. 643–663, 1975.
  * [31] V. Sood and S. Redner, “Voter model on heterogeneous graphs,” Physical review letters, vol. 94, no. 17, p. 178701, 2005.
  * [32] C. M. Schneider-Mizell and L. M. Sander, “A generalized voter model on complex networks,” Journal of Statistical Physics, vol. 136, no. 1, pp. 59–71, 2009.
  * [33] C. Castellano, M. A. Muñoz, and R. Pastor-Satorras, “Nonlinear q-voter model,” Physical Review E, vol. 80, no. 4, p. 041129, 2009.
  * [34] B. L. Granovsky and N. Madras, “The noisy voter model,” Stochastic Processes and their applications, vol. 55, no. 1, pp. 23–43, 1995.
  * [35] R. D. Congleton, “The median voter model,” in The encyclopedia of public choice, pp. 707–712, Springer, 2004.
  * [36] M. Mobilia, A. Petersen, and S. Redner, “On the role of zealotry in the voter model,” Journal of Statistical Mechanics: Theory and Experiment, vol. 2007, no. 08, p. P08029, 2007.
  * [37] D. Acemoglu, G. Como, F. Fagnani, and A. Ozdaglar, “Opinion fluctuations and disagreement in social networks,” Mathematics of Operations Research, vol. 38, no. 1, pp. 1–27, 2013.
  * [38] J. T. Cox, “Coalescing random walks and voter model consensus times on the torus in Zd,” The Annals of Probability, pp. 1333–1366, 1989.
  * [39] D. Aldous and J. Fill, “Reversible Markov chains and random walks on graphs,” 1995.
  * [40] R. Durrett, Probability: Theory and Examples, Edition 4.1, vol. 49.  Cambridge University Press, 2013.
  * [41] A. Kolmogoroff, “Zur Theorie der Markoffschen Ketten,” Mathematische Annalen, vol. 112, no. 1, pp. 155–160, 1936.
  * [42] A. A. Daddel, “Regular Markov Chains,” Lecture Notes on Applications of Linear Algebra, 2000.  https://bit.ly/3in7r2L.
  * [43] C. D. Meyer, Matrix Analysis and Applied Linear Algebra, vol. 71.  SIAM, 2000.
  * [44] C. Ravazzi, P. Frasca, R. Tempo, and H. Ishii, “Ergodic randomized algorithms and dynamics over networks,” IEEE Transactions on Control of Network Systems, vol. 2, no. 1, pp. 78–87, 2014.
  * [45] R. Stafford, “Random vectors with fixed sum,” 2006.