# Urns with Multiple Drawings and Graph-based Interaction

Yogesh D<EMAIL_ADDRESS>Indian Institute of Science Education and
Research Mohali (IISERM), India  Neeraja Sahasrabudhe
<EMAIL_ADDRESS>Indian Institute of Science Education and Research
Mohali (IISERM), India

###### Abstract

Consider a finite undirected graph and place an urn with balls of two colours
at each vertex. At every discrete time-step, for each urn, a fixed number of
balls are drawn from that same urn with probability $p$, and from a randomly
chosen neighbour of that urn with probability $1-p$. Based on what is drawn,
the urns then reinforce themselves or their neighbours. For every ball of a
given colour in the sample, in case of Pólya-type reinforcement, a constant
multiple of balls of that colour is added while in case of Friedman-type
reinforcement, balls of the other colour are reinforced. These different
choices for reinforcement give rise to multiple models. In this paper, we
study the convergence of the fraction of balls of either colour across urns
for all of these models. We show that in most cases the urns synchronize, that
is, the fraction of balls of either colour in each urn converges to the same
limit almost surely. A different kind of asymptotic behaviour is observed on
bipartite graphs. We also prove similar results for the case of finite
directed graphs.

Keywords \- Urn Processes, Synchronization, Stochastic Approximation,
Bipartite Graphs, Multiple Drawings.

##  1 Introduction

The Pólya urn process is widely used in applications across mathematics,
physics, economics and engineering. Since its introduction in 1923 by George
Pólya, and further generalization by Bernard Friedman, the study of urn
processes has given rise to a large body of work. More recently, there has
been work on urns with multiple or even infinite colours [1, 2] and urns with
multiple drawings [3, 4, 5, 6]. In [1], stochastic approximation techniques
are used to prove convergence results and central limit theorems (CLTs) for an
urn process with multiple drawings containing balls of multiple colours. While
the authors mainly consider a balanced urn and prove convergence results for
the fraction of balls of each colour, some partial results are obtained for a
two-colour unbalanced urn as well. In [5] and [6], the authors consider a two-
colour urn model (say, with white and black colour balls) wherein at each time
step, a constant number of balls is drawn from the urn, and the reinforcement
is done depending upon the composition of the balls of white and black colour
in the drawn sample. While in [5], for every white/black ball in the sample, a
fixed constant number of white/black balls are added back to the urn; in [6],
the opposite kind of reinforcement takes place, that is, for every white/black
ball in the sample, a fixed constant number of black/white balls are added
back to the urn. In [6], the first and second moments of the fraction of white
balls are calculated, along with an asymptomatic analysis of the higher
moments of the number of white balls in the urn centered around its mean; and
in [5] results are obtained pertaining to the distribution of the limiting
fraction of white balls in the urn.

The study of urn models has also been extended in the direction of multiple
urns with dependent reinforcement processes, however the focus has been on urn
processes where only one ball is drawn from each urn at every time-step. In
[7, 8], the authors consider a system where the underlying network for
interaction is a finite complete graph. At each time-step, for each urn, a
ball is sampled from that urn with probability $p$ or from the super urn
(formed by combining all the urns of the system) with probability $1-p$. The
reinforcement is of Pólya-type and the authors prove that the urns synchronize
almost surely, that is, the fraction of balls of either colour converges
almost surely to the same limit across all the urns. In [8], CLTs are proved
and it is shown that the rate of convergence and asymptotic variance depend on
the parameter $p$. Building on this, in [9, 10], the authors study
synchronization and fluctuations of a similar interacting Friedman urn system.
In [11], the authors study a more general model with graph based nearest-
neighbour interaction and a general reinforcement scheme that includes Pólya
and Friedman-type reinforcements as special cases. They show that under
certain conditions on the graph structure and the reinforcement type, the
fraction of balls of either colour converges almost surely to a deterministic
limit. Interacting urns on finite graphs have also been studied in [12, 13,
14]. There is also some recent work in the direction of generalizing the study
of interacting urns to interacting reinforced random walks and/or interacting
reinforced stochastic processes over networks (See [15, 16, 17]).

In this paper, we study a two-colour interacting urn process that combines the
‘multiple drawings’ aspect with graph-based interaction. We consider urns,
containing balls of two colours, placed at the vertices of a finite undirected
graph. For each urn, a fixed number of balls are drawn from that same urn with
probability $p$ (for a fixed $p\in[0,1]$), and from a randomly chosen
neighbour of that urn with probability $1-p$. During the reinforcement phase,
balls can be reinforced in a variety of ways: an urn can reinforce itself, it
can reinforce all its neighbours, or it can reinforce itself as well as its
neighbours. Further, as in [5] and [6], we classify the two types of
reinforcement schemes as Pólya-type and Friedman-type. When the reinforcement
scheme is Pólya-type, for every white/black ball in the sample, $C>0$ number
of white/black balls are added. In contrast, in the case of Friedman-type
reinforcement scheme, white reinforces black and black reinforces white. By
including interaction with neighbours during the sampling as well as the
reinforcement step, we get a dependence on the square of the scaled adjacency
matrix which makes this model different from those studied earlier. This can
further be generalized by studying sampling and reinforcement that goes beyond
nearest-neighbour influence.

We study the effects of the graph structure, the interaction parameter $p$ and
the reinforcement type on the asymptotic behaviour of the urn system. In this
paper, we mainly focus on Friedman-type reinforcement and obtain convergence,
synchronization and fluctuation results for the fraction of balls of either
colour in the urns. However, we also obtain convergence results for the Pólya-
type reinforcement scheme under the added assumption of the regularity of the
underlying graph and an assumption on the initial configuration of the urns.
For Friedman-type reinforcement, universal synchronization of urns to a
deterministic limit of $1/2$ is observed when either $p$ lies strictly between
$0$ and $1$, or when the reinforcement scheme is such that each urn as well as
its neighbours are being reinforced. In some cases (when $p=0$ or $p=1$), only
partial synchronization takes place if the underlying graph is bipartite. By
partial synchronization, we mean that urns belonging to a common partition in
the bipartite graph synchronize with each other. In this case, we show that
for Friedman-type reinforcement, the fraction of balls of white colour in each
urn belonging to a particular partition converges to the same limit almost
surely. Further, if the limits are $Z_{1}^{*}$ and $Z_{2}^{*}$ on the two
partitions, then $Z^{*}_{1}+Z^{*}_{2}=1$. The convergence result for bipartite
graphs is obtained under certain constraints on the graph and initial
configuration of the urns. We observe that the ‘multiple drawings’ aspect does
not have any effect on the convergence and synchronization results, however
the limiting variance in the fluctuation theorems depends on both the size of
the drawn sample and the interaction parameter $p$.

The organization of the paper is as follows. In Section 2 we introduce the urn
process and the various models. In section 3 we state and prove the
convergence of the fraction of balls of either colour in each urn for various
models using the theory of stochastic approximation. We show that for a large
class of models, the limit is $1/2$ almost surely. In section 4, we study the
special case of Friedman-type self-reinforcement for $p=0$ on bipartite graphs
and under some assumptions, prove that the fraction of balls of either colour
in each urn converges to the same limiting fraction almost surely provided the
urns are placed at vertices of the same partition of the graph. The behaviour
of the limit, in terms of its distributional properties etc., is not known. In
section 5 we state and prove the fluctuation results, and show that
appropriately scaled differences between the fraction of balls of either
colour and the limit $1/2$ converge to a Gaussian distribution in most cases.
Finally, in section 6 we discuss the behaviour of some of these models on
directed networks. We briefly recall some of the stochastic approximation
results used in the paper in the Appendix. Throughout the paper, we write
$f(t)\sim g(t)$ to mean $f(t)=\mathcal{O}(g(t))$. For a matrix
$B(t)\in\mathbb{R}^{n\times m}$, by $B(t)\sim g(t)$ we mean that every entry
of the matrix has the same order, that is $B_{ij}(t)\sim g(t)$ for $1\leq
i\leq n$ and $1\leq j\leq m$. $\|\cdot\|$ refers to the standard Euclidean
norm, and for $k>0$, ${\bf 0}$ denotes a $k$-dimensional row vector of zeroes
and $\mathbf{0}_{k\times k}$ denotes a zero matrix with $k$ rows and $k$
columns.

##  2 Urn Process and Reinforcement Schemes

We consider a connected undirected graph
$\mathcal{G}=([N],\mbox{${\mathcal{E}}$})$ on $N$ vertices, where $[N]$
denotes the set $\\{1,2,\ldots,N\\}$ and
$\mbox{${\mathcal{E}}$}\subseteq[N]\times[N]$ denotes the set of edges. At
each vertex, we place an urn with a non-zero number of white and black balls.
The configuration of each urn (the number of balls of white and black colour)
is updated simultaneously at every discrete time-step.

For a vertex $v$, we define its neighbourhood as
$\mathcal{N}(v)=\\{w\in[N]:(w,v)\in\mbox{${\mathcal{E}}$}\\}$. Define
$d_{v}\coloneqq|\mathcal{N}(v)|$ as the degree of the vertex $v$. We assume
that the graph is connected, therefore $d_{v}>0\;\forall v\in[N]$. Let A
denote the adjacency matrix of the graph ${\mathcal{G}}$, and let D denote the
diagonal matrix consisting of the degrees of the vertices on the diagonal,
that is, $\textbf{D}_{ij}=d_{i}$ for $i=j$ and $0$ otherwise. For a matrix
$M$, denote by $\operatorname{Tr}(M)$ the trace of $M$. Denote by $\mathbf{1}$
an $N-$dimensional row vector with each entry being $1$, and for an event $A$,
let $\mbox{${\mathbb{I}}$}_{A}$ denote the indicator function of $A$.
Throughout this paper, whenever the graph $\mathcal{G}$ is bipartite, the two
disjoint partitions of the graph are denoted by $V$ and $W$, with
$V=\\{1,\dots,m\\}$ and $W=\\{m+1,\dots,N\\}$.

The urn process is a two-phase process, consisting of sampling and
reinforcement. At each step each urn samples from itself or from one of its
randomly chosen neighbours. The reinforcement process can be characterized by
two types of dependence: (1) neighbourhood dependence: reinforcement in each
urn depends on other urns in its neighbourhood, and (2) replacement scheme:
reinforcement depends on which colour reinforces which colour. We study three
types of neighbourhood dependence.

  1. 1.

Self-reinforcement: each urn reinforces itself.

  2. 2.

Neighbour-reinforcement: each urn reinforces its neighbours in the graph.

  3. 3.

Self and neighbour-reinforcement: each urn reinforces itself as well as its
neighbours.

Two types of reinforcement schemes are studied.

  1. 1.

Pólya-type reinforcement scheme: each colour reinforces itself. That is, for
every ball of colour white in the sample, $C$ balls of the same colour are
reinforced.

  2. 2.

Friedman-type reinforcement scheme: each colour reinforces the opposite
colour, and not itself. That is, for every ball of colour white in the sample,
$C$ balls of black colour are reinforced.

Note that due to the multiple drawing aspect of sampling, the replacement
matrix of the Pólya-type reinforcement described above is not a diagonal
matrix as in the classical Pólya urn model. The above terminology is
consistent with [5, 6] where multiple drawing urn models have been studied.

We now describe the process by which the configuration of urns evolves. Fix
$p\in[0,1]$. At each discrete time-step $t$, the following process takes
place.

  * •

Sampling: For each urn, $s$ number of balls are drawn uniformly at random
(with or without replacement) from that same urn with probability $p$, and
from a randomly chosen urn from the neighbourhood with probability $1-p$. The
sampling event for each urn is assumed to be independent of sampling from
every other urn. As we shall see later, the asymptotic behaviour of the urns
(convergence of the fraction of balls of a particular colour) is the same
regardless of whether sampling is done with replacement or without replacement
of balls.

  * •

Reinforcement The $N$ samples, each consisting of $s$ balls, are collated. We
study the following types of reinforcement processes.

    1. 1.

Pólya-type reinforcement.

      1. (a)

Pólya-type Self-Reinforcement (PTSR) model: For every white/black ball in the
drawn sample, $C$ white/black balls are added to that same urn to which the
sample corresponds.

      2. (b)

Pólya-type Neighbour-Reinforcement (PTNR) model: For every white/black ball in
the drawn sample, $C$ white/black balls are added to all the neighbours of
that urn.

      3. (c)

Pólya-type Self and Neighbour-Reinforcement (PTSNR) model: For every
white/black ball in the drawn sample, $C$ white/black balls are added to that
urn as well as to all the neighbours of that urn.

    2. 2.

Friedman-type reinforcement.

      1. (a)

Friedman-type Self-Reinforcement (FTSR) model: For every white/black ball in
the drawn sample, $C$ black/white balls are added to that same urn to which
the sample corresponds.

      2. (b)

Friedman-type Neighbour-Reinforcement (FTNR) model: For every white/black ball
in the drawn sample, $C$ black/white balls are added to all the neighbours of
that urn.

      3. (c)

Friedman-type Self and Neighbour-Reinforcement (FTSNR) model: For every
white/black ball in the drawn sample, $C$ black/white balls are added to that
urn as well as to all the neighbours of that urn.

Observe that in the case of FTSR with $p=0$, for each urn the balls are
sampled from a randomly chosen neigbour and the urn is reinforced. In the case
of FTNR with $p=1$, balls are sampled from each urn and the neighbours are
reinforced. For large time $t$, these two are essentially the same processes
and therefore they exhibit the same asymptotic behaviour. The same holds for
PTSR with $p=0$ and PTNR with $p=1$.

The reinforcement in each urn is balanced. That is, a constant number of balls
is added to each urn at every time step. Let $T_{t}(i)$ denote the total
number of balls in the $i^{th}$ urn at time $t$. Observe that $T_{t}(i)$ is
deterministic, and we have $T_{t+1}(i)=T_{t}(i)+Cs\omega_{i}$, where for
$1\leq i\leq N$,

$\omega_{i}=\begin{cases}1&\ \text{in case of self-reinforcement (PTSR and
FTSR models)},\\\ d_{i}&\ \text{in case of neighbour-reinforcement (PTNR and
FTNR models)},\\\ d_{i}+1&\ \text{in case of self and neighbour-reinforcement
(PTSNR and FTSNR models)}.\end{cases}$

Let $\Omega$ denote the diagonal matrix consisting of $\omega_{i}$’s on the
diagonal, and let $W_{t}(i)$ and $Z_{t}(i)$ denote the number and fraction of
white balls in the $i^{th}$ urn at time $t$ respectively. Define
$Z_{t}:=(Z_{t}(1),\ldots,Z_{t}(N))\in\mathbb{R}^{N}$.

Let $Y_{t+1}(i)$ be the number of white balls sampled from the $i^{th}$ urn at
time $t$. Then, the evolution of the number of white balls in the $i^{th}$ urn
(for $1\leq i\leq N)$ can be described as follows.

  1. 1.

Pólya-type: $W_{t+1}(i)=W_{t}(i)+C\left(\eta
Y_{t+1}(i)+\kappa\sum\limits_{j\in N(i)}Y_{t+1}(j)\right)$,

  2. 2.

Friedman-type:
$W_{t+1}(i)=W_{t}(i)+C\left(\eta(s-Y_{t+1}(i))+\kappa\sum\limits_{j\in
N(i)}(s-Y_{t+1}(j))\right)$.

where $\kappa$ and $\eta$ depend on the kind of urn reinforcement in question.
More precisely, we have

$\kappa=\begin{cases}0&\ \text{in case of self-reinforcement (PTSR and FTSR
models),}\\\ 1&\ \text{in case of neighbour-reinforcement (PTNR and FTNR
models),}\\\ 1&\ \text{in case of self and neighbour-reinforcement (PTSNR and
FTSNR models).}\\\ \end{cases}$

$\eta=\begin{cases}1&\ \text{in case of self-reinforcement (PTSR and FTSR
models),}\\\ 0&\ \text{in case of neighbour-reinforcement (PTNR and FTNR
models),}\\\ 1&\ \text{in case of self and neighbour-reinforcement (PTSNR and
FTSNR models).}\\\ \end{cases}$

Define a filtration $\\{\mbox{${\mathcal{F}}$}_{t}\\}_{t\geq 0}$ by
$\mbox{${\mathcal{F}}$}_{t}=\sigma(Y_{s}(i):i\in[N]\text{ and }s\leq t)$. For
$1\leq j\leq N$, and for $0\leq k\leq s$,

$P(Y_{t+1}(j)=k|\mbox{${\mathcal{F}}$}_{t})={s\choose
k}\left\\{pZ_{t}(j)^{k}(1-Z_{t}(j))^{s-k}+\frac{1-p}{d_{j}}\sum\limits_{l\in
N(j)}Z_{t}(l)^{k}(1-Z_{t}(l))^{s-k}\right\\},$ (2.1)

when the sampling is done with replacement. In case of sampling without
replacement, we have

$P(Y_{t+1}(j)=k|\mbox{${\mathcal{F}}$}_{t})=p\frac{{W_{t}(j)\choose
k}{{T_{t}(j)-W_{t}(j)}\choose{s-k}}}{{T_{t}(j)\choose
s}}+\frac{1-p}{d_{j}}\sum\limits_{l\in N(j)}\frac{{W_{t}(l)\choose
k}{{T_{t}(j)-W_{t}(j)}\choose{s-k}}}{{T_{t}(j)\choose s}}.$ (2.2)

Note that for any $j\in[N]$, the sequence $\\{Y_{t}(j)\\}_{t\geq 0}$ is not
exchangeable. For $j\in[N]$, define

$\chi_{t}(j)=\begin{cases}Y_{t}(j)&\text{in case of P\'{o}lya-type
reinforcement},\\\ s-Y_{t}(j)&\text{in case of Friedman-type
reinforcement}.\end{cases}$

For any $i\in[N]$, we have

$\displaystyle Z_{t+1}(i)$ $\displaystyle=$
$\displaystyle\frac{W_{t+1}(i)}{T_{t+1}(i)}$ (2.3) $\displaystyle=$
$\displaystyle\frac{1}{T_{t+1}(i)}\left(Z_{t}(i)T_{t}(i)+C\left(\eta\chi_{t+1}(i)+\kappa\sum\limits_{j\in
N(i)}\chi_{t+1}(j)\right)\right).$

This implies

$\displaystyle E[Z_{t+1}(i)|\mbox{${\mathcal{F}}$}_{t}]$ $\displaystyle=$
$\displaystyle\frac{1}{T_{t+1}(i)}\left[Z_{t}(i)T_{t}(i)+C\left(\eta
E[\chi_{t+1}(i)|\mbox{${\mathcal{F}}$}_{t}]+\kappa\sum\limits_{j\in
N(i)}E[\chi_{t+1}(j)|\mbox{${\mathcal{F}}$}_{t}]\right)\right].$

Using (2.1) and (2.2), we get that for $i\in[N]$,

$E[\chi_{t+1}(i)|\mbox{${\mathcal{F}}$}_{t}]=s\times\begin{cases}pZ_{t}(i)+\frac{1-p}{d_{i}}\sum\limits_{l\in
N(i)}Z_{t}(l)&\text{for P\'{o}lya-type reinforcement,}\\\
1-pZ_{t}(i)-\frac{1-p}{d_{i}}\sum\limits_{l\in N(i)}Z_{t}(l)&\text{for
Friedman-type reinforcement}.\end{cases}$ (2.4)

The asymptotic behaviour of any urn $i\in[N]$ depends on
$E[\chi_{t+1}(i)|\mbox{${\mathcal{F}}$}_{t}]$, which is the expected
reinforcement in that urn at that time given the past. Since (2.4) turns out
to be the same regardless of whether sampling is done with replacement of
balls or without replacement, all our results hold for both kinds of sampling
unless stated otherwise. We now write the recursion for $Z_{t}$ as an
$N$-dimensional stochastic approximation scheme (see Appendix). Using (2.3),
for $i\in[N]$ we have

$\displaystyle Z_{t+1}(i)$ $\displaystyle=$
$\displaystyle\frac{T_{t}(i)}{T_{t+1}(i)}Z_{t}(i)+\frac{C}{T_{t+1}(i)}\left(\eta\chi_{t+1}(i)+\kappa\sum\limits_{j\in
N(i)}\chi_{t+1}(j)\right)$ $\displaystyle=$ $\displaystyle
Z_{t}(i)+\frac{C}{T_{t+1}(i)}\left(\eta\chi_{t+}(i)-s\omega_{i}Z_{t}(i)+\kappa\sum\limits_{j\in
N(i)}\chi_{t+1}(j)\right)$ $\displaystyle=$ $\displaystyle
Z_{t}(i)+\frac{1}{t+1}\left[\frac{1}{s\omega_{i}}\left(\eta\chi_{t+1}(i)+\kappa\sum\limits_{j\in
N(i)}\chi_{t+1}(j)\right)-Z_{t}(i)\right]+\epsilon_{t}(i),$

where
$\epsilon_{t}(i)=\left(\frac{Cs\omega_{i}}{T_{t+1}(i)}-\frac{1}{t+1}\right)\left[\frac{1}{s\omega_{i}}\left(\eta\chi_{t+1}(i)+\kappa\sum\limits_{j\in
N(i)}\chi_{t+1}(j)\right)-Z_{t}(i)\right]\to 0$ as $t\to\infty$ (since
$T_{t+1}(i)=T_{0}(i)+Cs\omega_{i}(t+1)$). For $j\in[N]$, define by $\Delta
M_{t+1}(j)=\chi_{t+1}(j)-E[\chi_{t+1}(j)|\mbox{${\mathcal{F}}$}_{t}]$ the
martingale difference. Then,

$\displaystyle Z_{t+1}(i)$ $\displaystyle=$ $\displaystyle
Z_{t}(i)+\frac{1}{s\omega_{i}(t+1)}\left(\eta
E[\chi_{t+1}(i)|\mbox{${\mathcal{F}}$}_{t}]-s\omega_{i}Z_{t}(i)+\kappa\sum\limits_{j\in
N(i)}E[\chi_{t+1}(j)|\mbox{${\mathcal{F}}$}_{t}]\right)$ $\displaystyle+$
$\displaystyle\frac{1}{s\omega_{i}(t+1)}\left(\eta\Delta
M_{t+1}(i)+\kappa\sum\limits_{j\in N(i)}\Delta
M_{t+1}(j)\right)+\epsilon_{t}(i).$

We denote the row vectors $(\chi_{t}(1),\dots,\chi_{t}(N)),(\Delta
M_{t}(1),\dots,\Delta M_{t}(N))$ and $(\epsilon_{t}(1),\dots,\epsilon_{t}(N))$
by $\chi_{t}$, $\Delta M_{t}$ and $\epsilon_{t}$ respectively. Then we can
write the $N$-dimensional recursion for $Z_{t}$ as

$\displaystyle Z_{t+1}$ $\displaystyle=$ $\displaystyle
Z_{t}+\frac{1}{s(t+1)}\left(E[\chi_{t+1}|\mbox{${\mathcal{F}}$}_{t}]\left(\eta
I+\kappa\textbf{A}\right){\Omega}^{-1}-sZ_{t}+\Delta M_{t+1}(\eta
I+\kappa\textbf{A}){\Omega}^{-1}\right)+\epsilon_{t}$ $\displaystyle=$
$\displaystyle Z_{t}+\frac{1}{t+1}\left(h(Z_{t})+\frac{\Delta M_{t+1}}{s}(\eta
I+\kappa\textbf{A}){\Omega}^{-1}\right)+\epsilon_{t},$

where
$h(Z_{t})=\frac{1}{s}\left(E[\chi_{t+1}|\mbox{${\mathcal{F}}$}_{t}]\left(\eta
I+\kappa\textbf{A}\right){\Omega}^{-1}\right)-Z_{t}$ is a Lipschitz function
of $Z_{t}$ and $\epsilon_{t}\to 0$ as $t\to\infty$. Note that the matrix
$\Omega$ equals $I$ in case of self-reinforcement, D for neighbour-
reinforcement, and $\textbf{D}+I$ for the case of self and neighbour-
reinforcement. Using the appropriate value of $\kappa$ and $\eta$ based on the
kind of reinforcement, the fact that
$\mathbf{1}\textbf{A}\textbf{D}^{-1}=\mathbf{1}$ (since
$\textbf{A}\textbf{D}^{-1}$ is column stochastic), and using (2.4), we get

$h(Z_{t})=\begin{cases}(1-p)Z_{t}(\textbf{A}\textbf{D}^{-1}-I)&\text{for the
PTSR model,}\\\
Z_{t}(p\textbf{A}\textbf{D}^{-1}+(1-p)(\textbf{A}\textbf{D}^{-1})^{2}-I)&\text{for
the PTNR model,}\\\
Z_{t}\left[(pI+(1-p)\textbf{A}\textbf{D}^{-1})(\textbf{A}+I)(I+\textbf{D})^{-1}-I\right]&\text{for
the PTSNR model,}\\\
\mathbf{1}-Z_{t}((1+p)I+(1-p)\textbf{A}\textbf{D}^{-1})&\text{for the FTSR
model,}\\\
\mathbf{1}-Z_{t}(I+p\textbf{A}\textbf{D}^{-1}+(1-p)(\textbf{A}\textbf{D}^{-1})^{2})&\text{for
the FTNR model,}\\\
\mathbf{1}-Z_{t}\left[(pI+(1-p)\textbf{A}\textbf{D}^{-1})(\textbf{A}+I)(I+\textbf{D})^{-1}+I\right]&\text{for
the FTSNR model.}\end{cases}$ (2.6)

As mentioned before, the cases FTSR with $p=0$ and FTNR with $p=1$ (similarly,
PTSR with $p=0$ and PTNR with $p=1$) do not require a separate analysis of the
asymptotic behaviour. This is further clear from the fact that the $h(\cdot)$
function for these cases is identical.

The stochastic approximation theory (see Appendix) can be used to analyse the
limiting behaviour of $Z_{t}$. In order to find the points of convergence for
$Z_{t}$, we need to find the stable limit points of the O.D.E.
$\dot{z}_{t}=h(z_{t})$, which are a subset of $\\{h(Z_{t})=\mathbf{0}\\}$. To
determine the set of zeroes of $h$, we need to study the spectral properties
of the matrices involved in $h(\cdot)$ for various urn models described above.
In the next section, using the spectral analysis of the matrices involved and
using the stochastic approximation theory, we study the asymptotic behaviour
of $Z_{t}$ and characterize the limits for both Pólya-type and Friedman-type
reinforcement schemes.

##  3  Convergence Results

We begin by showing that for the Friedman-type reinforcement scheme, whenever
there is a unique limit point of the O.D.E. $\dot{z}_{t}=h(z_{t})$, it is
stable. In other words, we show that the corresponding Jacobian matrices
(denoted by $\frac{\partial h}{\partial z}$) are such that their eigenvalues
have non-positive real parts.

######  Lemma 3.1.

For Friedman-type reinforcement, the real part of each eigenvalue of
$\frac{\partial h}{\partial z}$ is non-positive, where $h(\cdot)$ is as in
(2.6).

###### Proof.

Since $h$ is a linear function of $z_{t}$, the Jacobian is independent of
$z_{t}$ and we have

$\frac{\partial h}{\partial
z}=\begin{cases}-I-(pI+(1-p)\textbf{A}\textbf{D}^{-1})&\text{for the FTSR
model,}\\\
-I-(p\textbf{A}\textbf{D}^{-1}+(1-p)(\textbf{A}\textbf{D}^{-1})^{2})&\text{for
the FTNR model,}\\\
-I-(pI+(1-p)\textbf{A}\textbf{D}^{-1})(A+I)(I+D)^{-1}&\text{for the FTSNR
model}.\end{cases}$

Note that the matrices $\textbf{A}\textbf{D}^{-1}$,
$(\textbf{A}+I)(I+\textbf{D})^{-1}$ and $pI+(1-p)\textbf{A}\textbf{D}^{-1}$
are column stochastic, and since the product of two column stochastic matrices
is column stochastic, the matrices
$p\textbf{A}\textbf{D}^{-1}+(1-p)(\textbf{A}\textbf{D}^{-1})^{2}$ and
$(pI+(1-p)\textbf{A}\textbf{D}^{-1})(\textbf{A}+I)(I+\textbf{D})^{-1}$ are
also column stochastic. So, it is enough to show that the lemma is satisfied
for matrices of the form $-I-X$ where $X$ is column stochastic. Let $\lambda$
be an arbitrary eigenvalue of $-I-X$. Then $-\lambda-1$ is an eigenvalue of
the matrix $X$, which is column stochastic. Therefore, $|\lambda+1|\leq 1$.
This implies $(Re(\lambda)+1)^{2}+(Im(\lambda))^{2}\leq 1$. Hence, $-2\leq
Re(\lambda)\leq 0$. $\Box$

Using arguments similar to those in Lemma 2.2 of [18] for the case of an
undirected graph, we get the following.

######  Lemma 3.2.

Suppose ${\mathcal{G}}$ is a connected undirected graph. The matrix
$I+\textbf{A}\textbf{D}^{-1}$ has the following properties.

  1. 1.

All eigenvalues of $I+\textbf{A}\textbf{D}^{-1}$ are real and non-negative.

  2. 2.

$Rank(I+\textbf{A}\textbf{D}^{-1})$ equals $N$, if the graph ${\mathcal{G}}$
is non-bipartite, and $N-1$ if ${\mathcal{G}}$ is bipartite.

  3. 3.

Assume that the matrix $I+\textbf{A}\textbf{D}^{-1}$ is diagonalizable. If the
graph ${\mathcal{G}}$ is bipartite, then the algebraic multiplicity of the
eigenvalue $0$ is one.

###### Proof.

For the graph ${\mathcal{G}}$, define the set
$\mbox{${\mathcal{E}}$}^{\prime}$ as the set of edges in ${\mathcal{G}}$ such
that for any $(x,y)\in\mathcal{E}$, both $(x,y)$ and $(y,x)$ are in
$\mbox{${\mathcal{E}}$}^{\prime}$.

  1. 1.

For any $x\in\mathbb{R}$,
$det(xI-\textbf{A}\textbf{D}^{-1})=det(\textbf{D}^{1/2}(xI-\textbf{D}^{-1/2}\textbf{A}\textbf{D}^{-1/2})\textbf{D}^{-1/2})$.
So, the eigenvalues of $\textbf{A}\textbf{D}^{-1}$ are the same as those of
$\textbf{D}^{-1/2}\textbf{A}\textbf{D}^{-1/2}$, which is symmetric. Therefore,
the eigenvalues of $AD^{-1}$ and hence, those of $I+\textbf{A}\textbf{D}^{-1}$
are real. Since $\textbf{A}\textbf{D}^{-1}$ is column stochastic, the
eigenvalues of $I+\textbf{A}\textbf{D}^{-1}$ are non-negative.

  2. 2.

For $x\in\mathbb{R}^{N}$,

$\displaystyle x^{T}(\textbf{D}+\textbf{A})x$ $\displaystyle=$
$\displaystyle\sum_{i=1}^{N}d_{i}x_{i}^{2}+\sum_{(i,j)\in\mbox{${\mathcal{E}}$}^{\prime}}x_{i}x_{j}$
(3.1) $\displaystyle=$
$\displaystyle\sum_{(i,j)\in\mbox{${\mathcal{E}}$}^{\prime}}\frac{x_{i}^{2}}{2}+\sum_{(i,j)\in\mbox{${\mathcal{E}}$}^{\prime}}\frac{x_{j}^{2}}{2}+\sum_{(i,j)\in\mbox{${\mathcal{E}}$}^{\prime}}x_{i}x_{j}$
$\displaystyle=$
$\displaystyle\sum_{(i,j)\in\mbox{${\mathcal{E}}$}^{\prime}}\frac{(x_{i}+x_{j})^{2}}{2}.$

Now, $x^{T}(\textbf{D}+\textbf{A})x=0$ implies that $x_{i}=-x_{j}$ whenever
$(i,j)\in\mbox{${\mathcal{E}}$}^{\prime}$. Let
$V=\\{i\in[N]:x_{i}>0\\},W=\\{i\in[N]:x_{i}<0\\}$ and
$L=\\{i\in[N]:x_{i}=0\\}$. For a connected graph, $L$ is either empty or whole
of $[N]$.

Suppose $V$ is non-empty and suppose $v\in V$ such that $x_{v}=\alpha$. Then,
$x_{i}=\alpha\forall i\in V$, and $x_{i}=-\alpha\forall i\in W$. Thus, the
graph can be partitioned into two disjoint vertex sets $V$ and $W$ such that
the edges only connect vertices from $V$ to vertices of $W$, and hence the
graph is bipartite ($V$ and $W$ being the two partitions of the graph). In
this case, we have
$Rank(I+\textbf{A}\textbf{D}^{-1})=Rank(\textbf{D}+\textbf{A})=N-1$ because
the solution of $x^{T}(\textbf{D}+\textbf{A})x=0$ is representable in terms of
one variable alone. Since the graph cannot be partitioned in the case of a
non-bipartite graph, we must have that $L=[N]$, which means that
$x=\mathbf{0}$, where $\mathbf{0}$ is the zero vector of dimension $N$.
$\textbf{D}+\textbf{A}$ is full rank in this case.

  3. 3.

Since $Rank(I+\textbf{A}\textbf{D}^{-1})=N-1$ for a bipartite graph, the
geometric multiplicity of $0$ eigenvalue is equal to one, and since the matrix
is assumed to be diagonalizable, algebraic multiplicity of $0$ also equals
one.

$\Box$

We now state and prove results for almost sure convergence of $Z_{t}$.

######  Theorem 3.3.

For the Friedman-type reinforcement scheme, as $t\rightarrow\infty$,
$Z_{t}\rightarrow\frac{1}{2}\mathbf{1}$ almost surely whenever one of the
following holds.

  1. 1.

FTSR model

    1. (a)

$0<p\leq 1$.

    2. (b)

$p=0$ and the graph $\mathcal{G}$ is non-bipartite.

  2. 2.

FTNR model

    1. (a)

$0\leq p<1$.

    2. (b)

$p=1$ and the graph $\mathcal{G}$ is non-bipartite.

  3. 3.

The model is FTSNR, regardless of the value of $p$.

###### Proof.

Using the theory of stochastic approximation, we know that it is enough to
show that $\frac{1}{2}\mathbf{1}$ is the unique stable limit point of the
solution of the O.D.E. $\dot{z}_{t}=h(z_{t})$. From (2.6), it is clear that
$h(Z_{t})=\mathbf{0}$ has a unique solution in each of the cases if the
matrices $(1+p)I+(1-p)\textbf{A}\textbf{D}^{-1}$,
$p\textbf{A}\textbf{D}^{-1}+(1-p)(\textbf{A}\textbf{D}^{-1})^{2}+I$ and
$(pI+(1-p)\textbf{A}\textbf{D}^{-1})(\textbf{A}+I)(I+\textbf{D})^{-1}+I$ are
invertible. Since for all these matrices, each column-sum is $2$, it follows
that $\frac{1}{2}\mathbf{1}$ is a solution of $h(Z_{t})=\mathbf{0}$ in all
three cases of Friedman-type reinforcement. Note that from Lemma 3.1, it
follows that if this is a unique solution, it is also stable. Thus, it is
enough to prove the invertibility of these matrices under the conditions of
the theorem.

  1. 1.

    1. (a)

We have
$(1+p)I+(1-p)\textbf{A}\textbf{D}^{-1}=(1+p)(I+(1-p)/(1+p)\textbf{A}\textbf{D}^{-1})$.
Since $\textbf{A}\textbf{D}^{-1}$ is a column stochastic matrix,
$I+r\textbf{A}\textbf{D}^{-1}$ is invertible for any $r\in\mathbb{C}$ such
that $\left|r\right|<1$. Since $\Big{|}\frac{1-p}{1+p}\Big{|}<1$ for $0<p\leq
1$ we are done.

    2. (b)

It follows from Lemma 3.2 that the matrix $\textbf{D}+\textbf{A}$ is
invertible whenever ${\mathcal{G}}$ is non-bipartite.

  2. 2.

    1. (a)

For $0<p<1$, we have

$\displaystyle
p\textbf{A}\textbf{D}^{-1}+(1-p)(\textbf{A}\textbf{D}^{-1})^{2}+I$
$\displaystyle=$
$\displaystyle\left(I+\frac{p-\sqrt{p^{2}-4(1-p)}}{2}\textbf{A}\textbf{D}^{-1}\right)\times$
$\displaystyle\left(I+\frac{p+\sqrt{p^{2}-4(1-p)}}{2}\textbf{A}\textbf{D}^{-1}\right)$
$\displaystyle=$
$\displaystyle\left(I+\frac{p-\sqrt{(p+2)^{2}-8}}{2}\textbf{A}\textbf{D}^{-1}\right)\times$
$\displaystyle\left(I+\frac{p+\sqrt{(p+2)^{2}-8}}{2}\textbf{A}\textbf{D}^{-1}\right).$

Since $0<p<1$, whenever $(p+2)^{2}-8\geq 0$,
$\Big{|}\frac{p\pm\sqrt{{{(p+2)}^{2}}-8}}{2}\Big{|}<1$. For ${(p+2)^{2}}-8<0$,
$\Big{|}\frac{p\pm\sqrt{(p+2)^{2}-8}}{2}\Big{|}=\sqrt{1-p}<1$. Thus,
$p\textbf{A}\textbf{D}^{-1}+(1-p)(\textbf{A}\textbf{D}^{-1})^{2}+I$ can be
written as a product $(I+r_{1}B_{1})(I+r_{2}B_{2})$, where $B_{1},B_{2}$ are
column-stochastic and $|r_{1}|,|r_{2}|<1$. This implies
$p\textbf{A}\textbf{D}^{-1}+(1-p)(\textbf{A}\textbf{D}^{-1})^{2}+I$ is
invertible.

For $p=0$,
$I+(\textbf{A}\textbf{D}^{-1})^{2}=(I+i\textbf{A}\textbf{D}^{-1})(I-i\textbf{A}\textbf{D}^{-1})$,
and both $(I+i\textbf{A}\textbf{D}^{-1})$ and $(I-i\textbf{A}\textbf{D}^{-1})$
are invertible since from Lemma 3.2 (1), we know that
$\textbf{A}\textbf{D}^{-1}$ has real eigenvalues.

    2. (b)

This case is the same as that of FTSR with $p=0$.

  3. 3.

Notice that
$(pI+(1-p)\textbf{A}\textbf{D}^{-1})(\textbf{A}+I)(I+\textbf{D})^{-1}=[p\textbf{A}+(1-p)\textbf{A}\
\textbf{D}^{-1}\textbf{A}+pI+(1-p)\textbf{A}\textbf{D}^{-1}](I+\textbf{D})^{-1}$
is irreducible for $0\leq p\leq 1$ since $\mathcal{G}$ is connected. To show
that this matrix is aperiodic for $0\leq p\leq 1$, it is enough to show that
one of the diagonal terms of this matrix is strictly positive. This is obvious
when $0<p\leq 1$ (because of the term $pI$). For $p=0$, this is true since
$\exists j\in[N]$ such that $(1,j)\in\mathcal{E}$, hence we have
$(\textbf{A}\textbf{D}^{-1}\textbf{A})_{1,1}>0$. Since this matrix is also
stochastic, it cannot have $-1$ as an eigenvalue (because of aperiodicity,
there can exist only one eigenvalue with absolute value $1$). Hence,
$(pI+(1-p)\textbf{A}\textbf{D}^{-1})(\textbf{A}+I)(I+\textbf{D})^{-1}+I$ is
invertible for $0\leq p\leq 1$.

$\Box$

We now address the remaining cases. We use Theorem 2.1 from [19] (see Theorem
A.1 in the Appendix) to show that on a connected regular bipartite graph with
some conditions on the initial configuration, under the reinforcement scheme
FTSR with $p=0$, $Z_{t}$ admits an almost sure limit. Under these conditions,
the $h$ function corresponding to the stochastic approximation scheme for
$Z_{t}$ can be realized as the gradient of a function $f$. Similar results are
obtained for Pólya-type reinforcement on regular graphs. We first check that
both Pólya and Friedman-type schemes with self or neighbour-reinforcement
satisfy the assumptions of Theorem 2.1 [19].

######  Lemma 3.4.

Assume that the underlying graph ${\mathcal{G}}$ is regular with degree $d$
and $T_{0}(i)=T_{0}\ \forall i\in[N]$. Then, models with both Pólya and
Friedman-type reinforcement (except for the FTSNR model) satisfy assumptions
1-3 as stated in Theorem A.1 in the Appendix.

###### Proof.

Since the graph is regular, we have that $d_{i}=d$ and $\omega_{i}=\omega\
\forall\ 1\leq i\leq N$. Then using (2), we have

$\displaystyle Z_{t+1}(i)$ $\displaystyle=$
$\displaystyle\frac{T_{t}(i)}{T_{t+1}(i)}Z_{t}(i)+\frac{C}{T_{t+1}(i)}\left(\eta\chi_{t+1}(i)+\kappa\sum\limits_{j\in
N(i)}\chi_{t+1}(j)\right)$ $\displaystyle=$ $\displaystyle
Z_{t}(i)+\frac{1}{\frac{T_{0}}{Cs\omega}+t+1}\left(\eta\frac{E[\chi_{t+1}(i)|\mbox{${\mathcal{F}}$}_{t}]}{s\omega}-Z_{t}(i)+\kappa\left(\frac{\sum\limits_{j\in
N(i)}E[\chi_{t+1}(j)|\mbox{${\mathcal{F}}$}_{t}]}{s\omega}\right)\right)$
$\displaystyle+\frac{1}{\frac{T_{0}}{Cs\omega}+t+1}\left(\frac{1}{s\omega}\left(\eta\Delta
M_{t}(i)+\kappa\sum\limits_{j\in N(i)}\Delta M_{t}(j)\right)\right).$

Writing in vector form, we get

$\displaystyle
Z_{t+1}=Z_{t}+\frac{1}{\frac{T_{0}}{Cs\omega}+t+1}\left(\frac{E[\chi_{t+1}|\mbox{${\mathcal{F}}$}_{t}]}{s\omega}(\eta
I+\kappa\textbf{A})-Z_{t}+\frac{1}{s\omega}\Delta M_{t}(\eta
I+\kappa\textbf{A})\right).$ (3.2)

Define
$X\coloneqq(1-\frac{p\eta}{\omega})I-\frac{1}{\omega}\left(p\kappa+\frac{(1-p)\eta}{d}\right)\textbf{A}-\frac{(1-p)\kappa}{d\omega}\textbf{A}^{2}$
and
$Y\coloneqq(1+\frac{p\eta}{\omega})I+\frac{1}{\omega}\left(p\kappa+\frac{(1-p)\eta}{d}\right)\textbf{A}+\frac{(1-p)\kappa}{d\omega}\textbf{A}^{2}$.
Then, $X$ and $Y$ are symmetric matrices. For $z=(z_{1},z_{2}\ldots
z_{N})\in[0,1]^{N}$, define
$f:\mathbb{R}^{N}\to\mathbb{R}^{N}$ by

$f(z)=\begin{cases}\frac{\sum_{i=1}^{N}{z_{i}}^{2}X_{ii}}{2}+\sum_{i<j}z_{i}z_{j}X_{ij}&\text{for
P\'{o}lya-type reinforcement scheme,}\\\
\frac{\sum_{i=1}^{N}{z_{i}}^{2}Y_{ii}}{2}+\sum_{i<j}z_{i}z_{j}Y_{ij}-\sum_{i=1}^{N}z_{i}&\text{for
the Friedman-type reinforcement scheme.}\end{cases}$

Using the symmetry of $X$, for $r\in[N]$ and for Pólya-type reinforcement, we
have

$\displaystyle\frac{\partial f}{\partial
z_{r}}=z_{r}X_{r,r}+\sum_{i<r}z_{i}X_{i,r}+\sum_{j>r}z_{j}X_{r,j}=\sum_{j=1}^{N}z_{j}X_{j,r}.$

Combining this with a similar calculation for Friedman-type reinforcement, we
get

$\displaystyle\nabla f(Z_{t})=\begin{cases}Z_{t}X&\text{for P\'{o}lya-type
reinforcement scheme, }\\\ Z_{t}Y-\mathbf{1}&\text{for the Friedman-type
reinforcement scheme.}\end{cases}$ (3.3)

$X$ and $Y$ have been defined in such a way that $\nabla f(Z_{t})=-h(Z_{t})$
for all the six models (after substituting corresponding $\eta,\kappa$ and
$\omega$ for each model). Hence, with
$a_{t}=1/\left(\frac{T_{0}}{Cs\omega}+t+1\right)$ and $\beta_{t}=-\Delta
M_{t}(\eta I+\kappa A)/s\omega$ for $t\geq 0$, recursion in (3.2) can be
written in the form of the stochastic approximation scheme in (A.2) of the
Appendix.

Now we verify the three assumptions of theorem A.1. Assumption $1$ is clearly
satisfied for the chosen $\\{{a}_{t}\\}_{t\geq 0}$. Assumption 3 is satisfied
since $f$ is an analytic function on its entire domain. We now check
assumption 2. Let $S_{t}=\sum_{i=0}^{t-1}a_{i}\gamma_{i}^{2}\beta_{i}$, where
$\gamma_{i}=\sum_{j=0}^{i-1}a_{j}$. Since $\\{\Delta M_{t}\\}_{t\geq 0}$is a
martingale difference sequence, we have $E[S_{t+1}|{\mathcal{F}}_{t}]=S_{t}$.
Hence, $\\{S_{t}\\}_{t\geq 0}$ is a martingale. Note that $a_{t}\sim 1/t$ and
therefore $\gamma_{k}\sim H_{k}$, where $H_{k}$ is the $k^{th}$ Harmonic
number. Since $H_{n}\sim\log n$,
$\sum_{n=1}^{\infty}\frac{{H_{n}}^{4}}{n^{2}}<\infty$. Since
$\left|\left|\beta_{i}\right|\right|$ is uniformly bounded, we therefore have
$\sum_{i=0}^{t}E[{\|S_{i+1}-S_{i}\|}^{2}|{\mathcal{F}}_{i}]\leq\sum_{i=0}^{t}{a_{i}}^{2}{\gamma_{i}}^{4}{\left|\left|\beta_{i}\right|\right|}^{2}<\infty$.
Hence, $\\{S_{t}\\}_{t\geq 0}$ converges almost surely to a finite random
vector. This implies that it is also almost surely Cauchy and we have
$\limsup\limits_{n\to\infty}\max\limits_{n\leq
k<a(n,1)}\left|\left|\sum_{i=n}^{k}a_{i}{\gamma_{i}}^{2}\beta_{i}\right|\right|<\infty$.
$\Box$

######  Theorem 3.5.

Consider FTSR with $p=0$ or FTNR with $p=1$ on an undirected bipartite
connected regular graph. Then, as $t\rightarrow\infty$, $Z_{t}$ converges
almost surely to a random vector $\zeta=(\zeta_{1},\zeta_{2}\ldots\zeta_{N})$
such that $\zeta_{i}=\zeta_{\infty}\ \forall\ 1\leq i\leq m$ and
$\zeta_{i}=1-\zeta_{\infty}\ \forall\ m+1\leq i\leq N$, where $\zeta_{\infty}$
is a random variable supported on [0,1].

###### Proof.

The result follows from Theorem A.1 and Lemma 3.4. For $p=0$, in the case of
the FTSR model, we have that $\nabla
f(Z_{t})=Z_{t}\left(I+\frac{1}{d}\textbf{A}\right)-\mathbf{1}$. From Lemma
3.2, we know that for a bipartite graph,
$Rank\left(I+\frac{1}{d}\textbf{A}\right)=N-1$. So, the solution set of the
linear equation $\nabla f(Z_{t})=0$ for this case can be described using one
single free variable. It is straightforward to check that
$\\{(z_{1},z_{2}\ldots z_{N}):z_{i}=\zeta\ \forall\ 1\leq i\leq m$ and
$z_{i}=1-\zeta\ \forall\ m+1\leq i\leq N$ for $\zeta\in[0,1]\\}$ is the
solution set of the equation in this case. This follows from the fact that for
a bipartite graph, $A$ is of the form

$\begin{pmatrix}{\mbox{\Large 0}}_{m\times m}&\vline&\begin{matrix}*&\\\
&*\end{matrix}\\\ \hline\cr\begin{matrix}*&\\\
&*\end{matrix}\par&\vline&{\mbox{\Large 0}}_{(N-m)\times(N-m)}\end{pmatrix},$

where the off-diagonal blocks are non-zero, and ${\mbox{\Large 0}}_{m\times
m}$ denotes a zero sub-matrix with $m$ rows and $m$ columns. As remarked
before, the analysis of FTNR with $p=1$ is essentially the same. $\Box$

######  Theorem 3.6.

Consider Pólya-type reinforcement on an undirected connected regular graph.
Then, as $t\rightarrow\infty$, we have the following.

  1. 1.

In the following cases, $Z_{t}$ converges almost surely to a random vector
$Z=(Z_{1},Z_{2}\ldots Z_{N})$ such that $Z_{i}=Z_{\infty}\ \forall\ 1\leq
i\leq m$ and $Z_{i}=1-Z_{\infty}\ \forall\ m+1\leq i\leq N$, where
$Z_{\infty}$ is a random variable supported on $[0,1]$.

    1. (a)

PTSR model with $0\leq p<1$.

    2. (b)

PTNR model with either $0<p\leq 1$, or if $p=0$ and the graph ${\mathcal{G}}$
is non-bipartite.

    3. (c)

PTSNR model for any $p\in[0,1]$.

  2. 2.

In the case of PTNR model with $p=0$ and the graph ${\mathcal{G}}$ bipartite,
$Z_{t}$ converges almost surely to a random vector
$Z^{\prime}=(Z^{\prime}_{1},Z^{\prime}_{2}\ldots Z^{\prime}_{N})$ such that
$Z^{\prime}_{i}=Z^{(1)}_{\infty}\ \forall\ 1\leq i\leq m$ and
$Z^{\prime}_{i}=Z^{(2)}_{\infty}\ \forall\ m+1\leq i\leq N$, where
$Z^{(1)}_{\infty}$ and $Z^{(2)}_{\infty}$ are random variables supported on
$[0,1]$.

PTSR with $p=1$ is equivalent to studying $N$ independent Pólya-type urns
where each one of them behaves like the urn studied in [5].

###### Proof.

Convergence follows from Lemma 3.4. We characterize the zeroes of $\nabla f$.
Note that from Theorem 3.10 of [20], we have that
$Rank\left(I-\frac{1}{d}\textbf{A}\right)=Rank\left(D-A\right)=N-1$ (since the
graph ${\mathcal{G}}$ is connected).

  1. 1.

Note that for Pólya-type reinforcement $\nabla f(Z_{t})$ is of the form
$Z_{t}g(\textbf{A})$, where $g$ is some function of A. We will first show that
in all three cases, $Rank(g(\textbf{A}))=N-1$.

    1. (a)

For the PTSR model, we get $\nabla
f(Z_{t})=(1-p)Z_{t}\left(I-\frac{1}{d}\textbf{A}\right)$( put
$\eta=1,\kappa=0$ and $\omega=1$ in the matrix $X$ in (3.3)) and
$Rank(g(\textbf{A}))=Rank\left((1-p)\left(I-\frac{1}{d}\textbf{A}\right)\right)=N-1$.

    2. (b)

For the PTNR model, $\nabla f(Z_{t})=Z_{t}\left(dI-
pA-\frac{1-p}{d}A^{2}\right)$. For $p=1$, $\nabla
f(Z_{t})=Z_{t}\left(dI-\textbf{A}\right)$ and the result follows from the same
argument as (1). For $0<p<1$, $dI-
pA-\frac{1-p}{d}\textbf{A}^{2}=\left(dI-\textbf{A}\right)\left(I+\frac{(1-p)}{d}\textbf{A}\right)$.
Since $\frac{1}{d}\textbf{A}$ is stochastic, $I+\frac{(1-p)}{d}\textbf{A}$ is
invertible. Hence,

$Rank\left(dI-p\textbf{A}-\frac{1-p}{d}\textbf{A}^{2}\right)=\
Rank(dI-\textbf{A})=N-1.$

For $p=0$, when the graph is non-bipartite, by Lemma 3.2 (2) we have that
$dI+\textbf{A}$ is invertible. Therefore,
$Rank(dI-\frac{1}{d}\textbf{A}^{2})=Rank\left(\left(dI+\textbf{A}\right)\left(I-\frac{\textbf{A}}{d}\right)\right)=Rank(I-\frac{\textbf{A}}{d})=N-1$.

    3. (c)

Finally, for the PTSNR model, we have

$\displaystyle\nabla f(Z_{t})$ $\displaystyle=$ $\displaystyle
Z_{t}\left((d+1-p)I-pA-\frac{(1-p)A}{d}-\frac{(1-p)A^{2}}{d}\right)$
$\displaystyle=$ $\displaystyle
Z_{t}\left(I-\frac{1}{d}\textbf{A}\right)\left[(1-p+d)I+(1-p)\textbf{A}\right].$

Since $Rank\left(I-\frac{1}{d}\textbf{A}\right)=N-1$, it is enough to show
that $(1-p+d)I+(1-p)\textbf{A}$ is a full rank matrix. Since
$\frac{1}{d}\textbf{A}$ is stochastic and
$\left|\frac{(1-p)d}{1-p+d}\right|<1$, we get that
$I+\frac{(1-p)d}{(1-p+d)}\frac{1}{d}\textbf{A}$ is invertible.

In all the three cases above, since $Rank(g(\textbf{A}))=N-1$, the solution
set of $\nabla f=0$ can be described using a single free variable. It is easy
to verify that the solution set of $\nabla f=0$ is given by
$\\{(z_{1},z_{2}\ldots z_{N}):z_{i}=\zeta\ \forall\ 1\leq i\leq N$ for
$\zeta\in[0,1]\\}$.

  2. 2.

For the second part of the theorem,
$dI-\frac{1}{d}\textbf{A}^{2}=\left(dI-\textbf{A}\right)\left(I+\frac{1}{d}\textbf{A}\right)$.
Since the graph is connected and bipartite we have that Rank
$(dI-\textbf{A})=$ Rank $\left(I+\frac{1}{d}\textbf{A}\right)=N-1$. By
Sylvester’s inequality, we also have that
$Rank\left(dI-\frac{1}{d}\textbf{A}^{2}\right)\geq N-1+N-1-N=N-2$. Hence, the
solution set of $\nabla f=0$ can be represented by at most two free variables.
Since setting $z_{i}=a\ \forall\ 1\leq i\leq m$ and $z_{i}=b\ \forall\ m+1\leq
i\leq N$ solves the equation, the most general solution of the equation is
given by $\\{(z_{1},z_{2}\ldots z_{N}):z_{i}=a\ \forall\ 1\leq i\leq m$ and
$z_{i}=b\ \forall\ m+1\leq i\leq N$ for $a,b\in[0,1]\\}$.

$\Box$

Thus, we have shown that $Z_{t}$ admits an almost sure limit but the limiting
fraction of balls of white colour in each urn depends on the underlying graph
structure and the reinforcement scheme. In particular, it is crucial whether
the dynamics is being studied on a bipartite or a non-bipartite graph. In the
next section, we study the convergence of $Z_{t}$ for the FTSR $p=0$ case on a
bipartite graph using martingale methods that allow us to drop the regularity
assumption in theorem 3.5.

##  4 Special Case: FTSR with $p=0$ on Bipartite Graphs

We now prove a convergence result for the FTSR model with $p=0$ on bipartite
graphs. The result proved in this section does not need the regularity
assumption as in theorem 3.5 but we assume the following.

  * (I)

$T_{0}(i)=T_{0}\ \forall 1\leq i\leq N$, that is, all urns have the same
number of balls at time $t=0$.

  * (II)

$\textbf{A}\textbf{D}^{-1}$ is diagonalizable. More precisely, let $P$ be an
$N\times N$ matrix such that $I+\textbf{A}\textbf{D}^{-1}=P\Lambda P^{-1}$,
with $\Lambda=Diag(\lambda_{1}\ldots\lambda_{N})$, where
$\lambda_{1},\dots,\lambda_{N}$ are the eigenvalues of
$I+\textbf{A}\textbf{D}^{-1}$.

Note that $\lambda_{i}\geq 0$ for all $1\leq i\leq N$. Since the underlying
graph is bipartite, $0$ is an eigenvalue, and from Lemma 3.2, we know that it
is a simple eigenvalue. Without loss of generality, assume that
$\lambda_{1}=0$. Define

$\theta:=\min\\{\lambda_{j}:\lambda_{j}\text{ is a non-zero eigenvalue of}\
I+\textbf{A}\textbf{D}^{-1}\\}.$ (4.1)

In the case of the FTSR model (I) implies that at any given time $t$, the
total number of balls in each urn is the same and we denote if by $T_{t}$.
Further, for FTSR $\omega_{i}=1$ for $i\in[N]$, and therefore we have the
following recursion.

$Z_{t+1}=\left(1-\frac{Cs}{T_{t+1}}\right)Z_{t}+\frac{C}{T_{t+1}}\chi_{t+1}.$
(4.2)

We show that the fraction of balls of either colour in urns placed on vertices
of $V$ (resp. $W$) converges to the same random limit almost surely. Define
$Z^{v}_{t}=(Z_{t}(1),Z_{t}(2)\ldots Z_{t}(m),0,0\ldots 0)$ and
$Z^{w}_{t}=(Z_{t}(m+1),Z_{t}(m+2)\ldots Z_{t}(N),0,0\ldots 0)$ as
$N$-dimensional vectors. For $0<k<N$, let $e_{k}\in\mathbb{R}^{N}$ be a row
vector with $1$ as the entry in the first $k$ positions and $0$ otherwise (in
the rest of the $N-k$ positions). Further, define

$\bar{d_{v}}=\sum\limits_{i\in
V}d_{i}=e_{m}\textbf{D}e_{m}^{\top},\bar{d_{w}}=\sum\limits_{i\in
W}d_{i}=(\mathbf{1}-e_{m})\textbf{D}(\mathbf{1}-e_{m})^{\top},\bar{d}=\sum\limits_{i\in[N]}d_{i}=\mathbf{1}D\mathbf{1}^{\top},$

$\bar{Z}_{t}=\dfrac{1}{\bar{d}}\sum\limits_{i\in[N]}d_{i}Z_{t}(i)=\dfrac{1}{\bar{d}}Z_{t}\textbf{D}\mathbf{1}^{\top},\
\bar{Z}^{v}_{t}=\dfrac{1}{\bar{d_{v}}}\sum\limits_{i\in
V}d_{i}Z_{t}(i)=\dfrac{1}{\bar{d_{v}}}Z_{t}\textbf{D}e_{m}^{\top}$

and

$\bar{Z}^{w}_{t}=\dfrac{1}{\bar{d_{w}}}\sum\limits_{i\in
W}d_{i}Z_{t}(i)=\dfrac{1}{\bar{d_{w}}}Z_{t}\textbf{D}(\mathbf{1}-e_{m})^{\top}.$

The main result of this section, stated in the following theorem shows that
urns on vertices in $V$ and $W$ synchronize almost surely respectively. More
precisely, we show that as $t\to\infty$,
$Z_{t}(i)-\bar{Z}^{v}_{t}\xrightarrow{a.s.}0$ for $i\in V$,
$Z_{t}(i)-\bar{Z}^{w}_{t}\xrightarrow{a.s.}0$ for $i\in W$, and that
$\bar{Z}_{t}^{v}+\bar{Z}_{t}^{w}\xrightarrow{a.s.}1$.

######  Theorem 4.1.

For the FTSR model with $p=0$ on a bipartite graph, under assumptions (I) and
(II), as $t\to\infty$,
$Z^{v}_{t}-\bar{Z}^{v}_{t}e_{m}\xrightarrow{a.s.}\mathbf{0}$ and
$Z^{w}_{t}-\bar{Z}^{w}_{t}(\mathbf{1}-e_{m})\xrightarrow{a.s.}\mathbf{0}$.

We first show that $\bar{Z}_{t}$ converges to a unique deterministic limit.

######  Theorem 4.2.

For the FTSR model with $p=0$ on a bipartite graph, under assumption (I),
$\bar{Z}_{t}\xrightarrow{a.s.}1/2$ and
$\bar{Z}_{t}^{v}+\bar{Z}_{t}^{w}\xrightarrow{a.s.}1$, as $t\to\infty$.

###### Proof.

We write a stochastic approximation scheme for $\bar{Z}_{t}$. Using (4.2),

$\displaystyle\bar{Z}_{t+1}$ $\displaystyle=$
$\displaystyle\frac{1}{\bar{d}}Z_{t+1}\textbf{D}\mathbf{1}^{\top}$ (4.3)
$\displaystyle=$
$\displaystyle\frac{1}{\bar{d}}\left(1-\frac{Cs}{T_{t+1}}\right)Z_{t}\textbf{D}\mathbf{1}^{\top}+\frac{C}{\bar{d}~{}T_{t+1}}\chi_{t+1}\textbf{D}\mathbf{1}^{\top}$
$\displaystyle=$
$\displaystyle\bar{Z}_{t}+\frac{C}{\bar{d}T_{t+1}}\left(\chi_{t+1}-sZ_{t}\right)\textbf{D}\mathbf{1}^{\top}$
$\displaystyle=$
$\displaystyle\bar{Z}_{t}+\frac{C}{\bar{d}~{}T_{t+1}}\left(E[\chi_{t+1}|\mbox{${\mathcal{F}}$}_{t}]-sZ_{t}\right)\textbf{D}\mathbf{1}^{\top}+\frac{C}{\bar{d}~{}T_{t+1}}\Delta\bar{M}_{t+1},$

where
$\Delta\bar{M}_{t+1}=(\chi_{t+1}-E[\chi_{t+1}|\mbox{${\mathcal{F}}$}_{t}])\textbf{D}\mathbf{1}^{\top}$
is a bounded martingale difference. Note that

$\displaystyle\left(E[\chi_{t+1}|\mbox{${\mathcal{F}}$}_{t}]-sZ_{t}\right)\textbf{D}\mathbf{1}^{\top}$
$\displaystyle=$ $\displaystyle
s(\mathbf{1}-Z_{t}\textbf{A}\textbf{D}^{-1})\textbf{D}\mathbf{1}^{\top}-\bar{d}s\bar{Z}_{t}$
(4.4) $\displaystyle=$ $\displaystyle
s(\bar{d}-Z_{t}\textbf{A}\mathbf{1}^{\top}-\bar{d}\bar{Z}_{t})$
$\displaystyle=$ $\displaystyle s\bar{d}(1-2\bar{Z}_{t}),$

since $\textbf{A}\mathbf{1}^{\top}=D\mathbf{1}^{\top}$. From the theory of
stochastic approximation, we know that the iterates of (4.3) converge almost
surely to the stable zeroes of $\dot{x}_{t}=s\bar{d}(1-2x_{t})$. Thus,
$\bar{Z}_{t}\to 1/2$ almost surely. Since the graph is bipartite, we have that
$\bar{d_{v}}=\bar{d_{w}}=\frac{\bar{d}}{2}$. Hence,
$\bar{Z}_{t}^{v}+\bar{Z}_{t}^{w}=2\bar{Z}_{t}\to 1$ almost surely. $\Box$

We now prove a useful lemma for the moments of certain linear functions of
$\\{Z_{t}(i)\\}_{i\in[N]}$. Let $\mathcal{M}_{N,m}$ be the space of all
$N\times N$ matrices with the property that for each column of the matrix, the
sum of the first $m$ terms of that column is equal to the sum of the last
$N-m$ terms. That is,

$\mathcal{M}_{N,m}=\\{M\in\mathbb{R}^{N\times
N}:e_{m}M=(\mathbf{1}-e_{m})M\\},$

where $\mathbb{R}^{N\times N}$ denotes the set of all $N\times N$ matrices
over $\mathbb{R}$.

######  Lemma 4.3.

Let $\Phi_{t}=Z_{t}Q$ such that $Q\in\mathcal{M}_{N,m}$. The following hold
under assumptions (I) and (II).

  1. 1.

Suppose that, in addition, $Q$ is such that $e_{m}Q=\mathbf{0}$. Then,
$E[\Phi_{t}]\sim\frac{1}{t^{\theta}}$, where $\theta$ is as defined in (4.1).

  2. 2.

$Var(\Phi_{t})\sim\frac{1}{t^{\epsilon}}$ for some $\epsilon>0$.

###### Proof.

  1. 1.

From (4.2) we get

$\displaystyle E[Z_{t+1}|\mbox{${\mathcal{F}}$}_{t}]$ $\displaystyle=$
$\displaystyle
Z_{t}\left(1-\frac{Cs}{T_{t+1}}\right)+\frac{Cs(\mathbf{1}-Z_{t}\textbf{A}\textbf{D}^{-1})}{T_{t+1}}$
(4.5) $\displaystyle=$ $\displaystyle
Z_{t}\left(I-\frac{Cs}{T_{t+1}}(I+\textbf{A}\textbf{D}^{-1})\right)+\frac{Cs\mathbf{1}}{T_{t+1}}.$

This implies

$E[\Phi_{t+1}]=Z_{0}\left(\prod_{i=0}^{t}H_{i}\right)Q+\sum_{i=0}^{t}\frac{Cs\mathbf{1}}{T_{i+1}}\left(\prod_{j=i+1}^{t}H_{j}\right)Q,$
(4.6)

where $H_{j}=I-\frac{Cs}{T_{j+1}}(I+\textbf{A}\textbf{D}^{-1})$ for $j\geq 1$.
Now, using $\mathbf{1}\textbf{A}\textbf{D}^{-1}=\mathbf{1}$, we get that the
second term in (4.6) is zero. Indeed,

$\displaystyle\frac{Cs\mathbf{1}}{T_{i+1}}\left[\prod_{j=i+1}^{t}\left(I-\frac{Cs}{T_{j+1}}(I+\textbf{A}\textbf{D}^{-1})\right)\right]Q$
$\displaystyle=$
$\displaystyle\frac{Cs}{T_{i+1}}\left(\mathbf{1}-\frac{Cs}{T_{i+2}}(\mathbf{1}+\mathbf{1})\right)\left[\prod_{j=i+2}^{t}\left(I-\frac{Cs}{T_{j+1}}(I+\textbf{A}\textbf{D}^{-1})\right)\right]Q$
$\displaystyle=$
$\displaystyle\frac{Cs}{T_{i+1}}\left(1-\frac{2Cs}{T_{i+2}}\right)\mathbf{1}\left[\prod_{j=i+2}^{t}\left(I-\frac{Cs}{T_{j+1}}(I+\textbf{A}\textbf{D}^{-1})\right)\right]Q$
$\displaystyle=$
$\displaystyle\frac{Cs}{T_{i+1}}\left[\prod_{j=i+1}^{t}\left(1-\frac{2Cs}{T_{j+1}}\right)\right]\mathbf{1}Q$
$\displaystyle=$ $\displaystyle\mathbf{0}.$

Using the diagonalization of $I+\textbf{A}\textbf{D}^{-1}$, the first term in
(4.6), can be rewritten as
$Z_{0}P\left[\prod_{i=0}^{t}\left(I-\frac{Cs}{T_{i+1}}\Lambda\right)\right]P^{-1}Q$.
Using Euler’s approximation we have that, for $2\leq j\leq N$,
$\prod_{i=0}^{t}\left(1-\frac{Cs}{T_{i+1}}\lambda_{j}\right)\sim
t^{-\lambda_{j}}$. Hence, as $t\rightarrow\infty$

$\prod_{i=0}^{t}\left(I-\frac{Cs}{T_{i+1}}\Lambda\right)\to
e_{1}^{\top}e_{1}=\begin{pmatrix}1&0&0&\ldots&0\\\ 0&0&0&\ldots&0\\\
\vdots&\vdots&\vdots&\vdots&\vdots\\\ 0&0&0&\ldots&0\\\ \end{pmatrix}.$ (4.7)

Since the first row of $P^{-1}$ is the left eigenvector of the matrix
$I+\textbf{A}\textbf{D}^{-1}$ corresponding to the eigenvalue $0$ and is of
the form $\alpha(\mathbf{1}-2e_{m})$ for some $\alpha\in\mathbb{R}$, we get
that

$e_{1}^{\top}e_{1}P^{-1}Q=\mathbf{0}_{N\times N},$ (4.8)

because $Q\in\mathcal{M}_{N,m}$. Thus, $E[\Phi_{t}]\to\mathbf{0}$ as
$t\to\infty$, with rate $\frac{1}{t^{\theta}}$, (since
$\prod_{i=0}^{t}\left(1-\frac{Cs}{T_{i+1}}\lambda_{j}\right)\sim
t^{-\lambda_{j}}$ for $j\geq 2$).

  2. 2.

From (4.2), we get

$Var(Z_{t+1}|{\mathcal{F}}_{t})=\frac{C^{2}}{T^{2}_{t+1}}Var(\chi_{t+1}|{\mathcal{F}}_{t}).$

Note that for $1\leq j\leq N$,
$E[Var(\chi_{t+1}(j)|{\mathcal{F}}_{t})]=E[Var(Y_{t+1}(j)|{\mathcal{F}}_{t})]$
and using the conditional distribution of $Y_{t+1}(j)$ from (2.1) we get

$\displaystyle E[Var(Y_{t+1}(j)|{\mathcal{F}}_{t})]$ $\displaystyle=$
$\displaystyle\frac{s(s-1)\sum_{l\in N(j)}E[{Z_{t}(l)}^{2}]+s\sum_{l\in
N(j)}E[{Z_{t}(l)}]}{d_{j}}$ (4.9) $\displaystyle-\left(\frac{s\sum_{l\in
N(j)}E[{Z_{t}(l)}]}{d_{j}}\right)^{2}\eqqcolon\gamma_{t}(j).$

Thus, we get

$E[Var(Z_{t+1}|{\mathcal{F}}_{t})]=\frac{C^{2}}{{T_{t+1}}^{2}}\begin{pmatrix}\gamma_{t}(1)&&\\\
&\ddots&\\\
&&\gamma_{t}(N)\end{pmatrix}\eqqcolon\frac{C^{2}}{{T_{t+1}}^{2}}G_{t}.$ (4.10)

From (4.5) and (4.10), we get

$\displaystyle Var(Z_{t+1})$ $\displaystyle=$ $\displaystyle
E[Var(Z_{t+1}|{\mathcal{F}}_{t})]+Var(E[Z_{t+1}|\mbox{${\mathcal{F}}$}_{t}])$
$\displaystyle=$
$\displaystyle\frac{C^{2}}{{T_{t+1}}^{2}}G_{t}+H_{t}^{\top}Var(Z_{t})H_{t},$

where $H_{t}=I-\frac{Cs}{T_{t+1}}(I+\textbf{A}\textbf{D}^{-1})$. We have

$\displaystyle Var(\Phi_{t+1})$ $\displaystyle=$ $\displaystyle
Q^{\top}Var(Z_{t+1})Q$ $\displaystyle=$ $\displaystyle
Q^{\top}\left(\frac{C^{2}}{{T_{t+1}}^{2}}G_{t}+H_{t}^{\top}Var(Z_{t})H_{t}\right)Q$
$\displaystyle=$ $\displaystyle
Q^{\top}\left[\left(\prod_{i=0}^{t-1}H_{t-i}^{\top}\right)Var(Z_{1})\left(\prod_{i=1}^{t}H_{i}\right)+\sum\limits_{k=1}^{t}\frac{C^{2}}{T_{k+1}^{2}}\left(\prod_{i=0}^{t-k-1}H_{t-i}^{\top}\right)G_{k}\left(\prod_{i=k+1}^{t}H_{i}\right)\right]Q.$

Since $Var(Z_{1})=\frac{C^{2}}{T_{1}^{2}}G(0)$, we have

$Var(\Phi_{t+1})=Q^{\top}\left[\sum\limits_{k=0}^{t}\frac{C^{2}}{T_{k+1}^{2}}\left(\prod_{i=0}^{t-k-1}H_{t-i}^{\top}\right)G_{k}\left(\prod_{i=k+1}^{t}H_{i}\right)\right]Q.$

Using diagonalization of $I+\textbf{A}\textbf{D}^{-1}$, we get

$\displaystyle Var(\Phi_{t+1})$ $\displaystyle=$ $\displaystyle
Q^{\top}\left[\sum\limits_{k=0}^{t}\frac{C^{2}}{T_{k+1}^{2}}(P^{-1})^{\top}\left(\prod_{i=0}^{t-k-1}\left(I-\frac{Cs}{T_{t-i+1}}\Lambda\right)\right)P^{\top}G_{k}P\prod_{i=k+1}^{t}\left(I-\frac{Cs}{T_{i+1}}\Lambda\right)P^{-1}\right]Q$
$\displaystyle=$ $\displaystyle Q^{\top}(P^{-1})^{\top}\Delta_{t}P^{-1}Q,$

where
$\Delta_{t}\coloneqq\sum\limits_{k=0}^{t}\frac{C^{2}}{T_{k+1}^{2}}\left[\prod_{i=0}^{t-k-1}\left(I-\frac{Cs}{T_{t-i+1}}\Lambda\right)\right]P^{\top}G_{k}P\prod_{i=k+1}^{t}\left(I-\frac{Cs}{T_{i+1}}\Lambda\right)$.

For $(p,q)\neq(1,1)$, the $(p,q)^{th}$ element of $\Delta_{t}$ is given by

$\displaystyle\Delta_{t}(p,q)$ $\displaystyle=$
$\displaystyle\sum\limits_{k=0}^{t}\frac{C^{2}}{T_{k+1}^{2}}\left[\prod_{i=0}^{t-k-1}\left(1-\frac{Cs}{T_{t-i+1}}\lambda_{p}\right)\right]s_{k}(p,q)\prod_{i=k+1}^{t}\left(1-\frac{Cs}{T_{i+1}}\lambda_{q}\right),$

where $s_{k}(p,q)$ is the $(p,q)^{th}$ element of $P^{\top}G_{k}P$. Again, by
using the Euler’s approximation, we get

$\displaystyle\Delta_{t}(p,q)$ $\displaystyle\leq$ $\displaystyle
C^{\prime}t^{-(\lambda_{p}+\lambda_{q})}\sum\limits_{k=1}^{t}\frac{1}{k^{2-(\lambda_{p}+\lambda_{q})}}$
(4.11) $\displaystyle=$
$\displaystyle\begin{cases}\mathcal{O}\left(\frac{1}{t}\right)&\text{ if
}\lambda_{p}+\lambda_{q}>1,\\\ \mathcal{O}\left(\frac{\log t}{t}\right)&\text{
if }\lambda_{p}+\lambda_{q}=1,\\\
\mathcal{O}\left(t^{-(\lambda_{p}+\lambda_{q})}\right)&\text{ if
}\lambda_{p}+\lambda_{q}<1.\end{cases}$

Since $\Delta_{t}(1,1)$ converges to
$\sum\limits_{k=0}^{\infty}\frac{C^{2}}{T_{k+1}^{2}}s_{k}(p,q)$, there exists
a constant $c$ such that $\Delta_{t}\to ce_{1}^{\top}e_{1}$ as $t\to\infty$.
Since $e_{1}^{\top}e_{1}P^{-1}Q=\mathbf{0}_{N\times N}$, $Var(\Phi_{t+1})$
converges to zero at rates given in (4.11). This concludes the proof.

$\Box$

We remark that the expression for $\gamma_{t}(j)$ as defined in (4.9) in the
proof above is different in case of sampling without replacement. However,
since it does not affect the final result, we skip the details for the
sampling without replacement case and do not state the explicit expression of
$\gamma_{t}(j)$ for that case.

Before we show that the urns synchronize almost surely on each partition, we
will show that the fraction of balls of either colour in each urn attains an
almost sure limit. Using the convergence of quasi-martingales (see [21]), we
get the following.

######  Proposition 4.4.

$Z_{t}$ admits an almost sure limit.

###### Proof.

From (4.3) and (4.4), we get
$E[\bar{Z}_{t+1}|\mbox{${\mathcal{F}}$}_{t}]=\bar{Z}_{t}+\frac{2Cs}{T_{t+1}}(1/2-\bar{Z}_{t})$.
This implies,

$\displaystyle E[\bar{Z}_{t+1}-1/2]$ $\displaystyle=$ $\displaystyle
E[\bar{Z}_{t}]-1/2+\frac{2Cs}{T_{t+1}}(1/2-E[\bar{Z}_{t}])$ $\displaystyle=$
$\displaystyle\prod_{k=0}^{t}\left(1-\frac{2Cs}{T_{k+1}}\right)(\bar{Z}_{0}-1/2)$
$\displaystyle\sim$ $\displaystyle\frac{1}{t^{2}}(\bar{Z}_{0}-1/2).$

Hence,

$\left|E[\bar{Z}_{t}-1/2]\right|\sim\frac{1}{t^{2}}(\left|Z_{0}-1/2\right|).$
(4.12)

Using (4.5), we have,

$\displaystyle\sum_{t=0}^{\infty}E[\|E[Z_{t+1}|\mbox{${\mathcal{F}}$}_{t}]-Z_{t}\|]$
$\displaystyle=$ $\displaystyle
Cs\sum_{t=0}^{\infty}\frac{E[\|\mathbf{1}-Z_{t}(I+\textbf{A}\textbf{D}^{-1})\|]}{T_{t+1}}$
$\displaystyle=$ $\displaystyle
Cs\sum_{t=0}^{\infty}\frac{E[\|\mathbf{1}-\bar{Z}_{t}\mathbf{1}(I+\textbf{A}\textbf{D}^{-1})-(Z_{t}-\bar{Z}_{t}\mathbf{1})(I+\textbf{A}\textbf{D}^{-1})\|]}{T_{t+1}}$
$\displaystyle\leq$ $\displaystyle
Cs\sum_{t=0}^{\infty}\left\\{\frac{E[\|\mathbf{1}-2\bar{Z}_{t}\mathbf{1}\|+E[\|(Z_{t}-\bar{Z}_{t}\mathbf{1})(I+\textbf{A}\textbf{D}^{-1})\|]}{T_{t+1}}\right\\}$
$\displaystyle\leq$ $\displaystyle
Cs\left\\{\sum_{t=0}^{\infty}\frac{E[\|\mathbf{1}-2\bar{Z}_{t}\mathbf{1}\|}{T_{t+1}}+\sum_{t=0}^{\infty}\frac{E[\|(Z_{t}-\bar{Z}_{t}\mathbf{1})(I+\textbf{A}\textbf{D}^{-1})\|]}{T_{t+1}}\right\\}$
$\displaystyle\leq$ $\displaystyle
Cs\left\\{\sum_{t=0}^{\infty}\frac{2\|1\|E[|\bar{Z}_{t}-1/2|]}{T_{t+1}}+\sum_{t=0}^{\infty}\frac{E[\|(\bar{Z}_{t}\mathbf{1}-Z_{t})(I+\textbf{A}\textbf{D}^{-1})\|]}{T_{t+1}}\right\\}$
$\displaystyle\leq$ $\displaystyle
Cs\left\\{2\|1\|\left[\sum_{t=0}^{\infty}\frac{E[|\bar{Z}_{t}-E[\bar{Z}_{t}]|]}{T_{t+1}}+\sum_{t=0}^{\infty}\frac{E[|E[\bar{Z}_{t}-1/2]|]}{T_{t+1}}\right]\right.$
$\displaystyle+\sum_{t=0}^{\infty}\frac{E[\|(\bar{Z}_{t}\mathbf{1}-Z_{t}-E[\bar{Z}_{t}\mathbf{1}-Z_{t}])(I+\textbf{A}\textbf{D}^{-1})\|]}{T_{t+1}}$
$\displaystyle+\left.\sum_{t=0}^{\infty}\frac{E[\|E[(\bar{Z}_{t}\mathbf{1}-Z_{t})(I+\textbf{A}\textbf{D}^{-1})]\|]}{T_{t+1}}\right\\}$
$\displaystyle\leq$ $\displaystyle
Cs\left\\{2\|1\|\left[\sum_{t=0}^{\infty}\frac{E[|\bar{Z}_{t}-E[\bar{Z}_{t}]|]}{T_{t+1}}+\sum_{t=0}^{\infty}\frac{|E[\bar{Z}_{t}-1/2]|}{T_{t+1}}\right]\right.$
$\displaystyle+\sum_{t=0}^{\infty}\frac{E[\|(\bar{Z}_{t}\mathbf{1}-Z_{t}-E[\bar{Z}_{t}\mathbf{1}-Z_{t}])(I+\textbf{A}\textbf{D}^{-1})\|]}{T_{t+1}}$
$\displaystyle+\left.\sum_{t=0}^{\infty}\frac{\|E[(\bar{Z}_{t}\mathbf{1}-Z_{t})(I+\textbf{A}\textbf{D}^{-1})]\|}{T_{t+1}}\right\\}$
$\displaystyle\leq$ $\displaystyle
Cs\left\\{2\|1\|\left[\sum_{t=0}^{\infty}\frac{\sqrt{Var(\bar{Z}_{t})}}{T_{t+1}}+\sum_{t=0}^{\infty}\frac{|E[\bar{Z}_{t}-1/2]|}{T_{t+1}}\right]\right.$
$\displaystyle+\sum_{t=0}^{\infty}\frac{\sqrt{\operatorname{Tr}(Var((\bar{Z}_{t}\mathbf{1}-Z_{t})(I+\textbf{A}\textbf{D}^{-1})))}}{T_{t+1}}$
$\displaystyle+\left.\sum_{t=0}^{\infty}\frac{\|E[(\bar{Z}_{t}\mathbf{1}-Z_{t})(I+\textbf{A}\textbf{D}^{-1})]\|}{T_{t+1}}\right\\}.$

Note that $\bar{Z}_{t}=\frac{Z_{t}D{\mathbf{1}}^{T}}{\bar{d}}$and
$(\bar{Z}_{t}\mathbf{1}-Z_{t})(I+\textbf{A}\textbf{D}^{-1})=Z_{t}\left(\frac{D{\mathbf{1}}^{T}\mathbf{1}}{\bar{d}}-I\right)(I+\textbf{A}\textbf{D}^{-1})=Z_{t}\left[\frac{2D{\mathbf{1}}^{T}\mathbf{1}}{\bar{d}}-I-\textbf{A}\textbf{D}^{-1}\right]$.
Since
$\frac{2D{\mathbf{1}}^{T}\mathbf{1}}{\bar{d}}-(I+\textbf{A}\textbf{D}^{-1}),\frac{D{\mathbf{1}}^{T}\mathbf{1}}{\bar{d}}\in\mathcal{M}_{N,m}$
and
$e_{m}\left(\frac{2D{\mathbf{1}}^{T}\mathbf{1}}{\bar{d}}-(I+\textbf{A}\textbf{D}^{-1})\right)=\frac{2d_{v}\mathbf{1}}{\bar{d}}-e_{m}-(\mathbf{1}-e_{m})=\mathbf{0}$
( since $d_{v}=\frac{\bar{d}}{2}$), therefore by Lemma 4.3 we get that

$\sum_{t=0}^{\infty}\frac{\|(E[\bar{Z}_{t}\mathbf{1}-Z_{t}])(I+\textbf{A}\textbf{D}^{-1})\|}{T_{t+1}}<\infty,\sum_{t=0}^{\infty}\frac{\sqrt{Var(\bar{Z}_{t})}}{T_{t+1}}<\infty\text{
and }$
$\sum_{t=0}^{\infty}\frac{\sqrt{\operatorname{Tr}(Var((\bar{Z}_{t}\mathbf{1}-Z_{t})(I+\textbf{A}\textbf{D}^{-1})))}}{T_{t+1}}<\infty.$

Using (4.12) we also have that
$\sum_{t=0}^{\infty}\frac{|E[\bar{Z}_{t}-1/2]|}{T_{t+1}}<\infty$. Thus,
$\sum_{t=0}^{\infty}E[\|E[Z_{t+1}|\mbox{${\mathcal{F}}$}_{t}]-Z_{t}\|]<\infty$.
That is, $\\{Z_{t}\\}_{t\geq 0}$ is a Quasi martingale and therefore $Z_{t}$
has an almost sure limit. $\Box$

We are now ready to prove the main synchronization result for FTSR on
bipartite graphs. Let $I_{m}$ be the diagonal matrix containing $1$ at the
first $m$ diagonal positions, and $0$ elsewhere.

###### Proof of Theorem 4.1.

Let $\Phi_{t}^{v}=Z_{t}^{v}-\bar{Z}^{t}_{v}e_{m}=Z_{t}M$ where
$M=I_{m}-\frac{De_{m}^{T}e_{m}}{\bar{d_{v}}}$. Note that
$e_{m}M=e_{m}\left(I_{m}-\frac{De_{m}^{T}e_{m}}{\bar{d_{v}}}\right)=e_{m}-e_{m}=\mathbf{0}$,
and $M\in\mathcal{M}_{N,m}$. Using Lemma 4.3 above, we get that
$Var(\Phi_{t}^{v})\rightarrow\mathbf{0}$ and
$E[\Phi_{t}^{v}]\rightarrow\mathbf{0}$, which implies that
$Z^{v}_{t}-\bar{Z}^{v}_{t}e_{m}\xrightarrow{\mathcal{L}^{2}}\mathbf{0}$. Since
$Z_{t}$ is a bounded random vector and since we showed above that it has an
almost sure limit, we have that $Z_{t}\xrightarrow{a.s}Z_{\infty}$, where
$Z_{\infty}$ is finite almost surely. Since ${\|\cdot\|}^{2}$ is a continuous
function on $\mathbb{R}^{N}$, using continuous mapping theorem we have that
$\|\Phi_{t}^{v}\|^{2}\xrightarrow{a.s}{\|Z_{\infty}M\|}^{2}$. But we already
know that $E[\|\Phi_{t}^{v}\|^{2}]\rightarrow 0$, therefore
$E[{\|Z_{\infty}M\|}^{2}]=0$ (by bounded convergence theorem). This means that
$Z_{\infty}M=\mathbf{0}$ almost surely. That is,
$\Phi_{t}^{v}=Z^{v}_{t}-\bar{Z}^{v}_{t}e_{m}\xrightarrow{a.s.}\mathbf{0}$.
Similarly,
$Z^{w}_{t}-\bar{Z}^{w}_{t}(\mathbf{1}-e_{m})\xrightarrow{a.s.}\mathbf{0}$.
$\Box$

We remark that the PTSR case can also be treated in the same way and the
condition of regularity can be dropped. In particular, the following
synchronization result holds.

######  Theorem 4.5.

For the PTSR model with $0\leq p<1$ under assumptions (I) and (II),
$Z_{t}-\bar{Z_{t}}\mathbf{1}\xrightarrow{a.s.}\mathbf{0}$ as $t\to\infty$.

The proof involves the same arguments as above. Recalling (4.2) and using
$E[\chi_{t+1}|\mbox{${\mathcal{F}}$}_{t}]=sZ_{t}(pI+(1-p)\textbf{A}\textbf{D}^{-1})$
for PTSR model, we get

$\displaystyle E[Z_{t+1}|\mbox{${\mathcal{F}}$}_{t}]$ $\displaystyle=$
$\displaystyle
Z_{t}\left(1-\frac{Cs}{T_{t+1}}\right)+\frac{CE[\chi_{t+1}|\mbox{${\mathcal{F}}$}_{t}]}{T_{t+1}}$
$\displaystyle=$ $\displaystyle
Z_{t}\left(I-\frac{Cs(1-p)}{T_{t+1}}(I-\textbf{A}\textbf{D}^{-1})\right),$

which is a much simpler recursion compared to (4.5) above, and hence a result
analogous to Lemma 4.3 can be proved with ease, using similar arguments as
above. We can also show that $Z_{t}$ admits an almost sure limit using the
Quasi-martingale argument. The rest of the proof is similar.

##  5 Fluctuation Results

We now state and prove a fluctuation result for FTSR and FTNR models on a
specific class of graphs. We also assume that the sampling is done with
replacement.

######  Theorem 5.1.

Consider the Friedman-type reinforcement scheme, and assume that the sampling
is done with replacement. Assume that $Z_{t}$ has a unique convergent point
$1/2\mathbf{1}$. Let $\rho$ be the smallest eigenvalue of the matrix
$p\textbf{A}\textbf{D}^{-1}+(1-p)(\textbf{A}\textbf{D}^{-1})^{2}+I$ for the
FTNR case, and the smallest eigenvalue of
$(1+p)I+(1-p)\textbf{A}\textbf{D}^{-1}$ for the FTSR case. Further, assume
that the matrix $\textbf{A}\textbf{D}^{-1}$ is symmetric, with
$\textbf{A}\textbf{D}^{-1}=U\Lambda^{\prime}{U}^{-1}$ Then, we have

  1. 1.

When $\rho>\frac{1}{2}$,
$\sqrt{t}\left(Z_{t}-\frac{1}{2}\mathbf{1}\right)\xrightarrow{d}\mathcal{N}\left(\mathbf{0},\Sigma\right)$,
where $\Sigma$ equals
$\frac{1}{4s}I+\frac{p}{2s}\textbf{A}\textbf{D}^{-1}+\frac{1-p}{2s}(\textbf{A}\textbf{D}^{-1})^{2}$
for the FTNR case and equals
$\frac{1+2p}{4s}I+\frac{1-p}{2s}\textbf{A}\textbf{D}^{-1}$ for the FTSR case.

  2. 2.

Let $\lambda^{\prime}_{1},\lambda^{\prime}_{2}\ldots\lambda^{\prime}_{N}$ be
the eigenvalues of
$I+2p\textbf{A}\textbf{D}^{-1}+2(1-p)(\textbf{A}\textbf{D}^{-1})^{2}$ and
$\mu_{1},\mu_{2}\ldots\mu_{N}$ be the eigenvalues of
$(2p+1)I+2(1-p)\textbf{A}\textbf{D}^{-1}$. Let $a_{1},a_{2}\ldots a_{q}$ and
$b_{1},b_{2}\ldots b_{r}$ be indices such that
$\lambda^{\prime}_{a_{1}}=\lambda^{\prime}_{a_{2}}=\ldots=\lambda^{\prime}_{a_{q}}=\mu_{b_{1}}=\mu_{b_{2}}=\ldots=\mu_{b_{r}}=0$.
When $\rho=\frac{1}{2}$, we have

$\sqrt{\frac{t}{\log
t}}\left(Z_{t}-\frac{1}{2}\mathbf{1}\right)\xrightarrow{d}\mathcal{N}\left(\mathbf{0},\widetilde{\Sigma}\right),$

where $\widetilde{\Sigma}=\frac{1}{4s}UBU^{-1}$ where the matrix $B$ is a
diagonal matrix, defined as follows for FTSR and FTNR cases. For the FTNR
case, $B$ is such that
$B_{a_{1},a_{1}}=B_{a_{2},a_{2}}=\ldots=B_{a_{q},a_{q}}=1$. For the FTSR case,
it is such that $B_{b_{1},b_{1}}=B_{b_{2},b_{2}}=\ldots=B_{b_{r},b_{r}}=1$.
The rest of the diagonal terms are zero in both cases.

######  Remark 1.

From Theorem 3.3 we know the exact conditions for $Z_{t}$ to have the unique
limit $\frac{1}{2}\mathbf{1}$. Also note that using an argument similar to
that in Lemma 3.2, we get that the eigenvalues of matrices
$(1+p)I+(1-p)\textbf{A}\textbf{D}^{-1}$ and
$p\textbf{A}\textbf{D}^{-1}+(1-p)(\textbf{A}\textbf{D}^{-1})^{2}+I$ are all
real. Further, note that $\Lambda^{\prime}=\Lambda-I$, where
$\Lambda=Diag(\lambda_{1},\dots,\lambda_{N})$ is as defined in the earlier
sections.

###### Proof.

We use Theorems 1.1 and 2.1 from [22]. From Lemma 3.1, recall that

$\frac{\partial h}{\partial
z}=\begin{cases}-(I+p\textbf{A}\textbf{D}^{-1}+(1-p)(\textbf{A}\textbf{D}^{-1})^{2})&\
\text{for the FTNR case, }\\\ -((1+p)I+(1-p)\textbf{A}\textbf{D}^{-1})&\
\text{for the FTSR case.}\\\ \end{cases}$

Define $\Gamma\coloneqq\lim\limits_{t\to\infty}\frac{1}{s^{2}}E[{\Delta
M_{t+1}}^{T}\Delta M_{t+1}|{\mathcal{F}}_{t}]$, where $\\{\Delta
M_{t}\\}_{t\geq 0}$ is the martingale-difference sequence as defined in
Section 2 . Note that $\Gamma$ is the same for both FTSR and FTNR models since
it only depends on sampling, and not reinforcement.

Now, for $i\neq j$, since the event of sampling from urn $i$ is independent of
sampling from urn $j$, we have

$(E[{\Delta M_{t+1}}^{T}\Delta
M_{t+1}|{\mathcal{F}}_{t}])_{i,j}=E[(\chi_{t+1}(i)-E[\chi_{t+1}(i)|{\mathcal{F}}_{t}])(\chi_{t+1}(j)-E[\chi_{t+1}(j)|{\mathcal{F}}_{t}])|{\mathcal{F}}_{t}]=0.$

For $1\leq i\leq N$,

$\displaystyle\lim_{t\to\infty}(E[{\Delta M_{t+1}}^{T}\Delta
M_{t+1}|\mathcal{F}_{t}])_{i,i}$ $\displaystyle=$
$\displaystyle\lim_{t\to\infty}E[(Y_{t+1}(i))^{2}|{\mathcal{F}}_{t}]+s^{2}\lim_{t\to\infty}\left(pZ_{t}(i)+\frac{1-p}{d_{i}}\sum\limits_{l\in
N(i)}Z_{t}(l)\right)^{2}$
$\displaystyle-2s\lim_{t\to\infty}\left(pZ_{t}(i)+\frac{1-p}{d_{i}}\sum\limits_{l\in
N(i)}Z_{t}(l)\right)\times\lim_{t\to\infty}E[Y_{t+1}(i)|{\mathcal{F}}_{t}].$
(5.1)

We have,
$\lim\limits_{t\to\infty}E[Y_{t+1}(i)|{\mathcal{F}}_{t}]=\lim\limits_{t\to\infty}s\left(pZ_{t}(i)+\frac{1-p}{d_{i}}\sum\limits_{l\in
N(i)}Z_{t}(l)\right)=\frac{s}{2}$. Further,

$\displaystyle E[(Y_{t+1}(i))^{2}|{\mathcal{F}}_{t}]$
$\displaystyle=\left\\{s(s-1)(Z_{t}(i)^{2}+sZ_{t}(i)\right\\}p+\frac{1-p}{d_{i}}\left\\{s(s-1)\sum\limits_{l\in
N(i)}(Z_{t}(l))^{2}+s\sum\limits_{l\in N(i)}Z_{t}(l)\right\\}.$

This gives,
$\lim_{t\to\infty}E[(Y_{t+1}(i))^{2}|{\mathcal{F}}_{t}]=\frac{s(s+1)}{4}$.
Now, substituting these in (5), we get

$\lim_{t\to\infty}\left(E[{\Delta M_{t+1}}^{T}\Delta
M_{t+1}|{\mathcal{F}}_{t}]\right)_{i,i}=\frac{s(s+1)}{4}+\frac{s^{2}}{4}-2s\left(\frac{s}{2}\right)\left(\frac{1}{2}\right)=\frac{s}{4}.$

Thus,

$\Gamma=\frac{s}{4s^{2}}I_{N\times N}=\frac{1}{4s}I_{N\times N}.$

For the FTNR case, using
$\textbf{A}\textbf{D}^{-1}=U{\Lambda}^{\prime}{U}^{-1}$ and the symmetry of
$\textbf{A}\textbf{D}^{-1}$, for $\rho>1/2$ we get

$\displaystyle\Sigma$ $\displaystyle=$
$\displaystyle\int_{0}^{\infty}{(e^{-(-\frac{\partial h}{\partial
z}(\frac{1}{2}\mathbf{1})-\frac{I}{2})u})}^{T}\Gamma e^{-(-\frac{\partial
h}{\partial z}(\frac{1}{2}\mathbf{1})-\frac{I}{2})u}du$ $\displaystyle=$
$\displaystyle\frac{1}{4s}\int_{0}^{\infty}{(e^{-(p\textbf{A}\textbf{D}^{-1}+(1-p)(\textbf{A}\textbf{D}^{-1})^{2}+\frac{I}{2})u})^{T}(e^{-(p\textbf{A}\textbf{D}^{-1}+(1-p)(\textbf{A}\textbf{D}^{-1})^{2}+\frac{I}{2})u})}\,du\
$ $\displaystyle=$
$\displaystyle\frac{1}{4s}\int_{0}^{\infty}U{(e^{-(p\Lambda^{\prime}+(1-p)(\Lambda^{\prime})^{2}+\frac{I}{2})u}){U}^{-1}{U}(e^{-(p\Lambda^{\prime}+(1-p)(\Lambda^{\prime})^{2}+\frac{I}{2})u})}{U}^{-1}\,du\
$ $\displaystyle=$
$\displaystyle\frac{1}{4s}U\int_{0}^{\infty}{(e^{-(2p\Lambda^{\prime}+2(1-p){\Lambda^{\prime}}^{2}+I)u})}\,du\
\ {U}^{-1}$ $\displaystyle=$
$\displaystyle\frac{1}{4s}U(2p\Lambda^{\prime}+2(1-p){\Lambda^{\prime}}^{2}+I){U}^{-1}$
$\displaystyle=$
$\displaystyle\frac{1}{4s}I+\frac{p}{2s}\textbf{A}\textbf{D}^{-1}+\frac{1-p}{2s}(\textbf{A}\textbf{D}^{-1})^{2}.$

A similar computation gives us the corresponding $\Sigma$ for the FTSR case.

For $\rho=\frac{1}{2}$, note that in the case of the FTNR model, since the
smallest eigenvalue of the matrix
$I+p\textbf{A}\textbf{D}^{-1}+(1-p)(\textbf{A}\textbf{D}^{-1})^{2}$ is equal
to $1/2$, we have that the eigenvalues of the matrix
$I+2p\textbf{A}\textbf{D}^{-1}+2(1-p)(\textbf{A}\textbf{D}^{-1})^{2}$ are all
non-negative. Hence,

$\displaystyle\widetilde{\Sigma}$ $\displaystyle=$
$\displaystyle\lim_{t\to\infty}\frac{1}{\log t}\int_{0}^{\log
t}{(e^{-(-\frac{\partial h}{\partial
z}(\frac{1}{2}\mathbf{1})-\frac{I}{2})u})}^{T}\Gamma e^{-(-\frac{\partial
h}{\partial z}(\frac{1}{2}\mathbf{1})-\frac{I}{2})u}\,du\ $ $\displaystyle=$
$\displaystyle\lim_{t\to\infty}\frac{1}{4s\log t}U\int_{0}^{\log
t}{(e^{-(2p\Lambda^{\prime}+2(1-p){\Lambda^{\prime}}^{2}+I)u})}\,du{U}^{-1}.$

Since, for $y>0$, $\lim_{t\to\infty}\frac{1}{\log t}\int_{0}^{\log
t}{e^{-yu}}\,du=\lim_{t\to\infty}\frac{1-t^{-y}}{y\log t}=0$ and since
$\lim_{t\to\infty}\frac{1}{\log t}\int_{0}^{\log t}{e^{-yu}}\,du=1$ for $y=0$,
the second part of the statement of the theorem clearly holds for the FTNR
case. For the FTSR case, the eigenvalues of
$(2p+1)I+2(1-p)\textbf{A}\textbf{D}^{-1}$ are non-negative and the rest of the
computation is similar. $\Box$

A similar result can also be obtained for the FTSNR model (albeit with a few
extra assumptions than those used below), but we desist from explicitly
stating it here.

##  6 Friedman-type Urns on Directed Graphs

The sampling and reinforcement dynamics described in section 2 has a natural
analogue on directed graphs. In this case, for each urn, balls are sampled
balls from the in-neighbourhood of that urn and the reinforcement is done (to
self, out-neighbours or both) depending on the configuration of the drawn
sample. We define the in-neighbours and out-neighbours of the $i^{th}$ vertex
as $V_{i}^{in}\coloneqq\\{v:v\to i\\}$ and $V_{i}^{out}\coloneqq\\{v:i\to
v\\}$, where $u\to w$ denotes the existence of a directed edge from $u$ to
$w$. Further, we define the in-degree of $i$ as $d_{i}^{in}=|V_{i}^{in}|$. The
$(i,j)^{th}$ entry of the adjacency matrix is given by $\mathbb{I}_{\\{i\to
j\\}}$. We assume that all the vertices have a non-zero in-degree and that
there are no self-loops.

We extend the convergence result in Theorem 3.3 to the case of weakly
connected directed graphs with no self-loops. Assume that the directed graph
$\mathcal{G}$ consists of $r$ strongly connected components. Without loss of
generality (after a renumbering of vertices, if required), assume that these
components $\mathcal{G}_{1},\mathcal{G}_{2}\ldots\mathcal{G}_{r}$ are such
that for any directed edge $(l,m)$ between the components, if
$l\in\mathcal{G}_{i}$ and $m\in\mathcal{G}_{j}$ for $1\leq i,j\leq r$, then
$i<j$. Since the graph is weakly connected, for every component
$\mathcal{G}_{j}$ with $j>1$, there exists a $k<j$ such that there is at least
one directed edge from a vertex in $G_{k}$ to a vertex in $\mathcal{G}_{j}$. A
similar recursion for $Z_{t}$ can be written with D replaced by
$\textbf{D}_{in}$, the diagonal matrix consisting of in-degrees of each
vertex/urn on the diagonal. We restrict our discussion to Friedman-type
reinforcement. Similar to (2.6), for the corresponding stochastic
approximation scheme on directed graphs, we have

$h(Z_{t})=\begin{cases}\mathbf{1}-Z_{t}((1+p)I+(1-p)\textbf{A}\textbf{D}_{in}^{-1})&\text{for
the FTSR model,}\\\
\mathbf{1}-Z_{t}(I+p\textbf{A}\textbf{D}_{in}^{-1}+(1-p)(\textbf{A}\textbf{D}_{in}^{-1})^{2})&\text{for
the FTNR model,}\\\
\mathbf{1}-Z_{t}\left[(pI+(1-p)\textbf{A}\textbf{D}_{in}^{-1})(\textbf{A}+I)(I+\textbf{D}_{in})^{-1}+I\right]&\text{for
the FTSNR model.}\end{cases}$ (6.1)

To obtain conditions for convergence, we classify cases for which the matrix
$-\nabla h(Z_{t})$ is invertible and the corresponding ODE $\dot{z}=h(z)$ has
a unique stable limit point. For $1\leq i\leq r$, define $\textbf{A}_{i}$ and
$\textbf{D}_{in}^{(i)}$ as the adjacency matrix and the in-degree matrix
restricted to $\mathcal{G}_{i}$. Given the above decomposition of the graph,
$-\nabla h(Z_{t})$ becomes an upper triangular block diagonal matrix of the
form

$\begin{pmatrix}h_{1}(\textbf{A}_{1},\textbf{D}_{in}^{(1)})&*&*&\ldots&\ldots&*\\\
0&h_{2}(\textbf{A}_{2},\textbf{D}_{in}^{(2)})&*&*&\ldots&*\\\
0&0&h_{3}(\textbf{A}_{3},\textbf{D}_{in}^{(3)})&*&\vdots&\vdots&\\\
\vdots&\vdots&0&\ddots&\ldots&*\\\
0&0&\vdots&0&h_{r-1}(\textbf{A}_{r-1},\textbf{D}_{in}^{(r-1)})&*&\\\
0&0&\ldots&0&0&h_{r}(\textbf{A}_{r},\textbf{D}_{in}^{(r)})\end{pmatrix}$

where, for $1\leq i\leq r$, $h_{i}(\textbf{A}_{i},\textbf{D}_{in}^{(i)})$ is a
matrix that is a function of $A_{i}$ and $\textbf{D}_{in}^{(i)}$ and depends
on the type of reinforcement. For instance, for the FTSR model,
$h_{1}(\textbf{A}_{1},\textbf{D}_{in}^{(1)})=(1+p)I+(1-p)\textbf{A}_{1}({\textbf{D}_{in}^{(1)}})^{-1}$.
Note that for $2\leq i\leq r$, $h_{i}(\textbf{A}_{i},\textbf{D}_{in}^{(i)})-I$
is a strictly (column) sub-stochastic, irreducible matrix (because there is at
least one incoming edge to the strongly connected component
$\mathcal{G}_{i}$), hence $h_{i}(\textbf{A}_{i},\textbf{D}_{in}^{(i)})$ is
invertible for $2\leq i\leq r$. Thus, the invertibility of
$h_{1}(\textbf{A}_{1},\textbf{D}_{in}^{(1)})$ is sufficient for the
invertibility of $-\nabla h(Z_{t})$. We now state and prove a result analogous
to Theorem 3.3.

######  Theorem 6.1.

For the Friedman-type reinforcement scheme and for a weakly connected directed
graph (with a positive in-degree for each vertex) with $r$ strongly connected
components $\mathcal{G}_{1},\mathcal{G}_{2}\ldots\mathcal{G}_{r}$ which are
arranged as above (so that $\mathcal{G}_{1}$ has no incoming edges from any
other component), as $t\rightarrow\infty$,
$Z_{t}\rightarrow\frac{1}{2}\mathbf{1}$ almost surely whenever one of the
following holds.

  1. 1.

FTSR model

    1. (a)

$0<p\leq 1$.

    2. (b)

$p=0$ and $\mathcal{G}_{1}$ is a directed cycle of odd length.

  2. 2.

FTNR model

    1. (a)

$0<p<1$.

    2. (b)

$p=1$ and $\mathcal{G}_{1}$ is a directed cycle of odd length.

  3. 3.

The model is FTSNR, regardless of the value of $p$.

###### Proof.

The proofs for 1.(a) and 2.(a) are identically like before since we only
require stochasticity of $\textbf{A}{\textbf{D}_{in}}^{-1}$ to prove these.
For 1.(b) and 2.(b) we need to show that the matrix
$\textbf{D}_{in}+\textbf{A}$ is invertible for a directed cycle of odd length.
For this case, for a column vector $v=(v_{1},v_{2}\ldots v_{N})^{T}$
satisfying $(\textbf{D}_{in}+\textbf{A})v=\mathbf{0}$, we have $v_{N}+v_{1}=0$
and $v_{i}+v_{i+1}=0$ for $1\leq i\leq N-1$. When $N$ is odd, this set of
equations is satisfied only if $v=0$. For the third part, the proof for
$0<p\leq 1$ also follows like before. For $p=0$, we make use of the structure
of the matrix $-\nabla h(Z_{t})$ as shown above. We first show that
$\textbf{A}\textbf{D}_{in}^{-1}\textbf{A}+\textbf{A}\textbf{D}_{in}^{-1}$ is
aperiodic for a strongly connected graph.

Let the length of the directed cycle starting and ending at the vertex
labelled $1$ be denoted by $\gamma$ ($\gamma\geq 2$ since self-loops are not
allowed). If $\gamma=2$, the matrix above is aperiodic since
($\textbf{A}\textbf{D}_{in}^{-1}\textbf{A}+\textbf{A}\textbf{D}_{in}^{-1})_{1,1}\geq(\textbf{A}\textbf{D}_{in}^{-1}\textbf{A})_{1,1}>0$.
For $\gamma\geq 3$, first note that
($\textbf{A}\textbf{D}_{in}^{-1}\textbf{A}+\textbf{A}\textbf{D}_{in}^{-1})^{\gamma}_{1,1}\geq(\textbf{A}\textbf{D}_{in}^{-1})^{\gamma}_{1,1}>0$.
Let the cycle in question be denoted by $1\rightarrow\ldots x\rightarrow
y\rightarrow 1$. Now, $(\textbf{A}\textbf{D}_{in}^{-1})^{\gamma-2}_{1,x}>0$
and $(\textbf{A}\textbf{D}_{in}^{-1}\textbf{A})_{x,1}>0$. Hence,
($\textbf{A}\textbf{D}_{in}^{-1}\textbf{A}+\textbf{A}\textbf{D}_{in}^{-1})^{\gamma-1}_{1,1}\geq(\textbf{A}\textbf{D}_{in}^{-1})^{\gamma-2}_{1,x}(\textbf{A}\textbf{D}_{in}^{-1}\textbf{A})_{x,1}>0$,
and we are done with this case also. We use this fact to conclude the
invertibility of
$h_{1}(\textbf{A}_{1},\textbf{D}_{in}^{(1)})=(\textbf{A}_{1}(\textbf{D}_{in}^{(1)})^{-1})(\textbf{A}_{1}+I)(I+\textbf{D}_{in}^{(1)})^{-1}+I$
for the FTSNR case, which further shows that $-\nabla h(Z_{t})$ is also
invertible for this case.

$\Box$

Note that for the case of FTSR, when $p=0$ (or FTNR with $p=1$) the class of
graphs for which the matrix $\textbf{D}_{in}+\textbf{A}$ is full rank is, in
fact, much larger. For example, $\textbf{D}_{in}+\textbf{A}$ is invertible for
the directed graph shown in Figure 1. So, for a graph $\mathcal{G}$ with
$\mathcal{G}_{1}$ as in Figure 1, $Z_{t}\rightarrow\frac{1}{2}\mathbf{1}$
almost surely as $t\rightarrow\infty$.

$1$$2$$3$$4$$5$ Figure 1: A strongly connected directed graph on 5 vertices
containing an odd cycle $2\to 3\to 5\to 2$. It can be easily verified that the
corresponding matrix $\textbf{D}_{in}+\textbf{A}$ is invertible for this
graph.

We leave a complete classification of the nature of limit points for the case
of directed graphs for future work. In general, the limiting behaviour can be
very complicated and it is very different from urns on undirected graphs. We
illustrate this in the example below.

We look at an example where $h_{1}(\textbf{A}_{1},\textbf{D}_{in}^{(1)})$ (and
therefore $-\nabla h(Z_{t})$) is not invertible. In order to prove a
convergence result for this example, we make use of the method developed in
Section 4.

######  Example 6.2.

Consider the graph in Figure 2 with reinforcement type FTSR and $p=0$. Assume
that $T_{0}^{i}=T_{0}\ \forall 1\leq i\leq 5$. Then,
$T_{t}^{i}=T_{t}^{1}\eqqcolon T_{t}\ \forall\ 1\leq i\leq 5,t\geq 0$.

$1$$2$$3$$4$$5$ Figure 2: A directed graph on 5 vertices. Example 6.2
discusses the FTSR model with $p=0$ on this graph. Observe that if the
direction of the edge between nodes 3 and 1 is reversed, the resulting graph
falls into the category of graphs that are covered under Theorem 6.1.

For the graph in Figure 2, we can use neither of the stochastic approximation
theorems used earlier to conclude convergence, because neither is the limit
point unique nor can we write $h$ function as the gradient of some function
since the graph is not regular and the adjacency matrix is also not symmetric.
However, on solving $h(Z_{t})=\mathbf{0}$ for this example, we get
$Z_{t}=(3a-1,2-3a,1-a,a,1-a)$ for $a\in\left[\frac{1}{3},\frac{2}{3}\right]$.
Motivated by this, we will use arguments similar to those in Section 4 to
conclude that $Z_{t}$ converges almost surely to a random vector
$Z=(Z_{1},Z_{2}\ldots Z_{5})$, where $Z_{1}=3Z_{\infty}-1$,
$Z_{2}=2-3Z_{\infty}$, $Z_{3}=1-Z_{\infty}$, $Z_{4}=Z_{\infty}$ and
$Z_{5}=1-Z_{\infty}$, where $Z_{\infty}$ is a random variable supported on
$\left[\frac{1}{3},\frac{2}{3}\right]$

It suffices to show that $Z_{t}$ admits an almost sure limit and that
$Z_{t}(1)+Z_{t}(2)\xrightarrow{a.s.}1,Z_{t}(3)+Z_{t}(4)\xrightarrow{a.s.}1,Z_{t}(4)+Z_{t}(5)\xrightarrow{a.s.}1$,
and $Z_{t}(1)+3Z_{t}(3)\xrightarrow{a.s.}2$, which is equivalent to showing
$Z_{t}M\xrightarrow{a.s.}(1,1,1,1,1)$ where

$M=\begin{pmatrix}1&0&0&\frac{1}{2}&0\\\ 1&0&0&0&0\\\ 0&1&0&\frac{3}{2}&0\\\
0&1&1&0&1\\\ 0&0&1&0&1\\\ \end{pmatrix}.$

Consider the stochastic matrix $\textbf{A}\textbf{D}_{in}^{-1}$. Note that
$\mbox{\bf v}=(1,1,0,0,0)^{\top}$ is an eigenvector of
$\textbf{A}\textbf{D}_{in}^{-1}$ corresponding to the eigenvalue $1$. Let
$\tilde{Z_{t}}=Z_{t}\mbox{\bf v}=Z_{t}\textbf{A}\textbf{D}_{in}^{-1}\mbox{\bf
v}$. Then, recalling 4.2, we have

$\displaystyle\tilde{Z}_{t+1}$ $\displaystyle=Z_{t+1}\mbox{\bf v}$
$\displaystyle=\left(\left(1-\frac{Cs}{T_{t+1}}\right)Z_{t}+\frac{C}{T_{t+1}}\chi_{t+1}\right)\mbox{\bf
v}$ $\displaystyle=\tilde{Z_{t}}+\frac{C}{T_{t+1}}\left(\chi_{t+1}\mbox{\bf
v}-s\tilde{Z_{t}}\right)$
$\displaystyle=\tilde{Z_{t}}+\frac{C}{T_{t+1}}\left((\chi_{t+1}-E[\chi_{t+1}|\mbox{${\mathcal{F}}$}_{t}])\mbox{\bf
v}+E[\chi_{t+1}|\mbox{${\mathcal{F}}$}_{t}]\mbox{\bf v}-s\tilde{Z_{t}}\right)$
$\displaystyle=\tilde{Z_{t}}+\frac{C}{T_{t+1}}\left((\chi_{t+1}-E[\chi_{t+1}|\mbox{${\mathcal{F}}$}_{t}])\mbox{\bf
v}+s(\mathbf{1}-Z_{t}\textbf{A}\textbf{D}_{in}^{-1})\mbox{\bf
v}-s\tilde{Z_{t}}\right)$
$\displaystyle=\tilde{Z_{t}}+\frac{C}{T_{t+1}}\left(\Delta
M_{t}+s(\mathbf{1}\mbox{\bf v}-2\tilde{Z_{t}})\right),$ (6.2)

where $\Delta
M_{t}=(\chi_{t+1}-E[\chi_{t+1}|\mbox{${\mathcal{F}}$}_{t}])\mbox{\bf v}$ is
the martingale difference, and we have used
$E[\chi_{t+1}|\mbox{${\mathcal{F}}$}_{t}]=s(\mathbf{1}-Z_{t}\textbf{A}\textbf{D}_{in}^{-1})$.
Using stochastic approximation theory, we get $Z_{t}\mbox{\bf
v}\xrightarrow{a.s.}1$ (that is, $Z_{t}(1)+Z_{t}(2)\xrightarrow{a.s.}1$).
Hence, showing $Z_{t}M\xrightarrow{a.s.}\mathbf{1}$ is equivalent to showing
$Z_{t}Q\xrightarrow{a.s.}0$, where $Q=M-\mbox{\bf v}\mathbf{1}$. It can be
verified that for this example, $0$ is a simple eigenvalue of the matrix
$I+\textbf{A}\textbf{D}_{in}^{-1}$, and that this matrix is diagonalizable, so
we can compute matrices $P$ and $\Lambda$ such that
$I+\textbf{A}\textbf{D}_{in}^{-1}=P\Lambda P^{-1}$. Like before, we have
numbered vertices of the graph in such a way that the first diagonal element
of $\Lambda$ is $0$. Recall from the proof of Lemma 4.3 that in the case of
FTSR, when $p=0$, for a matrix $M$, if we have that $e_{1}^{T}e_{1}P^{-1}M=0$,
we can concude that $Var(Z_{t}M)\sim\frac{1}{t^{\epsilon}}$ for some
$\epsilon>0$. If we also have that $\mathbf{1}M=0$, then we can additionally
conclude that $E[Z_{t}M]\sim\frac{1}{t^{\epsilon^{\prime}}}$ for some
$\epsilon^{\prime}>0$. Now, for this example we have

$Q=\begin{pmatrix}0&-1&-1&\frac{-1}{2}&-1\\\ 0&-1&-1&-1&-1\\\
0&1&0&\frac{3}{2}&0\\\ 0&1&1&0&1\\\ 0&0&1&0&1\\\ \end{pmatrix},\quad
I+\textbf{A}\textbf{D}_{in}^{-1}=\begin{pmatrix}1&1&\frac{1}{2}&0&0\\\
1&1&0&0&0\\\ 0&0&1&1&0\\\ 0&0&0&1&1\\\ 0&0&\frac{1}{2}&0&1\\\ \end{pmatrix},$

and

$e_{1}^{T}e_{1}P^{-1}Q=\begin{pmatrix}1&0&0&0&0\\\ 0&0&0&0&0\\\ 0&0&0&0&0\\\
0&0&0&0&0\\\ 0&0&0&0&0\\\
\end{pmatrix}\begin{pmatrix}-\frac{1}{2}&\frac{1}{2}&\frac{1}{6}&-\frac{1}{6}&\frac{1}{6}\\\
*&*&*&*&*\\\ \vdots&\vdots&\vdots&\vdots&\vdots\\\ *&*&*&*&*\\\
\end{pmatrix}\begin{pmatrix}0&-1&-1&\frac{-1}{2}&-1\\\ 0&-1&-1&-1&-1\\\
0&1&0&\frac{3}{2}&0\\\ 0&1&1&0&1\\\ 0&0&1&0&1\\\
\end{pmatrix}=\mathbf{0}_{N\times N}.$

Clearly $\mathbf{1}Q=\mathbf{0}$. So,
$Z_{t}Q\xrightarrow{\mathcal{L}^{2}}\mathbf{0}$. Also, note that using (6.2)
we have

$\displaystyle E[\tilde{Z}_{t+1}-1]$ $\displaystyle=$ $\displaystyle
E[\tilde{Z}_{t}]-1+\frac{2Cs}{T_{t+1}}(1-E[\tilde{Z}_{t}])$ $\displaystyle=$
$\displaystyle\prod_{k=0}^{t}\left(1-\frac{2Cs}{T_{k+1}}\right)(\tilde{Z}_{0}-1)$
$\displaystyle\sim$ $\displaystyle\frac{1}{t^{2}}(\tilde{Z}_{0}-1).$

Hence,

$\left|E[\tilde{Z}_{t}-1]\right|\sim\frac{1}{t^{2}}\left(\left|\tilde{Z}_{0}-1\right|\right).$
(6.3)

We now show that $Z_{t}$ attains an almost sure limit. Indeed, we have

$\displaystyle\sum_{t=0}^{\infty}E[\|E[Z_{t+1}|\mbox{${\mathcal{F}}$}_{t}]-Z_{t}\|]$
$\displaystyle=$ $\displaystyle
Cs\sum_{t=0}^{\infty}\frac{E[\|\mathbf{1}-Z_{t}(I+\textbf{A}\textbf{D}^{-1})\|]}{T_{t+1}}$
$\displaystyle=$ $\displaystyle
Cs\sum_{t=0}^{\infty}\frac{E[\|\mathbf{1}-\frac{\tilde{Z}_{t}}{2}\mathbf{1}(I+\textbf{A}\textbf{D}^{-1})-(Z_{t}-\frac{\tilde{Z}_{t}}{2}\mathbf{1})(I+\textbf{A}\textbf{D}^{-1})\|]}{T_{t+1}}$
$\displaystyle\leq$ $\displaystyle
Cs\sum_{t=0}^{\infty}\left\\{\frac{E[\|\mathbf{1}-\tilde{Z}_{t}\mathbf{1}\|+E[\|(Z_{t}-\frac{\tilde{Z}_{t}}{2}\mathbf{1})(I+\textbf{A}\textbf{D}^{-1})\|]}{T_{t+1}}\right\\}$
$\displaystyle\leq$ $\displaystyle
Cs\left\\{\|1\|\left[\sum_{t=0}^{\infty}\frac{\sqrt{Var(\tilde{Z}_{t})}}{T_{t+1}}+\sum_{t=0}^{\infty}\frac{|E[\tilde{Z}_{t}-1]|}{T_{t+1}}\right]\right.$
$\displaystyle+\sum_{t=0}^{\infty}\frac{\sqrt{\operatorname{Tr}(Var((\frac{\tilde{Z}_{t}}{2}\mathbf{1}-Z_{t})(I+\textbf{A}\textbf{D}^{-1})))}}{T_{t+1}}$
$\displaystyle+\left.\sum_{t=0}^{\infty}\frac{\|E[(\frac{\tilde{Z}_{t}}{2}\mathbf{1}-Z_{t})(I+\textbf{A}\textbf{D}^{-1})]\|}{T_{t+1}}\right\\},$

where we have skipped some of the intermediate steps because they follow like
before. Now, note that
$(\frac{\tilde{Z}_{t}}{2}\mathbf{1}-Z_{t})(I+\textbf{A}\textbf{D}^{-1})=Z_{t}Q^{\prime}$,
where $Q^{\prime}=(\frac{v}{2}\mathbf{1}-I)(I+\textbf{A}\textbf{D}^{-1})$. We
have

$Q^{\prime}=\begin{pmatrix}0&0&-\frac{1}{2}&-1&-1\\\ 0&0&-1&-1&-1\\\
0&0&1&1&0\\\ 0&0&0&1&1\\\ 0&0&\frac{1}{2}&0&1\\\ \end{pmatrix}$

and

$e_{1}^{T}e_{1}P^{-1}Q^{\prime}=\begin{pmatrix}1&0&0&0&0\\\ 0&0&0&0&0\\\
0&0&0&0&0\\\ 0&0&0&0&0\\\ 0&0&0&0&0\\\
\end{pmatrix}\begin{pmatrix}-\frac{1}{2}&\frac{1}{2}&\frac{1}{6}&-\frac{1}{6}&\frac{1}{6}\\\
*&*&*&*&*\\\ \vdots&\vdots&\vdots&\vdots&\vdots\\\ *&*&*&*&*\\\
\end{pmatrix}\begin{pmatrix}0&0&-\frac{1}{2}&-1&-1\\\ 0&0&-1&-1&-1\\\
0&0&1&1&0\\\ 0&0&0&1&1\\\ 0&0&\frac{1}{2}&0&1\\\
\end{pmatrix}=\mathbf{0}_{N\times N}.$

Clearly $\mathbf{1}Q^{\prime}=0$. So,

$\sum_{t=0}^{\infty}\frac{\|E[(\frac{\tilde{Z}_{t}}{2}\mathbf{1}-Z_{t})(I+\textbf{A}\textbf{D}^{-1})]\|}{T_{t+1}}<\infty\text{
and
}\sum_{t=0}^{\infty}\frac{\sqrt{\operatorname{Tr}(Var((\frac{\tilde{Z}_{t}}{2}\mathbf{1}-Z_{t})(I+\textbf{A}\textbf{D}^{-1})))}}{T_{t+1}}<\infty.$

Also, the matrix $v\mathbf{1}$ satisfies
$e_{1}^{T}e_{1}P^{-1}v\mathbf{1}=\mathbf{0}_{N\times N}$. So,
$\sum_{t=0}^{\infty}\frac{\sqrt{Var(\tilde{Z}_{t})}}{T_{t+1}}<\infty$.
Combining all this with (6.3), we have
$\sum_{t=0}^{\infty}\frac{|E[\tilde{Z}_{t}-1]|}{T_{t+1}}<\infty$. So, $Z_{t}$
admits an almost sure limit. The rest of the arguments are identical to those
in the proof of Theorem 4.1. Hence, we have that
$Z_{t}Q\xrightarrow{a.s.}\mathbf{0}$.

##  Appendix A Appendix

###  A.1 Stochastic Approximation Theory

Stochastic approximation has been used extensively in recent times to analyze
the behaviour of urn processes (for instance, see [1, 23]). A recursion of the
form

$x_{t+1}=x_{t}+a_{t+1}\left(h(x_{t})+\Delta
M_{t+1}+\epsilon_{t+1}\right),\qquad\forall t\geq 0$ (A.1)

is called a stochastic approximation scheme if it satisfies the following
conditions.

  1. 1.

$\sum_{t\geq 1}a_{t}=\infty$ and $\sum_{t\geq 1}a_{t}^{2}<\infty$.

  2. 2.

$h:\mathbb{R}^{d}\to\mathbb{R}^{d}$ is a Lipschitz function.

  3. 3.

There exists a constant $\delta>0$, such that $E\left[\|\Delta
M_{t+1}\|^{2}|\mbox{${\mathcal{F}}$}_{t}\right]\leq\delta(1+\|x_{t}\|^{2})$,
almost surely $\forall t\geq 0$, where
$\mbox{${\mathcal{F}}$}_{t}={\sigma(x_{0},M_{1},\ldots,M_{t})}$.

  4. 4.

$\sup_{t\geq 0}\|x_{t}\|<\infty$, almost surely.

  5. 5.

$\\{\epsilon_{t}\\}_{t\geq 1}$ is a bounded sequence such that
$\epsilon_{t}\to 0$, almost surely as $t\to\infty$.

The main result (see Chapter 2 of [24]) implies that the iterates of the
recursion for $x_{t}\in\mathbb{R}^{d}$ satisfying the conditions (1)-(5) above
converge almost surely to the stable limit points of the solutions of an
ordinary differential equation given by $\dot{x}_{t}=h(x_{t})$. Recall that
$x^{*}$ is a stable limit point of the O.D.E. $\dot{x}_{t}=h(x_{t})$ if the
real parts of all the eigenvalues of the Jacobian $\frac{\partial h}{\partial
z}(x^{*})$ are non-positive.

Further, suppose there exists a differentiable function
$f:\mathbb{R}^{d}\to\mathbb{R}$ such that $h=-\nabla f$. The stochastic
approximation scheme can then be written as

$x_{t+1}=x_{t}-a_{t+1}(\nabla f(x_{t})+\beta_{t}),$ (A.2)

where $\\{\beta_{t}\\}_{t\geq 0}$ is an $\mathbb{R}^{d}$\- valued stochastic
process. This recursion is also known as the stochastic gradient descent. We
now state the main convergence theorem from [19]. the Let $S$ be the set of
stationary points of $f(\cdot)$, i.e., $S=\\{x\in\mathbb{R}^{d}:\nabla
f(x)=0\\}$. Sequence $\\{\gamma_{t}\\}_{t\geq 0}$ is defined by $\gamma_{0}=0$
and $\gamma_{t}=\sum_{i=0}^{t-1}a_{i}$. For $t\in(0,\infty)$ and $n\geq 0$,
$\tilde{a}(n,t)$ is the integer defined as $\tilde{a}(n,t)=\max\\{k\geq
n:\gamma_{k}-\gamma_{n}\leq t\\}$. Then,

######  Theorem A.1 (Theorem 2.1 [19]).

Suppose the following conditions hold.

  1. 1.

$\lim_{t\to\infty}a_{t}=0$ and $\sum_{t=0}^{\infty}a_{t}=\infty$.

  2. 2.

There exists a real number $r\in(1,\infty)$ such that on $\\{\sup_{t\geq
0}\left|\left|x_{t}\right|\right|<\infty\\}$,

$P\left(\limsup_{n\to\infty}\max\limits_{n\leq
k<\tilde{a}(n,1)}\Big{\|}\sum_{i=n}^{k}a_{i}{\gamma_{i}}^{r}\beta_{i}\Big{\|}<\infty\right)=1.$

  3. 3.

For any compact set $Q\subset\mathbb{R}^{d}$ and any $c\in f(Q)$, there exist
real numbers $\delta_{Q,c}\in(0,1],$ $M_{Q,c}\in[1,\infty)$ such that

$\left|f(x)-c\right|\leq M_{Q,c}{\left|\left|\nabla
f(x)\right|\right|}^{\mu_{Q,c}}$

for all $x\in Q$ satisfying $\left|f(x)-c\right|\leq\delta_{Q,c}.$

Then, $x^{*}=\lim_{t\to\infty}x_{t}$ exists and satisfies $\nabla
f(x^{*})=\mathbf{0}$ with probability $1$ on $\\{\sup_{t\geq
0}\|x_{t}\|<\infty\\}$.

## Acknowledgment

The first author was supported by IISER Mohali doctoral fellowship. The second
author was supported in part by DST-INSPIRE fellowship and SERB-MATRICS grant.

## References

  * [1] Nabil Lasmar, Cécile Mailler, and Olfa Selmi.  Multiple drawing multi-colour urns by stochastic approximation.  J. Appl. Probab., 55(1):254–281, 2018.
  * [2] Antar Bandyopadhyay and Debleena Thacker.  Pólya urn schemes with infinitely many colors.  Bernoulli, 23(4B):3243–3267, 2017.
  * [3] Markus Kuba and Hosam M. Mahmoud.  Two-color balanced affine urn models with multiple drawings.  Adv. in Appl. Math., 90:1–26, 2017.
  * [4] Aguech Rafik, Lasmar Nabil, and Selmi Olfa.  A generalized urn with multiple drawing and random addition.  Ann. Inst. Statist. Math., 71(2):389–408, 2019.
  * [5] May-Ru Chen and Ching-Zong Wei.  A new urn model.  J. Appl. Probab., 42(4):964–976, 2005.
  * [6] Markus Kuba, Hosam Mahmoud, and Alois Panholzer.  Analysis of a generalized Friedman’s urn with multiple drawings.  Discrete Appl. Math., 161(18):2968–2984, 2013.
  * [7] Paolo Dai Pra, Pierre-Yves Louis, and Ida G. Minelli.  Synchronization via interacting reinforcement.  J. Appl. Probab., 51(2):556–568, 2014.
  * [8] Irene Crimaldi, Paolo Dai Pra, and Ida Germana Minelli.  Fluctuation theorems for synchronization of interacting pólya’s urns.  Stochastic processes and their applications, 126(3):930–947, 2016\.
  * [9] Giacomo Aletti and Andrea Ghiglietti.  Interacting generalized friedman’s urn systems.  Stochastic Processes and their Applications, 127(8):2650–2678, 2017\.
  * [10] Neeraja Sahasrabudhe.  Synchronization and fluctuation theorems for interacting friedman urns.  Journal of Applied Probability, 53(4):1221–1239, 2016.
  * [11] Gursharn Kaur and Neeraja Sahasrabudhe.  Interacting urns on a finite directed graph.  Journal of Applied Probability, 60(1):166–188, 2023.
  * [12] Jun Chen and Cyrille Lucas.  A generalized Pólya’s urn with graph based interactions: convergence at linearity.  Electron. Commun. Probab., 19:no. 67, 13, 2014.
  * [13] Michel Benaïm, Itai Benjamini, Jun Chen, and Yuri Lima.  A generalized Pólya’s urn with graph based interactions.  Random Structures Algorithms, 46(4):614–634, 2015.
  * [14] Anna Maria Paganoni and Piercesare Secchi.  Interacting reinforced-urn systems.  Adv. in Appl. Probab., 36(3):791–804, 2004.
  * [15] Irene Crimaldi, Paolo Dai Pra, Pierre-Yves Louis, and Ida G Minelli.  Synchronization and functional central limit theorems for interacting reinforced random walks.  Stochastic processes and their applications, 129(1):70–101, 2019\.
  * [16] Giacomo Aletti, Irene Crimaldi, and Andrea Ghiglietti.  Synchronization of reinforced stochastic processes with a network-based interaction.  2017\.
  * [17] Giacomo Aletti, Irene Crimaldi, and Andrea Ghiglietti.  Networks of reinforced stochastic processes: asymptotics for the empirical means.  2019\.
  * [18] Xiao-Dong Zhang and Jiong-Sheng Li.  The Laplacian spectrum of a mixed graph.  Linear Algebra Appl., 353:11–20, 2002.
  * [19] Vladislav B. Tadić.  Convergence and convergence rate of stochastic gradient search in the case of multiple and non-isolated extrema.  Stochastic Process. Appl., 125(5):1715–1755, 2015.
  * [20] Anne Marsden.  Eigenvalues of the laplacian and their relationship to the connectedness of a graph.  University of Chicago, REU, 2013.
  * [21] Michel Métivier.  Semimartingales.  In Semimartingales. de Gruyter, 2011.
  * [22] Li-Xin Zhang.  Central limit theorems of a recursive stochastic algorithm with applications to adaptive designs.  Ann. Appl. Probab., 26(6):3630–3658, 2016.
  * [23] Sophie Laruelle and Gilles Pagès.  Addendum and corrigendum to” randomized urn models revisited using stochastic approximation”.  The Annals of Applied Probability, pages 1296–1298, 2017.
  * [24] Vivek S. Borkar.  Stochastic approximation: a dynamical systems viewpoint.  Cambridge University Press ; Hindustan Book Agency, Cambridge, UK : New York : New Delhi, 2008.  OCLC: ocn231580915.