# Social Opinion Formation and Decision Making Under Communication Trends

Mert Kayaalp, Virginia Bordignon, Ali H. Sayed
École Polytechnique Fédérale de Lausanne (EPFL) The authors are with Adaptive
Systems Laboratory, EPFL. Emails: {mert.kayaalp, virginia.bordignon,
<EMAIL_ADDRESS>This work was supported in part by SNSF grant
205121-184999.

###### Abstract

This work studies the learning process over social networks under partial and
random information sharing. In traditional social learning models, agents
exchange full belief information with each other while trying to infer the
true state of nature. We study the case where agents share information about
only one hypothesis, namely, the trending topic, which can be randomly
changing at every iteration. We show that agents can learn the true hypothesis
even if they do not discuss it, at rates comparable to traditional social
learning. We also show that using one’s own belief as a prior for estimating
the neighbors’ non-transmitted beliefs might create opinion clusters that
prevent learning with full confidence. This phenomenon occurs when a single
hypothesis corresponding to the truth is exchanged exclusively during all
times. Such a practice, however, avoids the complete rejection of the truth
under any information exchange procedure — something that could happen if
priors were uniform.

###### Index Terms:

social learning, distributed inference, distributed hypothesis testing,
diffusion strategy, trending topics, partial information sharing

##  I Introduction

Social learning [1, 2, 3, 4, 5] models opinion formation and decision making
by agents connected by a graph topology. In these models, agents observe data
and interact with their neighbors in order to infer the true state of nature
from a finite set of hypotheses. In a behavioral context, for example, voters
may seek to agree on the best political representative among a set of
candidates {A, B, C, D}, based on their personal biases as well as on their
interactions over a social network. Other examples arise in the context of
engineering systems: A sensor network may be cooperating to detect whether the
weather is sunny or rainy or to classify imagery captured from a common scene
[6].

Figure 1: Number of tweets about two mobile operators for each week. (Mobile
operator A- Swisscom, B- SunRise). Total of 64 weeks between 01/01/2021 and
30/04/2022, tweets in Switzerland.

In this work, our focus is on _locally_ Bayesian (a.k.a non-Bayesian) social
learning strategies [7, 8, 9, 10, 11]. While _fully_ Bayesian social learning
[12] seeks to form the global Bayesian posterior, it necessitates extensive
knowledge about other agents, such as their likelihood functions and network
topology. Even under this extensive knowledge, achieving the global Bayesian
posterior is known to be NP-hard [13]. In contrast, locally Bayesian social
learning strategies rely solely on the localized processing of data and on
localized interactions, and have been shown to allow the inference of the true
state of nature [7, 8]. Furthermore, these strategies are better suited to
real-world scenarios compared to fully Bayesian strategies [12, 13] for at
least two reasons. First, from a behavioral perspective, non-Bayesian
strategies agree with the theory of bounded rationality in human decision
making [14, 15]. Second, from an engineering perspective, they allow fully
decentralized designs with moderate complexity and efficient memory [7].

Non-Bayesian social learning algorithms repeatedly execute the following two
steps: $i)$ agents update their _local_ beliefs, based on personal
observations; $ii)$ agents combine their neighbors’ beliefs using a weighted
averaging scheme like consensus [16] or diffusion [17]. An implicit assumption
common to these models is that agents are willing to share with neighbors
their _full_ belief vector. That is, they share their beliefs about all
possible hypotheses. In the context of social networks, this can be an
unrealistic assumption. For instance, oftentimes, Twitter users concentrate on
particular topics that constitute Twitter Trends. If candidate A gave a recent
press release, Twitter users will likely focus on A when exchanging opinions
and ignore other candidates. Another example can be users trying to determine
the best mobile operator — see Fig. 1 displaying the evolution of discussions
on Twitter over time about two operators in Switzerland. The communication
trends in this case can change based on the campaigns and advertisements by
the mobile service providers (rather than being fixed over time as assumed by
[18]). Furthermore, in the context of engineering systems, transmitting
partial beliefs rather than full beliefs enable the design of communication-
efficient systems under limited resources. Motivated by these examples, we are
interested in the case where social agents share information on a random
hypothesis of interest at each iteration.

Contributions.

  * •

We propose a social learning algorithm, where agents share their beliefs on
_only one_ randomly chosen hypothesis at each time instant — see Section IV.
As opposed to the prior work [18], the hypothesis being exchanged between
agents is allowed to change over time. Moreover, under this partial
information sharing scheme, agents complete the missing components of the
received beliefs by using their own beliefs.

  * •

When a wrong hypothesis is exchanged with positive probability, we show that
beliefs evaluated at that hypothesis decay exponentially. The decay rate is
the same as the asymptotic learning rate of traditional social learning
algorithms (Theorem 1). As a result, if each wrong hypothesis is exchanged
with positive probability, then, learning occurs with probability one
(Corollary 1).

  * •

We develop new proof techniques to tackle the randomness in the combination
policy stemming from the shared hypothesis. The constraint that the beliefs
belong to the probability simplex couples the processes for different
hypotheses, making the standard application of the strong-law-of-large-numbers
nonfeasible. Thus, we utilize martingale arguments to handle the non-
linearity.

  * •

We provide a counter-example in Section V-B to show that sharing information
about the true hypothesis is not sufficient for truth learning with full
confidence when agents use their own beliefs as a prior for other agents’
beliefs.

  * •

On the other hand, Theorem 2 states that agents will never discard the truth
completely. Namely, their beliefs on the true hypothesis will never be zero,
which also means that they will never be fully confident on a wrong hypothesis
being the true hypothesis. This contrasts with the findings in [18], where
truth sharing is shown to lead to truth learning when agents adopt uniform
priors for the missing components. However, with such an approach, agents
might also become fully confident in an incorrect hypothesis [18].

  * •

We support the theoretical findings with simulations in Section VI.

##  II Related Work

The connections between the current work and the distributed decision-making
literature can be grouped as follows.

Partial information sharing: Partial information is considered in the context
of social learning in [18], where each agent shares a single hypothesis of
interest, which is fixed over time. This setup does not cover the situation in
which the hypothesis of interest might change, which is relevant in real
social network dynamics. In our recurrent political example, users can switch
the discussion topic from candidate A to candidate B, if suddenly a new event
brings relevance to B. To represent this randomness, we choose to model the
hypothesis of interest, or _trending_ hypothesis, as a random variable
following some underlying probability mass function over the set of
hypotheses. Another notable work on social learning with partial information
is [19], which assumes that each agent shares an _action_ (i.e., a sample)
that is determined with respect to its belief, which is a different problem
than the current one.

Limited communication over networks: There are also works whose purpose is to
design communication-efficient distributed decision-making systems. For
instance, the work [20] studies event-triggered information sharing
mechanisms. In contrast, we consider a _random_ choice of the trending
hypothesis independent of the history of the environment. In [21],
distributing partial hypotheses sets for agents to track is examined, but we
do not consider hypothesis assignment problems in this work. In addition to
these, the work [22] proposes communicating with one randomly sampled agent
instead of all neighbors at each time instant. Moreover, quantizing the
beliefs is possible and studied in [23, 24]. In our work, decreasing the
communication burden on the nodes is instead achieved by transmitting partial
beliefs.

Estimation of hidden belief components: When agents share partial beliefs, one
is faced with the challenge of estimating the hidden/latent belief components.
In [18], the hidden beliefs are assumed to be uniform among non-transmitted
components. Under some situations, this strategy can become fully confident on
a wrong hypothesis. In this work, we propose an algorithm where agents
_bootstrap_. Namely, they utilize their own beliefs for estimating their
neighbors’ non-transmitted components. As it is shown in the sequel, this
practice helps make the system more robust by precluding learning a wrong
hypothesis. Note that the concurrent work [25] extends [18] for memory-aware
strategies for the fixed transmitted hypothesis case. In contrast, we study
dynamic hypotheses and the strategy we propose in this work estimates the
hidden belief components in a different way.

Network disagreement: In traditional social learning where agents share their
entire belief with each other, it is known that all agents eventually come to
an agreement on the truth [7, 8, 9, 10]. However, a full agreement across
agents is rarely encountered over social networks in real life. As we show in
Sec. V-B, the property that agents utilize their own information while filling
hidden components of the received beliefs, make them _conservative_. This can
prevent agreement across the network as well as truth learning. Note that this
phenomenon is different from the _stubborn_ behavior considered in [26, 27,
28, 29], where the stubborn agents are non-typical agents that do not change
their beliefs and possibly supply misinformation to the network. Other works
that provide proofs for network disagreement include $i)$ the work [30, 31],
which considers social learning under dynamic state of nature, and also $ii)$
the works [32, 33], which studies homophilic agents.

Decentralized optimization: A related line of work is decentralized
optimization over networks which has a rich literature (see e.g., [34, 35, 17,
36, 37]). Several scenarios for networked agents behavior are considered in
the literature, including asynchronous behavior [38, 39, 40, 41, 42, 43],
quantized communication [44, 45], and randomized partial adaptation based on
coordinate descent algorithms [46, 47]. However, our study is on social
learning, which amounts to a different problem formulation. For example,
within a deep learning context, decentralized optimization corresponds to
collaborative training of neural networks using labeled data, whereas social
learning corresponds to a collective inference process, where agents aim to
classify sequential and unlabeled data under partial and heterogeneous
information [48]. Another important concept from the optimization domain is
the stochastic mirror descent algorithm [49, 37] whose connection to canonical
social learning algorithms is studied in [50]. In Appendix B, we provide the
connection to mirror descent for the current partial information sharing
setting.

Notation. We denote random variables in bold, e.g., $\bm{x}$. The expectation
with respect to the distribution of $\bm{x}$ is denoted by $\mathbb{E}_{x}$.
We use $i$ to denote time steps as opposed to some prior works that use it for
agent indices. Almost sure convergence of a sequence of random variables
$\\{\bm{x}_{i}\\}$ to a random variable $\bm{x}$ is denoted by

$\lim_{i\to\infty}\bm{x}_{i}\operatorname{\stackrel{{\scriptstyle\textup{a.s.}}}{{=}}}\bm{x}.$
(1)

When clear from the context, we simply write
$\bm{x}_{i}\operatorname{\xrightarrow{\textup{a.s.}}}\bm{x}$.
$D_{\textup{KL}}(p||q)$ represents the Kullback-Leibler (KL) divergence of two
distributions $p$ and $q$. All-ones vector of dimension $K$ is denoted by
$\mathds{1}_{K}$. The operator $\mathbb{I}$ denotes the indicator function
such that when the Boolean condition $B$ is true, then $\mathbb{I}\\{B\\}=1$.
Otherwise, $\mathbb{I}\\{B\\}=0$.

##  III Preliminaries

###  III-A Problem Setting

We consider the setting in which $K$ agents over a network $\mathcal{N}$ try
to distinguish the true state of nature $\theta^{\circ}\in\Theta$, from among
a finite set of $H$ hypotheses, collected into the set
$\Theta=\\{1,2,\dots,H\\}$. The confidence of each agent $k$ on
$\theta\in\Theta$ being the true hypothesis at time instant $i$ is denoted by
the belief $\mu_{k,i}(\theta)$. The belief vector $\mu_{k,i}$ is assumed to be
a probability mass function (pmf) over all hypotheses $\Theta$. At each time
instant $i$, each agent $k$ receives a private observation $\bm{\xi}_{k,i}$
that is partially informative about the true state $\theta^{\circ}$. This
observation is distributed according to some marginal distribution
$L_{k}(\cdot|\theta^{\circ})$, with all observations assumed to be independent
and identically distributed (i.i.d.) over time. However, observations can be
dependent across different agents. As in other works on social learning, we
assume that agents know their own marginal likelihood functions, denoted by
$L_{k}(\cdot|\theta)$ for all $\theta\in\Theta$. The models by agent $k$ are
only known to that agent. To ensure that the models share the same support
with the unknown true distribution, it is assumed that:

$\displaystyle
D_{\textup{KL}}(L_{k}(\cdot|\theta^{\circ})||L_{k}(\cdot|\theta))<\infty$ (2)

for all agents and hypotheses, i.e., for all $k\in\mathcal{N}$ and
$\theta\in\Theta$. This assumption ensures that each observation has finite
informativeness about the true state.

Network topology: Agents are assumed to be connected by a strongly-connected
graph [17] to which we associate a combination matrix $A\triangleq[a_{\ell
k}]$ — see Fig. 2. In other words, there exists a path between any pair of
agents $(\ell,k)$, and there is at least one agent with a positive self-loop,
say, $a_{mm}>0$ for some agent $m$. This implies that $A$ is a primitive
matrix [17]. Each entry $a_{\ell k}$ of the matrix $A$ is nonnegative and
represents the weight agent $k$ assigns to the information it receives from
agent $\ell$. The scalar $a_{\ell k}$ is nonzero if, and only if, agent $\ell$
is a neighbor of agent $k$, i.e., $\ell\in\mathcal{N}_{k}$. The matrix $A$ is
assumed to be left stochastic; i.e., the entries on each of its columns add up
to 1. In other words,

$\mathds{1}_{K}^{\operatorname{\mathsf{T}}}A=\mathds{1}_{K}^{\operatorname{\mathsf{T}}},\quad
a_{\ell k}\geq 0,\quad a_{\ell k}=0\iff\ell\notin\mathcal{N}_{k}.$ (3)

It follows from the Perron-Frobenius theorem [17, 37] that $A$ has an
eigenvector corresponding to the eigenvalue at 1, and all entries of this
eigenvector are positive and add up to one, i.e.,

$Av=v,\quad\mathds{1}_{K}^{\operatorname{\mathsf{T}}}v=1,\quad v\succ 0,$ (4)

where $\succ$ denotes an element-wise inequality. We refer to $v$ as the
Perron vector of $A$. Its $k$-th entry $v_{k}$ is a measure of the centrality
of agent $k$.

Figure 2: An illustration of the network model. While the network is in
general directed, for visual simplicity, the edges are represented with lines
instead of arrows in this figure.

In this work, we are interested in whether individual agents can distinguish
the true state $\theta^{\circ}$ from other hypotheses. We distinguish three
possible scenarios on this matter.

######  Definition 1 (Learning and mislearning).

We say that truth learning occurs whenever:

$\bm{\mu}_{k,i}(\theta^{\circ})\operatorname{\xrightarrow{\textup{a.s.}}}1,\qquad\forall
k\in\mathcal{N}$ (5)

In other words, truth learning means that agents become fully confident on the
true hypothesis with probability one. In any other scenario we say that there
is no learning. Among the cases where there is no learning, we define total
mislearning as corresponding to the case in which for some
$\theta\in\Theta\setminus\\{\theta^{\circ}\\}$:

$\bm{\mu}_{k,i}(\theta)\operatorname{\xrightarrow{\textup{a.s.}}}1,\qquad\forall
k\in\mathcal{N}$ (6)

In this case, agents become fully confident on a wrong hypothesis, with
probability one.$\hfill\blacksquare$

We emphasize that according to Definition 1, learning and mislearning occur
whenever agents become fully confident on some hypothesis. In traditional
Bayesian learning, the belief incorporates knowledge from an increasing number
of measurements, with the expectation that the belief is not only maximized
around the truth but also concentrates its mass on it. Any other outcome would
imply a system malfunction. The same asymptotic learning outcome is expected
in our scenario as well. An infinite amount of evidence should lead to
certainty. An alternative definition of learning could be to require that the
agents’ beliefs are maximized at the true hypothesis [30]. We adopt the former
definition for consistency with other traditional works in the field.

Before presenting the main contributions of this work, for the benefit of
reader, we briefly review the traditional social learning paradigms with full
and partial information sharing [7, 8, 9, 10, 18].

###  III-B Full Information Sharing

In non-Bayesian social learning, at every iteration, agents first incorporate
their personal observations to their beliefs. To do so, they perform a _local_
Bayesian update and obtain intermediate beliefs:

$\displaystyle\bm{\psi}_{k,i}(\theta)=\frac{L_{k}(\bm{\xi}_{k,i}|\theta)\bm{\mu}_{k,i-1}(\theta)}{\sum_{\theta^{\prime}\in\Theta}L_{k}(\bm{\xi}_{k,i}|\theta^{\prime})\bm{\mu}_{k,i-1}(\theta^{\prime})}.$
(7)

Subsequently, they exchange the intermediate beliefs with their immediate
neighbors in the graph for _all_ hypotheses. Each agent then averages
geometrically the received intermediate beliefs from its neighbors to obtain
the updated belief:

$\bm{\mu}_{k,i}(\theta)=\frac{\prod\limits_{\ell\in\mathcal{N}_{k}}(\bm{\psi}_{\ell,i}(\theta))^{a_{\ell
k}}}{\sum\limits_{\theta^{\prime}\in\Theta}\prod\limits_{\ell\in\mathcal{N}_{k}}(\bm{\psi}_{\ell,i}(\theta^{\prime}))^{a_{\ell
k}}},$ (8)

for each $\theta\in\Theta$. In (8), the term in the numerator is a weighted
geometric average of the received intermediate beliefs, and the denominator is
a normalization term that makes sure the belief vector $\bm{\mu}_{k,i}$ is a
pmf over $\Theta$. Note that there are variations where the combination step
(8) uses an arithmetic averaging operation, as opposed to geometric averaging
[7, 8]. These two averaging strategies possess distinct properties [51] and
the choice of using which for social learning is dependent upon the specific
application under consideration. However, in general, it is more common to use
geometric averaging for fusing probability density functions, while arithmetic
averaging is typically favored for combining point estimates of random
variables [52]. Moreover, in the context of social learning, the work [53]
demonstrated that geometric averaging yields a faster rate learning compared
to the arithmetic averaging. Therefore, in this work, we focus on geometric
averaging strategies as in [9, 10].

To avoid trivial cases where agents discard some hypotheses right from the
start, the following condition is necessary.

######  Assumption 1 (Initial beliefs).

All initial beliefs are strictly positive at all hypotheses, i.e., for each
agent $k$ and for all hypotheses $\theta\in\Theta$,
$\bm{\mu}_{k,0}(\theta)>0$. $\hfill\blacksquare$

If Assumption 1 is violated for a hypothesis $\theta$, due to the nature of
the geometric fusion rule, all agents would have zero belief on $\theta$ in
finite time. Moreover, the following condition enables the aggregate of all
agents to distinguish the true hypothesis from the wrong ones.

######  Assumption 2 (Global identifiability).

For each wrong hypothesis $\theta\neq\theta^{\circ}$, there exists at least
one agent $k$ that can distinguish $\theta$ from $\theta^{\circ}$, namely,

$\displaystyle
D_{\textup{KL}}\Big{(}L_{k}(\cdot|\theta^{\circ})\big{|}\big{|}L_{k}(\cdot|\theta)\Big{)}>0$
(9)

$\hfill\blacksquare$

Note that this is a weaker assumption than _local_ identifiability, which
requires _all_ agents (not only one) to have the capability of distinguishing
the truth individually. Under Assumptions 1 and 2, agents can learn the truth
with full confidence.

######  Proposition 1 (Learning with full communication [9, 10]).

Under Assumptions 1 and 2, the social learning algorithm (7)–(8) allows each
agent $k$ to learn the truth with probability one, i.e.,

$\bm{\mu}_{k,i}(\theta^{\circ})\operatorname{\xrightarrow{\textup{a.s.}}}1.$
(10)

Furthermore, the asymptotic learning of the truth occurs at an exponential
rate. That is to say, the asymptotic convergence rate of the beliefs on wrong
hypotheses $\theta\neq\theta^{\circ}$ to zero is given by

$\frac{1}{i}\log\frac{\bm{\mu}_{k,i}(\theta)}{\bm{\mu}_{k,i}(\theta^{\circ})}\operatorname{\xrightarrow{\textup{a.s.}}}\sum_{k=1}^{K}-v_{k}D_{\textup{KL}}\Big{(}L_{k}(\cdot|\theta^{\circ})\big{|}\big{|}L_{k}(\cdot|\theta)\Big{)}.$
(11)

###### Proof.

The full proof appears in [9, 10]. In Appendix A, we provide a brief sketch
for the benefit of the reader. $\hfill\blacksquare$

The future results stated in Theorem 1 and Corollary 1 will show that agents
can still learn the truth if they exchange beliefs on _only one_ random
hypothesis at each time instant. The randomness in the shared hypothesis and
the incomplete information received from the neighbors introduce new
challenges into the analysis, in comparison to the proof of Proposition 1
above. This aspect is treated in later sections.

###  III-C Partial Information Sharing

The canonical setting described in the previous section assumes that agents
share their _entire_ beliefs with each other at every iteration. The work [18]
considers an alternative setting where agents share their beliefs on only one
hypothesis of interest $\tau\in\Theta$, which is _fixed_ over time. In
particular, after agents perform the local adaptation step (7), each agent $k$
receives $\bm{\psi}_{\ell,i}(\tau)$ from its neighbors
$\ell\in\mathcal{N}_{k}$. Then, each agent $k$ completes the missing entries
of the received belief vectors by using the construction:

$\displaystyle\widehat{\bm{\psi}}_{\ell,i}(\theta)=\begin{dcases}\bm{\psi}_{\ell,i}(\tau),&\theta=\tau\\\
\frac{1-\bm{\psi}_{\ell,i}(\tau)}{H-1},&\theta\neq\tau\end{dcases}$ (12)

for $\ell\in\mathcal{N}_{k}$. Observe that the received component of the
intermediate belief is used as is, while the remaining components are assigned
uniform weight. Then, these modified beliefs are used in the combination step:

$\bm{\mu}_{k,i}(\theta)=\frac{\prod\limits_{\ell\in\mathcal{N}_{k}}(\widehat{\bm{\psi}}_{\ell,i}(\theta))^{a_{\ell
k}}}{\sum\limits_{\theta^{\prime}\in\Theta}\prod\limits_{\ell\in\mathcal{N}_{k}}(\widehat{\bm{\psi}}_{\ell,i}(\theta^{\prime}))^{a_{\ell
k}}}.$ (13)

The work [18] provides a detailed analysis of this algorithm and proposes a
self-aware variant of it where each agent $k$ uses $\bm{\psi}_{k,i}(\theta)$
instead of the approximation $\widehat{\bm{\psi}}_{k,i}(\theta)$ in (13). For
the purposes of the current work, it is enough to state the following results,
which we will refer to in the sequel. Let us introduce the following notation
for the average likelihood function. The average is over the non-transmitted
components (denoted by the symbol $\overline{\tau}$):

$L_{k}(\xi|\overline{\tau})\triangleq\frac{1}{H-1}\sum_{\theta\in\Theta\setminus\\{\tau\\}}L_{k}(\xi|\theta).$
(14)

Then, the following two results are from [18].

######  Proposition 2 (Learning with truth sharing [18, Theorem 1]).

If $\tau=\theta^{\circ}$, under Assumption 1 and a modified global
identifiability assumption, i.e., if there exists an agent such that

$D_{\textup{KL}}\Big{(}L_{k}(\cdot|\tau)\big{|}\big{|}L_{k}(\cdot|\overline{\tau})\Big{)}>0,$
(15)

then, truth learning occurs with full confidence:

$\bm{\mu}_{k,i}(\tau)\operatorname{\xrightarrow{\textup{a.s.}}}1$ (16)

for each agent $k$ under (12)–(13). $\hfill\blacksquare$

Proposition 2 shows that if the hypothesis $\tau$ agents exchange information
about happens to be the truth $\theta^{\circ}$, then this is sufficient for
truth learning with full confidence. However, if they are not discussing the
truth, this can lead to mislearning a wrong hypothesis as the next result
illustrates.

######  Proposition 3 (Total mislearning [18, Theorem 3]).

If $\tau\neq\theta^{\circ}$, under Assumption 1 and the condition that

$\sum_{k=1}^{K}\\!v_{k}D_{\textup{KL}}\Big{(}\\!L_{k}(\cdot|\theta^{\circ})\big{|}\big{|}L_{k}(\cdot|\tau)\\!\Big{)}\\!<\\!\sum_{k=1}^{K}\\!v_{k}D_{\textup{KL}}\Big{(}\\!L_{k}(\cdot|\theta^{\circ})\big{|}\big{|}L_{k}(\cdot|\overline{\tau})\\!\Big{)}$
(17)

all agents learn a wrong hypothesis with full confidence:

$\bm{\mu}_{k,i}(\tau)\operatorname{\xrightarrow{\textup{a.s.}}}1$ (18)

for each agent $k$ under (12)–(13). $\hfill\blacksquare$

In the algorithm we propose in this work (Alg. 1), agents will fill the
missing beliefs using their own information, instead of assigning uniform
values to them. This practice will result in outcomes that are opposite of
Propositions 2 and 3. Namely, we show in the following that exclusive truth
sharing does not suffice for truth learning (Sec. V-B), while total
mislearning can never occur (Theorem 2) under Algorithm 1.

##  IV Social Learning under Trending Topics

As opposed to existing works that require transmission of the entire beliefs
at each iteration, or exchanging a fixed component of the beliefs, in this
work we allow agents to share a random component at each iteration. Similar to
[18], each agent will continue to compute its intermediate belief
$\bm{\psi}_{k,i}(\theta)$ for every possible $\theta\in\Theta$ according to
(7), and the agents will continue to share with their neighbors information
about their belief for _only one_ of the hypotheses. However, the agents will
be sharing information about the same _trending_ hypothesis
$\bm{\tau}_{i}\in\Theta$. Here, $\bm{\tau}_{i}$ is a random variable that
depends on the time instant $i$, and is therefore allowed to change over time.
The motivation for this setting is two-fold. First, people tend to concentrate
on particular topics of discussion over social networks, as indicated earlier
in the introduction. Second, if agents (e.g., sensors, robots) have the same
random key, they can choose the same hypothesis at each iteration without
needing a central controller, and then exchange beliefs on that hypothesis
alone, as opposed to the more costly approach of exchanging entire beliefs.
Utilizing randomness this way can prove useful compared to a periodic
scheduling scheme for security reasons, since deciphering a random key is
harder for eavesdroppers than inferring a fixed schedule. We denote the
distribution of $\bm{\tau}_{i}$ by $\pi$, where $\pi$ is a probability vector
over the set of hypotheses $\Theta$, and write
$\mathbb{P}(\bm{\tau}_{i}=\theta)=\pi_{\theta}$. We further assume that
$\bm{\tau}_{i}$ is i.i.d. over time and also independent of all observations
over space and time. Again, since the agents receive incomplete belief vectors
from their neighbors (actually, they receive only one entry from these
vectors), the agents will again need to complete the missing entries. In the
proposed strategy, the agents use their own intermediate local beliefs to fill
in for the missing beliefs from their neighbors by using the following
construction. Namely, agent $k$ completes the belief vector received from its
neighbor $\ell$ by using:

$\displaystyle\bm{\phi}^{(k)}_{\ell,i}(\theta)=\begin{dcases}\bm{\psi}_{\ell,i}(\theta),&\theta=\bm{\tau}_{i}\\\
\bm{\psi}_{k,i}(\theta),&\theta\neq\bm{\tau}_{i}\end{dcases}.$ (19)

By doing so, the entries of $\bm{\phi}^{(k)}_{\ell,i}$ need not add up to 1.
For this reason, agent $k$ can normalize (19) according to:

$\widehat{\bm{\psi}}^{(k)}_{\ell,i}(\theta)=\frac{\bm{\phi}^{(k)}_{\ell,i}(\theta)}{\sum_{\theta^{\prime}\in\Theta}\bm{\phi}^{(k)}_{\ell,i}(\theta^{\prime})}.$
(20)

whose denominator can be written as

$\sum_{\theta^{\prime}\in\Theta}\bm{\phi}^{(k)}_{\ell,i}(\theta^{\prime})=1-\bm{\psi}_{k,i}(\bm{\tau}_{i})+\bm{\psi}_{\ell,i}(\bm{\tau}_{i}).$
(21)

We refer to (19)–(20) as a bootstrapping step. Subsequently, the agents
combine the _approximate_ intermediate beliefs from (20) to update their
beliefs as in (8) and (13):

$\displaystyle\bm{\mu}_{k,i}(\theta)=\frac{\prod\limits_{\ell\in\mathcal{N}_{k}}(\widehat{\bm{\psi}}_{\ell,i}^{(k)}(\theta))^{a_{\ell
k}}}{\sum\limits_{\theta^{\prime}\in\Theta}\prod\limits_{\ell\in\mathcal{N}_{k}}(\widehat{\bm{\psi}}_{\ell,i}^{(k)}(\theta^{\prime}))^{a_{\ell
k}}}.$ (22)

The procedure is summarized in Algorithm 1. Its connection to distributed
stochastic mirror descent algorithms is explained in Appendix B. Observe that
the algorithm is _self-aware_ because for each agent $k$, it follows from (24)
that $\widehat{\bm{\psi}}^{(k)}_{k,i}(\theta)=\bm{\psi}_{k,i}(\theta)$. In
other words, agents use their own intermediate beliefs as is.

Algorithm 1 Social learning with trending hypothesis

1:set initial priors $\bm{\mu}_{k,0}(\theta)>0$, $\forall\theta\in\Theta$ and
$\forall k\in\mathcal{N}$

2:while $i\geq 1$ do

3: for each agent $k$ do

4: receive private observation $\bm{\xi}_{k,i}$

5: adapt to obtain intermediate belief:
$\bm{\psi}_{k,i}(\theta)=\frac{L_{k}(\bm{\xi}_{k,i}|\theta)\bm{\mu}_{k,i-1}(\theta)}{\sum_{\theta^{\prime}\in\Theta}L_{k}(\bm{\xi}_{k,i}|\theta^{\prime})\bm{\mu}_{k,i-1}(\theta^{\prime})}$
(23)

6: end for

7: agents exchange $\\{\bm{\psi}_{k,i}(\bm{\tau}_{i})\\}$ on the current
hypothesis

8: of interest $\bm{\tau}_{i}\sim\pi$

9: for each agent $k$ do

10: approximate intermediate beliefs for $\ell\in\mathcal{N}_{k}$ by
bootstrapping:
$\displaystyle\quad\widehat{\bm{\psi}}^{(k)}_{\ell,i}(\theta)=\begin{dcases}\frac{\bm{\psi}_{\ell,i}(\theta)}{1-\bm{\psi}_{k,i}(\bm{\tau}_{i})+\bm{\psi}_{\ell,i}(\bm{\tau}_{i})},&\theta=\bm{\tau}_{i}\\\
\frac{\bm{\psi}_{k,i}(\theta)}{1-\bm{\psi}_{k,i}(\bm{\tau}_{i})+\bm{\psi}_{\ell,i}(\bm{\tau}_{i})},&\theta\neq\bm{\tau}_{i}\end{dcases}$
(24)

11: combine approximate beliefs:
$\bm{\mu}_{k,i}(\theta)=\frac{\prod\limits_{\ell\in\mathcal{N}_{k}}(\widehat{\bm{\psi}}_{\ell,i}^{(k)}(\theta))^{a_{\ell
k}}}{\sum\limits_{\theta^{\prime}\in\Theta}\prod\limits_{\ell\in\mathcal{N}_{k}}(\widehat{\bm{\psi}}_{\ell,i}^{(k)}(\theta^{\prime}))^{a_{\ell
k}}}$ (25)

12: end for

13: $i\leftarrow i+1$

14:end while

Recall that in traditional non-Bayesian social learning (7)–(8), entire belief
vectors are exchanged and hence there is no approximation of the intermediate
beliefs, that is to say,

$\displaystyle\widehat{\bm{\psi}}^{(k)}_{\ell,i}(\theta)=\bm{\psi}_{\ell,i}(\theta).$
(26)

In addition, in the fixed hypothesis sharing case (12), there is a fixed
transmitted hypothesis $\bm{\tau}_{i}=\tau$ and non-transmitted hypotheses are
assumed to be uniformly likely. In contrast, in (24) agents exploit their own
beliefs as prior information.

##  V Main Results

###  V-A Truth Learning

In this section, we present results that characterize truth learning under
certain conditions. First, we define the following loss function in order to
assess the disagreement between the truth and the belief of each agent $k$ at
time $i$:

$\displaystyle Q(\bm{\mu}_{k,i})\triangleq
D_{\textup{KL}}(\delta_{\theta^{\circ}}||\bm{\mu}_{k,i}),$ (27)

where we denote the true probability mass function as the Kronecker-delta
function:

$\displaystyle\delta_{\theta^{\circ}}(\theta)=\begin{dcases}1,&\theta=\theta^{\circ}\\\
0,&\theta\neq\theta^{\circ}\end{dcases}.$ (28)

Observe that

$Q(\bm{\mu}_{k,i})=\sum_{\theta\in\Theta}\delta_{\theta^{\circ}}(\theta)\log\frac{\delta_{\theta^{\circ}}(\theta)}{\bm{\mu}_{k,i}(\theta)}=-\log\bm{\mu}_{k,i}(\theta^{\circ}),$
(29)

where we use the convention that $0\log 0=0$. The network loss is defined as
the weighted average of the individual loss functions, where the weighting is
given by the Perron entries:

$Q(\bm{\mu}_{i})\triangleq\sum_{k=1}^{K}v_{k}Q(\bm{\mu}_{k,i})=-\sum_{k=1}^{K}v_{k}\log\bm{\mu}_{k,i}(\theta^{\circ}).$
(30)

We denote the history of observations and transmitted hypotheses up to time
$i$ by
$\bm{\mathcal{F}}_{i}~{}\triangleq~{}\\{\bm{\tau}_{i},\bm{\xi}_{i},\bm{\tau}_{i-1},\bm{\xi}_{i-1},\dots\\}$,
where we introduced the aggregate vector of observations
$\bm{\xi}_{i}\triangleq\\{\bm{\xi}_{k,i}\\}_{k=1}^{K}$. The following result
shows that the conditional expectation of the network loss does not increase,
given the history $\bm{\mathcal{F}}_{i-1}$.

######  Lemma 1 (Network average loss).

The network loss $Q(\bm{\mu}_{i})$ is a super-martingale, namely,

$\displaystyle\mathbb{E}\Big{[}Q(\bm{\mu}_{i})\Big{|}\bm{\mathcal{F}}_{i-1}\Big{]}$
$\displaystyle\leq Q(\bm{\mu}_{i-1})$ (31)

###### Proof.

See Appendix C. $\hfill\blacksquare$

In view of this lemma, Algorithm 1 leads to a robust design in the sense that
given any particular network loss realization, the loss in the next iteration
will not increase in expectation. Note that this result holds for any possible
transmission distribution $\pi$. Similar to Eq. (11) for traditional social
learning, we continue our presentation by focusing on the decay rate of the
belief ratio for some wrong hypothesis
$\theta\in\Theta\setminus\\{\theta^{\circ}\\}$ under the proposed strategy
(23)–(25).

######  Theorem 1 (Asymptotic learning rate).

For each wrong hypothesis $\theta\in\Theta\setminus\\{\theta^{\circ}\\}$, if
the transmission probability is strictly positive, i.e., $\pi_{\theta}>0$,
then the belief on that wrong hypothesis will converge to zero at an
asymptotically exponential rate under Assumption 1. Namely, for each agent
$k$:

$\displaystyle\frac{1}{i}\log\frac{\bm{\mu}_{k,i}(\theta)}{\bm{\mu}_{k,i}(\theta^{\circ})}\operatorname{\xrightarrow{\textup{a.s.}}}\sum_{k=1}^{K}-v_{k}D_{\textup{KL}}\Big{(}L_{k}(\cdot|\theta^{\circ})\big{|}\big{|}L_{k}(\cdot|\theta)\Big{)}.$
(32)

###### Proof.

See Appendix D. $\hfill\blacksquare$

The convergence rate expression in (32) is an average of the local KL-
divergences of agents, which measures their individual informativeness,
weighted by their network centralities (i.e., Perron entries). Observe that
this rate matches the rate (11) for traditional social learning algorithms,
which require transmission of full beliefs. Therefore, a positive probability
of transmitting the wrong hypothesis suffices for achieving the same
asymptotic performance with probability one, regardless of the transmission
probabilities for the remaining hypotheses. Combining Theorem 1 and Assumption
2 directly yields the following sufficient conditions for truth learning.

######  Corollary 1 (Truth learning).

Under Assumptions 1 and 2, if $\pi_{\theta}>0$ for all wrong hypotheses
$\theta\in\Theta\setminus\\{\theta^{\circ}\\}$, then each agent $k$ learns the
truth with probability one, i.e.,

$\displaystyle\bm{\mu}_{k,i}(\theta^{\circ})\operatorname{\xrightarrow{\textup{a.s.}}}1.$
(33)

$\hfill\blacksquare$

Notice that any asymmetry between the entries of $\pi$ does not affect the
learning. In particular, more or less frequent communication of a hypothesis
does not change the asymptotic rate of convergence. In [18], truth learning
(in the sense of Definition 1) occurs if, and only if, the fixed transmitted
hypothesis is the true hypothesis. Corollary 1 shows that if agents are
bootstrapping as opposed to using uniform weights [18], then learning can
occur as long as $\pi_{\theta}>0$ for all wrong hypotheses $\theta$. This
implies that they can learn the truth even if they do not discuss the true
hypothesis, i.e. even if $\pi_{\theta^{\circ}}=0$.

###  V-B Truth Sharing

In the previous section, we drew the following two conclusions: In Theorem 1,
we established that if there is a positive probability $\pi_{\theta}>0$ of
transmitting a wrong hypothesis $\theta\neq\theta^{\circ}$, this is sufficient
to reject $\theta$, i.e., beliefs on that hypothesis will go to zero
exponentially fast. Building upon this, in Corollary 1 we showed that
exchanging all wrong hypotheses with positive probability (i.e.,
$\pi_{\theta}>0,\>\forall\theta\neq\theta^{\circ}$) is sufficient for agents
to infer the truth. Given these findings, the question arises: Is the
_exclusive_ exchange ($\pi_{\theta^{\circ}}=1$) of the true hypothesis alone
enough for learning? We give a negative answer to this question by providing a
toy counter-example where agents do not learn even when
$\pi_{\theta^{\circ}}=1$.

Consider a fully-connected network of 3 agents (see Fig. 3). The hypotheses
set is $\Theta=\\{1,2,3,4\\}$ where incidentally $\theta^{\circ}=4$. Assume
that agent $k$ cannot distinguish between the true hypothesis
$\theta^{\circ}=4$ and the hypothesis $\theta_{k}=k$, i.e.,
$D_{\textup{KL}}(L_{k}(\cdot|\theta^{\circ})||L_{k}(\cdot|\theta_{k}))=0$.
Assume further that each agent $k$ is capable of distinguishing hypotheses
other than $\theta_{k}$ and $\theta^{\circ}$ (e.g., agent $1$ can distinguish
hypotheses $2$ and $3$, but cannot distinguish $1$ and $4$). Since each wrong
hypothesis $\theta\neq\theta^{\circ}$ can be distinguished by at least one
agent, the problem is globally identifiable, satisfying Assumption 2.

Figure 3: A network of 3 agents. Each agent $k$ can distinguish all but the
hypotheses $\theta^{\circ}=4$ and $\theta_{k}=k$. In the assumed scenario,
belief values on $\theta^{\circ}=4$ are assumed to be $\alpha\in(0,1)$ for all
agents. Belief values at locally distinguishable hypotheses are assumed to be
0.

Imagine that at time $i$, $\bm{\mu}_{k,i}(\theta^{\circ})=\alpha$ and
$\bm{\mu}_{k,i}(\theta_{k})=1-\alpha$ for each agent $k$. In other words, for
each agent $k$, the beliefs on hypotheses that are locally distinguishable are
equal to 0 111Under Assumption 1 and Eq. (2), the belief values remain nonzero
for all finite time instants. For the ease of the presentation, we assume that
sufficient time has elapsed so that the beliefs on locally distinguishable
hypotheses are sufficiently close to 0.. Using (7) yields the intermediate
beliefs:

$\displaystyle\bm{\psi}_{k,i+1}(\theta^{\circ})=\frac{L_{k}(\bm{\xi}_{k,i+1}|\theta^{\circ})\bm{\mu}_{k,i}(\theta^{\circ})}{L_{k}(\bm{\xi}_{k,i+1}|\theta^{\circ})\bm{\mu}_{k,i}(\theta^{\circ})+L_{k}(\bm{\xi}_{k,i+1}|\theta_{k})\bm{\mu}_{k,i}(\theta_{k})}.$
(34)

Since
$L_{k}(\bm{\xi}_{k,i+1}|\theta^{\circ})=L_{k}(\bm{\xi}_{k,i+1}|\theta_{k})$
(their KL divergence is assumed to be 0):

$\displaystyle\bm{\psi}_{k,i+1}(\theta^{\circ})=\frac{\bm{\mu}_{k,i}(\theta^{\circ})}{\bm{\mu}_{k,i}(\theta_{k})+\bm{\mu}_{k,i}(\theta^{\circ})}=\bm{\mu}_{k,i}(\theta^{\circ})=\alpha$
(35)

Similarly,

$\displaystyle\bm{\psi}_{k,i+1}(\theta_{k})=\bm{\mu}_{k,i}(\theta_{k})=1-\alpha.$
(36)

Agents fill the received intermediate beliefs by using their own beliefs (i.e,
they bootstrap) according to (24). Here, since $\pi_{\theta^{\circ}}=1$ (i.e.,
$\bm{\tau}_{i+1}=\theta^{\circ}$) we get:

$\displaystyle\widehat{\bm{\psi}}^{(k)}_{\ell,i+1}(\theta^{\circ})=\bm{\psi}_{\ell,i+1}(\theta^{\circ})=\alpha,$
(37)

and

$\displaystyle\widehat{\bm{\psi}}^{(k)}_{\ell,i+1}(\theta_{k})=\bm{\psi}_{k,i+1}(\theta_{k})=1-\alpha.$
(38)

Finally, after the combination of the approximate intermediate beliefs (25),
we arrive at

$\displaystyle\bm{\mu}_{k,i+1}(\theta^{\circ})=\bm{\mu}_{k,i}(\theta^{\circ})=\alpha,$
(39)

and

$\displaystyle\bm{\mu}_{k,i+1}(\theta_{k})=\bm{\mu}_{k,i}(\theta_{k})=1-\alpha.$
(40)

This is an equilibrium (fixed point) for the algorithm. Regardless of the
emitted observations, the beliefs of agents will not change over time.
Consequently, if $\alpha$ is small, agents can get stuck in beliefs where
their confidence levels on the wrong hypotheses are higher than their
confidence on the true hypothesis.

The results in Sec. V-A and the counter-example in this section reveal that it
is the exchange of the wrong hypotheses that promotes truth learning, and not
truth sharing. The intuition behind this rather surprising outcome is the
following. In the current strategy, agents fill the missing belief components
with their own beliefs (using bootstrapping). If their beliefs happen to align
closely on the true hypothesis, it is difficult to change them. This
undesirable equilibrium is bypassed when agents exchange beliefs on wrong
hypotheses. This is due to Assumption 2, which states that there exists at
least one agent that is able to drive the beliefs on a wrong hypothesis to
zero.

In [18] (see Eq. (12)), when the fixed transmitted hypothesis corresponds to
the truth, truth learning in the sense of Definition 1 occurs almost surely.
The example described in this section suggests that using one’s own belief for
estimating non-transmitted components of neighbors, i.e., bootstrapping, as
opposed to using uniform priors, may lead regular agents to become
_conservative_ about their own opinions. It can prevent learning under partial
information sharing. In addition to not learning the truth, the network can
also fail to reach consensus and opinion clusters might emerge. In Fig. 3,
agents having positive beliefs for different hypotheses can have a major
effect especially when $\alpha$ is small. It leads to a strong network
disagreement. Network disagreement phenomena were observed in the works [26,
27, 28, 29] when there are special agents who never change their opinions,
i.e., stubborn agents. Our result, on the other hand, indicates that even when
the network is only composed of regular agents, limited communication can
hinder concurrence and truth learning.

###  V-C Impossibility of Mislearning

The previous section demonstrated that bootstrapping might induce network
disagreement and poor equilibrium. In this section, we provide a positive
result in the opposite direction: Agents will never be fully confident on a
wrong hypothesis. Total mislearning cannot occur.

######  Theorem 2 (Impossibility of mislearning).

Under Assumption 1, agents will always have positive confidence on the true
hypothesis. Namely, for each agent $k$, $\bm{\mu}_{k,i}(\theta^{\circ})>0$ for
any finite time $i$, and

$\displaystyle\mathbb{P}\Big{(}\liminf_{i\to\infty}\bm{\mu}_{k,i}(\theta^{\circ})=0\Big{)}=0,$
(41)

or alternatively, for $\theta\in\Theta\setminus\\{\theta^{\circ}\\}$

$\displaystyle\mathbb{P}\Big{(}\limsup_{i\to\infty}\bm{\mu}_{k,i}(\theta)=1\Big{)}=0.$
(42)

###### Proof.

See Appendix E. $\hfill\blacksquare$

Notice that there is no assumption on the transmission probabilities in
Theorem 2. With bootstrapping, agents never learn a wrong hypothesis. In [18],
it was shown that agents might mislearn a wrong hypothesis if the fixed
transmitted hypothesis is not the true hypothesis — recall Proposition 3. As a
matter of fact, bootstrapping leads to a more robust design in the face of
partial communication.

Figure 4: Leftmost panel: Network topology. Middle panel: Evolution of the
shared hypothesis $\bm{\tau}_{i}$ over time in the upper panel, and belief
evolution for agent 1 showing _truth learning_ in the bottom panel. Rightmost
panel: Experimental rates of convergence for agent 1, i.e.,
$\bm{r}_{1,i}(\theta)$, defined in (45), for different hypotheses (in colored
lines), compared with the theoretical asymptotic rate of convergence, i.e.,
${\sf d}_{\sf ave}$ defined in (46) (in black dotted lines).

##  VI Numerical Simulations

Consider a $10-$agent strongly-connected network (see the topology in the
leftmost panel of Fig. 4). The combination matrix is designed using the
Metropolis rule [17], yielding a doubly-stochastic matrix. Agents are trying
to detect the true state $\theta^{\circ}$ among a set of five hypotheses,
namely $\Theta\triangleq\\{1,2,3,4,5\\}$. Incidentally, we assume that
$\theta^{\circ}=1$. To accomplish this task, agents use the protocol described
in (23)-(25), where the random shared hypothesis $\bm{\tau}_{i}$ is
distributed according to the following probability mass function:

$\mathbb{P}(\bm{\tau}_{i}=\theta)=\pi_{\theta}=\begin{cases}0,&\text{ if
}\theta=\theta^{\circ}\\\ 0.25,&\text{ otherwise}.\end{cases}$ (43)

Agents consider a family of unit-variance Gaussian densities:

$f_{n}(x)=\frac{1}{\sqrt{2\pi}}\exp\Big{\\{}-\frac{(x-0.3n)^{2}}{2}\Big{\\}}$
(44)

for $n=1,2,3,4,5$. The likelihoods of agents are chosen among these Gaussian
densities according to the identifiability setup in Table I. For example, we
note that agents $8$–$10$ cannot distinguish hypotheses $1$ and $5$. Observe
that the global identifiability condition in Assumption 2 is satisfied.

TABLE I: Identifiability Setup for Network in Fig. 4 Agent $k$ |  Likelihood Function: $L_{k}(x|\theta)$
---|---
$\theta=1$ | $\theta=2$ | $\theta=3$ | $\theta=4$ | $\theta=5$
$1-2$ | $f_{1}$ | $f_{1}$ | $f_{3}$ | $f_{4}$ | $f_{5}$
$3-5$ | $f_{1}$ | $f_{2}$ | $f_{1}$ | $f_{4}$ | $f_{5}$
$6-7$ | $f_{1}$ | $f_{2}$ | $f_{3}$ | $f_{1}$ | $f_{5}$
$8-10$ | $f_{1}$ | $f_{2}$ | $f_{3}$ | $f_{4}$ | $f_{1}$

In the middle panel of Fig. 4, we see the evolution of the belief for agent 1,
which shows that, although the agents never share information about the true
hypothesis, i.e., $\pi_{\theta^{\circ}}=0$, the agent asymptotically learns
the truth, as suggested by Corollary 1. A similar behavior happens for the
remaining agents.

The rightmost panel of Fig. 4 shows that the experimental convergence rates
for agent $1$, i.e.,

$\displaystyle\bm{r}_{1,i}(\theta)\triangleq\log\frac{\bm{\mu}_{1,i}(\theta)}{\bm{\mu}_{1,i}(\theta^{\circ})}$
(45)

which are shown in colored lines, approach the asymptotic convergence rates of
traditional social learning (black dotted lines):

$\displaystyle{\sf d}_{\sf
ave}(\theta)\triangleq\sum_{k=1}^{K}-v_{k}D_{\textup{KL}}\Big{(}L_{k}(\cdot|\theta^{\circ})\big{|}\big{|}L_{k}(\cdot|\theta)\Big{)}$
(46)

as predicted by Theorem 1. This means that regarding the asymptotic
convergence rate, there is no performance loss when only one hypothesis is
exchanged at each iteration as long as all wrong hypotheses have positive
probability of being transmitted.

Figure 5: Belief evolution of agent $1$ when the shared hypothesis is _fixed
over time_ to be the true state of nature. This demonstrates that while there
is no truth learning with full confidence, there is no complete rejection of
the true hypothesis as well.

In the next simulation, we illustrate that truth sharing is not sufficient for
truth learning. For that purpose, we fix the transmitted hypothesis at the
true hypothesis $\bm{\tau}_{i}=\theta^{\circ}=1$ for all $i=1,2,\dots$. The
result can be seen in Fig. 5, where we show the evolution of the belief of
agent $1$ over time. Despite sharing the true hypothesis, the _conservative_
behavior described in Section V-B hinders the ability of the agent to learn
the truth. We note that agent $1$ cannot _decidedly_ distinguish between
hypothesis $1$ and $2$, which are indistinguishable from its local point of
view (see Table I). This was suggested by the example in Section V-B, where
agents are caught in an equilibrium where they have non-zero belief values for
locally indistinguishable hypotheses. Notice that although truth learning is
not observed, there is no total mislearning phenomena as well. As suggested by
Theorem 2, the confidence in the truth is not going to 0.

##  VII Conclusion

In this work, we studied social learning under partial information sharing
where the transmitted hypothesis is changing at every iteration. In Sec. IV,
we proposed an algorithm for this setting in which agents fill the latent
belief components with their own beliefs. In Sec. V-A, we derived the rate of
convergence under the proposed algorithm and provided sufficient conditions
for truth learning. Then, in Secs. V-B and V-C, we demonstrated that by
exchanging beliefs exclusively on the true hypotheses, agents will neither
learn the truth with full confidence nor mislearn, i.e., learn a false
hypothesis with full confidence. Instead they will be unsure about the truth
among their indistinguishable hypotheses.

There are many possible extensions to the setting considered in this work. For
instance, each agent $k$ can choose a possibly different hypothesis
$\bm{\tau}_{k,i}$ to transmit at each iteration. Alternatively, the
transmitted hypothesis $\bm{\tau}_{i}$ can evolve according to some Markovian
model, instead of independently over time. These extensions introduce
additional complexities to the technical analysis, especially when managing
the random matrix products. Another interesting extension would be to see if
the current work on finite hypothesis sets can extend to continuous hypothesis
sets, such as compact sets as in [54] or non-compact sets as in the
distributed estimation literature (see e.g., [35, 55, 56]).

##  Appendix A Proof Sketch of Proposition 1

The full proof appears in [9, 10, 53]. The algorithm (7)–(8) gives rise to the
following recursion for the log-belief ratios:

$\log\frac{\bm{\mu}_{k,i}(\theta)}{\bm{\mu}_{k,i}(\theta^{\circ})}=\sum_{\ell\in\mathcal{N}_{k}}a_{\ell
k}\Big{(}\log\frac{L_{\ell}(\bm{\xi}_{\ell,i}|\theta)}{L_{\ell}(\bm{\xi}_{\ell,i}|\theta^{\circ})}+\log\frac{\bm{\mu}_{\ell,i-1}(\theta)}{\bm{\mu}_{\ell,i-1}(\theta^{\circ})}\Big{)}.$
(47)

Iterating over $i$ and dividing by $i$ gives

$\displaystyle\frac{1}{i}\log\frac{\bm{\mu}_{k,i}(\theta)}{\bm{\mu}_{k,i}(\theta^{\circ})}$
$\displaystyle=\frac{1}{i}\sum_{j=1}^{i}\sum_{\ell=1}^{K}[A^{i-j+1}]_{\ell
k}\log\frac{L_{\ell}(\bm{\xi}_{\ell,j}|\theta)}{L_{\ell}(\bm{\xi}_{\ell,j}|\theta^{\circ})}$
$\displaystyle\qquad+\frac{1}{i}\sum_{\ell=1}^{K}[A^{i}]_{\ell
k}\log\frac{\bm{\mu}_{\ell,0}(\theta)}{\bm{\mu}_{\ell,0}(\theta^{\circ})}.$
(48)

Now, since $A$ is primitive and left-stochastic, it holds that
$A^{i}~{}\to~{}v\mathds{1}_{K}^{T}$ [57, Chapter 8], as $i\to\infty$. If we
incorporate this fact into (A), the second term on the right hand side (RHS)
vanishes due to Assumption 1 and the expression transforms into:

$\displaystyle\frac{1}{i}\log\frac{\bm{\mu}_{k,i}(\theta)}{\bm{\mu}_{k,i}(\theta^{\circ})}$
$\displaystyle\to\frac{1}{i}\sum_{j=1}^{i}\sum_{\ell=1}^{K}v_{\ell}\log\frac{L_{\ell}(\bm{\xi}_{\ell,j}|\theta)}{L_{\ell}(\bm{\xi}_{\ell,j}|\theta^{\circ})}$
(49)

as $i$ gets larger. Remember that the observations $\\{\bm{\xi}_{\ell,i}\\}$
are i.i.d. over time, and the expectation of the log-likelihood ratio
satisfies:

$\mathbb{E}\Big{[}\log\frac{L_{k}(\bm{\xi}_{k,i}|\theta^{\circ})}{L_{k}(\bm{\xi}_{k,i}|\theta)}\Big{]}=D_{\textup{KL}}(L_{k}(.|\theta^{\circ})||L_{k}(.|\theta))<\infty.$
(50)

Using (50) and applying the strong law of large numbers [58, Chapter 7] to
(49), we establish (11). In addition, if Assumption 2 holds, then the RHS of
(11) is strictly positive for each $\theta\neq\theta^{\circ}$. Consequently,
$\forall\theta\in\Theta\setminus\\{\theta^{\circ}\\}$,
$\bm{\mu}_{k,i}(\theta)\operatorname{\xrightarrow{\textup{a.s.}}}0$, which in
turn implies (10).

##  Appendix B Connection to Stochastic Mirror Descent

The goal of social learning can be formulated as solving:

$\min_{\theta\in\Theta}\sum_{k=1}^{K}D_{\textup{KL}}\big{(}L_{k}(\cdot|\theta^{\circ})||L_{k}(\cdot|\theta)\big{)}$
(51)

Under Assumption 2, the unique solution is the true hypothesis
$\theta^{\circ}$. However, since the true hypothesis is unknown, agents can
use stochastic algorithms based on instantaneous data. In [50], it is shown
that the traditional full information sharing algorithm (7)–(8) corresponds to
a distributed stochastic mirror descent algorithm for this problem (see [37]),
with the KL-divergence chosen as the Bregman divergence. Namely, they show
that at each iteration, the agents’ updates coincide with the distributed
stochastic mirror descent algorithm applied to (51):

$\min_{\mu\in\Delta_{H}}\\!\\!\left\\{\sum_{\ell\in\mathcal{N}_{k}}\\!\\!a_{\ell
k}\Big{(}D_{\textup{KL}}(\mu||\bm{\mu}_{\ell,i-1})-\,\mathbb{E}_{\mu}\log
L_{\ell}(\bm{\xi}_{\ell,i}|\theta)\Big{)}\\!\\!\right\\}$ (52)

where $\Delta_{H}$ is the probability simplex of dimension $H$, and
$\mathbb{E}_{\mu}$ is the expectation computed with respect to $\mu$, i.e.,

$\displaystyle\mathbb{E}_{\mu}\log
L_{\ell}(\bm{\xi}_{\ell,i}|\theta)\triangleq\sum_{\theta\in\Theta}\mu(\theta)\log
L_{\ell}(\bm{\xi}_{\ell,i}|\theta).$ (53)

The objective function in (52) consists of two terms. The first term is the
weighted average of KL-divergences across neighboring agents; this average
penalizes the disagreement among the neighbors’ prior beliefs
$\\{\bm{\mu}_{\ell,i-1}\\}$. The second term in (52) corresponds to the
likelihood of the observations received within the neighborhood, averaged over
the hypotheses with respect to $\mu$. The cost in (52) then seeks to minimize
disagreement while maximizing the likelihood.

However, in our problem setting, agents get only the $\bm{\tau}_{i}$ component
of their neighbors’ beliefs at $i$. Therefore, problem (52) can be modified to
use only that component and fill the rest with the information from agent $k$.
That is to say, the KL-divergence is modified as:

$\displaystyle D_{\textup{KL}}$
$\displaystyle(\mu||\bm{\mu}_{\ell,i-1})\Longrightarrow$
$\displaystyle\sum_{\theta\neq\bm{\tau}_{i}}\mu(\theta)\log\frac{\mu(\theta)}{\bm{\mu}_{k,i-1}(\theta)}+\mu(\bm{\tau}_{i})\log\frac{\mu(\bm{\tau}_{i})}{\bm{\mu}_{\ell,i-1}(\bm{\tau}_{i})},$
(54)

and the expectation with respect to $\mu$ is modified to:

$\displaystyle\mathbb{E}_{\mu}$ $\displaystyle\log
L_{\ell}(\bm{\xi}_{\ell,i}|\theta)\Longrightarrow$
$\displaystyle\sum_{\theta\neq\bm{\tau}_{i}}\mu(\theta)\log
L_{k}(\bm{\xi}_{k,i}|\theta)+\mu(\bm{\tau}_{i})\log
L_{\ell}(\bm{\xi}_{\ell,i}|\bm{\tau}_{i}).$ (55)

##  Appendix C Proof of Lemma 1

From the combination step (25),

$\displaystyle\log\bm{\mu}_{k,i}(\theta^{\circ})$
$\displaystyle\\!\\!\\!=\sum_{\ell\in\mathcal{N}_{k}}a_{\ell
k}\log\widehat{\bm{\psi}}^{(k)}_{\ell,i}(\theta^{\circ})-\log\sum_{\theta^{\prime}\in\Theta}\text{exp}\Big{\\{}\sum_{\ell\in\mathcal{N}_{k}}a_{\ell
k}\log\widehat{\bm{\psi}}^{(k)}_{\ell,i}(\theta^{\prime})\Big{\\}}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\geq}}\sum_{\ell\in\mathcal{N}_{k}}a_{\ell
k}\log\widehat{\bm{\psi}}^{(k)}_{\ell,i}(\theta^{\circ})-\log\sum_{\theta^{\prime}\in\Theta}\sum_{\ell\in\mathcal{N}_{k}}a_{\ell
k}\widehat{\bm{\psi}}^{(k)}_{\ell,i}(\theta^{\prime})$
$\displaystyle=\sum_{\ell\in\mathcal{N}_{k}}a_{\ell
k}\log\widehat{\bm{\psi}}^{(k)}_{\ell,i}(\theta^{\circ})-\log\sum_{\ell\in\mathcal{N}_{k}}a_{\ell
k}\sum_{\theta^{\prime}\in\Theta}\widehat{\bm{\psi}}^{(k)}_{\ell,i}(\theta^{\prime})$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{=}}\sum_{\ell\in\mathcal{N}_{k}}a_{\ell
k}\log\widehat{\bm{\psi}}^{(k)}_{\ell,i}(\theta^{\circ})$ (56)

where $(a)$ follows from Jensen’s inequality, and $(b)$ follows from the fact
that $\widehat{\bm{\psi}}^{(k)}_{\ell,i}$ is a pmf and $A$ is left-stochastic.
Therefore, the conditional expectations satisfy

$\displaystyle\mathbb{E}\Big{[}\log\bm{\mu}_{k,i}(\theta^{\circ})\Big{|}\bm{\mathcal{F}}_{i-1}\Big{]}$
$\displaystyle\qquad\geq\mathbb{E}\Big{[}\sum_{\ell\in\mathcal{N}_{k}}a_{\ell
k}\log\widehat{\bm{\psi}}^{(k)}_{\ell,i}(\theta^{\circ})\Big{|}\bm{\mathcal{F}}_{i-1}\Big{]}$
$\displaystyle\qquad\stackrel{{\scriptstyle(a)}}{{=}}\mathbb{E}_{\xi_{i},\tau_{i}}\Big{[}\sum_{\ell\in\mathcal{N}_{k}}a_{\ell
k}\log\widehat{\bm{\psi}}^{(k)}_{\ell,i}(\theta^{\circ})\Big{]}$
$\displaystyle\qquad\stackrel{{\scriptstyle(b)}}{{=}}\mathbb{E}_{\xi_{i}}\mathbb{E}_{\tau_{i}|\xi_{i}}\Big{[}\sum_{\ell\in\mathcal{N}_{k}}a_{\ell
k}\log\widehat{\bm{\psi}}^{(k)}_{\ell,i}(\theta^{\circ})\Big{]}$
$\displaystyle\qquad\stackrel{{\scriptstyle(c)}}{{=}}\mathbb{E}_{\xi_{i}}\mathbb{E}_{\tau_{i}}\Big{[}\sum_{\ell\in\mathcal{N}_{k}}a_{\ell
k}\log\widehat{\bm{\psi}}^{(k)}_{\ell,i}(\theta^{\circ})\Big{]}$ (57)

where $(a)$ follows from the fact that arguments inside the expectation are
functions of $\\{\bm{\xi}_{i},\bm{\tau}_{i},\bm{\mathcal{F}}_{i-1}\\}$, $(b)$
follows from the tower rule of expectation, and $(c)$ follows from the fact
that $\bm{\xi}_{i}$ and $\bm{\tau}_{i}$ are assumed to be independent. The
inner expectation can be written as

$\displaystyle\mathbb{E}_{\tau_{i}}\Big{[}\sum_{\ell\in\mathcal{N}_{k}}a_{\ell
k}\log\widehat{\bm{\psi}}^{(k)}_{\ell,i}(\theta^{\circ})\Big{]}$
$\displaystyle=\pi_{\theta^{\circ}}\sum_{\ell\in\mathcal{N}_{k}}a_{\ell
k}\log\frac{\bm{\psi}_{\ell,i}(\theta^{\circ})}{1-\bm{\psi}_{k,i}(\theta^{\circ})+\bm{\psi}_{\ell,i}(\theta^{\circ})}$
$\displaystyle\qquad+\sum_{\tau\neq\theta^{\circ}}\pi_{\tau}\sum_{\ell\in\mathcal{N}_{k}}a_{\ell
k}\log\frac{\bm{\psi}_{k,i}(\theta^{\circ})}{1-\bm{\psi}_{k,i}(\tau)+\bm{\psi}_{\ell,i}(\tau)}$
$\displaystyle=\pi_{\theta^{\circ}}\sum_{\ell\in\mathcal{N}_{k}}a_{\ell
k}\log\bm{\psi}_{\ell,i}(\theta^{\circ})+\sum_{\tau\neq\theta^{\circ}}\pi_{\tau}\log\bm{\psi}_{k,i}(\theta^{\circ})$
$\displaystyle\qquad-\sum_{\tau\in\Theta}\pi_{\tau}\sum_{\ell\in\mathcal{N}_{k}}a_{\ell
k}\log\Big{(}1-\bm{\psi}_{k,i}(\tau)+\bm{\psi}_{\ell,i}(\tau)\Big{)}.$ (58)

Using the Perron vector defined by (4), taking the expectation of (C) with
respect to $\bm{\tau}_{i}$, and using (C) imply that:

$\displaystyle\mathbb{E}_{\tau_{i}}\Big{[}\sum_{k=1}^{K}v_{k}\log\bm{\mu}_{k,i}(\theta^{\circ})\Big{]}$
$\displaystyle\geq\pi_{\theta^{\circ}}\sum_{k=1}^{K}v_{k}\log\bm{\psi}_{k,i}(\theta^{\circ})+\sum_{\tau\neq\theta^{\circ}}\pi_{\tau}\sum_{k=1}^{K}v_{k}\log\bm{\psi}_{k,i}(\theta^{\circ})$
$\displaystyle\qquad-\sum_{\tau\in\Theta}\pi_{\tau}\sum_{k=1}^{K}v_{k}\sum_{\ell\in\mathcal{N}_{k}}a_{\ell
k}\log\Big{(}1-\bm{\psi}_{k,i}(\tau)+\bm{\psi}_{\ell,i}(\tau)\Big{)}$
$\displaystyle=\sum_{k=1}^{K}v_{k}\log\bm{\psi}_{k,i}(\theta^{\circ})$
$\displaystyle\qquad-\sum_{\tau\in\Theta}\pi_{\tau}\sum_{k=1}^{K}v_{k}\sum_{\ell\in\mathcal{N}_{k}}a_{\ell
k}\log\Big{(}1-\bm{\psi}_{k,i}(\tau)+\bm{\psi}_{\ell,i}(\tau)\Big{)}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\geq}}\sum_{k=1}^{K}v_{k}\log\bm{\psi}_{k,i}(\theta^{\circ})$
$\displaystyle\quad-\log\Bigg{(}\sum_{\tau\in\Theta}\pi_{\tau}\sum_{k=1}^{K}v_{k}\sum_{\ell\in\mathcal{N}_{k}}a_{\ell
k}\big{(}1-\bm{\psi}_{k,i}(\tau)+\bm{\psi}_{\ell,i}(\tau)\big{)}\\!\Bigg{)}$
$\displaystyle=\sum_{k=1}^{K}v_{k}\log\bm{\psi}_{k,i}(\theta^{\circ})$
$\displaystyle\qquad-\log\Bigg{(}\sum_{\tau\in\Theta}\pi_{\tau}\sum_{k=1}^{K}v_{k}\big{(}1-\bm{\psi}_{k,i}(\tau)+\bm{\psi}_{k,i}(\tau)\big{)}\Bigg{)}$
$\displaystyle=\sum_{k=1}^{K}v_{k}\log\bm{\psi}_{k,i}(\theta^{\circ})-\log(1)$
$\displaystyle=\sum_{k=1}^{K}v_{k}\log\bm{\psi}_{k,i}(\theta^{\circ}),$ (59)

where $(a)$ follows from Jensen’s inequality. Applying the expectation with
respect to $\bm{\xi}_{i}$ to the both sides of (C), we arrive at

$\displaystyle\mathbb{E}_{\xi_{i}}\mathbb{E}_{\tau_{i}}$
$\displaystyle\Big{[}\sum_{k=1}^{K}v_{k}\log\bm{\mu}_{k,i}(\theta^{\circ})\Big{]}$
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:inner_exp}}}{{\geq}}\mathbb{E}_{\xi_{i}}\Big{[}\sum_{k=1}^{K}v_{k}\log\bm{\psi}_{k,i}(\theta^{\circ})\Big{]}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\mathbb{E}_{\xi_{i}}\Big{[}\sum_{k=1}^{K}v_{k}\log\frac{L_{k}(\bm{\xi}_{k,i}|\theta^{\circ})}{\sum_{\theta^{\prime}\in\Theta}L_{k}(\bm{\xi}_{k,i}|\theta^{\prime})\bm{\mu}_{k,i-1}(\theta^{\prime})}\Big{]}$
$\displaystyle\qquad+\sum_{k=1}^{K}v_{k}\log\bm{\mu}_{k,i-1}(\theta^{\circ})$
$\displaystyle=\sum_{k=1}^{K}v_{k}D_{\textup{KL}}\Big{(}L_{k}(\cdot|\theta^{\circ})\Big{|}\Big{|}{\sum_{\theta^{\prime}\in\Theta}L_{k}(\cdot|\theta^{\prime})\bm{\mu}_{k,i-1}(\theta^{\prime})}\Big{)}$
$\displaystyle\qquad+\sum_{k=1}^{K}v_{k}\log\bm{\mu}_{k,i-1}(\theta^{\circ})$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\geq}}\sum_{k=1}^{K}v_{k}\log\bm{\mu}_{k,i-1}(\theta^{\circ})$
(60)

where $(a)$ follows from the fact that belief vectors at time $i-1$ are
independent of the new observations at time $i$, and $(b)$ follows from the
fact that KL-divergences are non-negative. It is worth noting that this proof
holds even in cases where the transmission distribution is time-dependent, or
when it depends on the observations. Therefore, the result is more general
than what is explicitly stated. However, to maintain consistency with the
other parts of the paper, we used the fixed distribution notation $\pi$.

##  Appendix D Proof of Theorem 1

By the proposed strategy (23)–(25), the log-belief ratio can be written as

$\displaystyle\log\frac{\bm{\mu}_{k,i}(\theta)}{\bm{\mu}_{k,i}(\theta^{\circ})}$
$\displaystyle=\sum_{\ell\in\mathcal{N}_{k}}a_{\ell
k}\log\frac{\widehat{\bm{\psi}}^{(k)}_{\ell,i}(\theta)}{\widehat{\bm{\psi}}^{(k)}_{\ell,i}(\theta^{\circ})}$
$\displaystyle=\mathbb{I}\\{\bm{\tau}_{i}=\theta\\}\sum_{\ell\in\mathcal{N}_{k}}a_{\ell
k}\log\frac{\bm{\psi}_{\ell,i}(\theta)}{\bm{\psi}_{k,i}(\theta^{\circ})}$
$\displaystyle\quad+\mathbb{I}\\{\bm{\tau}_{i}=\theta^{\circ}\\}\sum_{\ell\in\mathcal{N}_{k}}a_{\ell
k}\log\frac{\bm{\psi}_{k,i}(\theta)}{\bm{\psi}_{\ell,i}(\theta^{\circ})}$
$\displaystyle\quad+(1-\mathbb{I}\\{\bm{\tau}_{i}=\theta\\}-\mathbb{I}\\{\bm{\tau}_{i}=\theta^{\circ}\\})\log\frac{\bm{\psi}_{k,i}(\theta)}{\bm{\psi}_{k,i}(\theta^{\circ})}.$
(61)

Observe from (D) that the log-belief ratio is a random variable given the
intermediate beliefs, because of the randomness of the trending topic
$\bm{\tau}_{i}$. Next, we fix a wrong hypothesis $\theta\neq\theta^{\circ}$
and define the effective combination matrix for $\theta$ at time $i$ as

$\displaystyle\widetilde{\bm{A}}_{i}\triangleq\begin{dcases}A,&\theta=\bm{\tau}_{i}\\\
I,&\theta\neq\bm{\tau}_{i}\end{dcases}.$ (62)

This is a binary random variable taking the value of the original combination
matrix $A$ if the hypothesis is exchanged at iteration $i$, and the identity
matrix $I$ otherwise. More compactly,

$\displaystyle\widetilde{\bm{A}}_{i}=\mathbb{I}\\{\bm{\tau}_{i}=\theta\\}A+(1-\mathbb{I}\\{\bm{\tau}_{i}=\theta\\})I.$
(63)

Using this definition, the recursion in (D) can be rewritten for
$\theta\neq\theta^{\circ}$ as:

$\displaystyle\log\frac{\bm{\mu}_{k,i}(\theta)}{\bm{\mu}_{k,i}(\theta^{\circ})}$
$\displaystyle=\sum_{\ell\in\mathcal{N}_{k}}[\widetilde{\bm{A}}_{i}]_{\ell
k}\log\frac{\bm{\psi}_{\ell,i}(\theta)}{\bm{\psi}_{\ell,i}(\theta^{\circ})}$
$\displaystyle\qquad+(\mathbb{I}\\{\bm{\tau}_{i}=\theta^{\circ}\\}-\mathbb{I}\\{\bm{\tau}_{i}=\theta\\})\sum_{\ell\in\mathcal{N}_{k}}a_{\ell
k}\log\frac{\bm{\psi}_{k,i}(\theta^{\circ})}{\bm{\psi}_{\ell,i}(\theta^{\circ})}$
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:alg_adapt}}}{{=}}\sum_{\ell\in\mathcal{N}_{k}}[\widetilde{\bm{A}}_{i}]_{\ell
k}\log\frac{L_{\ell}(\bm{\xi}_{\ell,i}|\theta)}{L_{\ell}(\bm{\xi}_{\ell,i}|\theta^{\circ})}+\sum_{\ell\in\mathcal{N}_{k}}[\widetilde{\bm{A}}_{i}]_{\ell
k}\log\frac{\bm{\mu}_{\ell,i-1}(\theta)}{\bm{\mu}_{\ell,i-1}(\theta^{\circ})}$
$\displaystyle\quad+(\mathbb{I}\\{\bm{\tau}_{i}=\theta^{\circ}\\}-\mathbb{I}\\{\bm{\tau}_{i}=\theta\\})\sum_{\ell\in\mathcal{N}_{k}}a_{\ell
k}\log\frac{\bm{\psi}_{k,i}(\theta^{\circ})}{\bm{\psi}_{\ell,i}(\theta^{\circ})}.$
(64)

The first two terms in the RHS of (D) are analogous to the terms that arise in
the standard log-linear social learning analysis (see Eq. (47)), albeit with
the random matrix $\widetilde{\bm{A}}_{i}$ in place of the original
combination matrix $A$. The last term in (D) is a residue term due to the
network disagreement. In order to expand the recursion over time, we introduce
the following notation for the product of the effective combination matrices
for $j\leq i$:222If $j>i$, we set $\widetilde{\bm{A}}^{j\shortrightarrow
i}=I$.

$\displaystyle\widetilde{\bm{A}}^{j\shortrightarrow
i}\triangleq\widetilde{\bm{A}}_{j}\widetilde{\bm{A}}_{j+1}\dots\widetilde{\bm{A}}_{i-1}\widetilde{\bm{A}}_{i},$
(65)

and also for the residue terms for $j~{}\leq~{}i$ as

$\displaystyle\bm{R}_{j}^{k}\triangleq$
$\displaystyle(\mathbb{I}\\{\bm{\tau}_{j}=\theta^{\circ}\\}-\mathbb{I}\\{\bm{\tau}_{j}=\theta\\})$
$\displaystyle\qquad\times\sum_{\ell=1}^{K}[\widetilde{\bm{A}}^{j+1\shortrightarrow
i}]_{\ell
k}\sum_{m=1}^{K}a_{m\ell}\log\frac{\bm{\psi}_{\ell,j}(\theta^{\circ})}{\bm{\psi}_{m,j}(\theta^{\circ})}.$
(66)

In other words, $\bm{R}_{j}^{k}$ denotes the residual term at time $i$ caused
by the network disagreement at time $j$. Expanding (D) with these definitions
and dividing both sides by $i$, we arrive at the following expression for the
convergence rate.

$\displaystyle\frac{1}{i}\log\frac{\bm{\mu}_{k,i}(\theta)}{\bm{\mu}_{k,i}(\theta^{\circ})}$
$\displaystyle=\frac{1}{i}\sum_{j=1}^{i}\sum_{\ell=1}^{K}[\widetilde{\bm{A}}^{j\shortrightarrow
i}]_{\ell
k}\log\frac{L_{\ell}(\bm{\xi}_{\ell,j}|\theta)}{L_{\ell}(\bm{\xi}_{\ell,j}|\theta^{\circ})}$
$\displaystyle\quad+\frac{1}{i}\sum_{\ell=1}^{K}[\widetilde{\bm{A}}^{1\shortrightarrow
i}]_{\ell
k}\log\frac{\bm{\mu}_{\ell,0}(\theta)}{\bm{\mu}_{\ell,0}(\theta^{\circ})}+\frac{1}{i}\sum_{j=1}^{i}\bm{R}_{j}^{k}.$
(67)

In Lemma 3, we show that the summation of the residue terms in (D) stays
finite with probability one as $i$ grows, i.e.,

$\displaystyle\frac{1}{i}\sum_{j=1}^{i}\bm{R}_{j}^{k}\operatorname{\xrightarrow{\textup{a.s.}}}0.$
(68)

Therefore, the residue terms do not affect the convergence rate in (D) as
$i\to\infty$. Consequently, we proceed to study the remaining terms in (D).
Observe that the finiteness of the KL-divergence of likelihood functions (see
Eq. (2)) can be expressed as

$\displaystyle\Big{|}\mathbb{E}\Big{[}\log\frac{L_{k}(\bm{\xi}_{k,i}|\theta)}{L_{k}(\bm{\xi}_{k,i}|\theta^{\circ})}\Big{]}\Big{|}<\infty$
(69)

which in turn implies:

$\displaystyle\Big{|}\log\frac{L_{k}(\bm{\xi}_{k,i}|\theta)}{L_{k}(\bm{\xi}_{k,i}|\theta^{\circ})}\Big{|}\stackrel{{\scriptstyle\text{a.s.}}}{{<}}\infty.$
(70)

The set of events such that

$\displaystyle\lim_{n\to\infty}[\widetilde{\bm{A}}^{j\shortrightarrow
j+n}-v\mathds{1}_{K}^{\top}]_{\ell
k}\log\frac{L_{\ell}(\bm{\xi}_{\ell,j}|\theta)}{L_{\ell}(\bm{\xi}_{\ell,j}|\theta^{\circ})}\neq
0$ (71)

is a subset of the union of the event sets:

$\displaystyle\lim_{n\to\infty}[\widetilde{\bm{A}}^{j\shortrightarrow
j+n}-v\mathds{1}_{K}^{\top}]_{\ell k}\neq 0$ (72)

and

$\displaystyle\Big{|}\log\frac{L_{\ell}(\bm{\xi}_{\ell,j}|\theta)}{L_{\ell}(\bm{\xi}_{\ell,j}|\theta^{\circ})}\Big{|}=\infty.$
(73)

But we know that these two sets are null sets because of the auxiliary Lemma 4
and (70), respectively. Therefore, for any time instant $j$, it holds that

$\displaystyle\lim_{n\to\infty}[\widetilde{\bm{A}}^{j\shortrightarrow
j+n}-v\mathds{1}_{K}^{\top}]_{\ell
k}\log\frac{L_{\ell}(\bm{\xi}_{\ell,j}|\theta)}{L_{\ell}(\bm{\xi}_{\ell,j}|\theta^{\circ})}\operatorname{\stackrel{{\scriptstyle\textup{a.s.}}}{{=}}}0.$
(74)

This implies for the convergence of the Cesàro mean [59] that

$\displaystyle\lim_{t\to\infty}\frac{1}{t}\sum_{n=0}^{t-1}[\widetilde{\bm{A}}^{j\shortrightarrow
j+n}-v\mathds{1}_{K}^{\top}]_{\ell
k}\log\frac{L_{\ell}(\bm{\xi}_{\ell,j}|\theta)}{L_{\ell}(\bm{\xi}_{\ell,j}|\theta^{\circ})}\operatorname{\stackrel{{\scriptstyle\textup{a.s.}}}{{=}}}0.$
(75)

By using $j=i-n$, this can alternatively be written as

$\displaystyle\lim_{t\to\infty}\frac{1}{t}\sum_{n=0}^{t-1}[\widetilde{\bm{A}}^{i-n\shortrightarrow
i}-v\mathds{1}_{K}^{\top}]_{\ell
k}\log\frac{L_{\ell}(\bm{\xi}_{\ell,i-n}|\theta)}{L_{\ell}(\bm{\xi}_{\ell,i-n}|\theta^{\circ})}\operatorname{\stackrel{{\scriptstyle\textup{a.s.}}}{{=}}}0.$
(76)

Since this holds for any time instant $i\geq t$ (which ensures $j\geq 1$), we
can set $i=t$. By also changing the summation index $n$ to $j$, we arrive at

$\displaystyle\lim_{i\to\infty}\frac{1}{i}\sum_{j=1}^{i}[\widetilde{\bm{A}}^{j\shortrightarrow
i}-v\mathds{1}_{K}^{\top}]_{\ell
k}\log\frac{L_{\ell}(\bm{\xi}_{\ell,j}|\theta)}{L_{\ell}(\bm{\xi}_{\ell,j}|\theta^{\circ})}\operatorname{\stackrel{{\scriptstyle\textup{a.s.}}}{{=}}}0.$
(77)

As a result, the first term in (D) can be written as:

$\displaystyle\frac{1}{i}\sum_{j=1}^{i}$
$\displaystyle\sum_{\ell=1}^{K}[\widetilde{\bm{A}}^{j\shortrightarrow
i}]_{\ell
k}\log\frac{L_{\ell}(\bm{\xi}_{\ell,j}|\theta)}{L_{\ell}(\bm{\xi}_{\ell,j}|\theta^{\circ})}$
$\displaystyle=\frac{1}{i}\sum_{j=1}^{i}\sum_{\ell=1}^{K}[\widetilde{\bm{A}}^{j\shortrightarrow
i}-v\mathds{1}_{K}^{\top}]_{\ell
k}\log\frac{L_{\ell}(\bm{\xi}_{\ell,j}|\theta)}{L_{\ell}(\bm{\xi}_{\ell,j}|\theta^{\circ})}$
$\displaystyle\quad+\frac{1}{i}\sum_{j=1}^{i}\sum_{\ell=1}^{K}[v\mathds{1}_{K}^{\top}]_{\ell
k}\log\frac{L_{\ell}(\bm{\xi}_{\ell,j}|\theta)}{L_{\ell}(\bm{\xi}_{\ell,j}|\theta^{\circ})}$
$\displaystyle=\frac{1}{i}\sum_{j=1}^{i}\sum_{\ell=1}^{K}[\widetilde{\bm{A}}^{j\shortrightarrow
i}-v\mathds{1}_{K}^{\top}]_{\ell
k}\log\frac{L_{\ell}(\bm{\xi}_{\ell,j}|\theta)}{L_{\ell}(\bm{\xi}_{\ell,j}|\theta^{\circ})}$
$\displaystyle\quad+\frac{1}{i}\sum_{j=1}^{i}\sum_{k=1}^{K}v_{k}\log\frac{L_{k}(\bm{\xi}_{k,j}|\theta)}{L_{k}(\bm{\xi}_{k,j}|\theta^{\circ})}$
$\displaystyle=\frac{1}{i}\sum_{j=1}^{i}\sum_{\ell=1}^{K}[\widetilde{\bm{A}}^{j\shortrightarrow
i}-v\mathds{1}_{K}^{\top}]_{\ell
k}\log\frac{L_{\ell}(\bm{\xi}_{\ell,j}|\theta)}{L_{\ell}(\bm{\xi}_{\ell,j}|\theta^{\circ})}$
$\displaystyle\quad+\sum_{k=1}^{K}v_{k}\frac{1}{i}\sum_{j=1}^{i}\log\frac{L_{k}(\bm{\xi}_{k,j}|\theta)}{L_{k}(\bm{\xi}_{k,j}|\theta^{\circ})}$
$\displaystyle\operatorname{\xrightarrow{\textup{a.s.}}}\sum_{k=1}^{K}-v_{k}D_{\textup{KL}}\Big{(}L_{k}(\cdot|\theta^{\circ})\Big{|}\Big{|}L_{k}(\cdot|\theta)\Big{)}$
(78)

where the last step follows from (77) and the strong law of large numbers [58,
Chapter 7]. Also, since by Lemma 4 $\widetilde{\bm{A}}^{1\shortrightarrow
i}\operatorname{\xrightarrow{\textup{a.s.}}}v\mathds{1}_{K}^{\top}$ and by
Assumption 1 the initial beliefs are nonzero, it follows that

$\displaystyle\frac{1}{i}\sum_{\ell=1}^{K}[\widetilde{\bm{A}}^{1\shortrightarrow
i}]_{\ell
k}\log\frac{\bm{\mu}_{\ell,0}(\theta)}{\bm{\mu}_{\ell,0}(\theta^{\circ})}$
$\displaystyle\operatorname{\xrightarrow{\textup{a.s.}}}0.$ (79)

The asymptotic convergence rate then becomes

$\displaystyle\frac{1}{i}\log\frac{\bm{\mu}_{k,i}(\theta)}{\bm{\mu}_{k,i}(\theta^{\circ})}\operatorname{\xrightarrow{\textup{a.s.}}}\sum_{k=1}^{K}-v_{k}D_{\textup{KL}}\Big{(}L_{k}(\cdot|\theta^{\circ})\Big{|}\Big{|}L_{k}(\cdot|\theta)\Big{)}.$
(80)

$\hfill\blacksquare$

##  Appendix E Proof of Theorem 2

Since $Q(\bm{\mu}_{i})$ is a super-martingale (Lemma 1) and also non-negative
(i.e., uniformly bounded from below), by Doob’s forward martingale convergence
theorem [58, Chapter 11.5], there exists a finite random variable
$\bm{Q}_{\infty}$ such that, as $i\to\infty$,

$\displaystyle
Q(\bm{\mu}_{i})\operatorname{\xrightarrow{\textup{a.s.}}}\bm{Q}_{\infty}.$
(81)

Since $\bm{Q}_{\infty}$ is finite, it holds that:

$\displaystyle\lim_{i\to\infty}\sum_{k=1}^{K}v_{k}\log\bm{\mu}_{k,i}(\theta^{\circ})>-\infty$
$\displaystyle\Longrightarrow\liminf_{i\to\infty}\log\bm{\mu}_{k,i}(\theta^{\circ})>-\infty,\quad\forall
k\in\mathcal{N}$
$\displaystyle\Longrightarrow\liminf_{i\to\infty}\bm{\mu}_{k,i}(\theta^{\circ})>0$
(82)

with probability one.

##  Appendix F Auxiliary Results

###  F-A Vanishing Matrix Norm

######  Lemma 2.

If the wrong hypothesis $\theta$ is transmitted with positive probability,
i.e., $\pi_{\theta}>0$, then, for any matrix norm induced by a vector norm,

$\displaystyle\mathbb{E}\Big{[}\left\|(\widetilde{\bm{A}}^{j+1\shortrightarrow
i})^{\top}(I-A^{\top})\right\|\Big{]}=\mathcal{O}(\widetilde{\lambda}^{i-j})$
(83)

for a constant $\widetilde{\lambda}$ that satisfies
$0\leq\widetilde{\lambda}<1$.

###### Proof.

Define the time difference $n\triangleq i-j$. Since the matrices
$\widetilde{\bm{A}}_{i}$ are i.i.d. binary random variables over time, as
defined by (62), for time differences $0\leq m\leq n$, we get:

$\displaystyle\mathbb{P}\Big{(}\widetilde{\bm{A}}^{j+1\shortrightarrow
i}=A^{m}\Big{)}=\binom{n}{m}(\pi_{\theta})^{m}(1-\pi_{\theta})^{n-m}.$ (84)

Moreover, since $A$ is a primitive stochastic matrix, for consecutive time
instants, there exists a non-negative constant $\lambda<1$ such that [57, Eq.
(8.2.10)]:

$\displaystyle\|A^{m}-A^{m+1}\|\leq C\lambda^{m}(1-\lambda)$ (85)

where $C$ is a constant independent of $m$. Then, it follows that

$\displaystyle\mathbb{E}\Big{[}\|$
$\displaystyle(\widetilde{\bm{A}}^{j+1\shortrightarrow
i})^{\top}(I-A^{\top})\|\Big{]}$
$\displaystyle=\sum_{m=0}^{n}\mathbb{P}(\widetilde{\bm{A}}^{j+1\shortrightarrow
i}=A^{m})\|A^{m}-A^{m+1}\|$
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:eigenvalue_decrease}}}{{\leq}}\sum_{m=0}^{n}\mathbb{P}(\widetilde{\bm{A}}^{j+1\shortrightarrow
i}=A^{m})C\lambda^{m}(1-\lambda)$
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:binomial_probability}}}{{=}}C(1-\lambda)\sum_{m=0}^{n}\binom{n}{m}(\pi_{\theta})^{m}(1-\pi_{\theta})^{n-m}\lambda^{m}$
$\displaystyle=C(1-\lambda)\Big{(}\lambda\pi_{\theta}+(1-\pi_{\theta})\Big{)}^{n}$
$\displaystyle=C(1-\lambda)\Big{(}1-(1-\lambda)\pi_{\theta}\Big{)}^{n}=\mathcal{O}(\widetilde{\lambda}^{n})$
(86)

where $\widetilde{\lambda}\triangleq 1-(1-\lambda)\pi_{\theta}$, which is a
constant strictly smaller than $1$ as long as $\pi_{\theta}>0$.
$\hfill\blacksquare$

###  F-B Finiteness of the Residual Sum

######  Lemma 3.

As $i\to\infty$, if $\pi_{\theta}>0$, then, under Assumption 1

$\displaystyle\frac{1}{i}\sum_{j=1}^{i}\bm{R}_{j}^{k}\operatorname{\xrightarrow{\textup{a.s.}}}0.$
(87)

###### Proof.

First, we aggregate the residue terms and log-intermediate beliefs from across
the network into the following vectors:

$\displaystyle\bm{R}_{j}\triangleq\text{col}\\{\bm{R}_{j}^{k}\\}_{k=1}^{K},\quad\bm{\Psi}_{i}\triangleq\text{col}\\{\log\bm{\psi}_{k,i}(\theta^{\circ})\\}_{k=1}^{K}.$
(88)

By using these definitions, expression (D) can be transformed into the
following vector equation form:

$\displaystyle\bm{R}_{j}=(\mathbb{I}\\{\bm{\tau}_{j}=\theta^{\circ}\\}-\mathbb{I}\\{\bm{\tau}_{j}=\theta\\})(\widetilde{\bm{A}}^{j+1\shortrightarrow
i})^{\top}(\bm{\Psi}_{j}-A^{\top}\bm{\Psi}_{j}).$ (89)

To bound the terms in this expression, we start by using Lemma 2 and Markov’s
inequality to obtain:

$\displaystyle\mathbb{P}\Big{(}\|(\widetilde{\bm{A}}^{j+1\shortrightarrow
j+n})^{\top}(I-A^{\top})\|\geq\epsilon\Big{)}\leq\frac{C(1-\lambda)\widetilde{\lambda}^{n}}{\epsilon},$
(90)

where recall that we use $n=i-j$. Since $\widetilde{\lambda}<1$, it holds that

$\displaystyle\sum_{n=0}^{\infty}\frac{C(1-\lambda)\widetilde{\lambda}^{n}}{\epsilon}<\infty.$
(91)

Then, the first Borel-Cantelli Lemma [58, Chapter 2.7] implies:

$\displaystyle\lim_{n\to\infty}\Big{\|}(\widetilde{\bm{A}}^{j+1\shortrightarrow
j+n})^{\top}(I-A^{\top})\Big{\|}\operatorname{\stackrel{{\scriptstyle\textup{a.s.}}}{{=}}}0,$
(92)

for any value of $j$. Moreover, if we bound the norm of (89), it holds almost
surely that

$\displaystyle\|\bm{R}_{j}\|$
$\displaystyle=\Big{\|}(\mathbb{I}\\{\bm{\tau}_{j}=\theta^{\circ}\\}-\mathbb{I}\\{\bm{\tau}_{j}=\theta\\})(\widetilde{\bm{A}}^{j+1\shortrightarrow
i})^{\top}(\bm{\Psi}_{j}-A^{\top}\bm{\Psi}_{j})\Big{\|}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\Big{\|}\mathbb{I}\\{\bm{\tau}_{j}=\theta^{\circ}\\}-\mathbb{I}\\{\bm{\tau}_{j}=\theta\\}\Big{\|}\Big{\|}(\widetilde{\bm{A}}^{j+1\shortrightarrow
i})^{\top}(I-A^{\top})\Big{\|}\Big{\|}\bm{\Psi}_{j}\Big{\|}$
$\displaystyle\leq\Big{\|}(\widetilde{\bm{A}}^{j+1\shortrightarrow
i})^{\top}(I-A^{\top})\Big{\|}\Big{\|}\bm{\Psi}_{j}\Big{\|}$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}\Big{\|}(\widetilde{\bm{A}}^{j+1\shortrightarrow
i})^{\top}(I-A^{\top})\Big{\|}\bm{\Psi},$ (93)

where $(a)$ follows from the sub-multiplicity of the norm, and $(b)$ follows
from the definition

$\bm{\Psi}\triangleq\sup_{j\geq 1}\|\bm{\Psi}_{j}\|,$ (94)

which is shown to be finite under Assumption 1 in Appendix F-D. Subsequently,
the norm of the Cesàro mean satisfies

$\displaystyle\Big{\|}\frac{1}{i}\sum_{j=1}^{i}\bm{R}_{j}\Big{\|}$
$\displaystyle\leq\frac{1}{i}\sum_{j=1}^{i}\Big{\|}\bm{R}_{j}\Big{\|}$
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:rj_bound_psi}}}{{\leq}}\bm{\Psi}\frac{1}{i}\sum_{j=1}^{i}\Big{\|}(\widetilde{\bm{A}}^{j+1\shortrightarrow
i})^{\top}(I-A^{\top})\Big{\|}.$ (95)

Observe that (92) can alternatively be written as (by using the definition
$n=i-j$)

$\displaystyle\lim_{n\to\infty}\Big{\|}(\widetilde{\bm{A}}^{i-n+1\shortrightarrow
i})^{\top}(I-A^{\top})\Big{\|}\operatorname{\stackrel{{\scriptstyle\textup{a.s.}}}{{=}}}0.$
(96)

As a result, the Cesàro mean satisfies

$\displaystyle\lim_{t\to\infty}\frac{1}{t}\sum_{n=0}^{t-1}\Big{\|}(\widetilde{\bm{A}}^{i-n+1\shortrightarrow
i})^{\top}(I-A^{\top})\Big{\|}\operatorname{\stackrel{{\scriptstyle\textup{a.s.}}}{{=}}}0,$
(97)

for any $i\geq t$ (so that $j=i-n\geq 1$). If we set $i=t$, and change the
indices from $n$ to $j=i-n$, we get

$\lim_{i\to\infty}\frac{1}{i}\sum_{j=1}^{i}\Big{\|}(\widetilde{\bm{A}}^{j+1\shortrightarrow
i})^{\top}(I-A^{\top})\Big{\|}\operatorname{\stackrel{{\scriptstyle\textup{a.s.}}}{{=}}}0.$
(98)

Incorporating this into (F-B), we conclude that, as $i\to\infty$,

$\displaystyle\Big{\|}\frac{1}{i}\sum_{j=1}^{i}\bm{R}_{j}\Big{\|}\operatorname{\xrightarrow{\textup{a.s.}}}0,\quad\Longrightarrow\frac{1}{i}\sum_{j=1}^{i}\bm{R}_{j}^{k}\operatorname{\xrightarrow{\textup{a.s.}}}0.$
(99)

$\hfill\blacksquare$

###  F-C Convergence of the Matrix Product

######  Lemma 4.

For a fixed time instant $j$, if $\pi_{\theta}>0$, then

$\displaystyle\widetilde{\bm{A}}^{j\shortrightarrow
i}\operatorname{\xrightarrow{\textup{a.s.}}}v\mathds{1}_{K}^{\top}$ (100)

as $i\to\infty$.

###### Proof.

Recall from (62) that $\widetilde{\bm{A}}_{i}$ is a binary random variable and
let $E_{i}$ denote the event that $\widetilde{\bm{A}}_{i}=A$. Since
$\\{E_{i}\\}_{i=1}^{\infty}$ are independent events across time and their
probability of occurrence satisfies $\pi_{\theta}>0$, it holds that

$\displaystyle\sum_{i=1}^{\infty}\mathbb{P}(E_{i})=\sum_{i=1}^{\infty}\pi_{\theta}=\infty.$
(101)

Subsequently, by the second Borel-Cantelli Lemma [58, Chapter 4.3], we
conclude that

$\displaystyle\mathbb{P}(E_{i}\hskip 2.5pt\text{occurs for infinitely
many}\hskip 2.5pti)=1.$ (102)

Notice that in the product of random matrices

$\displaystyle\widetilde{\bm{A}}^{j\shortrightarrow
i}=\widetilde{\bm{A}}_{j}\widetilde{\bm{A}}_{j+1}\dots\widetilde{\bm{A}}_{i-1}\widetilde{\bm{A}}_{i},$
(103)

the realization of random matrices will either be equal to $A$ or the identity
matrix $I$. Multiplication with identity matrices has no effect on the product
and by (102), there will be infinitely many $A$’s in the product with
probability one, as $n=i-j\to\infty$. Thus, if we define
$A^{\infty}\triangleq\lim_{i\to\infty}A^{i}$,

$\displaystyle\mathbb{P}(\lim_{n\to\infty}\widetilde{\bm{A}}^{j\shortrightarrow
j+n}=A^{\infty})=1.$ (104)

Finally, since $A^{\infty}=v\mathds{1}_{K}^{\top}$ due to $A$ being a
primitive matrix, we conclude that:

$\displaystyle\lim_{n\to\infty}\widetilde{\bm{A}}^{j\shortrightarrow
j+n}\operatorname{\stackrel{{\scriptstyle\textup{a.s.}}}{{=}}}v\mathds{1}_{K}^{\top}$
(105)

for any time instant $j\geq 1$. $\hfill\blacksquare$

###  F-D Uniform Boundedness

In this section, we show that, under Assumption 1

$\bm{\Psi}=\sup_{j\geq
1}\|\bm{\Psi}_{j}\|\stackrel{{\scriptstyle\text{a.s.}}}{{<}}\infty.$ (106)

For that purpose, first, we show that Lemma 1 implies that
$\sum_{k=1}^{K}v_{k}\log\bm{\psi}_{k,i}(\theta^{\circ})$ is a sub-martingale.
To see this, observe that by (60),

$\mathbb{E}_{\xi_{i}}\Big{[}\sum_{k=1}^{K}v_{k}\log\bm{\psi}_{k,i}(\theta^{\circ})\Big{]}\geq\sum_{k=1}^{K}v_{k}\log\bm{\mu}_{k,i-1}(\theta^{\circ}),$
(107)

and in turn, by (C),

$\mathbb{E}_{\tau_{i-1}}\Big{[}\sum_{k=1}^{K}v_{k}\log\bm{\mu}_{k,i-1}(\theta^{\circ})\Big{]}\geq\sum_{k=1}^{K}v_{k}\log\bm{\psi}_{k,i-1}(\theta^{\circ}).$
(108)

Since it is also a non-positive sub-martingale, it converges to a finite limit
almost surely [58, Chapter 11.5], which means that as $i\to\infty$,

$\displaystyle\sum_{k=1}^{K}v_{k}\log\bm{\psi}_{k,i}(\theta^{\circ})$
$\displaystyle\stackrel{{\scriptstyle\text{a.s.}}}{{>}}-\infty$
$\displaystyle\Longrightarrow\forall
k\in\mathcal{N},\quad\log\bm{\psi}_{k,i}(\theta^{\circ})$
$\displaystyle\stackrel{{\scriptstyle\text{a.s.}}}{{>}}-\infty$
$\displaystyle\Longrightarrow\sum_{k=1}^{K}-\log\bm{\psi}_{k,i}(\theta^{\circ})$
$\displaystyle\stackrel{{\scriptstyle\text{a.s.}}}{{<}}\infty$
$\displaystyle\Longrightarrow\|\bm{\Psi}_{i}\|$
$\displaystyle\stackrel{{\scriptstyle\text{a.s.}}}{{<}}\infty.$ (109)

In addition, for any finite time instant $j$, it is true that
$\bm{\psi}_{k,i}(\theta^{\circ})>0$ for each agent $k$ because of the
following reasons. Due to Assumption 1, the initial beliefs are positive.
Moreover, the likelihood at the true hypothesis by definition cannot be zero
for emitted observations. Furthermore, the geometric combination rule results
in the intersection of the supports of its arguments [51]. Consequently, for
any time instant $j$, it is true that $\|\bm{\Psi}_{j}\|<\infty$. Combining
this with (F-D) establishes (106).

## References

  * [1] C. P. Chamley,  Rational Herds: Economic Models of Social Learning,  Cambridge University Press, 2003.
  * [2] P. M. Djurić and Y. Wang,  “Distributed Bayesian learning in multiagent systems: Improving our understanding of its capabilities and limitations,”  IEEE Signal Processing Magazine, vol. 29, no. 2, pp. 65–76, 2012\.
  * [3] C. Chamley, A. Scaglione, and L. Li,  “Models for the diffusion of beliefs in social networks: An overview,”  IEEE Signal Processing Magazine, vol. 30, no. 3, pp. 16–29, 2013\.
  * [4] V. Krishnamurthy and H. V. Poor,  “Social learning and Bayesian games in multiagent signal processing: how do local and global decision makers interact?,”  IEEE Signal Processing Magazine, vol. 30, no. 3, pp. 43–57, 2013\.
  * [5] E. Mossel and O. Tamuz,  “Opinion exchange dynamics,”  Probability Surveys, vol. 14, pp. 155–204, 2017.
  * [6] V. Bordignon, S. Vlaski, V. Matta, and A. H. Sayed,  “Learning from heterogeneous data based on social interactions over graphs,”  IEEE Transactions on Information Theory, vol. 69, no. 5, pp. 3347–3371, 2023.
  * [7] 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\.
  * [8] X. Zhao and A. H. Sayed,  “Learning over social networks via diffusion adaptation,”  in Proc. Asilomar Conference on Signals, Systems and Computers, 2012, pp. 709–713.
  * [9] A. Nedić, A. Olshevsky, and C. A. Uribe,  “Fast convergence rates for distributed non-Bayesian learning,”  IEEE Transactions on Automatic Control, vol. 62, no. 11, pp. 5538–5553, 2017.
  * [10] A. Lalitha, T. Javidi, and A. D. Sarwate,  “Social learning and distributed hypothesis testing,”  IEEE Transactions on Information Theory, vol. 64, no. 9, pp. 6161–6179, 2018.
  * [11] 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, vol. 9, no. 3, pp. 1202–1214, 2022.
  * [12] D. Acemoglu, M. A. Dahleh, I. Lobel, and A. Ozdaglar,  “Bayesian learning in social networks,”  The Review of Economic Studies, vol. 78, no. 4, pp. 1201–1236, 2011\.
  * [13] J. Hazla, A. Jadbabaie, E. Mossel, and M. A. Rahimian,  “Bayesian decision making in groups is hard,”  Operations Research, vol. 69, no. 2, pp. 632–654, 2021.
  * [14] H. A. Simon,  “Bounded rationality,”  in Utility and Probability, pp. 15–18. 1990.
  * [15] J. Conlisk,  “Why bounded rationality?,”  Journal of Economic Literature, vol. 34, no. 2, pp. 669–700, 1996\.
  * [16] M. H. DeGroot,  “Reaching a consensus,”  Journal of the American Statistical Association, vol. 69, no. 345, pp. 118–121, 1974.
  * [17] A. H. Sayed,  “Adaptation, learning, and optimization over networks,”  Foundations and Trends in Machine Learning, vol. 7, no. 4-5, pp. 311–801, July 2014.
  * [18] V. Bordignon, V. Matta, and A. H. Sayed,  “Partial information sharing over social learning networks,”  IEEE Transactions on Information Theory, vol. 69, no. 3, pp. 2033–2058, 2023.
  * [19] R. Salhab, A. Ajorlou, and A. Jadbabaie,  “Social learning with sparse belief samples,”  in Proc. IEEE CDC, 2020, pp. 1792–1797.
  * [20] A. Mitra, S. Bagchi, and S. Sundaram,  “Event-triggered distributed inference,”  in Proc. IEEE CDC, 2020, pp. 6228–6233.
  * [21] P. Paritosh, N. Atanasov, and S. Martinez,  “Hypothesis assignment and partial likelihood averaging for cooperative estimation,”  in Proc. IEEE CDC, 2019, pp. 7850–7856.
  * [22] Y. Inan, M. Kayaalp, E. Telatar, and A. H. Sayed,  “Social learning under randomized collaborations,”  in Proc. IEEE ISIT, 2022, pp. 115–120.
  * [23] M. T. Toghani and C. A. Uribe,  “Communication-efficient distributed cooperative learning with compressed beliefs,”  IEEE Transactions on Control of Network Systems, vol. 9, no. 3, pp. 1215–1226, 2022.
  * [24] A. Mitra, J. A. Richards, S. Bagchi, and S. Sundaram,  “Distributed inference with sparse and quantized communication,”  IEEE Transactions on Signal Processing, vol. 69, pp. 3906–3921, 2021.
  * [25] M. Cirillo, V. Bordignon, V. Matta, and A. H. Sayed,  “Memory-aware social learning under partial information sharing,”  IEEE Transactions on Signal Processing, vol. 71, pp. 2833–2848, 2023.
  * [26] 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\.
  * [27] E. Yildiz, A. Ozdaglar, D. Acemoglu, A. Saberi, and A. Scaglione,  “Binary opinion dynamics with stubborn agents,”  ACM Trans. Econ. Comput., vol. 1, no. 4, pp. 1–30, 2013.
  * [28] S. D. Lena,  “Non-Bayesian social learning and the spread of misinformation in networks,”  Working Papers 2019:09, Department of Economics, University of Venice Ca’ Foscari, 2019,  available at SSRN: https://ssrn.com/abstract=3355245.
  * [29] D. Vial and V. Subramanian,  “Local non-Bayesian social learning with stubborn agents,”  IEEE Transactions on Control of Network Systems, vol. 9, no. 3, pp. 1178–1188, 2022.
  * [30] V. Bordignon, V. Matta, and A. H. Sayed,  “Adaptive social learning,”  IEEE Transactions on Information Theory, vol. 67, no. 9, pp. 6053–6081, 2021.
  * [31] M. Kayaalp, V. Bordignon, S. Vlaski, V. Matta, and A. H. Sayed,  “Distributed Bayesian learning of dynamic states,”  arXiv:2212.02565, Dec. 2022.
  * [32] V. D. Blondel, J. M. Hendrickx, and J. N. Tsitsiklis,  “On Krause’s multi-agent consensus model with state-dependent connectivity,”  IEEE Transactions on Automatic Control, vol. 54, no. 11, pp. 2586–2597, 2009.
  * [33] D. Acemoglu, A. Ozdaglar, and J. Siderius,  “A model of online misinformation,”  Working Paper 28884, National Bureau of Economic Research, June 2021.
  * [34] A. Nedic and A. Ozdaglar,  “Distributed subgradient methods for multi-agent optimization,”  IEEE Transactions on Automatic Control, vol. 54, no. 1, pp. 48–61, 2009.
  * [35] A. H. Sayed,  “Adaptive networks,”  Proc. IEEE, vol. 102, no. 4, pp. 460–497, 2014.
  * [36] A. G. Dimakis, S. Kar, J. M. F. Moura, M. G. Rabbat, and A. Scaglione,  “Gossip algorithms for distributed signal processing,”  Proc. IEEE, vol. 98, no. 11, pp. 1847–1864, 2010.
  * [37] A. H. Sayed,  Inference and Learning from Data,  Cambridge University Press, 2022,  3 vols.
  * [38] M. G. Rabbat and K. I. Tsianos,  “Asynchronous decentralized optimization in heterogeneous systems,”  in Proc. IEEE CDC, 2014, pp. 1125–1130.
  * [39] X. Zhao and A. H. Sayed,  “Asynchronous adaptation and learning over networks—part i: Modeling and stability analysis,”  IEEE Transactions on Signal Processing, vol. 63, no. 4, pp. 811–826, 2015.
  * [40] X. Zhao and A. H. Sayed,  “Asynchronous adaptation and learning over networks—part ii: Performance analysis,”  IEEE Transactions on Signal Processing, vol. 63, no. 4, pp. 827–842, 2015.
  * [41] X. Zhao and A. H. Sayed,  “Asynchronous adaptation and learning over networks—part iii: Comparison analysis,”  IEEE Transactions on Signal Processing, vol. 63, no. 4, pp. 843–858, 2015.
  * [42] X. Lian, W. Zhang, C. Zhang, and J. Liu,  “Asynchronous decentralized parallel stochastic gradient descent,”  in Proc. International Conference on Machine Learning, 10–15 Jul 2018, vol. 80 of Proceedings of Machine Learning Research, pp. 3043–3052.
  * [43] A. S. Bedi, A. Koppel, and K. Rajawat,  “Asynchronous saddle point algorithm for stochastic optimization in heterogeneous networks,”  IEEE Transactions on Signal Processing, vol. 67, no. 7, pp. 1742–1757, 2019.
  * [44] X. Cao and T. Başar,  “Decentralized multi-agent stochastic optimization with pairwise constraints and quantized communications,”  IEEE Transactions on Signal Processing, vol. 68, pp. 3296–3311, 2020.
  * [45] O. A. Hanna, Y. H. Ezzeldin, C. Fragouli, and S. Diggavi,  “Quantization of distributed data for learning,”  IEEE Journal on Selected Areas in Information Theory, vol. 2, no. 3, pp. 987–1001, 2021.
  * [46] M. Ghassemi and A. D. Sarwate,  “Distributed proportional stochastic coordinate descent with social sampling,”  in Proc. Annual Allerton Conference on Communication, Control, and Computing, 2015, pp. 17–24.
  * [47] C. Wang, Y. Zhang, B. Ying, and A. H. Sayed,  “Coordinate-descent diffusion learning by networked agents,”  IEEE Transactions on Signal Processing, vol. 66, no. 2, pp. 352–367, 2017.
  * [48] P. Hu, V. Bordignon, M. Kayaalp, and A. H. Sayed,  “Performance of social machine learning under limited data,”  in Proc. IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), Rhodes Island, Greece, 2023, pp. 1–5.
  * [49] D. Yuan, Y. Hong, D. W. C. Ho, and G. Jiang,  “Optimal distributed stochastic mirror descent for strongly convex optimization,”  Automatica, vol. 90, pp. 196–203, 2018.
  * [50] A. Nedić, A. Olshevsky, and C. A. Uribe,  “A tutorial on distributed (non-Bayesian) learning: Problem, algorithms and results,”  in Proc. IEEE CDC, 2016, pp. 6795–6801.
  * [51] G. Koliander, Y. El-Laham, P. M. Djurić, and F. Hlawatsch,  “Fusion of probability density functions,”  Proc. IEEE, vol. 110, no. 4, pp. 404–453, 2022.
  * [52] T. Li, H. Fan, J. García, and J. M. Corchado,  “Second-order statistics analysis and comparison between arithmetic and geometric average fusion: Application to multi-sensor target tracking,”  Information Fusion, vol. 51, pp. 233–243, 2019.
  * [53] M. Kayaalp, Y. Inan, E. Telatar, and A. H. Sayed,  “On the arithmetic and geometric fusion of beliefs for distributed inference,”  IEEE Transactions on Automatic Control, pp. 1–16, 2023.
  * [54] C. A. Uribe, A. Olshevsky, and A. Nedić,  “Nonasymptotic concentration rates in cooperative learning—part ii: Inference on compact hypothesis sets,”  IEEE Transactions on Control of Network Systems, vol. 9, no. 3, pp. 1141–1153, 2022.
  * [55] S. Kar, J. M. F. Moura, and K. Ramanan,  “Distributed parameter estimation in sensor networks: Nonlinear observation models and imperfect communication,”  IEEE Transactions on Information Theory, vol. 58, no. 6, pp. 3575–3605, 2012.
  * [56] K. Dedecius and P. M. Djurić,  “Sequential estimation and diffusion of information over networks: A Bayesian approach with exponential family of distributions,”  IEEE Transactions on Signal Processing, vol. 65, no. 7, pp. 1795–1809, 2017.
  * [57] R. A. Horn and C. R. Johnson,  Matrix Analysis,  Cambridge University Press, 2012.
  * [58] D. Williams,  Probability with Martingales,  Cambridge University Press, 1991.
  * [59] E. Cesàro,  “Sur la convergence des séries,”  Nouvelles Annales de Mathématiques: Journal des Candidats aux Écoles Polytechnique et Normale, vol. 7, pp. 49–59, 1888.