# Averaging + Learning in Financial Markets

Ionel Popescu  School of Mathematics, Georgia Institute of Technology, 686
Cherry Street, Atlanta, GA 30332-0160 USA<EMAIL_ADDRESS>and
Tushar Vaidya  Engineering Systems and Design, Singapore University of
Technology and Design, 8 Somapah Rd, Singapore 487372
<EMAIL_ADDRESS>
###### Abstract.

This paper develops original models to study interacting agents in financial
markets. The key feature of these models is how interactions are formulated
and analysed. Agents learn from their observations and learning ability to
interpret news or private information. Central limit theorems are developed
but they arise rather unexpectedly. Under certain type of conditions governing
the learning, agents’ beliefs converge in distribution that can be even
fractal. The underlying randomness in the systems is not restricted to be of a
certain class. Fresh insights are gained not only from developing new non-
linear social learning models but also from using different techniques to
study discrete time random linear dynamical systems.

###### 2010 Mathematics Subject Classification:

Primary: 60F05, 91D30; Secondary: 91A99

I.P. was partially supported by UEFISCDI PN-III-P4-ID-PCE-2016-0372 and T.V.
is supported by the SUTD Presidential Graduate Fellowship

##  1\. Introduction

How do markets reach consensus on prices? This is the central theme of this
paper. Traders interact with one another and _learn_ from their environment.
Our aim is to propose new models of interaction and learning.

These new models of learning and interaction entail agents who observe actions
of other traders and update their own beliefs. Repeated interaction can in
certain cases lead to consensus on a particular value of a tradeable
commodity. Interaction models should take into account the environment of
trading. The more traditional or tried approach is to analyze limit order
books. However, the introduction of electronic limit order books poses
challenges but also offers new opportunities to develop new models.

Learning models offer a cogent and natural way to analyse interaction when
agents learn and observe each others’ past actions. For such models there is a
rich interplay between probability, dynamical systems and game theoretic ideas
[MT+17]. Our goal here is to introduce novel ways to analyse learning in the
financial markets. Researchers have developed many mathematical pricing models
that use tools from stochastic calculus and partial differential equations
(PDEs). The issue of price formation at a microscopic level is not really
addressed nor is interaction a feature in traditional stochastic asset pricing
models. The standard object is in formulating a stochastic process that
represents a stock price. For example, the most basic would be geometric
Brownian motion:

$dS_{t}=\mu S_{t}\,dt+\sigma S_{t}\,dW_{t}.$

Here $\mu$ and $\sigma$ denote the mean rate of return and volatility for some
stock and $W_{t}$ is a Brownian motion. These basic processes then form the
backbone of advanced option pricing models that postulate a process for the
asset. Let us turn the question on its head. What if we don’t know the
process? Traditional finance models assure us that $S_{t}$ is a good process
to model the stock price and $S_{t}$ is the market consensus price or the mid
price of indicative quotes. But if we dig a little bit deeper we have to ask
how did the marketplace decide on the stock price $S_{t}$ in the first place.
There must have been interactions between the players to arrive at this quote.

One may propose more advanced stochastic processes but we are interested in a
more basic question. How do we study interaction at the microscopic level? At
a higher frequency level, agents or machines (algorithms) are interacting
before a consensus is reached.

An alternative way to ask is how do agents actually trading come to reach a
consensus on a particular price? In many instance, models will postulate that
a financial asset’s current price be the available. What mechanism led to that
price being selected. It seems natural to develop aspects of social learning
as a starting point.

##  2\. Foundations

Social learning models are now actively studied in many disciplines and there
are many distinct frameworks. The literature is too vast for us to cite all
the major works. So we will highlight the most relevant ones. In all walks of
life, individuals make decisions by observing and inferring actions of others.
What thought process leads one to make a choice after seeing his or her peers
select theirs is a central question not only in the social sciences but also
in engineering and physics [Lor05]. The key point is observation. Human beings
are visual creatures. One of the most canonical models in learning and
aggregation of information is the Degroot model [DeG74].

######  Example 1.

Imagine we have $3$ agents who each have an initial opinion $X_{0}$. They also
take a weighted average of their neighbours: figure 1. Individuals act
simultaneously.

11/321/21/333/41/31/41/2 Figure 1. Trust chain of agents on opinions. All
individuals have self belief, which is identified by loops.

Round by round the agents observe the previous quotes and update their beliefs
by taking new average updates of the truth. The averaging matrix is

$A=\begin{pmatrix}1/3&1/3&1/3\\\ 1/2&1/2&0\\\ 0&1/4&3/4\end{pmatrix}$

and the dynamics are $X_{t}=AX_{t-1}$. Iterating this, we obtain
$X_{t}=A^{t}X_{0}$. Provided that the matrix $A$ is aperiodic and irreducible
consensus is reached and all the agents reach the same decision
$\lim_{t\to\infty}X=C\mathbbm{1}$ for some $C\in\mathbb{R}$. Of course, the
consensus value depends on the initial value. Instructive and illustrative
examples are developed in [Jac10].

This simple example Degroot belies many important subtleties. Some social
learning purists might object that there are redundancies. Agent 1 may take a
weighted average of all agents but then agent 2 is also incorporating views of
the other agents also which gets double counted by agent 1 in further
iterations. This is a strength of the model.

The whole updating process is such that provided the matrix $A$ is irreducible
and aperiodic there is eventual consensus. The fact there is double counting
is not viewing the problem correctly. As each player may weigh beliefs
differently. Players’ different averaging weights are seen as their own unique
take on the averaging rule. By repeated averaging, agents agree on how to
average the same way: the rows become equal.

We focus on Degroot learning models as these represent the reality of trading
accurately. This style of learning is preferable because agents act
simultaneously in a round-by-round fashion. In contrast, for sequential
learning models, each agent makes a decision or update based on the
information set of previous choices. Aggregation of information occurs as more
agents update but at each point in time only one agent updates. Private
signals can also be incorporated in this setting. However, the sequential
nature of updating seems unnatural. For a good survey of social learning in
both sequential and simultaneous settings one may refer to [GS, MT+17, AO11].
Average-based dynamics leads to efficient outcomes provided no individual
exerts a large influence [GJ10]. Averaging agents are also known as Naive
learners because they use the same rule repeatedly. More generally, these type
of dynamics fall under the growing literature on non-Bayesian social learning
.

###  2.1. Bayesian Observational Learning

Theoretical social learning models are roughly divided into two paradigms:
Bayesian and non-Bayesian. Bayesian observational learning examples include
[Ban92, BHW92] and [SS00]. They fall under the category of herd behaviour.
These models are sequential in nature. Agents have a common prior
$\mathbb{P}(\theta)$ for some state of the world $\theta\in\Theta$ at $t=0$,
where $\Theta$ is the set of possible states. As time passes, a player in turn
observes the actions of previous agents and receives a private signal. Each
agent has a one-off decision when she updates her posterior probability and
takes an action (usually a binary choice). In some instances a correct
decision is reached on the true state of the world by the $n$th agent as
$n\to\infty$. After some point, everyone may take the same action. So do
agents asymptotically learn the truth?

Even in the simplest of settings, characterizing equilibria is intractable
[CEMS08] and computationally difficult [HJMR18]. Agents are assumed to be
perfect Bayesian machines, who can do complex posterior calculations by
observing past actions and possess a common prior. These assumptions may seem
a bit unrealistic or too strong. There could be signals that leads society
astray. Information flows in one direction, where an infinite number of agents
are exogenously ordered on a line. If the first few signals are wrong, there
could be a cascade and no asymptotic learning takes place. Nevertheless,
Bayesian models serve as a useful benchmark. Asymptotic Bayesian social
learning is examined at length in [MST14], where the one-off action is relaxed
to allow for repeated plays.

Many modelling environments assume there is a ground truth that agents want to
learn. It could be that there is no ground truth. Recently there has been some
work to try an axiomatic semi-Bayesian approach [MTSJ18]. A more general
framework for rational learning is offered in [MF13] from a theoretical
economics standpoint.

###  2.2. Financial markets: non-Bayesian

In financial markets, trading is never sequential. Transactions occurs at
breakneck speed. Agents move simultaneously: cancellations are the norm in
today’s fast markets. In practical terms, sequential learning models don’t
seem appropriate. Interaction is important in the emergence of consensus.
Choices by agents from the previous round of play are available to all agents
in the current round of play. The question is then what sort of averaging or
heuristic process is ideal.

Degroot learning models convey an essential idea. They offer a functional form
of updating. Myopic updating occurs in each round. Something akin to
persuasion bias could explain our basic model [DVZ03]. As in an echo chamber,
agents in our setup have fixed weights but update their responses until
consensus is reached. One could think of it as a behavioural heuristic and why
repeated averaging is effective. Alternatively, with the right cost function
representing the distance of an agent’s opinion against other opinions the
best response is repeated averaging. Recently there have been some
experimental papers on evidence of Degroot updating [CLX15, BBC17]. Repeated
averaging models are our base precisely because they capture the nature of
interaction and learning in financial markets so succinctly. On top of the
base models we develop more sophisticated extensions, relaxing the fixed
nature of the weights and learning matrices.

###  2.3. Multiagent learning

Degroot updating is also studied as distributed consensus in the engineering
community [Bau16]. A group of sensors or drones communicate to reach
consensus. Here existing methods use graph theory. Moreover, the techniques we
introduce to solve the consensus problems are quite distinct from the usual
ones utilized in engineering literature. Distributed consensus has an updating
rule in the simplest of cases as $x_{t}=A(t)x_{t-1}$, with
$x_{t}\in\mathbb{R}^{n}$ and $A$ a row stochastic matrix. Agents can be seen
as vertices in a graph $(\mathbb{G})$ with edges that is represented as
$\mathbb{G}(\mathcal{V,E})$. Usually, the graphs have a fixed set of vertices
so $\mathcal{V}=\\{1,2,\cdots,n\\}$ and the edges $(j,k)$ denote if agent $j$
puts weight on $k$’s opinion. In our setting, this corresponds to the number
of agents being fixed while the edges or links can be random or time varying.
One can interpret the framework we investigate as a distributed consensus
problem. Generally, in engineering problems, the emphasis is on design of
algorithms that can control the decentralized process to reach consensus.
Distribution algorithms on agreement have been extensively studied in
engineering. Some related works are [MS07, BHOT05, OSFM07, Mor05].

###  2.4. Game theory

Our emphasis is on trading but any network where the players have access to
some sort of learning feedback is suitable. A game theoretic framework where
every player takes into account other players’ payoff is unrealistic and
points to serious difficulties on how to even represent utilities; these are
economic arguments that are better addressed by philosophical interludes.
Moreover, traders rarely have access to private information on how previous
decisions led to a certain payoff for their opponent at least not in a high
frequency sense. If a trading firm is a publicly listed company, then one can
infer its trading losses or gains from public records. Nevertheless specific
profit and loss accounts of trading individual stocks is a private matter.
Firms never break down their income statements down to specific asset classes
or instruments. Results are amalgamated and reported quarterly: not per hour,
minute or second.

Therefore, pure game theory has its shortcomings. Similar questions and issues
to this paper were raised in [Kir02] at an informal level. Our interest is in
building a suitable mathematical structure on which to ask those interesting
questions of price formation. Players can observe previous choices but not the
payoffs of their competitors. A more in depth discussion of learning in games
would take us further away from our goal of studying the mathematical nature
of interaction. The reader can consult [FDLL98, KL94] for a game theoretic
perspective. Dynamical learning is an active area of research in computer
science as well. Articles [PP18, PNGCS14, MPV17] propose and analyze the
dynamics separate from the concept of Nash equilibrium.

##  3\. Basic models

Economists also have many models of learning [Sob00]. Depending on the
question, different paradigms have been put forth. Our objective is learning
and so we aim to use aspects of both game theory and dynamical systems.
Difficulties in Bayesian environments mean the Degroot model has become a
workhorse for social learning [BBCM19]. It offers a way forward for tractable
models that can relax simple assumptions. Research using this framework is
still active. In our setting, a group of traders observe quotes of others and
incorporate an average of previous round quotes. The departure from standard
Degroot learning comes from the fact that not only are the agents learning but
they are getting feedback from an external source on the true consensus value.
To our knowledge, the setting of these types of consensus models to trading is
new. We use the framework of [VMP18] as the base case for our models. Consider

(3.1)
$x^{i}_{t+1}=\sum_{j=1}^{n}a_{ij}x^{j}_{t}+\epsilon_{i}(\bar{\sigma}-x^{i}_{t}),$

which in the matrix form reads

(3.2) $X_{t+1}=AX_{t}+\mathcal{E}(\bar{\sigma}{\bf 1}_{n}-X_{t}),$

where $X_{t}=(x^{1}_{t},...,x^{n}_{t})^{T}$ is the opinion of each agent in
discrete time $t$, and
$\mathcal{E}=\textrm{diag}(\epsilon_{1},...,\epsilon_{n})$ is the learning
rate of each agent when they are provided with a feedback on the consensus
$\bar{\sigma}$. The opinion matrix $A$ encapsulates the weights agents put on
each other. We require $\sum_{j=1}^{n}a_{ij}=1.$ Agents’ aptitude to determine
the quality of feedback is their ability $\epsilon$.

For our purposes, we are careful to distinguish between two concepts: learning
and trading time. We will focus on learning time. Typically in active
financial markets, the quotes (bids and offers) that agents post are cancelled
or revised many times before actual trades occur. Although trading is
occurring at a high frequency, the revision of quotes is occurring at an even
higher frequency. See [GPW+13] for a discussion on cancellations. Agents or
market participants are all trying to learn the true value of a traded
instrument. Agents can see all the previous quotes and thus take a weighted
view of what the next quote should be. The learning activity occurs before
$\bar{\sigma}$ is actually evolving due to trading. For us, time t is learning
time and is quite distinct from trading time, which we we will assume to be
constant. We weaken the condition of convergence as stated in [VMP18].

The feedback can best explain the situation where a similar instrument is
traded on another exchange or there is a common source of market chatter.
Moreover, such chatter is commonly provided through voice box brokers or over-
the-counter markets. We assume all agents have access to this feedback or
chatter. One example would the S&P500 European ETF (SPY) options, which are
not cash settled as SPX options but stock settled. Quotes for the SPY options
will also be linked with the SPX options. Another example of contracts that
contain information on vols is a VIX (volatility index) futures contract.
Sometimes trades occur off-exchange and get reported at the end of the day
through the exchange’s clearing system. How agents interpret information or
market chatter is their unique learning ability.

##  4\. Organization of results

We investigate variations of the model 3.1, characterizing different features.
In section 6, the result from [VMP18] is relaxed to see under what conditions
consensus is still possible. A key feature is that provided agents have
positive learning rates $\epsilon_{i}$, then consensus is the equilibrium
value. In this case, while the particular value is unknown at the start,
learning and interaction ensure convergence to equilibrium.

While the first type of deterministic dynamics are useful, they ignore the
reality of noise. Randomness is an additional term in the feedback term in
section 7. We introduce a random variable $\gamma_{t}$ as a source of noise.
The main theorem shows that if $\gamma_{t}\to 0$ almost surely or in
probability, then $X_{t}\to\bar{\sigma}$. However, the argument is not
straightforward.

Theorem 6 explains the mechanics behind these concepts. Furthermore, provided
the weights matrix $A$ and learning rates $\mathcal{E}$ satisfy some weak
conditions, $X_{t}$ reaches consensus. If the noise is not going to zero, then
the system converges in distribution. Numerical simulations confirm that
$X_{t}$ does reach an asymptotic distribution that may not even be Gaussian.

Nonlinear learning 8 is an extension of our Degroot learners. Players still
average from their observations of past actions but their own unique learning
ability and how they interpret the extra information is a nonlinear function.
This type of model fits with the earlier linear models, preserving the
averaging nature of interaction. Suitable conditions on the nonlinear function
are derived that exhibit consensus. If the shocks are permanent, then
convergence to distribution is possible as with the linear case.

Section 9 presents an important weak convergence (in law) result. The true
state is arrived at endogenously and the consensus value is an endogenous
feature. While the earlier sections assumed that the equilibrium value or
$\bar{\sigma}$ is present in the system, this section assumes no such
universal truth. Though the agents in earlier dynamics come to learn
$\bar{\sigma}$ they do not know it outright. In the averaging case, we propose
that $\bar{\sigma}$ is not part of the system. Whatever value agents
asymptotically converge to, provided they all agree, is the consensus value.
This presents challenges to prove convergence to a probability measure. The
main result in this section is the central limit theorem (9.13). Lindberg’s
original argument is helpful in proving the CLT.

In all our models, if the agents are already synchronized or at consensus,
then the system stays there. While this may seem a moot point, it is worth
mentioning. In traditional game-theoretic models the focus is on equilibrium.
The focus here is how do agents reach the steady state.

##  5\. Notation and Assumptions

In all subsequent analysis $A$ refers to a row-stochastic weights matrix,
whose rows sum to one. Depending on the setup, $A$ can be time varying or
fixed.

We use the infinity norm, namely we take for a vector
$v=\begin{bmatrix}v_{1}\\\ \vdots\\\ v_{n}\end{bmatrix},\,$

$|v|_{\infty}=\max_{i=1,\cdots,n}|v_{i}|.$

For any $m\times n$ matrix $B$, we denote

$|B|_{\infty}=\sup_{i=1,\dots,m}\sum_{j=1}^{n}|b_{ij}|.$

We then have for any $m\times n$ matrix $B$ and any $n$ dimensional vector $v$

$|Bv|_{\infty}\leq|B|_{\infty}|v|_{\infty}.$

##  6\. Base Model

In the base model, we have $n$ agents and a fixed row-stochastic matrix $A$,
which is the weights matrix. The dynamics for updating is

(6.1) $X_{t+1}=AX_{t}+\mathcal{E}(\bar{\sigma}{\bf 1}_{n}-X_{t}).$

We can impose a weaker condition on $\epsilon_{i}$ and use
$\bar{\sigma}=\bar{\sigma}{\bf 1}_{n}$ for notational convenience when the
dimension is clear.

######  Proposition 2.

If $0<\epsilon_{i}<2a_{ii}$, then all agents reach the same consensus value

$\lim_{t\to\infty}X_{t}=\bar{\sigma}.$

###### Proof.

Equation 6.1 now becomes

$X_{t+1}-\bar{\sigma}=(A-\mathcal{E})(X_{t}-\bar{\sigma}).$

Setting $B=(A-\mathcal{E})$ and $Y_{t}=X_{t+1}-\bar{\sigma}$, the updating
rule simplifies to

$(Y_{t})_{i}=\sum_{j=1}^{n}b_{ij}(Y_{t-1})_{j},$

from which can then obtain

$\displaystyle|(Y_{t})_{i}|$
$\displaystyle\leq\sum_{j=1}^{n}|b_{ij}||(Y_{t-1})_{j}|$
$\displaystyle\leq|Y_{t-1}|_{\infty}\sum_{j=1}^{n}|b_{ij}|.$

Therefore,
$|Y_{t}|_{\infty}\leq|Y_{t-1}|_{\infty}\max_{\begin{subarray}{c}i=1,\cdots,n\end{subarray}}\sum_{j=1}^{n}|b_{ij}|$.

On the other hand $b_{ij}=a_{ij}$, if $i\neq j$ so that

$\sum_{j=1}^{n}|b_{ij}|=|a_{ii}-\epsilon_{i}|+\sum_{j\neq
i}^{n}|a_{ij}|=|a_{ii}-\epsilon_{i}|+1-a_{ii},$

where we have used the stochasticity of $A$, that is sum of the elements of
each row is 1. From this if we check that $|a_{ii}-\epsilon_{i}|+1-a_{ii}<1$
which is the same as $|a_{ii}-\epsilon_{i}|<a_{ii}$ or equivalently
$0<\epsilon_{i}<2a_{ii}$, then with

$\rho=\max_{\begin{subarray}{c}i\end{subarray}}(|a_{ii}-\epsilon_{i}|+1-a_{ii}).$

we definitely obtain $0\leq\rho<1$ and
$|Y_{t}|_{\infty}\leq\rho\,|Y_{t-1}|_{\infty}$. This is enough to conclude
that

$|Y_{t}|_{\infty}\leq\rho^{t}\,|Y_{0}|_{\infty}.$

From which letting $t\to\infty$ shows that

$|Y_{t}|_{\infty}\xrightarrow[t\rightarrow\infty]{}0$

and in particular also proves that
$Y_{t}\underset{t\to\infty}{\longrightarrow}0.$ ∎

######  Remarks.

This argument allows an extension to the case when the matrices $A_{t}$ and
$\mathcal{E}_{t}$ depend on t. The bottom line here is that we want

$\rho_{t}=\max_{i}(|a_{ii}(t)-\epsilon_{i}(t)|+1-a_{ii}(t))$

so that

(6.2) $\prod_{i=1}^{t}\rho_{i}\underset{t\to\infty}{\longrightarrow}0.$

For example, this is the case if all $\rho_{t}$ are bounded by $\rho<1$.
However, condition 6.2 also allows cases where
$\rho_{t}\underset{t\to\infty}{\longrightarrow}1.$ We highlight two examples.
For the first we have convergence.

######  Example 3.

Let’s consider $\rho_{t}=\frac{t}{t+1}$, then
$\prod_{i=1}^{t}\rho_{i}=\frac{1}{t+1}$ which converges to 0 as $t\to\infty$.

However, condition 6.2 also ensures we don’t have the following situation.

######  Example 4.

Let’s consider $\rho_{t}=\exp(-\frac{1}{t^{2}})$, then
$\prod_{i=1}^{t}\rho_{i}=\exp(-\sum_{k=1}^{t}\frac{1}{k^{2}})$ which does not
converge to zero.

Condition 6.2 can also be written as

$\sum_{i=1}^{t}\log\rho_{i}\xrightarrow[t\rightarrow\infty]{}-\infty,$

or differently as

$\sum_{i=1}^{t}(-\log\rho_{i})\xrightarrow[t\rightarrow\infty]{}\infty.$

In fact, this is the case if $\frac{-\log\rho_{t}}{t^{-\alpha}}\geq C$ for
some $C>0$ and $\alpha>0$. This translates to

$\rho_{t}\leq e^{-Ct^{\alpha}}.$

We can extend the conclusions if we replace the $\infty$-norm of a vector by
something of the form

$|\nu|_{\infty,\beta}=\max_{i=1,\cdots,n}|\nu_{i}|/\beta_{i}$

where $\beta$ is a vector of positive values such that
$A\beta\leq\delta\beta$. In this new norm we now have

$\displaystyle|(Y_{t})_{i}|$
$\displaystyle\leq\sum_{j=1}^{n}|b_{ij}||(Y_{t-1})_{j}|$
$\displaystyle\dfrac{|(Y_{t})_{i}|}{\beta_{i}}$
$\displaystyle\leq\sum_{j=1}^{n}\dfrac{|b_{ij}|\beta_{j}}{\beta_{i}}\dfrac{|(Y_{t-1})|_{j}}{\beta_{j}},$

which yields

$\displaystyle|(Y_{t})|_{\infty,\beta}$
$\displaystyle\leq|(Y_{t-1})|_{\infty,\beta}\max_{i=1,\cdots,n}\sum_{j=1}^{n}\dfrac{|b_{ij}|\beta_{j}}{\beta_{i}}$
$\displaystyle=|(Y_{t-1})|_{\infty,\beta}\max_{i=1,\cdots,n}\left(|a_{ii}-\epsilon_{i}|+\dfrac{1}{\beta_{i}}\sum_{j\neq
i}^{n}a_{ij}\beta_{j}\right).$

From the assumption $A\beta\leq\delta\beta$ we can get in the first place that
$\sum_{j=1}^{n}a_{ij}\beta_{j}\leq\delta\beta_{i}$ or $\sum_{j\neq
i}^{n}a_{ij}\beta_{j}\leq\beta_{i}(\delta-a_{ii})$ and thus
$\frac{1}{\beta_{i}}\sum_{j\neq i}^{n}a_{ij}\beta_{j}\leq(\delta-a_{ii})$.
This yields

$|Y_{t}|_{\infty,\beta}\leq|(Y_{t-1})|_{\infty,\beta}\max_{i=1,\cdots,n}\left(|a_{ii}-\epsilon_{i}|+\delta-
a_{ii}\right).$

as long as $|a_{ii}-\epsilon_{i}|+\delta-a_{ii}<1$, which is satisfied by
$-(1-\delta)<\epsilon_{i}<1-\delta+2a_{ii}$. The question is if there exists
such a vector with $A\beta\leq\delta\beta$ (this means component wise). Such a
choice is $\beta=\begin{pmatrix}1\\\ \vdots\\\ 1\end{pmatrix}$ and $\delta=1$
since $A$ is a stochastic matrix. If such a $\beta$ exists with $\delta<1$
then we get a relaxation of the main condition.

Interestingly, if $A$ is not necessarily stochastic but has positive entries,
then by a theorem of Perron-Frobenius there exists a real eigenvalue that is
greater than the absolute value of all the other eigenvalues and its
eigenvector has positive entries. The argument above shows that we can
definitely choose $\delta$ and $\beta$ to have the same result.

The above arguments allow us to posit this result.

######  Theorem 5.

Assume $X_{t}=A_{t}X_{t-1}+\mathcal{E}_{t}(\bar{\sigma}-X_{t-1})$ and let
$\rho_{t}=\max_{i=1,\cdots,n}(|(a_{t})_{ii}-(\epsilon_{t})_{i}|+1-(a_{t})_{ii})$.
If $\prod_{s=1}^{t}\rho_{s}\underset{t\to\infty}{\longrightarrow}0$, then
$X_{t}\underset{t\to\infty}{\longrightarrow}\bar{\sigma}$.

In the case $A_{t}$ are all equal to A, then if
$0<\epsilon_{i}<2a_{ii},\>i=1,\cdots,n,$ then
$X_{t}\underset{t\to\infty}{\longrightarrow}\bar{\sigma}$.

##  7\. Learning with random noise

Our base model with learning can be extended to have random noise in the
feedback term. We introduce a random vector $\gamma_{t}$ which we quantify
later. The hypothesis is that $\gamma_{t}$ is small. For this section we also
consider the case of time depending evolution.

The model is given by

$X_{t}=A_{t}X_{t-1}+\mathcal{E}_{t}(\bar{\sigma}+\gamma_{t}-X_{t-1})$

where $X_{t}$ is the vector of prices at time $t$ and $\bar{\sigma}$ is the
vector of equilibrium price or consensus value the agents are trying to learn.
In order to prove that $X_{t}-\bar{\sigma}$ converges to 0, we rewrite the
equation as

$\displaystyle X_{t}-\bar{\sigma}$
$\displaystyle=A_{t}X_{t-1}-\bar{\sigma}+\mathcal{E}_{t}(\bar{\sigma}-X_{t-1})+\mathcal{E}_{t}\gamma_{t}$
$\displaystyle=AX_{t-1}-A_{t}\bar{\sigma}+\mathcal{E}_{t}(\bar{\sigma}-X_{t-1})+\mathcal{E}_{t}\gamma_{t}\mbox{
as $A\bar{\sigma}=\bar{\sigma}$ }$
$\displaystyle=(A_{t}-\mathcal{E}_{t})(X_{t-1}-\bar{\sigma})+\mathcal{E}_{t}\gamma_{t}.$

Therefore if we denote by $Y_{t}=X_{t-1}-\bar{\sigma}$, then we ca simplify
the above expression as

$Y_{t}=(A_{t}-\mathcal{E}_{t})Y_{t-1}+\mathcal{E}_{t}\gamma_{t}.$

With the same argument as before we obtain

$|Y_{t}|_{\infty}\leq\rho_{t}|Y_{t-1}|_{\infty}+C|\gamma_{t}|$

with

(7.1)
$\rho_{t}=\max_{i=1,\cdots,n}(|(a_{t})_{ii}-(\epsilon_{t})_{i}|+1-(a_{t})_{ii}).$

We formulate a general result as follows.

######  Theorem 6.

Assume the model
$X_{t}=A_{t}X_{t-1}+\mathcal{E}_{t}(\bar{\sigma}+\gamma_{t}-X_{t-1})$. With
the notation from (7.1) assume that

(7.2) $\sup_{t\geq
1}\\{\rho_{t}+\rho_{t}\rho_{t-1}+\rho_{t}\rho_{t-1}\rho_{t-2}+\dots+\rho_{t}\rho_{t-1}\dots\rho_{1}\\}<\infty.$

  1. (1)

If $\gamma_{t}\xrightarrow[t\to\infty]{a.s}0$, then
$X_{t}\xrightarrow[t\to\infty]{a.s}\bar{\sigma}$.

  2. (2)

If $\gamma_{t}\xrightarrow[t\to\infty]{\mathbb{P}}0$, then
$X_{t}\xrightarrow[t\to\infty]{\mathbb{P}}\bar{\sigma}$.

  3. (3)

If $\gamma_{t}\xrightarrow[t\to\infty]{L^{p}}0$, then
$X_{t}\xrightarrow[t\to\infty]{L^{p}}\bar{\sigma}$.

  4. (4)

If we assume

(7.3) $X_{t}=A_{t}X_{t-1}+\mathcal{E}_{t}(\gamma_{t}-X_{t-1})$

where now $(\gamma_{t})_{t\geq 1}$ are iid and integrable and in addition to
(7.2) we assume that

(7.4) $\sum_{t\geq
1}(|A_{t}-A_{t-1}|_{\infty}+|\mathcal{E}_{t}-\mathcal{E}_{t-1})|_{\infty})<\infty.$

Then,

(7.5) $X_{t}\text{ converges in distribution as }t\to\infty.$

  5. (5)

Furthermore, if $\gamma_{t}$ is integrable but not constant almost surely,
then, without condition (7.4), the conclusion of (7.5) does not hold.

Observe here the fact that in the last part of the Theorem we incorporated the
constant $\bar{\sigma}$ into $\gamma_{t}$. The convergence is in distribution
sense and thus it does not lead to convergence as in the previous cases. Even
if we assume that $\gamma_{t}$ is of the form $\bar{\sigma}+\gamma_{t}$, the
convergence will not be to $\bar{\sigma}$ alone. Thus this is a different
convergence scenario and in spirit is not of the same form as the other cases.

###### Proof.

  1. (1)

From our base model in terms of $Y_{t}$ is

(7.6) $Y_{t}=(A_{t}-\mathcal{E}_{t})Y_{t-1}+\mathcal{E}_{t}\gamma_{t}.$

From this we get

(7.7) $|Y_{t}|_{\infty}\leq\rho_{t}|Y_{t-1}|_{\infty}+C|\gamma_{t}|_{\infty}.$

If we assume that $|\gamma_{t}|_{\infty}\xrightarrow[t\to\infty]{a.s}0$, then
we get that $|Y_{t}|\xrightarrow[t\to\infty]{a.s}0$. Indeed, this becomes a
purely deterministic statement. For a given $\epsilon>0$, we can find that
$|\gamma_{t}|_{\infty}\leq\epsilon$ for all $t\geq t_{\epsilon}$. Then,

$|Y_{t}|_{\infty}\leq\rho_{t}|Y_{t-1}|_{\infty}+C\epsilon\quad\forall t\geq
t_{\epsilon}.$

Using the previous inequalities for $t-1$, $t-2$, …, $t_{\epsilon}$ gives that

$|Y_{t}|_{\infty}\leq(\prod_{s=t_{\epsilon}}^{t}\rho_{s})|Y_{t_{\epsilon}-1}|_{\infty}+C\epsilon(1+\rho_{t}+\cdots+\prod_{s=t_{\epsilon}}^{t}\rho_{s}).$

From (7.2) we obtain in the first place that for some constant $A>0$,

(7.8)
$A\geq\rho_{t}+\rho_{t}\rho_{t-1}+\dots+\rho_{t}\rho_{t-1}\dots\rho_{1}.$

We recall here the Cauchy-Schwartz inequality, which states that for any real
numbers $a_{1},a_{2},\dots,a_{t}$ and $b_{1},b_{2},\dots,b_{t}$, we have

$\left(\sum_{i=1}^{t}a_{i}^{2}\right)\left(\sum_{i=1}^{t}b_{i}^{2}\right)\geq\left(\sum_{i=1}^{t}a_{i}b_{i}\right)^{2}$

and in particular this implies that for any $a_{i}>0$,

(7.9)
$\left(\sum_{i=1}^{t}a_{i}\right)\left(\sum_{i=1}^{t}\frac{1}{a_{i}}\right)\geq
t^{2}.$

Now we can write using (7.9) that

$\displaystyle A$
$\displaystyle\geq\rho_{t}\rho_{t-1}\dots\rho_{1}(1+\frac{1}{\rho_{1}}+\frac{1}{\rho_{1}\rho_{2}}+\dots+\frac{1}{\rho_{1}\rho_{2}\dots\rho_{t-1}})$
$\displaystyle\geq\rho_{t}\rho_{t-1}\dots\rho_{1}\frac{t^{2}}{1+\rho_{1}+\rho_{1}\rho_{2}+\dots+\rho_{1}\rho_{2}\dots\rho_{t}}$
$\displaystyle\geq\rho_{t}\rho_{t-1}\dots\rho_{1}\frac{t^{2}}{tA}$

where we used the fact that from (7.8), we have that
$\rho_{1}\rho_{2}\dots\rho_{s}\leq A$ for any $s\geq 1$. Notice here that we
need to distinguish here two cases, namely $\rho_{t}\rho_{t-1}\dots\rho_{1}>0$
and $\rho_{t}\rho_{t-1}\dots\rho_{1}=0$. The above inequality works for the
former case, but in both cases we obtain that

(7.10) $\rho_{t}\rho_{t-1}\dots\rho_{1}\leq\frac{A^{2}}{t}$

which yields that $\rho_{t}\rho_{t-1}\dots\rho_{1}$ converges to $0$. Thus in
this case we get

$|Y_{t}|_{\infty}\xrightarrow[t\to\infty]{a.s.}0.$

  2. (2)

If we only assume a weaker condition, namely that
$\gamma_{t}\xrightarrow[t\to\infty]{\mathbb{P}}0$ (only convergence in
probability), then iterating (7.7) we obtain

(7.11)
$|Y_{t}|_{\infty}\leq(\prod_{s=1}^{t}\rho_{s})|Y_{0}|_{\infty}+\sum_{s=0}^{t}(\prod_{i=t-s+1}^{t}\rho_{i})|\gamma_{t-s}|_{\infty}$

with the convention that $\prod_{i=t+1}^{t}\rho_{i}=1$.

To finish the proof of we use the following Lemma with
$u_{t}=|\gamma_{t}|_{\infty}$.

######  Lemma 7.

Let $(u_{n})_{n\geq 1}$ be a random sequence such that

(7.12) $\displaystyle u_{n}\xrightarrow[n\to\infty]{\mathbb{P}}0$ (7.13)
$\displaystyle\mathbb{P}(\sup_{n\geq 1}|u_{n}|<\infty)=1.$

Then, under the assumption (7.2), we have the convergence
$\sum_{i=1}^{t}\rho_{t}\rho_{t-1}\dots\rho_{t-i+1}u_{t-i}\xrightarrow[t\to\infty]{\mathbb{P}}0.$

###### Proof.

For the argument denote for simplicity of writing
$\eta_{t,i}=\rho_{t}\rho_{t-i}\dots\rho_{t-i+1}$. The first observation here
is that condition (7.21) gives that for any $t\geq s$, using (7.9), we proceed
as in the proof of (7.10) to argue that

$\begin{split}A&\geq\rho_{t}+\rho_{t}\rho_{t-1}+\dots+\rho_{t}\rho_{t-1}\dots\rho_{t-s+1}\\\
&=\rho_{t}\rho_{t-1}\dots\rho_{t-s+1}\left(1+\frac{1}{\rho_{t-s+1}}+\frac{1}{\rho_{t-s+1}\rho_{t-s}}+\dots+\frac{1}{\rho_{t-s+1}\rho_{t-s}\dots\rho_{t-1}}\right)\\\
&\geq\rho_{t}\rho_{t-1}\dots\rho_{t-s+1}\frac{s^{2}}{1+\rho_{t-s+1}+\rho_{t-s+1}\rho_{t-s}+\dots+\rho_{t-s+1}\rho_{t-s}\dots\rho_{t-1}}\\\
&\geq\rho_{t}\rho_{t-1}\dots\rho_{t-s+1}\frac{s^{2}}{As}.\end{split}$

Notice that we used the fact that (from (7.8)) for any $s\leq t$,
$\rho_{t}\rho_{t-1}\dots\rho_{s}\leq A$. Therefore

(7.14) $\rho_{t}\rho_{t-1}\dots\rho_{t-s+1}\leq\frac{A^{2}}{s}$

and using this and again (7.8) for $t$ replaced by $t-s$ we obtain that

(7.15)
$\rho_{t}\rho_{t-1}\dots\rho_{t-s+1}(1+\rho_{t-s}+\rho_{t-s-1}\rho_{t-s-2}+\dots+\rho_{t-s}\dots\rho_{1})\leq\frac{A^{3}}{s}.$

Now, we fix $s\leq t$ and write

$|\sum_{i=1}^{t}\eta_{t,i}u_{t-i}|\leq\sum_{i=1}^{s}\eta_{t,i}|u_{t-i}|+\sum_{i=s+1}^{t}\eta_{t,i}|u_{t-i}|$

Now, for a given $\epsilon$ and $|\sum_{i=1}^{t}\eta_{t,i}u_{t-i}|>\epsilon$,
we must have that at least one of the above sums must be at least
$\epsilon/2$, thus, we can write for each fixed $\epsilon>0$,

(7.16)
$\mathbb{P}(|\sum_{i=1}^{t}\eta_{t,i}u_{t-i}|>\epsilon)\leq\mathbb{P}(\sum_{i=1}^{s}\eta_{t,i}|u_{t-i}|\geq\epsilon/2)+\mathbb{P}(\sum_{i=s+1}^{t}\eta_{t,i}|u_{t-i}|>\epsilon/2).$

The next step is to use the boundedness of $u_{t}$. Take arbitrary
$\delta,M>0$, (here $\delta$ is meant to be small and $M$ to be large) and
then set

$A_{M}=\\{|u_{n}|\leq M\text{ for all }n\geq 1\\}.$

From the condition (7.13) we definitely have that $\mathbb{P}(A_{M})$
converges to $1$ as $M$ tends to infinity. Therefore we can continue the
equation (7.16) with

$\displaystyle\mathbb{P}(|\sum_{i=1}^{t}\eta_{t,i}u_{t-i}|>\epsilon)$
$\displaystyle\leq\mathbb{P}(\sum_{i=1}^{s}\eta_{t,i}|u_{t-i}|\geq\epsilon/2)+\mathbb{P}(\sum_{i=s+1}^{t}\eta_{t,i}|u_{t-i}|>\epsilon/2,A_{M})+\mathbb{P}(\sum_{i=s+1}^{t}\eta_{t,i}|u_{t-i}|>\epsilon/2,A_{M}^{c})$
$\displaystyle\leq\sum_{i=1}^{s}\mathbb{P}(\eta_{t,i}|u_{t-i}|\geq\epsilon/(2s))+\mathbb{P}(M\sum_{i=s+1}^{t}\eta_{t,i}>\epsilon/2,A_{M})+\mathbb{P}(A_{M}^{c})$
$\displaystyle\leq\sum_{i=1}^{s}\mathbb{P}(\eta_{t,i}|u_{t-i}|\geq\epsilon/(2s))+\mathbb{P}(\sum_{i=s+1}^{t}\eta_{t,i}>\epsilon/(2M))+\mathbb{P}(A_{M}^{c})$
$\displaystyle\leq\sum_{i=1}^{s}\mathbb{P}(\eta_{t,i}|u_{t-i}|\geq\epsilon/(2s))+\mathbb{P}(\frac{A+1}{s}>\epsilon/(2M))+\mathbb{P}(A_{M}^{c})$

where in the passage from the first line to the second we used the union
bound, more precisely, if we have
$\sum_{i=1}^{s}\eta_{t,i}|u_{t-i}|\geq\epsilon/2$ then at least one of the
terms must be $\geq\epsilon/(2s)$ plus the union bound on the probability.
Finally in passage to the last line we simply used (7.15).

Next we can freeze for now $\epsilon,s,M$ and use the fact that for each $i$,
$\eta_{t,i}u_{t-i}$ converges to $0$ in probability since $\eta_{t,i}$ is
bounded by $A>0$ and use (7.15) to argue that the limit as $t\to\infty$ we
gain that

$0\leq\limsup_{t\to\infty}\mathbb{P}(|\sum_{i=1}^{t}\eta_{i}u_{t-i}|>\epsilon)\leq\mathbb{P}(\frac{A+1}{s}>\epsilon/(2M))+\mathbb{P}(A_{M}^{c}).$

For large $s$, obviously $\mathbb{P}(\frac{A+1}{s}>\epsilon/(2M))=0$ and thus
we arrive at

$0\leq\limsup_{t\to\infty}\mathbb{P}(|\sum_{i=1}^{t}\eta_{i}u_{t-i}|>\epsilon)\leq\mathbb{P}(A_{M}^{c}).$

From this, we take the limit as $M\to\infty$ and using (7.12)

$0\leq\limsup_{t\to\infty}\mathbb{P}(|\sum_{i=1}^{t}\eta_{i}u_{t-i}|>\epsilon)=0$

which means convergence of $\sum_{i=1}^{t}\eta_{i}u_{t-i}$ to $0$ in
probability. ∎

Now let’s return to the proof of the Theorem.

  3. (3)

For the $L^{p}$ convergence we just need to take expectation of (7.11).

  4. (4)

For the convergence in distribution we start by writing

$X_{t}=B_{t}X_{t-1}+\mathcal{E}_{t}\gamma_{t}$

where $B_{t}=A_{t}-\mathcal{E}_{t}$. The idea is that because $\gamma_{t}$ are
in $L^{1}$ so are all the variables $X_{t}$. We are going to use the
Wasserstein distance to control the difference between the distributions of
$X_{t}$ and $X_{t-1}$.

The basic idea is that in a slightly modified Wasserstein distance $D$ we have
a contraction in the sense that there exists some $\rho<1$ such that

(7.17) $D(X_{t},X_{t-1})\leq\rho D(X_{t-1},X_{t-2}).$

For the sake of completeness we define here for two $n$-dimensional random
variables, $X,Y$ or better for their distributions $\mu_{X},\mu_{Y}$,

(7.18)
$D(X,Y)=\left(\inf_{\alpha}\int|x-y|_{\infty}\alpha(dx,dy)\right)=\inf_{\alpha}\mathbb{E}[|\tilde{X}-\tilde{Y}|_{\infty}]$

where $\alpha$ is a $2n$-dimensional distribution with marginals $\mu_{X}$ and
$\mu_{Y}$ and $\tilde{X}$ $\tilde{Y}$ are two random variables on the same
probability space (we call it a coupling) with the same distributions as $X$,
respectively $Y$. The second equality follows easily from taking $\tilde{X}$
and $\tilde{Y}$ to be the projections from
$\pi_{i}:\mathbb{R}^{n}\times\mathbb{R}^{n}\to\mathbb{R}^{n}$, given by
$\pi_{1}(x,y)=x$ while $\pi_{2}(x,y)=y$. To go from the pair
$(\tilde{X},\tilde{Y})$ back to the measure $\alpha$, we just need to take
$\alpha$ to be the distribution of the pair $(\tilde{X},\tilde{Y})$.

The standard Wasserstein distance is defined as

$W_{1}(X,Y)=\left(\inf_{\alpha}\int|x-y|\alpha(dx,dy)\right)=\inf\mathbb{E}[|\tilde{X}-\tilde{Y}|].$

Because any two norms on $\mathbb{R}^{n}$ are equivalent, we can find two
constants $c_{1},c_{2}>0$ such that

$c_{1}W_{1}(X,Y)\leq D(X,Y)\leq c_{2}W_{1}(X,Y).$

It is known that $W_{1}$ gives the topology of weak converge on the space of
probability measures with finite first moment (that is
$\int|x|\mu(dx)<\infty$). Due to the above inequality we also infer the
completeness with respect to the metric $D$ on the same space
$\mathcal{P}_{1}(\mathbb{R}^{n})$.

To carry on this program we define for a distribution $\mu$, the following map

$F_{t}(\mu)=\text{ the distribution of }g_{t}(X_{t-1},\gamma)\text{ with
}g_{t}(x,\lambda)=(A_{t}-\mathcal{E}_{t})x+\mathcal{E}_{t}\lambda,x,\lambda,\in\mathbb{R}^{n},$

where $X$ is a random variable with distribution $\mu$ and $\gamma$ is a
random variable independent of $X$ and having the same distribution as the
sequence $\gamma_{t}$.

Now we want to look at $D(X_{t},X_{t-1})$ and estimate it from above. To do
this assume that we have a coupling between $X_{t-1}$ and $X_{t-2}$ and then
we can create an optimal coupling between $X_{t}$ and $X_{t-1}$ (with respect
to the distance $D$, which certainly exists from Kantorovich general result)
and then take $\gamma$ independent of both $X_{t-1}$ and $X_{t-2}$ and use

$\displaystyle X_{t}-X_{t-1}$
$\displaystyle=(A_{t}-\mathcal{E}_{t})X_{t-1}+\mathcal{E}_{t}\gamma-(A_{t-1}-\mathcal{E}_{t-1})X_{t-2}-\mathcal{E}_{t-1}\gamma$
$\displaystyle=(A_{t}-\mathcal{E}_{t})(X_{t-1}-X_{t-2})+(A_{t}-A_{t-1}-\mathcal{E}_{t}+\mathcal{E}_{t-1})X_{t-2}+(\mathcal{E}_{t}-\mathcal{E}_{t-1})\gamma.$

Taking $|\cdot|_{\infty}$ and the expectation both sides we get the estimate

(7.19)
$\begin{split}\mathbb{E}[|X_{t}-X_{t-1}|_{\infty}]&\leq\mathbb{E}[|(A_{t}-\mathcal{E}_{t})(X_{t-1}-X_{t-2})|_{\infty}]+\mathbb{E}[|(A_{t}-A_{t-1}-\mathcal{E}_{t}+\mathcal{E}_{t-1})X_{t-2}|_{\infty}]+\mathbb{E}[|(\mathcal{E}_{t}-\mathcal{E}_{t-1})\gamma|_{\infty}]\\\
&\leq\rho_{t}\mathbb{E}[|X_{t-1}-X_{t-2}|_{\infty}]+\alpha_{t}(\mathbb{E}[|X_{t-2}|_{\infty}]+\mathbb{E}[|\gamma|_{\infty}])\end{split}$

where we denoted by

$\alpha_{t}=|A_{t}-A_{t-1}|_{\infty}+|\mathcal{E}_{t}-\mathcal{E}_{t-1}|_{\infty}.$

Notice that in the time independent case, the terms $\alpha_{t}$ is 0, which
implies that $X_{t}$ converges in distribution.

In the general case we need to use the extra conditions from (7.4). From the
above considerations we actually show first that the expectation of $X_{t}$
obeys the equation (keep in mind that $\sup_{t\geq
1}|\mathcal{E}_{t}|_{\infty}\leq A+1$)

$\mathbb{E}[|X_{t}|_{\infty}]\leq\rho_{t}\mathbb{E}[|X_{t-1}|_{\infty}]+(A+1)\mathbb{E}[|\gamma|_{\infty}].$

Using this and the standard iterations combined with (7.2) we get that

$\sup_{t}\mathbb{E}[|X_{t}|_{\infty}]<C<\infty.$

On the other hand from (7.19) we get that

(7.20) $D(X_{t},X_{t-1})\leq\rho_{t}D(X_{t-1},X_{t-2})+C\alpha_{t}.$

Using this and a simple iteration it leads to

$D(X_{t},X_{t-1})\leq\rho_{t}\rho_{t-1}\dots\rho_{2}D(X_{1},X_{0})+C(\alpha_{t}+\alpha_{t-1}\rho_{t}+\alpha_{t-1}\rho_{t}\rho_{t-1}+\dots+\alpha_{1}\rho_{t}\rho_{t-1}\dots\rho_{1}).$

In particular, summing this over $t$ from $t$ to $t+s$, leads to

$D(X_{t},X_{t+s})\leq\sum_{i=1}^{s}\rho_{t+i-1}\dots\rho_{2}D(X_{1},X_{0})+C\sum_{k=1}^{t+s}\alpha_{k}\sum_{i=1}^{s}\rho_{t+i}\rho_{t+i-1}\dots\rho_{k}.$

According to (7.15) we conclude that the sum
$\sum_{i=1}^{s}\rho_{t+i-1}\dots\rho_{2}$ converges to $0$ as $s,t\to\infty$.
We will show that the other sum also converges to $0$ as both $t,s\to\infty$.
To this end notice that from (7.4), we can set

$\beta_{t}=\sum_{i\geq t}\alpha_{i}$

and write $\alpha_{t}=\beta_{t}-\beta_{t+1}$. After rearrangements, this leads
to

$\sum_{k=1}^{t+s}\alpha_{k}\sum_{i=1}^{s}\rho_{t+i}\rho_{t+i-1}\dots\rho_{k}=\beta_{1}\rho_{t+s}\rho_{t+s-1}\dots\rho_{1}+\beta_{2}\rho_{t+s}\rho_{t+s-1}\dots\rho_{1}+\dots+\beta_{t+s}.$

The first term converges to 0 because of (7.14) and the rest, converges to $0$
because of the above Lemma thanks to the fact that $\beta_{t}$ converges to
$0$, this converges to $0$.

This proves the convergence in distribution.

  5. (5)

Next we show that the condition (7.4) is also a necessary condition. Indeed,
if we take the one dimensional case with

$X_{t}=X_{t-1}+\epsilon_{t}(\gamma_{t}-X_{t-1})$

such that

$|\epsilon_{t}-\epsilon_{t-1}|=1/(10t)\text{ for }t\geq 1$

In fact we will choose

$\epsilon_{t}=1/2+c\sum_{k=1}^{t}w_{i}/i$

and we will choose $w_{i}=\pm 1$ in the following fashion. First we take all
$w_{1},w_{2},\dots,w_{\tau_{1}}$ such that $\epsilon_{\tau_{1}}\leq 3/4$ but
$3/4<\epsilon_{\tau_{1}}+c/(\tau_{1}+1)$. Notice that we can do this because
the harmonic series is divergent. Now, we choose $\tau_{2}>\tau_{1}$ such that
$w_{\tau_{1}+1}=w_{\tau_{1}+2}=\dots=w_{\tau_{2}}=-1$ and
$\epsilon_{\tau_{2}}-1/(10(\tau_{2}+1))<1/4\leq\epsilon_{\tau_{2}}$. Now we
choose $\tau_{3}>\tau_{2}$ and $w_{t_{2}+1}=\dots=w_{t_{3}}=1$ such that
$\epsilon_{\tau_{3}}\leq 3/4<\epsilon_{\tau_{3}}+c/(\tau_{3}+1)$. Then we
choose $\tau_{4}>\tau_{3}$ such that
$w_{\tau_{3}+1}=w_{\tau_{3}+2}=\dots=w_{\tau_{4}}=-1$ such that
$\epsilon_{\tau_{4}}-1/(10(\tau_{4}+1))<1/4\leq\epsilon_{\tau_{4}}$. And we
continue inductively. Thus we have defined a sequence $\epsilon_{t}$ such that

$1/4\leq\epsilon_{t}\leq 3/4\text{ such that
}\overline{\\{\epsilon_{t}\\}_{t\geq 1}}=[1/4,3/4].$

In other words the limit points of the sequence $\epsilon_{t}$ is just the
interval $[1/4,3/4]$ and obviously the condition (7.2) is fulfilled.

With this choice of the sequence $\epsilon_{t}$, we claim that the sequence
$X_{t}$ does not converge in distribution. Indeed the argument is based on the
simple observation that if it were, then taking the characteristic functions
$\phi_{X_{t}}$ we would get

$\phi_{X_{t}}(\xi)=\phi_{X_{t-1}}((1-\epsilon_{t})\xi)\phi_{\gamma}(\epsilon_{t}\xi).$

As a recall, $\phi_{X}(\xi)=\mathbb{E}[e^{i\xi X}]$ for any
$\xi\in\mathbb{R}$. In particular this means that if $X_{t}$ converges to some
random variable $Y$, then taking a subsequence $t_{n}$ for which
$\epsilon_{t_{n}}\xrightarrow[n\to\infty]{}x$ we obtain that

(7.21) $\phi_{Y}(\xi)=\phi_{Y}((1-x)\xi)\phi_{\gamma}(x\xi)\text{ for any
}x\in[1/4,3/4].$

Under the assumption that $\gamma$ is integrable we claim that $\gamma$ must
be constant and also $X$ is going to be the same constant. To carry this out
we argue that for $x=1/4$ and $x=3/4$ we get that

$\frac{\phi_{\gamma}(3\xi/4)}{\phi_{\gamma}(\xi/4)}=\frac{\phi_{Y}(3\xi/4)}{\phi_{Y}(\xi/4)}.$

Replacing $\xi$ by $4\xi/3$ we arrive at

$\frac{\phi_{\gamma}(\xi)}{\phi_{\gamma}(\xi/3)}=\frac{\phi_{Y}(\xi)}{\phi_{Y}(\xi/3)}.$

Replacing here $\xi$ by $\xi/3$, $\xi/3^{2}$, …, $\xi/3^{n}$ and multiplying
these we get that

$\frac{\phi_{\gamma}(\xi)}{\phi_{\gamma}(\xi/3^{n})}=\frac{\phi_{Y}(\xi)}{\phi_{Y}(\xi/3^{n})}.$

Now letting $n\to\infty$ and using the fact that for any random variable $Z$,
$\phi_{Z}(\xi/3^{n})\xrightarrow[n\to\infty]{}1$ we obtain that

$\phi_{\gamma}(\xi)=\phi_{Y}(\xi),$

in other words, $Y$ has the same distribution as $\gamma$. Using this in
(7.21) with $x=1/2$ we arrive at

$\phi_{Y}(\xi)=\phi_{Y}(\xi/2)^{2}.$

Iterating this we get

$\phi_{Y}(\xi)=\phi_{Y}(\xi/2^{n})^{2^{n}}$

which can be written alternatively as

(7.22) $\phi_{Y}(\xi)=\phi_{\frac{Y_{1}+Y_{2}+\dots+Y_{2^{n}}}{2^{n}}}(\xi),$

where $Y_{1},Y_{2},\dots$ are iid with the same distribution as $Y$. Since $Y$
and $\gamma$ have the same distributions and $\gamma$ is integrable, it
follows that $Y$ is also integrable. This in particular implies from the law
of large numbers that $\frac{Y_{1}+Y_{2}+\dots+Y_{2^{n}}}{2^{n}}$ converges
almost surely to $\mathbb{E}[Y]=\mathbb{E}[\gamma]$. Since convergence almost
surely implies convergence in distribution, we get that

(7.23) $\phi_{Y}(\xi)=\phi_{\mathbb{E}[Y]}(\xi),$

in other words, $Y$ must be constant. This implies that $\gamma$ is also
constant which then finishes the argument.

∎

######  Remark 8.

We need to point out that integrability is key for the conclusion of the last
part of Theorem 6. If we drop the integrability condition, then the passage
from (7.22) to (7.23) is not possible. In fact, if we take
$(\gamma_{t})_{t\geq 1}$ to be all iid Cauchy($1$) and $X_{0}=0$, then $X_{t}$
will also follow a Cauchy($1$) random variable for any choice of
$0\leq\epsilon_{t}\leq 1$ with $\epsilon_{1}>0$. Certainly in this case we do
not need any other assumptions on $\epsilon$ or $\rho_{t}$ to get convergence.
We leave as an open problem the optimal conditions under which the model (7.3)
converges as $t\to\infty$.

###  7.1. Simulations for convergence to distribution

Let us illustrate Theorem 6 and result 7.5. Suppose that the noise
$\gamma_{t}$ is a Normal random variable. Numerical simulations show that
$X_{t}$ converges to a Gaussian random variable for each component – figure 2.

Joint plot of contours with marginals

Figure 2. When the noise is Gaussian, then $X_{t}$ converges to a Normal
distribution. This is the picture on the left. The joint plot illustrates the
case for two agents who learn from each other with $A$ and $\mathcal{E}$
fixed. Variable x1 and x2 represent agents 1 and 2. The right hand side
picture represents the convergence results for $\gamma_{t}$ taking only values
$\pm 1$ with equal probability and independently of one another in each
component.

The the asymptotic distribution is Gaussian centered around the true value
$\bar{\sigma}$. The main point is that we do not need to scale $X_{t}$.

Suppose, the iid $(\gamma_{t})s$ are vectors of just $+1$ or $-1$, then
$X_{t}$ converges in distribution. In figure 2, the simulated distribution
looks distinctly non-Gaussian. For other noises non-standard distributions can
occur.

##  8\. Nonlinear learning

While Degroot updating is retained in this section, we develop nonlinear
models of learning. Instead of $\mathcal{E}$, there is a non-linear function.

######  Definition 9.

The learning function $f_{t}:\mathbb{R}^{n}\to\mathbb{R}^{n}$ is continuous on
some compact convex subset $K\subseteq\mathbb{R}^{n}$ and differentiable on
its interior, with $f(0)=0$. Component wise it is

$f_{t}\begin{pmatrix}x_{1}\\\ \vdots\\\
x_{n}\end{pmatrix}=\begin{pmatrix}f_{t}(x_{1})\\\ \vdots\\\
f_{t}(x_{n})\end{pmatrix}.$

Notice that the update or feedback is now varying with time. Learning or feed
back stops when $\bar{\sigma}-X_{t}=0$, so the condition $f_{t}(0)=0$ ensures
this. The updating rule for agent $i$ becomes

$x^{i}_{t+1}=\sum_{j=1}^{n}(a_{ij})_{t}x^{j}_{t}+f_{t,i}(\bar{\sigma}-x^{i}_{t}).$

Moreover, the weights matrix $A$ is also time varying. Previous sections
showed convergence results of linear updating $f_{t,i}=\epsilon_{i}$, a fixed
scalar. Actual updating of feedback can be be quite complex, and having a
nonlinear feedback or learning rule allows us to expand the linear model.

######  Theorem 10.

For $\forall i\in\\{1,\cdots,n\\}\mbox{ and }\forall t\geq 0$, suppose the
learning function satisfies

(8.1) $0<\inf f_{t,i}^{\prime}\leq\sup f_{t,i}^{\prime}<2(a_{ii})_{t},$

and if we denote

$\rho_{t}=\sup_{i}\sup_{\xi}\left(|(a_{ii})_{t}-f_{t,i}^{\prime}(\xi)|+1-(a_{ii})_{t}\right)$

we assume that

(8.2) $\sup_{t\geq
1}(\rho_{t}+\rho_{t}\rho_{t-1}+\dots+\rho_{t}\rho_{t-1}\rho_{t-2}\dots\rho_{1})<\infty.$

  1. (1)

With the dynamics

$X_{t}=A_{t}X_{t-1}+f_{t}(\bar{\sigma}-X_{t-1}),$

consensus is reached and $\lim_{t\to\infty}X_{t}=\bar{\sigma}$.

  2. (2)

If the evolution is given by

$X_{t}=A_{t}X_{t-1}+f_{t}(\bar{\sigma}+\gamma_{t}-X_{t-1})$

under the same assumption as in (8.1), then
$\gamma_{t}\xrightarrow[t\to\infty]{}0$ yields that
$X_{t}\xrightarrow[t\to\infty]{}\bar{\sigma}$. (If the noise converges to zero
$a.s$, in probability or in ${L^{1}}$, then $X_{t}$ converges accordingly).

  3. (3)

Again assume (8.2) and

(8.3) $X_{t}=A_{t}X_{t-1}+f_{t}(\gamma_{t}-X_{t-1})$

where the sequence $(\gamma_{t})_{t\geq 1}$ is assumed to be iid and
integrable. If in addition we have that

(8.4) $\sum_{t\geq
1}\left(|A_{t}-A_{t-1}|_{\infty}+\max_{i}\sup_{\xi\in\mathbb{R}}|f_{t,i}^{\prime}(\xi)-f_{t-1,i}^{\prime}(\xi)|\right)<\infty,$

then $X_{t}$ converges in distribution as $t\to\infty$.

Notice that the last part of the result above does not involve the
$\bar{\sigma}$ because it is actually hidden in the sequence $\gamma$. As
opposed to the other two cases, the convergence is only in distribution and in
principle that is implicitly defined, it is not a constant variable as in the
previous cases.

###### Proof.

  1. (1)

First we subtract $\bar{\sigma}$ from both sides of the dynamics equation. As
$A$ is stochastic, $A(t)\bar{\sigma}=\bar{\sigma}$, hence

$(X_{t+1}-\bar{\sigma})=A(t)(X_{t}-\bar{\sigma})+f_{t}(\bar{\sigma}-X_{t-1}).$

Second, we recast the equation using the infinity-norm

$|X_{t+1}-\bar{\sigma}|_{\infty}=\sup_{i}|(X_{t+1}-\bar{\sigma})_{i}|.$

For individual $i$, the updating rule becomes

$\displaystyle(X_{t+1}-\bar{\sigma})_{i}$
$\displaystyle=\sum_{j=1}^{n}(a_{ij})_{t}(X_{t-1}-\bar{\sigma})_{j}+f_{t}(\bar{\sigma}-(X_{t-1})_{i})$
$\displaystyle=\left((a_{ii})_{t}-\dfrac{f_{t,i}(\bar{\sigma}-(X_{t-1})_{i})}{(\bar{\sigma}-(X_{t-1})_{i})}\right)(X_{t-1}-\bar{\sigma})_{i}+\sum_{j\neq
i}^{n}(a_{ij})_{t}(X_{t-1}-\bar{\sigma})_{j}$
$\displaystyle\leq\left(|(a_{ii})_{t}-f_{t,i}^{\prime}(\xi_{i})||X_{t-1}-\bar{\sigma}|_{i}\right)+\sum_{j\neq
i}^{n}(a_{ij})_{t}|X_{t-1}-\bar{\sigma}|_{j}$
$\displaystyle\leq\left(|(a_{ii})_{t}-f_{t,i}^{\prime}(\xi_{i})|+1-(a_{ii})_{t}\right)|X_{t-1}-\bar{\sigma}|_{\infty}$
$\displaystyle\leq\sup_{i}\sup_{\xi}\left(|(a_{ii})_{t}-f_{t,i}^{\prime}(\xi_{i})|+1-(a_{ii})_{t}\right)|X_{t-1}-\bar{\sigma}|_{\infty}$

The second equality follows because the learning function is continuous and
differentiable hence

$f_{t,i}(x)-f_{t,i}(0)=(x-0)f_{t,i}^{\prime}(\xi)\implies\dfrac{f_{t,i}(x)}{x}=f_{t,i}^{\prime}(\xi).$

for some $\xi_{i}\in(0,x)$ by the Mean value theorem.

By assumption

$0<\inf f_{t,i}^{\prime}\leq\sup f_{t,i}^{\prime}<2(a_{ii})_{t}$

but this is equivalent there being some $0<\delta_{i}<1$ such that
$\forall\xi\in\mathbb{R}$

(8.5) $\delta_{i}<f_{t,i}^{\prime}(\xi)<2(a_{ii})_{t}-\delta_{i}.$

The above condition gives us two cases to consider. In the first case,
ignoring dependence on t, for all $i\in\\{1,\cdots,n\\}$ and $\xi$

$a_{ii}>f_{i}^{\prime}(\xi)\,\text{ (case 1) in which case,
}|a_{ii}-f_{i}^{\prime}(\xi)|+1-(a_{ii})=1-f_{t,i}^{\prime}(\xi)<1-\delta_{i}$

In the second case,

$a_{ii}\leq f_{i}^{\prime}(\xi)\,\text{ (case 1) in which case,
}|a_{ii}-f_{i}^{\prime}(\xi)|+1-(a_{ii})=1+f_{t,i}^{\prime}(\xi)-2a_{ii}<1-\delta_{i}.$

Thus we obtain that

$\sup_{i}\sup_{\xi}\left(|(a_{ii})_{t}-f_{t,i}^{\prime}(\xi_{i})|+1-(a_{ii})_{t}\right)<1-\min_{i}\delta_{i}<1$

thus we have a contraction in $|X_{t}-\bar{\sigma}|_{\infty}$ and
consequently,

$\lim_{t\to\infty}X_{t}=\bar{\sigma}.$

  2. (2)

The deviation equation from consensus is

$(X_{t+1}-\bar{\sigma})=A(t)(X_{t}-\bar{\sigma})+f_{t}(\bar{\sigma}+\gamma_{t}-X_{t-1}).$

Essentially the same steps follow as the in the proof with no noise

$\displaystyle(X_{t+1}-\bar{\sigma})_{i}$
$\displaystyle=\sum_{j=1}^{n}(a_{ij})_{t}(X_{t-1}-\bar{\sigma})_{j}+f_{t,i}(\bar{\sigma}+\gamma_{t}-(X_{t-1})_{i})$
$\displaystyle=\left((a_{ii})_{t}-\dfrac{f_{t,i}(\bar{\sigma}+\gamma_{t}-(X_{t-1})_{i})}{(\bar{\sigma}+\gamma_{t}-(X_{t-1})_{i})}\right)(X_{t-1}-\bar{\sigma}-\gamma_{t})_{i}+\sum_{j\neq
i}^{n}(a_{ij})_{t}(X_{t-1}-\bar{\sigma})_{j}$
$\displaystyle=\left((a_{ii})_{t}-f_{t,i}^{\prime}(\xi)\right)(X_{t-1}-\bar{\sigma})_{i}+\sum_{j\neq
i}^{n}(a_{ij})_{t}(X_{t-1}-\bar{\sigma})_{j}+\gamma_{t}f_{t,i}^{\prime}(\xi)$
$\displaystyle=\left((a_{ii})_{t}-f_{t,i}^{\prime}(\xi)\right)(X_{t-1}-\bar{\sigma})_{i}+(1-(a_{ii})_{t})(X_{t-1}-\bar{\sigma})_{j}+\gamma_{t}f_{t,i}^{\prime}(\xi)$
$\displaystyle\leq\left(|(a_{ii})_{t}-f_{t,i}^{\prime}(\xi_{i})||X_{t-1}-\bar{\sigma}|_{i}\right)+(1-(a_{ii})_{t})|X_{t-1}-\bar{\sigma}|_{j}+|\gamma_{t}|f_{t,i}^{\prime}(\xi)$
$\displaystyle\leq\left(|(a_{ii})_{t}-f_{t,i}^{\prime}(\xi_{i})|+1-(a_{ii})_{t}\right)|X_{t-1}-\bar{\sigma}|_{\infty}+|\gamma_{t}|f_{t,i}^{\prime}(\xi)$
$\displaystyle\leq\sup_{i}\sup_{\xi}\left(|(a_{ii})_{t}-f_{t,i}^{\prime}(\xi_{i})|+1-(a_{ii})_{t}\right)|X_{t-1}-\bar{\sigma}|_{\infty}+C|\gamma_{t}|$

The rest of the proof follows as in the proof of Theorem 6, more precisely,
following the same argument starting with (7.7). In all instances the
convergence follows the same arguments as in the linear case.

  3. (3)

First observe that from (8.3) we get

$\mathbb{E}[|X_{t}|_{\infty}]\leq\rho_{t}\mathbb{E}[|X_{t-1}|_{\infty}]+2\mathbb{E}[\gamma].$

From this, iterating and using (8.2) as in the linear case we obtain that

$\sup_{t\geq 1}\mathbb{E}[|X_{t}|_{\infty}]=C<\infty.$

To treat the case where $\gamma_{t}$ are all iid, we follow the same argument
as the linear case. Here we have to use in the first place the distance
defined in (7.18) and the argument for the estimate of $D(X_{t},X_{t-1})$ we
need to take a for any coupling $\tilde{X}_{t-1}$ and $\tilde{X}_{t-2}$ the
coupling $A_{t}\tilde{X}_{t-1}+f_{t}(\gamma-\tilde{X}_{t-1})$ and
$A_{t-1}\tilde{X}_{t-2}+f_{t-1}(\gamma-\tilde{X}_{t-2})$. Then,

$\begin{split}D(X_{t},X_{t-1})&\leq\mathbb{E}[|A_{t}\tilde{X}_{t-1}+f_{t}(\gamma-\tilde{X}_{t-1})-A_{t-1}\tilde{X}_{t-2}+f_{t-1}(\gamma-\tilde{X}_{t-2})|_{\infty}]\\\
&\leq\mathbb{E}[|A_{t}\tilde{X}_{t-1}+f_{t}(\gamma-\tilde{X}_{t-1})-(A_{t}\tilde{X}_{t-2}+f_{t}(\gamma-\tilde{X}_{t-2})|_{\infty}]\\\
&\quad+\mathbb{E}[|A_{t}\tilde{X}_{t-2}+f_{t}(\gamma-\tilde{X}_{t-2})-(A_{t-1}\tilde{X}_{t-2}+f_{t-1}(\gamma-\tilde{X}_{t-2}))|_{\infty}]\\\
&\leq\rho_{t}\mathbb{E}[|\tilde{X}_{t-1}-\tilde{X}_{t-2}|_{\infty}+\left(|A_{t}-A_{t-1}|_{\infty}+\max_{i}\sup_{\xi\in\mathbb{R}}|f_{t,i}^{\prime}(\xi)-f_{t-1,i}^{\prime}(\xi)|\right)\mathbb{E}[|X_{t-2}|_{\infty}]\\\
&\leq\rho_{t}D(X_{t-1},X_{t-2})+C\left(|A_{t}-A_{t-1}|_{\infty}+\max_{i}\sup_{\xi\in\mathbb{R}}|f_{t,i}^{\prime}(\xi)-f_{t-1,i}^{\prime}(\xi)|\right).\end{split}$

From this we proceed exactly in the same way as in the proof of the linear
case, more precisely, the same proof following (7.20) to show that $X_{t}$ is
Cauchy in the metric $D$.

∎

######  Remark 11.

Matrix $A(t)$ and learning function $f_{t}$ are allowed to be time dependent
or slowly varying. They could be random but in a controlled way. Were $A$ and
$f$ to be fixed in time, the above result would still hold. So the constant
case is a special case of what we have shown.

Continuity of the learning function $f_{t}$ is essential. We give an example
of a situation where it breaks down.

######  Example 12.

Consider the sign function

$\operatorname{sign}(x)=\begin{cases}-1&\text{ if }x<0\\\ 0&\text{ if }x=0\\\
1&\text{ if }x>0.\\\ \end{cases}$

If the learning $f$ were the signum function, then the dynamics would be

$X_{t}=A(t)X_{t-1}+\mathcal{E}\operatorname{sign}(\bar{\sigma}-X_{t-1}).$

Consensus in this case would not be achieved. One can plainly see this in the
one dimensional case of $A_{t}=1$, $\sigma=1$, $Y_{t}=X_{t}-\sigma$, $Y_{0}=1$
and take $1/3<\mathcal{E}<1/2$. With this setup we get

$Y_{1}=1-\mathcal{E},Y_{2}=1-2\mathcal{E},Y_{3}=1-3\mathcal{E},Y_{4}=1-2\mathcal{E},Y_{5}=1-3\mathcal{E},\dots$

which shows that $Y_{t}$ becomes periodic, thus not convergent. We can extend
this behaviour to more general situations of course, though this periodic
pattern still follows.

##  9\. Average dynamics

The previous model with learning assumes $\bar{\sigma}$ is already known. In
the case where the true $\sigma$ is not a priori assumed to exist, one of the
possibilities is to replace $\sigma$ by some average of all the players and
the model becomes

(9.1) $X_{t}=A_{t}X_{t-1}+\mathcal{E}_{t}(\overline{X}_{t-1}-X_{t-1}).$

where $\overline{X}_{t-1}$ is the average of the sigmas of all the players. On
a pure information level, this seems more satisfactory. There is no outside
knowledge, all information is entirely contained within the interactions. For
a large number of players, this makes perfect sense.

However, in this case the main issue is to show that the model converges. To
do this we interpret $\overline{U}$ for any vector $U$ as

$\overline{U}=\begin{pmatrix}\frac{U_{1}+\cdots+U_{n}}{n}\\\ \vdots\\\
\frac{U_{1}+\cdots+U_{n}}{n}\\\
\end{pmatrix}=\underbrace{\begin{bmatrix}\frac{1}{n}+\cdots+\frac{1}{n}\\\
\vdots\\\
\frac{1}{n}+\cdots+\frac{1}{n}\end{bmatrix}}_{\Delta}\begin{bmatrix}U_{1}\\\
\vdots\\\ U_{n}\end{bmatrix}.$

The system becomes now

(9.2) $\displaystyle
X_{t}=(A_{t}+\mathcal{E}_{t}\Delta-\mathcal{E}_{t})X_{t-1}.$

We want to show that $X_{t}$ converges to a vector which is a multiple of

$\mathbbm{1}=\left[\begin{array}[]{rrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrr}1\\\
\vdots\\\ 1\\\ \end{array}\right].$

###  9.1. Fixed $A$ and $\mathcal{E}$

In this section we give an algebraic approach of the case of $A$ and
$\mathcal{E}$ constant in time.

######  Theorem 13.

If $A$ is an $n\times n$ stochastic matrix and $\mathcal{E}$ is such that
$0<\epsilon_{i}<\dfrac{n}{n-1}a_{ii}$ for any $i$ and

$X_{t}=(A+\mathcal{E}\Delta-\mathcal{E})X_{t-1}$

then
$X_{t}\xrightarrow[t\to\infty]{}\lambda\mathbbm{1}=\lambda\begin{bmatrix}1\\\
\vdots\\\ 1\end{bmatrix}$. Convergence is also exponentially fast.

###### Proof.

Note that $\Delta X_{t-1}=\overline{X}_{t-1}$. Since

$\mathcal{E}\Delta-\mathcal{E}=\begin{bmatrix}-\frac{\epsilon_{1}(n-1)}{n}\quad\frac{\epsilon_{1}}{n}\cdots\quad\frac{\epsilon_{1}}{n}\\\
\frac{\epsilon_{2}}{n}\quad-\frac{\epsilon_{2}(n-1)}{n}\cdots\quad\frac{\epsilon_{2}}{n}\\\
\ddots\quad\ddots\end{bmatrix},$

it means that

$A+\mathcal{E}\Delta-\mathcal{E}=\begin{bmatrix}a_{11}-\frac{\epsilon_{1}(n-1)}{n}\quad\frac{\epsilon_{1}}{n}+a_{12}\cdots\quad\frac{\epsilon_{1}}{n}+a_{1n}\\\
a_{21}+\frac{\epsilon_{2}}{n}\quad
a_{22}-\frac{\epsilon_{2}(n-1)}{n}\cdots\quad\frac{\epsilon_{2}}{n}+a_{2n}\\\
\vdots\quad\vdots\end{bmatrix}.$

For the time homogenous case, we require $B=A+\mathcal{E}\Delta-\mathcal{E}$
to be a stochastic matrix. It suffices to enforce the condition

$0<\epsilon_{i}<\dfrac{n}{n-1}a_{ii}.$

In this case, $B$ is a stochastic matrix and we are requiring $b_{ii}>0$ or
positive self belief. The system now becomes

$X_{t}=BX_{t-1}.$

To show that $X_{t}$ converges, we can put $B$ in Jordan form $B=J^{-1}DJ$,
where $D$ is a block Jordan matrix. If we let $Y_{t}=JX_{t}$, we obtain the
equivalent system

$Y_{t}=DY_{t-1}.$

From the Perron-Frobenius theorem (notice here that indeed $B$ has positive
entries since $\epsilon_{i}>0$) we know that 1 is a single eigenvalue and all
other eigenvalues are in absolute value less than 1. Thus

(9.3) $D=\begin{bmatrix}1&0\\\ 0&J_{i}&0\\\ 0&\ddots&J_{n}\\\ \end{bmatrix}$

Where $J_{i}$ corresponds to Jordan block

$\begin{bmatrix}\lambda_{i}&1&0&&\\\ &\lambda_{i}&1&0&\\\ &&\ddots&\ddots&\\\
&&&&1\\\ &&&&\lambda_{i}\end{bmatrix}.$

In fact, from the above representation, $(Y_{t})_{1}=(Y_{t-1})_{1}$, which
means that the first entry of $Y_{t}$ does not change. The rest of the
analysis reduces to systems of the form

$Y_{t}=\begin{bmatrix}\lambda&1&0&&\\\ &\lambda&1&0&\\\ &&\ddots&\ddots&\\\
&&&&\lambda\end{bmatrix}Y_{t-1}$

with $|\lambda|<1$. For such a situation we use the concrete expression of

$Y_{t}=\begin{bmatrix}\lambda&1&&&\\\ &\lambda&1&&\\\ &&\ddots&\ddots&\\\
&&&&\lambda\end{bmatrix}^{t}Y_{0}.$

Now as $|\lambda|<1$, we can show that with

$U=\begin{bmatrix}0&1&0&\\\ &0&\ddots&&1\\\ &&&&0\\\ \end{bmatrix}$

(this is the matrix with 1’s in the super-diagonal) that we have

$\begin{bmatrix}\lambda&1&\\\ &&\ddots&1\\\ &&&\lambda\\\
\end{bmatrix}^{t}=(\lambda\mathbb{I}+U)^{t}=\sum_{k=0}^{t}\binom{n}{k}(\lambda\mathbb{I})^{t-k}U^{k}.$

On the other hand, it is not difficult to see that $U^{n}=0$, thus in the
above sum we have to collect only the terms $k<n$, in other words

$\begin{bmatrix}\lambda&1&\\\ &&\ddots&1\\\ &&&\lambda\\\
\end{bmatrix}^{t}=(\lambda\mathbb{I}+U)^{t}=\sum_{k=0}^{n}\binom{n}{k}(\lambda\mathbb{I})^{t-k}U^{k}\xrightarrow[t\to\infty]{}0$

because $|\lambda|<1$. The conclusion is that for
$0<\epsilon_{i}<\frac{n}{n-1}a_{ii}$ we have that $X_{t}$ converges to a
vector $v$. From the equation $X_{t}=BX_{t-1}$ we get that $v=Bv$, which from
Perron-Frobenius shows that $v=\lambda\begin{bmatrix}1\\\ 1\\\ \vdots\\\
1\end{bmatrix}.$ ∎

###  9.2. Time varying $A(t)$ and $\mathcal{E}(t)$

Time varying here allows for some randomness in that the entries can change
over time but not drastically enough to alter the structure of the matrix. In
the later sections, we will consider matrices which are allowed to be truly
random with less restrictions on entries. In the previous section $A$ and
$\mathcal{E}$ were constant. We now look at the behaviour of time varying
stochastic matrices and learning rates. We have the general model still given
by (9.1), which reduces to

$X_{t}=(A_{t}+\mathcal{E}_{t}\Delta-\mathcal{E}_{t})X_{t-1}$

or, if we set

(9.4) $B_{t}=A_{t}+\mathcal{E}_{t}\Delta-\mathcal{E}_{t},$

the above system becomes $X_{t}=B(t)X_{t-1}$.

We will just refer to this system as $X_{t}=B_{t}X_{t-1}$ for notation
purposes. For the general case of time varying matrices, we need a different
idea since the Jordan form of $B_{t}$ produces a matrix $J_{t}$ which depends
on $t$. The argument used above fails because for each $t$ a different
corresponding $J_{t}$ exists.

Another way is to look at how much the components of $X_{t}$ differ from each
other. A quantifier for this is the oscillation we introduce now.

######  Definition 14.

Define for a vector $X$,

$\operatorname{osc}(X)=\max_{i,j}|X_{i}-X_{j}|$

and for an $n\times n$ matrix $A$, the Dobrushin coefficient by

$\delta(A)=\frac{1}{2}\max_{i,j=1}\sum_{k=1}^{n}|a_{ik}-a_{jk}|.$

We provide here a Lemma which is classical but we provide also the proof for
reader’s convenience.

######  Lemma 15.

If $A$ is a matrix whose row sums are all equal and $X=AY$, then

(9.5) $\operatorname{osc}(X)\leq\delta(A)\operatorname{osc}(Y)$

In particular, if $A$ is a stochastic matrix, then

$\operatorname{osc}(X)\leq\operatorname{osc}(Y).$

###### Proof.

We can write $Y_{i}=(Y_{\min}+Y_{\max})/2+Z_{i}$ with
$Z_{i}\in[-\operatorname{osc}(Y)/2,\operatorname{osc}(Y)/2]$. Thus, because
the sums on rows does not change, we actually have

$X_{i}-X_{j}=\sum_{k=1}^{n}(a_{ik}-a_{jk})Z_{k}.$

Taking the absolute values and using the fact that
$|Z_{k}|\leq\operatorname{osc}(Y)/2$, gives the result.

∎

Before we state the next result, we define

$\mathbbm{1}=\left[\begin{array}[]{ccccccccccccccccccccccccccccccccc}1\\\ 1\\\
\vdots\\\ 1\\\
\end{array}\right],\,\Delta=\frac{1}{n^{2}}\mathbb{I}\,\mathbb{I}^{\top}=\frac{1}{n}\mathbb{I}\text{
where
}\mathbb{I}=\left[\begin{array}[]{rrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrr}1&1&\dots&1\\\
1&1&\dots&1\\\ {4}\\\ 1&1&\dots&1\\\ \end{array}\right]$

######  Theorem 16.

Assume we have the model with deterministic stochastic matrices $A_{t}$,
$\gamma_{t}$ random variables and

$X_{t}=A_{t}X_{t-1}+\mathcal{E}_{t}(\overline{X}_{t-1}-X_{t-1}+\gamma_{t}),$

with

(9.6) $0\leq(\epsilon_{i})_{t}\leq\frac{n}{n-1}(a_{ii})_{t}\quad\forall
i=1,\cdots,n,\forall t\geq 1.$

  1. (1)

Let $B_{t}=A_{t}+\mathcal{E}_{t}(\Delta-\mathbb{I})$ and assume that
$\rho_{t}=\delta(B_{t})>0$ for each $t\geq 1$ and

(9.7) $\quad\prod_{s=1}^{t}\rho_{s}\xrightarrow[t\to\infty]{}0,\text{ and
}\gamma_{t}=0,t\geq 0,$

then

(9.8) $\prod_{s=1}^{t}B_{s}\xrightarrow[t\to\infty]{}C$

where for some $\nu_{1},\nu_{2},\dots,\nu_{n}\geq 0$ with
$\sum_{s=1}^{t}\nu_{s}=1$,

(9.9)
$C=\left[\begin{array}[]{rrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrr}\nu_{1}&\nu_{2}&\dots&\nu_{n}\\\
\nu_{1}&\nu_{2}&\dots&\nu_{n}\\\ {4}\\\ \nu_{1}&\nu_{2}&\dots&\nu_{n}\\\
\end{array}\right].$

If $\gamma_{t}=0$ for all $t\geq 1$, then, for some $\lambda>0$

(9.10) $X_{t}\xrightarrow[t\to\infty]{a.s.}\lambda\mathbbm{1}$

  2. (2)

Assume now that we have

(9.11) $\sup_{t\geq
1}\\{\rho_{t}+\rho_{t}\rho_{t-1}+\rho_{t}\rho_{t-1}\rho_{t-2}+\dots+\rho_{t}\rho_{t-1}\dots\rho_{1}\\}<\infty.$

    1. (a)

If $\sum_{t\geq 1}|\gamma_{t}|_{\infty}<\infty$ almost surely, then
$X_{t}\xrightarrow[t\to\infty]{a.s.}\lambda\mathbbm{1}$ for some random
variable $\lambda\geq 0$.

    2. (b)

If $\sum_{t\geq 1}|\gamma_{t}|_{\infty}$ converges in $L^{p}$, then
$X_{t}\xrightarrow[t\to\infty]{L^{p}}\lambda\mathbbm{1}$ for some random
variable $\lambda\in L^{p}$.

  3. (3)

Assume that (9.11) holds true and that

(9.12) $\mathcal{E}_{t}\xrightarrow[t\to\infty]{}\mathcal{E}$

and that $(\gamma_{t})_{t\geq 1}$ is a sequence of iid random variables with
mean $\mu\in\mathbb{R}^{n}$ and covariance matrix $\Sigma$.

Then,

(9.13) $\frac{X_{t}-\mathbb{E}[X_{t}]}{\sqrt{t}}\Longrightarrow
N(0,C^{\top}\mathcal{E}^{\top}\Sigma\mathcal{E}C)$

in distribution sense.

######  Remark 17.

  1. (1)

Notice here that because of our assumption (9.6) we get that

$0<\rho_{t}=\delta(A_{t}+\mathcal{E}_{t}(\Delta-\mathbb{I}))<1$

and in particular we get another proof of the time independent model as well.

  2. (2)

For any matrix $B$ with sums of rows equal to $1$, which is the case of
$B=A_{t}+\mathcal{E}_{t}(\Delta-\mathbb{I})$, using the fact that $a\wedge
b=\frac{a+b-|a-b|}{2}$, we have another expression for

$\delta(B)=1-\min_{i,j}\sum_{k=1}^{n}b_{ik}\wedge b_{jk}.$

For instance, if we define

$\omega(B)=\max_{i,j}(1-b_{ij})$

and if $B$ is a stochastic matrix with all positive entries, then

$\delta(B)\leq 1-\omega(B)<1.$

This is our situation generated by the condition (9.6).

  3. (3)

The convergence in probability of the series $\sum_{t\geq
1}|\gamma_{t}|_{\infty}$ is the same as almost sure convergence, and this is
the reason why this is left out.

  4. (4)

As opposed to the case of Theorem 6, this time, to guarantee consensus in the
long run for $X_{t}$, we need the hypothesis of convergence of $\sum_{t\geq
1}|\gamma_{t}|_{\infty}$. Just convergence of $\gamma_{t}$ to $0$ is not
enough in this case. For instance, if $\gamma_{t}=(1/t)e$, and $X_{1}=0$, with
$A_{t}$ and $\mathcal{E}_{i}=\mathcal{E}_{1}$ for all $i$ independent of time
$t$, then $X_{t}=c(\sum_{i=1}^{t}1/i)e$ which is clearly not convergent.

  5. (5)

Contrary to the case of Theorem 6, if we take $\gamma_{t}$ to be iid, we do
not get converge in distribution of $X_{t}$ itself. For instance if we assume
that $X_{0}=0$ and $A_{t}$ and $\mathcal{E}_{t}$ are constant such that the
diagonal of $\mathcal{E}$ is also constant, then for $\gamma_{t}=u_{t}e$, we
get that $X_{t}=c(\sum_{i=1}^{t}u_{t})e$. This is not convergent unless
$u_{t}=0$ a.s.. However this is complemented by the last part of the Theorem
which show that properly scaled, this convergences to a multidimensional
normal random variable.

  6. (6)

Notice that the covariance matrix of the normal limit (9.13), is actually rank
one because the matrix $C$ is rank one. Thus the normal random variable is
actually supported on a line.

###### Proof.

We will show in fact first (9.13) and then (9.9) follows by taking initial
vectors to be the coordinate vectors of $\mathbb{R}^{n}$.

We prove the general situation and we take with the notation
$B_{t}=A_{t}+\mathcal{E}_{t}(\Delta-\mathbb{I})$,

$X_{t}=B_{t}X_{t-1}+\tilde{\gamma_{t}}\text{ where
}\tilde{\gamma}_{t}=\mathcal{E}_{t}\gamma_{t}$

from which we get in the first place that

(9.14)
$\operatorname{osc}(X_{t})\leq\delta(B_{t})\operatorname{osc}(X_{t-1})+\operatorname{osc}(\tilde{\gamma}_{t})=\rho_{t}\operatorname{osc}(X_{t-1})+\operatorname{osc}(\tilde{\gamma}_{t})$

and with the same argument from Theorem 6, under (9.7) we obtain that
$\operatorname{osc}(X_{t})$ converges to $0$ under the convergence of
$\sum_{t\geq 1}|\gamma_{t}|_{\infty}$ (in both a.s. case and also in $L^{p}$
sense). On the other hand, since $B_{t}$ is a stochastic matrix, we have also
that

(9.15)
$(X_{t-1})_{\min}+(\tilde{\gamma}_{t})_{\min}\leq(X_{t})_{\min}\leq(X_{t})_{\max}\leq(X_{t-1})_{\max}+(\tilde{\gamma}_{t})_{\max}.$

  1. (1)

From this, if we take $\gamma_{t}=0$, then (9.15) together with (9.14) gives
that $X_{t}$ converges to a multiple of the vector $\mathbbm{1}$. Thus, taking
for $X_{0}$ one of the basis vectors of $\mathbb{R}^{n}$, and using the fact
that

$X_{t}=\prod_{s=1}^{t}B_{s}X_{0}$

we obtain that the matrix $\prod_{s=1}^{t}B_{s}$ converges to a matrix $C$
which has repeated rows.

  2. (2)

We need here the following rewriting of (9.15)

(9.16)
$(X_{t})_{\max}-\sum_{s=1}^{t}(\tilde{\gamma}_{t})_{\max}\leq(X_{t-1})_{\max}-\sum_{s=1}^{t-1}(\tilde{\gamma}_{t})_{\max}\text{
and
}(X_{t-1})_{\min}-\sum_{s=1}^{t-1}(\tilde{\gamma}_{t})_{\min}\leq(X_{t})_{\min}-\sum_{s=1}^{t}(\tilde{\gamma}_{t})_{\min}$

    1. (a)

If $\sum_{t\geq 1}|\gamma_{t}|_{\infty}<\infty$ almost surely, then using
(9.16) and get that $(X_{t})_{\min}-\sum_{s=1}^{t}(\tilde{\gamma}_{t})_{\min}$
is convergent (monotone and bounded). In a similar way we also have that
$(X_{t})_{\max}-\sum_{s=1}^{t}(\tilde{\gamma}_{t})_{\max}$ is convergent.
Therefore, because the oscillation goes to zero we get that $X_{t}$ is almost
surely convergent. Combined with the fact that $\operatorname{osc}(X_{t})$
converges to $0$, this implies the convergence of $X_{t}$ in almost sure
sense.

    2. (b)

If $\sum_{t\geq 1}|\gamma_{t}|_{\infty}$ converges in some $L^{p}$, then it is
also a.s. convergent. Consequently, we have that $\sum_{t\geq
1}|\gamma_{t}|_{\infty}<\infty$ thus we can invoke the previous part to argue
that $X_{t}$ converges a.s. to a random variable $X$.

To show the $L^{p}$ convergence, we first notice that $X_{t}$ is in $L^{p}$
for every $p$ (just from the recurrence relation). Next, using (9.14), we have
that $\operatorname{osc}(X_{t})$ converges to $0$ in $L^{p}$. On the other
hand, for any $s<t$, we have

$X_{t}-X_{s}=(\prod_{i=1}^{t}B_{i}-\prod_{i=1}^{s}B_{i})X_{0}+\sum_{k=s+1}^{t}\prod_{i=1}^{k}B_{i}\tilde{\gamma}_{k}.$

Using this, the convergence of $B_{t}$ to $C$ and some standard estimates we
get that for some constant $K>0$,

$\||X_{t}-X_{s}|_{\infty}\|_{p}\leq\|\prod_{i=1}^{t}B_{i}X_{0}-\prod_{i=1}^{s}B_{i}X_{0}\|_{p}+K\|\sum_{k=s+1}^{t}|\gamma_{k}|\|_{p}$

This shows that the sequence $(X_{t})_{t\geq 0}$ is Cauchy in in $L^{p}$. In
particular this means the sequence is convergent in $L^{p}$ and because it
also converges almost surely it must converge to the same limit.

  3. (3)

To show convergence in distribution we proceed as follows. We first observe
that in the case $\gamma_{t}$ are normally distributed, the random variable
$X_{t}$ is actually normally distributed with mean

$\mu_{t}=\prod_{k=1}^{t}B_{k}X_{0}+\sum_{s=1}^{t}\prod_{k=1}^{s}B_{k}\mathcal{E}_{s}\mu$

and covariance matrix given by

$\Gamma_{t}=\sum_{s=1}^{t}(\prod_{k=1}^{s}B_{k})^{\top}\mathcal{E}^{\top}\Sigma\mathcal{E}(\prod_{k=1}^{s}B_{k}).$

Because $\prod_{k=1}^{t}B_{k}$ converges to $C$ and $\mathcal{E}_{t}$
converges to $\mathcal{E}$, this means that

$\frac{\Gamma_{t}}{t}\xrightarrow[t\to\infty]{}C^{\top}\mathcal{E}^{\top}\Sigma\mathcal{E}C,$

Therefore

$\frac{X_{t}-\mathbb{E}[X_{t}]}{\sqrt{t}}\Longrightarrow
N(0,C^{\top}\mathcal{E}^{\top}\Sigma\mathcal{E}C).$

On the other hand, if $\gamma_{t}$ are not normal, we can take copies of
$Z_{t}$ which are normal and we can put all the variables $\gamma_{t}$ and
$Z_{t}$ on the same probability space. We will compare the sums $X_{t}$ with
$Y_{t}$, which we define by

$Y_{t}=B_{t}Y_{t-1}+\mathcal{E}_{t}Z_{t}.$

with $Y_{0}=X_{0}$. We certainly have in the first place that

$\mathbb{E}[X_{t}]=\mathbb{E}[Y_{t}]=\tilde{B}_{t}X_{0}+\sum_{s=1}^{t}\tilde{B}_{s}\mathcal{E}_{s}\mathbb{E}[\gamma_{s}].$

where in order to simply the notation we set

$\tilde{B}_{t}=\prod_{s=1}^{t}B_{s}.$

From this we can reduce the rest of the proof to the case of $X_{0}=0$ and
$\mathbb{E}[\gamma_{t}]=0$. These do not change the covariance matrices of
$X_{t}$ and $Y_{t}$ which remain the same.

Next we will use the Lindberg argument which involves the comparison of
$X_{t}$ and $Y_{t}$. For a reference of this look at [Str00]. In the first
place realize that

$X_{t}=\sum_{s=1}^{t}\tilde{B}_{s}\mathcal{E}_{s}\gamma_{s}\text{ while
}Y_{t}=\sum_{s=1}^{t}\tilde{B}_{s}\mathcal{E}_{s}Z_{s}.$

Take now a smooth function $\phi:\mathbb{R}^{n}\to\mathbb{R}$ with all bounded
derivatives, and we will compare

(9.17)
$\begin{split}\mathbb{E}\left[\phi\left(\frac{X_{t}}{\sqrt{t}}\right)\right]-\mathbb{E}\left[\phi\left(\frac{Y_{t}}{\sqrt{t}}\right)\right]&=\sum_{s=1}^{t}\left(\mathbb{E}\left[\phi\left(\frac{W_{s}+\tilde{B}_{s}\mathcal{E}_{s}\gamma_{s}}{\sqrt{t}}\right)\right]-\mathbb{E}\left[\phi\left(\frac{W_{s}+\tilde{B}_{s}\mathcal{E}_{s}Z_{s}}{\sqrt{t}}\right)\right]\right)\\\
&=\sum_{s=1}^{t}\left(\mathbb{E}\left[\phi\left(\frac{W_{s}+\tilde{B}_{s}\mathcal{E}_{s}\gamma_{s}}{\sqrt{t}}\right)-\phi\left(\frac{W_{s}+\tilde{B}_{s}\mathcal{E}_{s}Z_{s}}{\sqrt{t}}\right)\right]\right)\end{split}$

with the definition

$W_{s}=\sum_{i=1}^{s-1}\tilde{B}_{i}\mathcal{E}_{i}Z_{i}+\sum_{i=s+1}^{t}\tilde{B}_{i}\mathcal{E}_{i}\gamma_{i}.$

Thus, $W_{k}$ is independent of $\gamma_{k}$ and $Z_{k}$. Now for a smooth
function we can use Taylor’s formula with integral remainder,

$\phi(x+y)=\phi(x)+D\phi(x)(y)+\int_{0}^{1}D^{2}\phi(x+ty)(y,y)tdt$

while using a Taylor’s formula to third order with integral remainder,

$\phi(x+y)=\phi(x)+D\phi(x)(y)+\frac{1}{2}D^{2}\phi(x)(y,y)+\frac{1}{2}\int_{0}^{1}D^{3}\phi(x+ty))(y,y,y)t^{2}dt.$

We can combine both of these to write

$\phi(x+y)-\phi(x)-D\phi(x)(y)-\frac{1}{2}D^{2}\phi(x)(y,y)=R(x,y)$

with

(9.18) $R(x,y)\leq\begin{cases}\|D^{2}\phi\|_{\infty}|y|^{2}\\\
\frac{1}{6}\|D^{3}\phi\|_{\infty}|y|^{3}\end{cases}$

Going now back to the decomposition (9.17), using the independence of $W_{s}$
from both $\gamma_{s}$ and also $Z_{s}$ and the fact that $\gamma_{s}$ and
$Z_{s}$ have the same mean and covariance, we can write

$\left|\mathbb{E}\left[\phi\left(\frac{W_{s}+\tilde{B}_{s}\mathcal{E}_{s}\gamma_{s}}{\sqrt{t}}\right)-\phi\left(\frac{W_{s}+\tilde{B}_{s}\mathcal{E}_{s}Z_{s}}{\sqrt{t}}\right)\right]\right|\leq\mathbb{E}\left[\left|R\left(\frac{W_{s}}{\sqrt{t}},\frac{\tilde{B}_{s}\mathcal{E}_{s}\gamma_{s}}{\sqrt{t}}\right)\right|+\left|R\left(\frac{W_{s}}{\sqrt{t}},\frac{\tilde{B}_{s}\mathcal{E}_{s}Z_{s}}{\sqrt{t}}\right)\right|\right].$

Now, for a given $\epsilon>0$, we write

$\begin{split}\mathbb{E}\left[\left|R\left(\frac{W_{s}}{\sqrt{t}},\frac{\tilde{B}_{s}\mathcal{E}_{s}\gamma_{s}}{\sqrt{t}}\right)\right|\right]&=\mathbb{E}\left[\left|R\left(\frac{W_{s}}{\sqrt{t}},\frac{\tilde{B}_{s}\mathcal{E}_{s}\gamma_{s}}{\sqrt{t}}\right)\right|,|\gamma_{s}|\leq\epsilon\sqrt{t}\right]+\mathbb{E}\left[\left|R\left(\frac{W_{s}}{\sqrt{t}},\frac{\tilde{B}_{s}\mathcal{E}_{s}\gamma_{s}}{\sqrt{t}}\right)\right|,|\gamma_{s}|>\epsilon\sqrt{t}\right]\\\
&\leq\frac{1}{6t^{3/2}}\|D^{3}\phi\|\mathbb{E}[|B_{s}\mathcal{E}_{s}\gamma_{s}|^{3},|\gamma_{s}|\leq\epsilon\sqrt{t}]+\frac{1}{t}\|D^{2}\phi\|\mathbb{E}[|B_{s}\mathcal{E}_{s}\gamma_{s}|^{2},|\gamma_{s}|>\epsilon\sqrt{t}]\\\
&\leq\frac{\epsilon
K}{6t}\|D^{3}\phi\|\mathbb{E}[|\gamma_{1}|^{2}]+\frac{K}{t}\|D^{2}\phi\|\mathbb{E}[|\gamma_{1}|^{2},|\gamma_{1}|>\epsilon\sqrt{t}].\end{split}$

For the first expectation we used the estimation of $R$ from (9.18) with the
second estimate, while for the second we use the first estimate in (9.18). The
next round of inequalities involves the fact that $\tilde{B}_{s}$ converges,
thus the operator norm is bounded. Similarly $\mathcal{E}_{t}$ is bounded and
$K$ is a common bound for all $|\tilde{B}_{s}\mathcal{E}_{s}|$.

A similar inequality is obtained for the other case, namely with $Z_{s}$
instead of $\gamma$. Thus we get that each term in the summation of (9.17) is
bounded by

$\frac{\epsilon
K}{6t}\|D^{3}\phi\|(\mathbb{E}[|\gamma_{1}|^{2}]+\mathbb{E}[|Z_{1}|^{2}])+\frac{K}{t}\|D^{2}\phi\|(\mathbb{E}[|\gamma_{1}|^{2},|\gamma_{1}|>\epsilon\sqrt{t}]+\mathbb{E}[|Z_{1}|^{2},|Z_{1}|>\epsilon\sqrt{t}])$

This means that we can bound now for every $\epsilon>0$,

$|\mathbb{E}\left[\phi\left(\frac{X_{t}}{\sqrt{t}}\right)\right]-\mathbb{E}\left[\phi\left(\frac{Y_{t}}{\sqrt{t}}\right)\right]|\leq\frac{\epsilon
K}{6}\|D^{3}\phi\|(\mathbb{E}[|\gamma_{1}|^{2}]+\mathbb{E}[|Z_{1}|^{2}])\\\
+K\|D^{2}\phi\|(\mathbb{E}[|\gamma_{1}|^{2},|\gamma_{1}|>\epsilon\sqrt{t}]+\mathbb{E}[|Z_{1}|^{2},|Z_{1}|>\epsilon\sqrt{t}])$

Letting now $t\to\infty$ and then $\epsilon\to 0$, finishes the argument,
showing that we can replace the $\gamma$ by normal random variables with the
same mean and variance for which the CLT is clear.

∎

###  9.3. Simulation result for CLT

In the averaging case, when the noise is Gaussian so is the asymptotic
distribution. However, we illustrate the less obvious CLT result (figure 3),
namely even when the noise terms are iid for any general distribution. Again
the simulations are for two agents with fixed $A$ and $\mathcal{E}$ matrices
and $(\gamma_{t}s)$ is a vector with $+1$ or $-1$. The joint plot are heavily
concentrated on a straight line indicating that agents are synchronized.

Joint plot of contours with marginals

Figure 3. Here $X_{t}$ converges to a Normal random variable. The joint plot
illustrates the case for two agents who learn from each other with $A$ and
$\mathcal{E}$ fixed. Large $t=2000$ and 3000 samples were created.

##  10\. Conclusion

To isolate learning, we dispensed with traditional game theoretic notions of
utility. There has been a growing trend across disciplines to study this
aspect. The abundance of data from the online world on interactions means
social network models are gaining the interests of theoreticians as well as
experimentalists. Our work is the first to our knowledge that generalizes
Degroot learning to incorporate randomness and develop distribution results on
the beliefs themselves. What kind of distributions arise, when there is no
consensus? This question was examined at length. It is not necessary that a
Gaussian distribution arises. It depends on the underlying randomness.

For previous studies in social learning, the noise is interpreted as a private
signal. In our setting, one can think of the noise in this way. However, the
emphasis we put was on the probabilistic notions of consensus. Agreement can
be to a point, a probability measure or to a line. This holds regardless of
the number of agents.

When the noise is not decaying, condition (7.4) is crucial to ensure
convergence in distribution. This condition can be thought of as a
stabilization feature of learning. Individuals learn with varying $A_{t}$ and
$\mathcal{E}_{t}$ but these cannot change too drastically. Eventually, all
agents settle down. We extended the standard Degroot learning models to
incorporate a variety of noise terms.

One criticism of having $\bar{\sigma}$ is that it is already incorporated into
the learning. To relax this assumption, we introduced averaging dynamics where
the ground truth is endogenous [Son16] to the social network. The central
limit theorem developed in Theorem 16 has an unusual feature. The marginal
distributions are Gaussian but the joint distribution encapsulates the
consensus property as agents synchronize along a line. An interesting aspect
of our results is that we place no restrictions on the interaction matrix $A$,
the implicit network topology, being fully connected _all the time_. Social
connections can change with time. The only requirement was that agents have
self-belief. However, there can be periods of insanity where learning rates
$\epsilon_{i}$’s are also zero or the interaction matrix is just the identity
matrix. Individual players can be insane and refuse fo learn for short bouts.
Mixing of beliefs and convergence to consensus is ensured by conditions (9.7)
or (7.2). These assumptions are weaker than previous attempts, which require
strong connectivity between the agents.

Thus far, agents’ rules are mechanical. Future work should address the issue
of rationality. In Degroot learning, individuals are boundedly rational. They
use the same rule. What if the agents are strategic? In the presence of noise
or disturbance, manipulation of opinion dynamics by forceful agents [AOP10]
becomes an interesting but difficult question. A possible way forward is to
look at fully nonlinear models. Random dynamical systems were reviewed by
[BM03]. Our results use different techniques to study social learning. Though
it must be acknowledged that recursive random dynamical systems are not new in
economics, their probabilistic analysis poses several challenges to
researchers. The interaction between mathematical finance and game theory
groups should take into account the resurgence of social learning models. How
a distribution of beliefs on prices for financial assets arises is not only a
fundamental question for game theorists but also of interest to proponents of
stochastic volatility and asset pricing models. Rather than viewing trading as
an exogenous activity, it should be seen as an essential combination of
interaction and learning.

## References

  * [AO11] Daron Acemoglu and Asuman Ozdaglar, _Opinion dynamics and learning in social networks_ , Dynamic Games and Applications 1 (2011), no. 1, 3–49.
  * [AOP10] Daron Acemoglu, Asuman Ozdaglar, and Ali ParandehGheibi, _Spread of (mis) information in social networks_ , Games and Economic Behavior 70 (2010), no. 2, 194–227.
  * [Ban92] Abhijit V Banerjee, _A simple model of herd behavior_ , The quarterly journal of economics 107 (1992), no. 3, 797–817.
  * [Bau16] Dario Bauso, _Game theory with engineering applications_ , SIAM, 2016.
  * [BBC17] Joshua Becker, Devon Brackbill, and Damon Centola, _Network dynamics of social influence in the wisdom of crowds_ , Proceedings of the national academy of sciences 114 (2017), no. 26, E5070–E5076.
  * [BBCM19] Abhijit Banerjee, Emily Breza, Arun G Chandrasekhar, and Markus Mobius, _Naive learning with uninformed agents_ , Tech. report, National Bureau of Economic Research, 2019.
  * [BHOT05] Vincent D Blondel, Julien M Hendrickx, Alex Olshevsky, and John N Tsitsiklis, _Convergence in multiagent coordination, consensus, and flocking_ , Proceedings of the 44th IEEE Conference on Decision and Control, IEEE, 2005, pp. 2996–3000.
  * [BHW92] Sushil Bikhchandani, David Hirshleifer, and Ivo Welch, _A theory of fads, fashion, custom, and cultural change as informational cascades_ , Journal of political Economy 100 (1992), no. 5, 992–1026.
  * [BM03] Rabi Bhattacharya and Mukul Majumdar, _Random dynamical systems: a review_ , Economic Theory 23 (2003), no. 1, 13–38.
  * [CEMS08] Martin W Cripps, Jeffrey C Ely, George J Mailath, and Larry Samuelson, _Common learning_ , Econometrica 76 (2008), no. 4, 909–933.
  * [CLX15] Arun G Chandrasekhar, Horacio Larreguy, and Juan Pablo Xandri, _Testing models of social learning on networks: Evidence from a lab experiment in the field_ , Tech. report, National Bureau of Economic Research, 2015.
  * [DeG74] Morris H DeGroot, _Reaching a consensus_ , Journal of the American Statistical Association 69 (1974), no. 345, 118–121.
  * [DVZ03] Peter M DeMarzo, Dimitri Vayanos, and Jeffrey Zwiebel, _Persuasion bias, social influence, and unidimensional opinions_ , The Quarterly journal of economics 118 (2003), no. 3, 909–968.
  * [FDLL98] Drew Fudenberg, Fudenberg Drew, David K Levine, and David K Levine, _The theory of learning in games_ , vol. 2, MIT press, 1998.
  * [GJ10] Benjamin Golub and Matthew O Jackson, _Naive learning in social networks and the wisdom of crowds_ , American Economic Journal: Microeconomics 2 (2010), no. 1, 112–49.
  * [GPW+13] Martin D Gould, Mason A Porter, Stacy Williams, Mark McDonald, Daniel J Fenn, and Sam D Howison, _Limit order books_ , Quantitative Finance 13 (2013), no. 11, 1709–1742.
  * [GS] Ben Golub and Evan Sadler, _Learning in social networks_ , The Oxford Handbook of the Economics of Networks.
  * [HJMR18] Jan Hazla, Ali Jadbabaie, Elchanan Mossel, and M. Amin Rahimian, _Reasoning in bayesian opinion exchange networks is pspace-hard_ , CoRR abs/1809.01077 (2018).
  * [Jac10] Matthew O Jackson, _Social and economic networks_ , Princeton university press, 2010.
  * [Kir02] Alan Kirman, _Reflections on interaction and markets_ , Quantitative Finance 2 (2002), 322–326.
  * [KL94] Ehud Kalai and Ehud Lehrer, _Weak and strong merging of opinions_ , Journal of Mathematical Economics 23 (1994), no. 1, 73–86.
  * [Lor05] Jan Lorenz, _A stabilization theorem for dynamics of continuous opinions_ , Physica A: Statistical Mechanics and its Applications 355 (2005), no. 1, 217 – 223, Market Dynamics and Quantitative Economics.
  * [MF13] Manuel Mueller-Frank, _A general framework for rational learning in social networks_ , Theoretical Economics 8 (2013), no. 1, 1–40.
  * [Mor05] Luc Moreau, _Stability of multiagent systems with time-dependent communication links_ , IEEE Transactions on automatic control 50 (2005), no. 2, 169–182.
  * [MPV17] Tung Mai, Ioannis Panageas, and Vijay V Vazirani, _Opinion dynamics in networks: Convergence, stability and lack of explosion_ , 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017), Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017.
  * [MS07] Shie Mannor and Jeff S Shamma, _Multi-agent learning for engineers_ , Artificial Intelligence 171 (2007), no. 7, 417–422.
  * [MST14] Elchanan Mossel, Allan Sly, and Omer Tamuz, _Asymptotic learning on bayesian social networks_ , Probability Theory and Related Fields 158 (2014), no. 1-2, 127–157.
  * [MT+17] Elchanan Mossel, Omer Tamuz, et al., _Opinion exchange dynamics_ , Probability Surveys 14 (2017), 155–204.
  * [MTSJ18] Pooya Molavi, Alireza Tahbaz-Salehi, and Ali Jadbabaie, _A theory of non-bayesian social learning_ , Econometrica 86 (2018), no. 2, 445–490.
  * [OSFM07] Reza Olfati-Saber, J Alex Fax, and Richard M Murray, _Consensus and cooperation in networked multi-agent systems_ , Proceedings of the IEEE 95 (2007), no. 1, 215–233.
  * [PNGCS14] Georgios Piliouras, Carlos Nieto-Granda, Henrik I. Christensen, and Jeff S. Shamma, _Persistent patterns: Multi-agent learning beyond equilibrium and utility_ , Proceedings of the 2014 International Conference on Autonomous Agents and Multi-agent Systems, AAMAS ’14, 2014, pp. 181–188.
  * [PP18] Christos Papadimitriou and Georgios Piliouras, _Game dynamics as the meaning of a game_ , SIGEcom Exchanges (2018).
  * [Sob00] Joel Sobel, _Economists’ models of learning_ , J. Economic Theory 94 (2000), 241–261.
  * [Son16] Yangbo Song, _Social learning with endogenous observation_ , Journal of economic theory 166 (2016), 324–333.
  * [SS00] Lones Smith and Peter Sørensen, _Pathological outcomes of observational learning_ , Econometrica 68 (2000), no. 2, 371–398.
  * [Str00] Daniel W. Stroock, _Probability Theory, an Analytic View_ , revised ed., Cambridge University Press, 2000.
  * [VMP18] Tushar Vaidya, Carlos Murguia, and Georgios Piliouras, _Learning agents in financial markets: Consensus dynamics on volatility_ , Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems (2018), 2106–2108.