{'fraction_non_alphanumeric': 0.048575283752678784, 'fraction_numerical': 0.007976823557425192, 'mean_word_length': 3.761715797430083, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 10, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 31, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
On Non-Bayesian Social Learning

We study a model of information aggregation and social learning recently proposed by Jadbabaie, Sandroni, and Tahbaz-Salehi, in which individual agents try to learn a correct state of the world by iteratively updating their beliefs using private observations and beliefs of their neighbors. No individual agent's private signal might be informative enough to reveal the unknown state. As a result, agents share their beliefs with others in their social neighborhood to learn from each other. At every time step each agent receives a private signal, and computes a Bayesian posterior as an intermediate belief. The intermediate belief is then averaged with the belief of neighbors to form the individual's belief at next time step. We find a set of minimal sufficient conditions under which the agents will learn the unknown state and reach consensus on their beliefs without any assumption on the private signal structure. The key enabler is a result that shows that using this update, agents will eventually forecast the indefinite future correctly.


Introduction
We discuss a model of how individuals might use relevant information available to them to form opinions about different social, economic, and political issues. Oftentimes, the "best" action an agent can take is not obvious and depends on certain unknown parameters that determine the agent's utility function. Consider the example of an institution making an investment decision. The expected utility of different investment options depend, among other things, on the expected policies of the next administration, which in turn depend on how likely different political candidates are to win the election. One can think of the candidate who is the most likely to win as an unknown parameter in the investment decision of institutions. We assume that the value of the parameter is an unknown state of the world that is exogenous to our model and is determined at time zero by nature.
Agents make relevant observations about the unknown state. Frequently, not all the agents make the same observations, and not all the observations are equally informative.
Lack of access to all the relevant information is a motivation for individuals to share their opinions with others in order to learn from their personal experiences. The importance of social interactions on opinion dynamics have been documented in several examples such as consumer choice, and diffusion of medical innovations and agricultural practices [1].
We study the scenario in which each individual has two sources of information: his personal observations, and those of his neighbors in a social network (e.g. friends, neighbors, colleagues, etc.). However, agents might not have direct access to personal experiences of their neighbors. Instead, we assume that they can only observe their neighbors' beliefs, i.e., their subjective probabilities of different feasible realizations of the unknown state of the world. An alternative equally valid interpretation is that agents play a particular repeated game of imperfect information where each agent can only observe the actions of his neighbors, and the actions completely reveal the beliefs of acting agents.
To study the effect of social networks on learning, we analyze the model in [2] in which agents use an update other than Bayes' rule to incorporate the new information available to them. Agents repeatedly interact with their neighbors and use a simple rule to update their beliefs. Each agent first forms the Bayesian posterior given his observed private signal, as an intermediate step. He then updates his belief to the convex combination of his Bayesian posterior and the beliefs of his neighbors.
There are two major motivations for considering non-Bayesian protocols: The positive point of view comes from the choice theoretic studies showing existence of non-Bayesian opinion dynamics among people (see [3][4][5] for instance). The second motivation comes from a normative point of view. Bayesian inference in social networks can be, except for certain simple scenarios, computationally complicated to carry out. Part of the complications is because there is no reason to believe that agents know the source of their neighbors' information. Rather, they have to infer it to be able to form an unbiased belief about the true state of the world. The complexities of Bayesian updating limit its applicability in practice.
In [2], the authors show that, under some assumptions, this update eventually leads to social learning, even in finite networks: They show that agents can eventually forecast the immediate future correctly. Furthermore, they will eventually learn the unknown state, if for each agent there exist a signal that is the more probable under the true state of the world than any other state. This assumption "turns the deck" in favor of learning by assuming that agents are infinitely often notified, indirectly, of the true state of the world.
We argue through a simple example that the assumption of having a "revealing" signal is very limiting. We show that agents will learn the state of the world under the much weaker assumption that they can distinguish the state collectively. Signals need not be independent among agents at the same time period. Instead, we require the signal structure to be such that the state is identifiable given the marginals of the likelihood function. We first prove that not only agents will forecast the immediate future correctly, but also they eventually will learn to forecast the indefinite future. We also show that there exist a signal sequence which is informative enough to let agents identify the true state of the world, even if no revealing signal exists. The results signify that even when none of the agents have enough information to learn the true state of the world, and in spite of individual signals not being revealing enough, social interaction can aggregate pieces of information available to the individuals such that each and everyone of them can distinguish the true state of the world. Furthermore, this paper suggests a distributed, computationally tractable algorithm for learning in networks that can be applied to real world problems such as parameter estimation in sensor networks (cf. [6] and the references therein).
Recently there has been a rapidly growing interest in models of learning in networks. For a survey of different models of non-strategic and strategic social learning see [1]. Since in the presence of social networks fully Bayesian inference faces tractability problems, different types of simplifications have been proposed. The first group of models assumes that agents interact sequentially. Examples include models in [7][8][9][10][11]. In such models each agent, having observed the actions of some of the agents acting before, takes an action. Each agent makes only one decision, and cannot reverse or change his choice. The other group of models suggests non-Bayesian rules of thumb for belief update. Examples include [2,[12][13][14][15][16][17][18]].

The Model
The social learning model we consider, was first proposed in [2]. Time is discrete and there is a finite number of agents, signals, and states of the world.
Let Θ be the finite set of possible states of the world, and θ * ∈ Θ be the true state that is determined at time zero by nature, and is unchanged thereafter. Let N = {1, 2, . . . , n} be the set of agents. At time t ≥ 0 each agent i has a belief about the true state, denoted by µ i,t (θ), which is a probability distribution over Θ.
At each time period t ≥ 1 each agent i observes a private random signal ω i,t ∈ S i where S i = {s 1 i , s 2 i , . . . , s M i i } is the set of possible signals for agent i. Conditional on θ ∈ Θ being the state of the world, the observation profile ω t = (ω 1,t , ω 2,t , . . . , ω n,t ) is generated according to the likelihood function ℓ(·| θ) with ℓ i (·| θ) as its ith marginal. Let P θ = ℓ(·| θ) N be the product measure that determines the realization of signals conditioned on θ being the state of the world. This definition allows for signals to be correlated among agents at the same time period, but makes them independent over time. Without loss of generality we assume that ℓ i (s i |θ * ) > 0 for all s i ∈ S i ; S i is only the set of signals that are realized with positive probability conditioned on the true state of the world being θ * .
for all s i ∈ S i } be the set of states that are observationally equivalent to the true state θ * from the point of view of agent i, and let Θ =Θ 1 ∩ · · · ∩Θ n be the set of states that are observationally equivalent to the true state of the world from the point of view of all agents.
(Ω, F , P) is the probability triple, where Ω = ( n i=1 S i ) N , F is the smallest σ-field that makes all ω i,t measurable, and P = P θ * is the probability distribution determining the realization of signals. N stands for the set of natural numbers. We use ω ∈ Ω to denote the infinite signal sequence (ω 1 , ω 2 , . . . ), and E to denote the expected value operator with respect to the probability measure P. Let F i,t = σ(ω i,1 , ω i,2 , . . . , ω i,t ) be the filtration generated by the observations of agent i up to time t, and let F t be the σ-field generated by the union of all F i,t for 1 ≤ i ≤ n.
We say that the adapted random variables X t and Y t are asymptotically P-almost surely equal, denoted by X t a.a.s. = Y t , if there existΩ ⊆ Ω such that P(Ω) = 1, and for all ω ∈Ω and all ǫ > 0, there exist T (ω, ǫ) such that for all t 1 , t 2 > T (ω, ǫ), It is an easy exercise to show that if X t a.a.s.
The interactions between the agents are captured by a directed graph G = (N , E). Let N i = {j ∈ N : (j, i) ∈ E} be the set of neighbors of agent i. It is assumed that agent i can observe the belief of agent j if there exist a directed edge from i to j, that is (i, j) ∈ E. A graph is called strongly connected if there exist a directed path from any vertex to any other one.
Each agent i starts with the initial belief µ i,0 (θ) that θ is the true state of the world. At the end of period t, each agent observes the beliefs of his neighbors. At the beginning of the next period, agent i receives the private signal ω i,t+1 , and then uses the following rule to update his belief: where m i,t (s i ) is defined for any s i ∈ S i as In the update in equation (1) each agent updates his belief to a convex combination of his own Bayesian posterior, given only his private signal and neglecting the social network, and his neighbors' previous period beliefs. a ij is the weight agent i assigns to the opinion of agent j, and a ii , called the self-reliance of agent i, is the weight he assigns to his Bayesian posterior conditional on his private signal. We assume that a ij ∈ R + and j∈N i ∪{i} a ij = 1 for the beliefs to remain a probability distribution over Θ after the update. It is sometimes more convenient to use vector notations. We use A to denote the n × n matrix whose ij element is a ij , and use µ t (θ) to denote the n dimensional column vector whose ith element is µ i,t (θ).
When there is no arrival of new information, this update becomes the same as DeGroot's naive learning model. Likewise, when a ij = 0 for all j = i, the model is the same as the Bayesian learning model with no network structure.
For all t > 0, µ i,t (θ) and m i,t (s i ) are random functions adapted to F t , the former on Θ and the latter on S i . m i,t (s i ) is the probability that agent i assigns, at time t, to signal s i being observed in the next time step, hence, it is called agent i's one step forecast. We can extend this notion to define the k-step forecast m i,t (s i,1 , s i,2 , . . . , s i,k ) as the forecast at time t of agent i that the signal sequence (s i,1 , s i,2 , . . . , s i,k ) ∈ (S i ) k will be realized in the next k time steps The update in equation (1) is local in the sense that each agent only needs the beliefs of his immediate neighbors to compute it.

Asymptotic Learning
In this section we find a set of sufficient conditions for learning when agents use equation (1) to update their beliefs. First we have to define what we mean by learning. For a discussion of different notions of learning and how they are related see [19]. The first one we examine here is the notion of weak merging of opinions.

Definition 1 Agent i learns the likelihood function on a sample path ω, in the sense of weak merging of opinions, if along that path
When an agent learns the likelihood function in this sense, he will know the probability distribution according to which signals are generated. In other words, the agent can forecast the immediate future correctly, as if he knows the likelihood function.
In [2], the authors show that if agents use the update in equation (1), learning in the sense of weak merging of opinions occurs under the following assumptions: is what is known as a "grain of truth" in agent's prior belief. In the discrete setting, this is equivalent to absolute continuity of the initial forecasts with respect to the likelihood function, which is often a necessary condition for learning. The following theorem shows that weak merging of opinions occurs when Assumptions 1(a)-(c) hold.
with P-probability one.
It can also easily be shown through counterexamples that none of the assumptions of the theorem can be relaxed. This theorem corresponds to weak merging of opinions. The much stronger notion of learning is asymptotic learning of the true state of the world.
Definition 2 Agent i asymptotically learns the true parameter θ * on a sample path ω, if along that path To prove asymptotic learning authors add the assumption that for any agent i, there exists a signalŝ i ∈ S i and a positive number δ i such that This assumption asks for existence of a signal that is more likely conditioned on θ * being the true state of the world rather than conditioned on any other state inΘ i being the true state of the world. Under this assumption and provided that the conditions of Theorem 1 hold, the authors prove that all agents asymptotically learn the true parameter θ * with P-probability one. The condition in (2) guarantees that there exist a revealing signal that is observed infinitely often. The following example shows that this is a weak assumption.
Example 1 Consider a strongly connected graph on two agents. Assume that Θ = {θ * , θ 1 , θ 2 }, and S 1 = S 2 = {H, T }. Also assume that the private signals of agents are independent and are generated according to the same probability distribution ℓ(s| θ) which is given by Table 1. In this example there is no signal that satisfies condition (2). But the signal sequence (H, T, T ) is most likely under θ * rather than any other θ ∈ Θ. Furthermore, (H, T, T ) is the shortest such signal sequence.
In this paper we show that to prove asymptotic learning no assumption should be made other than the distinguishability of the true state of the world θ * .

Assumption 2 (Distinguishability) There is no θ ∈ Θ that is observationally equivalent to θ * from the point of view of all agents, that is
This is obviously a necessary condition for the agents to learn the true state of the world. In Theorem 6 which is the main result of this section we show that it is also sufficient. To that end, we first show in Theorem 4 that the correct forecasts of the agents can be extended into the future. To prove these results we first need to present a few preliminary results. The following theorem is a variation of Borel-Cantelli lemma which can be found, among many other places, as Theorem 5.3.2 in [20].
The next theorem we need is the bounded convergence theorem for conditional expectations. For a proof see, for instance, page 263 of [20].
The next two lemmas are technical lemmas which will be used in proof of Theorem 4.

Lemma 1 If Assumption 1 holds then
with P-probability one for all θ ∈ Θ. Proof.

By a similar argument
The conditional expectation is sandwiched between two quantities, both of which go to one P-almost surely by Theorem 1, and so does it.
Proof. We take expectations of both sides of equation (1) conditioned on F t . Since µ j,t (θ) is F t measurable for all 1 ≤ j ≤ n, Taking the limit of the above equation as t → ∞ and using Lemma 1, which in vector form can be written as a.a.s.
The next theorem shows that not only the agents eventually forecast the next step correctly, as shown in Theorem 1, but also they do so for the next k steps for any finite k.

Theorem 4 If Assumption 1 holds, then
with P-probability one for all s i,1 , s i,2 , . . . , s i,k ∈ S i . Proof. To simplify notation we drop the subscript i from s i,1 , s i,2 , . . . , s i,k whenever there is no risk of confusion. We use induction on k. For k = 1 the result is proved in Theorem 1. Multiplying both sides of equation (1) by m i,t (ω i,t+1 )ℓ i (s 2 , . . . , s k | θ) and summing over θ ∈ Θ, Thus, Since all the terms are positive and ℓ i (s 2 , . . . , s k | θ) is a constant, using Fubini's theorem [20] we can change the order of sum and expectation to get By induction hypothesis m i,t+1 (s 2 , . . . , s k ) converges P-almost surely to ℓ i (s 2 , . . . , s k | θ * ). Since m i,t+1 is a probability measure it is bounded for all t. Also note that F t ↑ F . Hence, we can use Theorem 3 to conclude that E(m i,t+1 (s 2 , . . . , s k )| F t ) converges Palmost surely to E(ℓ i (s 2 , . . . , s k | θ * )| F ) which is just ℓ i (s 2 , . . . , s k | θ * ). Therefore, We can now solve for m i,t (ω i,t+1 , s 2 , . . . , s k ) to get By the induction hypothesis, m i,t (s 2 , . . . , s k ) converges on a set of P-probability one to ℓ i (s 2 ,. . . , s k | θ * ). Moreover, m i,t (ω i,t+1 ) is asymptotically P-almost surely equal to ℓ i (ω i,t+1 | θ * ). Therefore, m i,t (ω i,t+1 , s 2 ,. . . , s k ) is asymptotically P-almost surely equal to ℓ i (ω i,t+1 , s 2 , . . . , s k | θ * ). To get the result for any arbitrary s 1 , s 2 , . . . , s k ∈ S i , we need to use Theorem 2. For any ǫ > 0, let and for any s 1 ∈ S i , let Clearly A t is measurable with respect to F t for all t ≥ 1. Since asymptotically P-almost surely m t (ω i,t+1 , s 2 , . . . , s k ) is equal to ℓ i (ω i,t+1 , s 2 , . . . , s k | θ * ), P(A t i.o.) = 0 for any ǫ > 0, where i.o. is the abbreviation for infinitely often. Using Theorem 2 for the A n defined above, with P-probability one. We can write the summand in equation (3) as where for any A ∈ F , 1 A is a random variable defined as 1 Bt(s 1 ) ∈ F t−1 for any s 1 ∈ S, and ω i,t is independent of F t−1 . Since all the random variables in equation (4) are positive, we can switch the order of sum and expected value to get If we substitute the above equation for P(A t |F t−1 ) in equation (3) and use the fact that all the terms are positive to switch the order of the sums, we get that with P-probability. Therefore, P(B t (s 1 ) i.o.) = 0 for any s 1 ∈ S i , and m i,t (s 1 , s 2 , . . . , s k ) converges P-almost surely to ℓ i (s 1 , s 2 , . . . , s k | θ * ) for any s 1 , s 2 , . . . , s k ∈ S i . This theorem shows that, eventually, an agent's forecast at time t of a time t + k event is not different than his forecast at time t + k − 1 of the same event. That is, when agents already have accurate forecasts of immediate future, they cannot improve their forecasts of indefinite future by observing more signals.
The following theorem uses finiteness of S i to show that for any agent i there exist a long enough signal sequence that is more probable under θ * than any state θ / ∈Θ i .
Theorem 5 For any agent i, there exists a finite numberk i and signalsŝ i,1 ,ŝ i,2 , . . . ,ŝ i,k i such that Proof. First assume that ℓ i (s i | θ * ) is a rational number for all s i ∈ S i . In this case we will prove that we can takek i to be the least common denominator (LCD) of {ℓ i (s i | θ * )} s i ∈S i and (ŝ i,1 ,ŝ i,2 , . . . ,ŝ i,k i ) to be a sequence of signals in which the number of occurrences of each s i ∈ S i is exactly equal to the numerator of the fractional representation of ℓ i (s i | θ * ), when the denominator is equal tok i . In other words, we pick the signal sequence in which the frequency of each signal is equal to its probability under θ * . is maximized. As a result, for this sequence ℓ i (·| θ)/ℓ i (·| θ * ) is strictly less than one for any θ / ∈Θ i .
where Q is some probability measure on S i . To simplify notation we drop the subscript i whenever there is no risk of confusion. We solve the following concave maximization problem: where by (p j ) k j we mean p j to the power of k j . We can use a Lagrange multiplier ρ to incorporate the constraint into the cost function [21]. The resulting unconstrained optimization is still concave. Therefore, the optimal solutions can be found using the first order conditions. The resulting set of equalities are which have the unique solution By construction, this solution corresponds to the probability measure ℓ i (·| θ * ).
So far we have proved the theorem for the rational case. For the case that ℓ i (s i | θ * ) is irrational for some s i ∈ S i , the proof follows from continuity of the objective of the optimization problem (6) with respect to (p 1 , p 2 , . . . , p j ), and the fact that rational numbers are dense in reals.
The condition in (5) is the k-step counterpart of the condition in (2). We showed that even though a single signal revealing the true state might not exist, but there are signal sequences that will do so. We are now ready to prove the main result of this section: Theorem 6 If Assumption 1 holds, then with P-probability one for all i ∈ N .
Proof. First we prove that for any agent i, µ i,t (θ) → 0 as t → ∞ for all θ / ∈Θ i with P-probability one. Letk i and (ŝ i,1 ,ŝ i,2 , . . . ,ŝ i,k i ) be a positive integer and a sequence of signals respectively, that satisfy (5). By Theorem 4, m i,t (s i,1 , · · · , s i,k ) → ℓ i (s i,1 , · · · , s i,k | θ * ) with P-probability one for any sequence of finite length. We can use this result forŝ i,1 ,ŝ i,2 , . . . ,ŝ i,k i to conclude that for any ǫ > 0, there existΩ i ⊆ Ω and a random variable T i (ω, ǫ) such that P(Ω i ) = 1, and for any ω ∈Ω i and t > T i (ω, ǫ), and therefore, Using the result of Theorem 5 we can conclude that on any sample path ω ∈Ω i and t > T i (ω, ǫ), Since ǫ > 0 is arbitrary, this proves that µ i,t (θ) → 0 as t → ∞ for all θ / ∈Θ i . Taking limits of equation (1) as t → ∞ and using the result proved above shows that j∈N i a ij µ j,t (θ) converges to zero as t → ∞ and so does µ j,t (θ) for all θ / ∈Θ i and j ∈ N i with P-probability one. Proceeding in the same way and using the strong connectivity assumption, for all j ∈ N , µ j,t (θ) → 0 for all θ / ∈Θ i . Thus, with P-probability one µ i,t (θ) → 0 as t → ∞ ∀i ∈ N , ∀θ / ∈Θ.
Since µ i,t (·) is a probability distribution over Θ for all i and t, we have the following corollary.

Corollary 7 If Assumptions 1 and 2 hold, then
with P-probability one for all i ∈ N .

Conclusion and Future Direction
We analyzed a model of social learning where the agents form their beliefs about an unknown state of the world by taking the convex combination of their Bayesian posterior and the beliefs of their neighbors. Agents will learn the true state of the world if, (a) the social network is strongly connected, (b) all agents have strictly positive self-reliances, and (c) there exists an agent with positive prior belief on the true state. Furthermore, none of these assumptions can be relaxed in general. We also argued that there does not need to exist a revealing signal for learning to happen. Rather, there are always long enough signal sequences that are revealing. We also proved that once the immediate future forecasts of the agents become approximately correct, they can be extended to indefinite future with a negligible error.
We also have shown that, under the same assumptions, not only the agents eventually learn the true state of the world, but also they do so exponentially fast with an exponent that depends both on network topology and on signal structure. Therefore, even though network structure had a minimal effect on the possibility of learning through requiring strong connectivity, it influences the rate of learning in a more complicated and subtle way. Moreover, as a corollary of exponential learning, eventually the consensus dynamic becomes dominant. Hence, even if the true state is not distinguishable, agents eventually reach a consensus.
As we mentioned in Section 1, the model of social learning where the agents exchange their beliefs with their neighbors can be regarded as a trivial game of imperfect information where the actions of the agents completely reveal their beliefs. We would like to extend the model to nontrivial games where the observed actions only contain limited information about the underlying beliefs. Then, to be able to use the simple update discussed in this paper, agents have to estimate the belief of their neighbors based on the history of their observed actions. We are interested in quantifying how, and to what extent unobservability of the beliefs will change the results of this paper.