# On the Internal Stability of Diffusively Coupled Multi-Agent Systems
and the Dangers of Cancel Culture111Supported by the Israel Science Foundation
(grants 2000 /17 and 2285 /20).

Gal Barkai<EMAIL_ADDRESS>Leonid Mirkin
<EMAIL_ADDRESS>Daniel Zelazo<EMAIL_ADDRESS>Faculty of
Mechanical Engineering, Technion—IIT, Haifa 3200003, Israel  Faculty of
Aerospace Engineering, Technion—IIT, Haifa 3200003, Israel

###### Abstract

We study internal stability in the context of diffusively-coupled control
architectures, common in multi-agent systems (i.e. the celebrated consensus
protocol), for linear time-invariant agents. We derive a condition under which
the system can not be stabilized by any controller from that class. In the
finite-dimensional case the condition states that diffusive controllers cannot
stabilize agents that share common unstable dynamics, directions included.
This class always contains the group of homogeneous unstable agents, like
integrators. We argue that the underlying reason is intrinsic cancellations of
unstable agent dynamics by such controllers, even static ones, where
directional properties play a key role. The intrinsic lack of internal
stability explains the notorious behavior of some distributed control
protocols when affected by measurement noise or exogenous disturbances.

###### keywords:

Multi-agent systems, controller constraints and structure, stability.

##  1 Introduction

A multi-agent system (MAS) is a collection of independent systems (agents)
coupled via the pursuit of a common goal. In large-scale MASs the information
exchange between agents might be costly. As such, it is commonly limited to a
subset of agents, known as _neighbors_. Control laws that use only information
from neighboring agents are called _distributed_.

This work studies a class of distributed control laws, where only _relative_
measurements are exchanged between neighbors. In other words, each agent has
access only to the difference between its output and that of each of its
neighbours. Such control laws are called _diffusive_ and systems controlled by
them are known as _diffusively coupled_. Diffusive control laws are common in
the MAS literature. Relative sensing appears naturally in MAS tasks, where
absolute measurement are hard to obtain, such as space and aerial exploration
and sensor localization, see Smith and Hadaegh (2005); Khan et al. (2009);
Zelazo and Mesbahi (2011b) and the references therein. The consensus and
synchronization problems are well-known examples of diffusively coupled
systems Olfati-Saber et al. (2007); Wieland et al. (2011).

However, diffusively-coupled systems behave poorly when affected by
disturbances and noise. Measurement noise rapidly deteriorates performance
(Zelazo and Mesbahi, 2011a, §III-A) and even dynamic controllers can hardly
attenuate disturbances Ding (2015). To cope with the difficulties, different
relaxing assumptions are assumed. Some allow for non-relative state Yucelen
and Egerstedt (2012) or output Mo and Guo (2019) measurements, while others
employ an undisturbed leader Ding (2015) or impose limitations even on bounded
disturbances (Bürger and De Persis, 2015, Prop. 5). Despite these different
assumptions, if they fail, the resulting trajectories exhibit certain common
traits that can be associated with instability. These traits can be
illustrated by the classical consensus protocol, considered below for a set of
integrator agents and with a static interaction network.

###  1.1 Motivating example

Reaching agreement between autonomous agents is a fundamental building block
in multi-agent coordination Ren and Beard (2008). In its simplest form it
studies a group of independent integrator agents $\dot{x}_{i}(t)=u_{i}(t)$,
where $x_{i}$ and $u_{i}$ are their states and control inputs, respectively.
The goal is to reach asymptotic agreement between all agents, in the sense
that

$\lim_{t\to\infty}\bigl{(}x_{i}(t)-x_{j}(t)\bigr{)}=0,\quad\forall i,j,$ (1)

under the constraint that the $i$th agent has access only to states of its
neighbors, whose indices belong to a set $\mathcal{N}_{i}$. This problem can
be solved by the celebrated consensus protocol Olfati-Saber et al. (2007),
which is a diffusive state-feedback of the form

$u_{i}(t)=-\sum_{\mathclap{j\in\mathcal{N}_{i}}}\bigl{(}x_{i}(t)-x_{j}(t)\bigr{)},\quad\forall
i.$ (2)

If certain connectivity conditions on the communication topology hold (i.e.
connectedness), then the control law (2) drives the agents to agreement
exponentially fast (Mesbahi and Egerstedt, 2010, Ch. 3). The state
trajectories of four agents controlled by (2) are shown in Fig. 1 in the time
interval $[0,t_{d}]$. Observe that on this time interval the states converge
exponentially to the average of their initial conditions and the control
signals all asymptotically vanish.

(a) The states response.

(b) The control signals response.

Figure 1: Simulation of protocol (2) perturbed by a step at $t=t_{d}$.

This might no longer be the case if the agents are affected by load
disturbances $d_{i}$, viz.

$\dot{x}_{i}(t)=u_{i}(t)+d_{i}(t).$ (3)

An example of what happens in such situations is also shown in Fig. 1. At the
time instance $t=t_{d}$ one agent is affected by a unit step disturbance. As a
result, all states cease to agree and start to diverge when $t>t_{d}$, whereas
the control signals reach non-zero steady-state values.

The apparent instability of the whole system, manifested in the unboundedness
of the states, can be explained by the well-known fact that the consensus
protocol has a closed-loop eigenvalue at the origin Olfati-Saber et al.
(2007). Nevertheless, the boundedness of the control signals under such
conditions is intriguing. Situations wherein some signals in the closed-loop
system are bounded while some others are not normally indicate unstable _pole-
zero cancellations_ in the feedback loop (Zhou et al., 1996, Sec. 5.3).
However, controller (2) is static and thus has no zeros.

###  1.2 Contribution

The example above suggests that a deeper inspection of the _internal
stability_ property could offer insight into the behavior of diffusively-
coupled systems. The internal stability of any feedback interconnection
requires the stability of all possible input / output relations in the system,
see Zhou et al. (1996); Skogestad and Postlethwaite (2005). However, to the
best of our knowledge, internal stability has not been explicitly studied in
the context of diffusively-coupled architectures of MASs yet.

In this paper we show that diffusively-coupled systems of LTI (linear time-
invariant) agents might not be internally stabilizable. Loosely speaking, this
happens if the agents share common unstable dynamics, directions counting.
This, for example, is always the case in a group of homogeneous unstable
agents, like those discussed in §1.1.

When restricting the result to finite-dimensional agents, we also explain the
mechanism behind the shown internal instability. It is caused by _unstable
cancellations_ in the cascade of the aggregate plant and a diffusive
controller. Important is that these cancellations are caused not by controller
zeros, but rather by an intrinsic spatial deficiency of the diffusively-
coupled configuration. These cancellations are intrinsic to the diffusive
structure and cannot be affected by controller dynamics. Consequently, the
internal stability of feedback systems utilizing only relative measurements
depends solely on the agent dynamics.

In addition to providing a rigorous analysis of the internal stability of
diffusively-coupled systems, we show how the analysis is readily applied to
common extensions found in the literature. In particular, we discuss more
general symmetrically coupled multi-agent systems (i.e. not restricted to only
diffusive coupling), asymmetric coupling (i.e. MASs over directed graphs),
unstable systems with no closed right-half plane poles, and MASs over time-
varying networks. Numerous examples are also provided along the way to
illustrate the main results.

The paper is organized as follows. The problem is set up in Section 2 and the
main result is presented in Section 3, with several generalizations discussed
in §3.2. Section 4 addresses the case of finite-dimensional agents,
reformulating the main result in a more transparent form and revealing the
underlying reason for the reported behavior. Concluding remarks are provided
in Section 5. Two appendices collect definitions and technical results about
coprime factorizations over $H_{\infty}$ and poles and zero directions of
multivariable real-rational transfer functions.

#### Notation

The sets of integer, real, and complex numbers are $\mathbb{Z}$, $\mathbb{R}$,
and $\mathbb{C}$, respectively, with subsets
$\mathbb{N}_{\nu}\coloneq\\{i\in\mathbb{Z}\mid 1\leq i\leq\nu\\}$,
$\mathbb{C}_{0}\coloneq\\{s\in\mathbb{C}\mid\operatorname{Re}s>0\\}$, and
$\bar{\mathbb{C}}_{0}\coloneq\\{s\in\mathbb{C}\mid\operatorname{Re}s\geq
0\\}$. By $I_{\nu}$ and $\mathbb{1}_{\nu}$ we denote the $\nu\times\nu$
identity matrix and $\nu$-dimensional vector of ones, respectively. When the
dimension is immaterial or clear from context, we use $I$ and $\mathbb{1}$.
The complex-conjugate transpose of a matrix $A$ is denoted by $A^{\top}$, the
set of all its eigenvalues by $\operatorname{spec}(A)$, and its minimal
singular value by $\underline{\sigma\mkern-3.0mu}\mkern
3.0mu\\!\left(A\right)$. The notation $\operatorname{diag}\\{A_{i}\\}$ stands
for a block-diagonal matrix with diagonal elements $A_{i}$. The image (range)
and kernel (null) spaces of a matrix $A$ are notated $\operatorname{Im}A$ and
$\ker A$, respectively. Given two matrices $A$ and $B$, $A\otimes B$ denotes
their Kronecker product.

By the stability of a system $G$ we understand its $L_{2}$-stability. It is
known (Curtain and Zwart, 2020, §A.6.3) that a $p\times m$ LTI system is
causal and stable iff its transfer function $G(s)$ belongs to
$H_{\infty}^{p\times m}$, which is the space of holomorphic and bounded
functions $\mathbb{C}_{0}\to\mathbb{C}^{p\times m}$ (we write $H_{\infty}$
when the dimensions are clear). Given a real-rational transfer function
$G(s)$, its McMillan degree is denoted by $\deg(G)$. By $\operatorname{n\hskip
0.5ptrank}G(s)$ we understand the normal rank of a function $G(s)$.

A digraph $\mathcal{G}=(\mathcal{V},\mathcal{E})$ consists of a vertex set
$\mathcal{V}$ and an edge set
$\mathcal{E}\subset\mathcal{V}\times\mathcal{V}$, see Godsil and Royle (2001)
for more details. The (oriented) incidence matrix of $\mathcal{G}$ is denoted
by $E_{\mathcal{G}}$ or simply $E$ when the association with a concrete graph
is clear. It is a $\lvert\mathcal{V}\rvert\times\lvert\mathcal{E}\rvert$
matrix, whose $(i,j)$ entry is

$[E_{\mathcal{G}}]_{ij}=\begin{cases}1&\text{if vertex $i$ is the head of edge
$j$}\\\ -1&\text{if vertex $i$ is the tail of edge $j$}\\\ 0&\text{if vertex
$i$ does not belong to edge $j$}\end{cases}.$

Note that the construction of the incidence matrix implies that
$\mathbb{1}^{\top}E_{\mathcal{G}}=0$ for every $\mathcal{G}$.

##  2 Problem formulation

Consider $\nu$ continuous-time LTI agents $P_{i}$, each with $m$ inputs and
$p$ outputs, who interact over a graph $\mathcal{G}$ with $\nu$ nodes and
$\mu$ edges. In this formalism, agents $i$ and $j$ are neighbors, in the sense
defined in the Introduction, if they are incident to the same edge.

Figure 2: Diffusively-coupled feedback setup ($E$ is the incidence matrix of
the connectivity graph $\mathcal{G}$)

A general diffusively-coupled MAS, which is sometimes referred to as the
canonical cooperative control structure (Bullo, 2022, Ch. 9), is presented in
Fig. 2. It comprises the block-diagonal aggregate plant
$P\coloneq\operatorname{diag}\\{P_{i}\\}$ with $\nu$ blocks, a block-diagonal
edge controller $K_{\text{e}}\coloneq\operatorname{diag}\\{K_{\text{e},j}\\}$
with $\mu$ blocks, and pre- and post-processing based on the incidence matrix
$E$ associated with $\mathcal{G}$. To describe the logic of this setup we may
disregard the exogenous signals $d_{y}$ and $d_{u}$ for the time being. The
overall controller $K:y\mapsto u$ is thus defined as

$K\coloneq(E\otimes I_{m})K_{\text{e}}(E^{\top\\!}\otimes I_{p}).$ (4)

We now discuss how the controller $K$ processes signals.

  * 1.

The $(\nu p)$-dimensional aggregate output of the agents, $y$, is first
processed by the transpose of the incidence matrix to produce a $(\mu
p)$-dimensional vector $\tilde{y}=(E^{\top}\otimes I_{p})y$ representing the
relative outputs of neighbouring agents.

  * 2.

Each component of $\tilde{y}$, which is the relative measured coordinate along
one edge, is then processed independently by an edge controller
$K_{\text{e},j}$, to produce a $(\mu m)$-dimensional “edge correction” signal
$\tilde{u}$.

  * 3.

The $(\nu m)$-dimensional aggregate control signal $u$ is then produced by
processing all $\tilde{u}_{j}$ by the incidence matrix, which sums up edge
corrections for all edges connected to the corresponded node.

For example, if $\mathcal{G}$ is an undirected star undirected graph on three
nodes with node 3 as its center, then we can choose

$E=\left[\begin{array}[]{cccccc}1&0\\\ 0&1\\\ -1&-1\end{array}\right],$

in which case

$\tilde{y}=\left[\begin{array}[]{cccccc}y_{1}-y_{3}\\\
y_{2}-y_{3}\end{array}\right]\quad\text{and}\quad
u=\left[\begin{array}[]{cccccc}\tilde{u}_{1}\\\ \tilde{u}_{2}\\\
-\tilde{u}_{1}-\tilde{u}_{2}\end{array}\right].$

The consensus protocol (2) corresponds to the choice $K_{\text{e}}=-I$ in this
case, as well as for any other choice of $\mathcal{G}$ and $\nu$.

Now consider the exogenous signals $d_{u}$ and $d_{y}$, which we refer to as
disturbances. On the physical level they represent inevitable effects of the
outside world on the controlled plant (agents). These signals are supposed to
be bounded and independent of the signals generated by the controlled system.
We introduce disturbances to define the notion of the internal stability for
the system in Fig. 2, which is the focus point of this paper. We say that this
system is _internally stable_ if the four systems connecting $d_{u}$ and
$d_{y}$ with $u$ and $y$ are stable.

The general question of interest in this paper is _under what conditions on
the agents $P_{i}$ are there causal edge controllers $K_{\text{e},j}$
internally stabilizing the diffusively-coupled system in Fig. 2?_

Addressing this question in the most general, nonlinear and time-varying, case
might be overly technical. We thus limit our attention to the class of LTI
plants and edge controllers, whose transfer functions belong to the quotient
field of $H_{\infty}$, see (Curtain and Zwart, 2020, §A.7.1), which is a
sufficiently general class. We further assume that

  * $\boldsymbol{\mathcal{A}}_{\text{\hskip 0.75pt\bf 1}}$:

there are right coprime $M_{i},N_{i}\in H_{\infty}$ and left coprime
$\tilde{M}_{i},\tilde{N}_{i}\in H_{\infty}$ such that
$P_{i}=N_{i}M_{i}^{-1}=\tilde{M}_{i}^{-1}\tilde{N}_{i}$ for all $i$,

where coprimeness is understood as the existence of Bézout coefficients in
$H_{\infty}$, see Appendix A. The representation of $P_{i}$ above is known as
its coprime factorization. We hereafter refer to the transfer functions
$M_{i}(s)$ and $\tilde{M}_{i}(s)$ as the right and left denominators of
$P_{i}$, respectively, and the transfer functions $N_{i}(s)$ and
$\tilde{N}_{i}(s)$ as its right and left numerator. Assumption
$\boldsymbol{\mathcal{A}}_{\text{\hskip 0.75pt\bf\ref{ass:Picf}}}$ is
practically nonrestrictive. It holds for all finite-dimensional agents with
proper transfer functions and is equivalent to the stabilizability of $P_{i}$
by feedback for agents with transfer functions from the quotient field of
$H_{\infty}$ Smith (1989). Thus, if an agent fails to satisfy
$\boldsymbol{\mathcal{A}}_{\text{\hskip 0.75pt\bf\ref{ass:Picf}}}$, we cannot
expect any MAS that includes it to be stabilizable by diffusive coupling.

Figure 3: Diffusively-coupled feedback setup as edge stabilization

###  2.1 Where shall disturbances enter?

It is important to emphasize that the application points of the disturbances
are chosen to be at the points where the agents, $P$, are connected with the
controller $K$ defined in (4). In this choice we follow the physical nature of
the interconnection in Fig. 2 and treat $K$ as the controller. Separating the
blocks $E\otimes I$ and $E^{\top\\!}\otimes I$ is then merely a way to
streamline the choice of the design parameters, which are the edge controllers
in $K_{\text{e}}$. This logic is frequently followed, see e.g. Bürger and De
Persis (2015), although not in the internal stability context.

An alternative treatment is the so-called edge stabilization, see e.g. Zelazo
and Mesbahi (2011a), in which all _fixed_ parts are regarded as the controlled
plant, somewhat in line with the generalized plant philosophy (Skogestad and
Postlethwaite, 2005, Sec. 3.8). In our case this combination of fixed parts is

$P_{\text{e}}\coloneq(E^{\top\\!}\otimes I_{p})P(E\otimes I_{m}).$

Under this viewpoint one might be inclined to introduce exogenous inputs at
$\tilde{y}$ and $\tilde{u}$, as shown in Fig. 3, and study the boundedness of
the internal signals $\tilde{y}$ and $\tilde{u}$.

Still, we believe that the configuration in Fig. 2 is the right way to address
the internal stability of MASs. After all, it is the agents who interact with
the environment. Even if $\tilde{y}$ represents a physical relative
measurement, which might require to introduce another exogenous input, like
$\tilde{d}_{y}$ in Fig. 3, any realistic setup shall (i) allow the signals
$d_{u}$ and $d_{y}$ as in Fig. 2 to affect the system and (ii) ensure that
physical inputs and outputs of agents, $u$ and $y$, are bounded. As such, the
internal stability in the configuration of Fig. 2 is justified regardless what
control objectives are addressed.

##  3 The main result

The main technical result of this work, whose proof is postponed to §3.1, is
formulated as follows.

###### Theorem 3.1

No LTI $K_{\text{e},j}$ can internally stabilize the diffusively-coupled
system in Fig. 2 if there is $\lambda\in\bar{\mathbb{C}}_{0}$, common to all
agents, such that

$\displaystyle\bigcap_{i=1}^{\nu}\ker\,[M_{i}(\lambda)]^{\top}\neq\\{0\\}$
(5a) or
$\displaystyle\bigcap_{i=1}^{\nu}\ker\tilde{M}_{i}(\lambda)\neq\\{0\\}.$ (5b)

where $M_{i}$ and $\tilde{M}_{i}$ are denominators in the coprime
factorizations of $P_{i}$ under $\boldsymbol{\mathcal{A}}_{\text{\hskip
0.75pt\bf\ref{ass:Picf}}}$.

Theorem 3.1, formulated in terms of coprime factors of agents, might appear
somewhat abstract and technical. This is a consequence of considering a fairly
general class of LTI agents under the mild assumption
$\boldsymbol{\mathcal{A}}_{\text{\hskip 0.75pt\bf\ref{ass:Picf}}}$. We show in
the next section that if the class of admissible agents is limited to finite-
dimensional ones, then more insightful statements can be provided.
Nevertheless, the formulation in Theorem 3.1 becomes substantially more
intuitive in some frequently studied special cases.

The first of them is the case of homogeneous agents, which is perhaps the best
studied situation.

###### Corollary 3.2

If the agents are homogeneous, i.e. $P_{i}=P_{0}$ for all
$i\in\mathbb{N}_{\nu}$, and $P_{0}(s)$ has at least one pole in
$\bar{\mathbb{C}}_{0}$, then no LTI $K_{\text{e},j}$ can internally stabilize
the system in Fig. 2.

###### Proof 1

By Lemma A.2, if $\lambda\in\bar{\mathbb{C}}_{0}$ is a pole of $P_{0}(s)$,
then both $M_{0}(\lambda)$ and $\tilde{M}_{0}(\lambda)$ are singular, whence
the result follows.

This result readily applies to the problem studied in §1.1. The agents in (3)
are homogeneous and $P_{0}(s)=1/s$ has an unstable pole at the origin.
Corollary 3.2 then agrees with the conclusion of §1.1 that the closed-loop
system is not internally stable.

######  Remark 1 (DFM)

The lack of internal stability of the consensus protocol (2) for the
integrator agents (3) is not related to the decentralized fixed modes (DFMs)
phenomena (Davison et al., 2020, Sec. 2.2). If a potential presence of load
disturbances $d_{u}$ at agents is ignored, like in Fig. 3, then the consensus
protocol, which corresponds to the decentralized $K_{\text{e}}=-I$, stabilizes
the system if and only if $E^{\top}E>0$. Yet the edge Laplacian $E^{\top}E$ is
nonsingular if and only if the graph is a forest Zelazo and Mesbahi (2011a).
Thus, in certain configurations $(E^{\top\\!}\otimes I_{p})P(E\otimes I_{m})$
has no DFMs, but the system in Fig. 2 is nevertheless not internally
stabilizable.

Another particular case for which the formulation is simplified is a MAS with
SISO agents.

###### Corollary 3.3

If the agents are SISO and all have a pole at the same
$\lambda\in\bar{\mathbb{C}}_{0}$, regardless of multiplicities, then no LTI
$K_{\text{e},j}$ can internally stabilize the diffusively-coupled system in
Fig. 2.

###### Proof 2

By Lemma A.2, in this case $M_{i}(\lambda)=\tilde{M}_{i}(\lambda)=0$ for all
$i\in\mathbb{N}_{\nu}$, whence the result follows.

A consequence of Corollary 3.3 is that the consensus protocol, as well as any
other diffusively-coupled control laws, cannot internally stabilize a group of
SISO agents if all of them contain an integral action. This result is
reminiscent of that by Wieland et al. (2011) that states that a common
internal model is a necessary condition for a diffusively-coupled system to
synchronize their state trajectories. It highlights a contradiction or trade-
off of sorts, where on the one hand, a common pole at the origin among agents
is required for synchronization, and on the other hand, this common (unstable)
pole is precisely the cause for lack of internal stability.

###  3.1 Proof of Theorem 3.1

We are now prepared to prove Theorem 3.1. Only the statement about the right
coprime factor, i.e. (5a), is proved. The proof of (5b) follows by dual
arguments.

The proof requires a technical result of Fuhrmann (1968), known as the matrix
corona theorem, see also the proof of (Georgiou and Smith, 1993, Prop. 11) for
a closer formulation.

###### Lemma 3.4

If $G\in H_{\infty}^{n\times n}$, then

$G^{-1}\in
H_{\infty}\iff\textstyle\inf_{s\in\bar{\mathbb{C}}_{0}}\underline{\sigma\mkern-3.0mu}\mkern
3.0mu\\!\left(G(s)\right)>0.$

It is readily seen that $M_{P}\coloneq\operatorname{diag}\\{M_{i}\\}$ and
$N_{P}\coloneq\operatorname{diag}\\{N_{i}\\}$ are right coprime factors of
$P=\operatorname{diag}\\{P_{i}\\}$. Because any internally stabilizing $K$ in
(4) is in effect stabilized by the plant, we only need to consider edge
controllers for which $K$ admits coprime factorizations over $H_{\infty}$. So
let $K=N_{K}M_{K}^{-1}$ for right coprime $M_{K},N_{K}\in H_{\infty}$. By (4),

$N_{K}(s)=(E\otimes I_{m})K_{\text{e}}(s)(E^{\top\\!}\otimes I_{p})M_{K}(s).$

Because $\mathbb{1}^{\top}E=0$, we have that $(\mathbb{1}^{\top}\otimes
I_{m})(E\otimes I_{m})=0$ as well and, hence, $(\mathbb{1}^{\top}\otimes
I_{m})N_{K}(s)=0$ for all $s$ at which $K_{\text{e}}(s)$ is finite. But
$K_{\text{e}}(s)$ is in the quotient field of $H_{\infty}$, meaning that the
denominators of its entries are holomorphic in $\mathbb{C}_{0}$ and, by
(Rudin, 1987, Thm. 10.18), may have at most countable number of isolated
zeros. As such, we can always find a region in $\mathbb{C}_{0}$ in which
$(\mathbb{1}^{\top}\otimes I_{m})N_{K}(s)=0$. But the latter implies that

$(\mathbb{1}^{\top\\!}\otimes I_{m})N_{K}=0,$

by the same (Rudin, 1987, Thm. 10.18).

Now, return to the system in Fig. 2. It is readily verified that the closed-
loop system $T_{4}\coloneq(d_{y},d_{u})\mapsto(y,u)$ reads

$T_{4}=\left[\begin{array}[]{cccccc}I\\\
K\end{array}\right](I-PK)^{-1}\left[\begin{array}[]{cccccc}I&P\end{array}\right]\eqcolon\left[\begin{array}[]{cccccc}S&T_{\text{d}}\\\
T_{\text{c}}&T\end{array}\right],$ (6)

where the blocks of $T_{4}$ are the four fundamental closed-loop transfer
functions. Straightforward algebra yields that

$T_{4}=\left[\begin{array}[]{cccccc}M_{K}&0\\\
N_{K}&0\end{array}\right]\smash{\left[\begin{array}[]{cccccc}M_{K}&-N_{P}\\\
-N_{K}&M_{P}\end{array}\right]^{-1}}.$ (7)

This is a right coprime factorization of $T_{4}$, as attested by the Bézout
equality (cf. (13a))

$\left[\begin{array}[]{cccccc}\tilde{M}_{P}&\tilde{N}_{P}\\\
-Y_{P}&X_{P}\end{array}\right]\left[\begin{array}[]{cccccc}M_{K}&-N_{P}\\\
-N_{K}&M_{P}\end{array}\right]\\\
+\left[\begin{array}[]{cccccc}X_{K}-\tilde{M}_{P}&Y_{K}+\tilde{N}_{P}\\\
Y_{P}&X_{P}\end{array}\right]\left[\begin{array}[]{cccccc}M_{K}&0\\\
N_{K}&0\end{array}\right]=I,$

where $\tilde{M}_{P}\coloneq\operatorname{diag}\\{\tilde{M}_{i}\\}$ and
$\tilde{N}_{P}\coloneq\operatorname{diag}\\{\tilde{N}_{i}\\}$. By Lemma A.1,
$T_{4}$ is stable if and only if

$\left[\begin{array}[]{cccccc}M_{K}&-N_{P}\\\
-N_{K}&M_{P}\end{array}\right]^{-1\\!}\in H_{\infty},$ (8)

or

$\inf_{s\in\bar{\mathbb{C}}_{0}}\underline{\sigma\mkern-3.0mu}\mkern
3.0mu\\!\left(\left[\begin{array}[]{cccccc}M_{K}(s)&-N_{P}(s)\\\
-N_{K}(s)&M_{P}(s)\end{array}\right]\right)>0$ (9)

by Lemma 3.4. But (5a) implies that there is $v\neq 0$ such that
$v^{\top}M_{i}(\lambda)=0$ for all $i$ or, equivalently, $(\mathbb{1}\otimes
v)^{\top}M_{P}(\lambda)=0$. Taking into account that $(\mathbb{1}\otimes
v)^{\top}N_{K}=v^{\top}(\mathbb{1}\otimes I_{m})^{\top}N_{K}=0$, we end up
with

$\left[\begin{array}[]{cccccc}0&(\mathbb{1}\otimes
v)^{\top}\end{array}\right]\left[\begin{array}[]{cccccc}M_{K}(\lambda)&-N_{P}(\lambda)\\\
-N_{K}(\lambda)&M_{P}(\lambda)\end{array}\right]=0,$ (10)

which violates (9). We thus have that if (5a) holds, then there is no
$K_{\text{e}}$ that internally stabilizes the system in Fig. 2.

###  3.2 Generalizations

Some possible generalizations of the result of Theorem 3.1 are outlined below.

####  3.2.1 Arbitrary symmetric coupling

The result of Theorem 3.1 still holds if the incidence matrix is replaced with
a different coupling matrix, say $F\in\mathbb{R}^{\mu\times\nu}$, as long as
there is a vector $0\neq v\in\mathbb{R}^{\mu}$ such that $v^{\top}F=0$. Such
generalizations of a MAS were recently discussed in Belabbas et al. (2021),
but are also included in works considering, for example, distributed function
calculation in MAS Sundaram and Hadjicostis (2008).

####  3.2.2 Asymmetric coupling

Some MAS problems consider a _directed_ interaction graph, making the notion
of neighboring agents asymmetric. Controllers under such constrains are no
longer diffusive in the sense discussed in Section 2. Still, a variant of
Theorem 3.1 may still apply.

For example, let an edge going from node $i$ to node $j$ indicate that the
$i$th agent has access to $y_{i}-y_{j}$. The existence of the edge $(i,j)$
does not imply that there is also the edge $(j,i)$. A controller constrained
in such a way can be written as

$K_{\text{out}}\coloneq(B_{\text{out}}\otimes
I_{m})K_{\text{e}}(E^{\top\\!}\otimes I_{p}),$ (11)

where

$[B_{\text{out}}]_{ij}=\begin{cases}1&\text{if vertex $i$ is the head of edge
$j$}\\\ 0&\text{otherwise}\end{cases}.$

Setting $K_{\text{e}}=-I$ results in the (out-degree) directed consensus
protocol (Bullo, 2022, Sec. 7.3). The controller structure in (11) mirrors
that in (4). If (5b) holds, then the proof of Theorem 3.1 applies verbatim to
a MASs controlled by (11).

If we define the analogous $K_{\text{in}}$ (corresponding to the in-degree
directed consensus protocol) and consider only condition (5a), then again the
proof holds unchanged.

####  3.2.3 Unstable systems with no poles in $\bar{\mathbb{C}}_{0}$

It might happen that $P_{i}\not\in H_{\infty}$ not because of poles, or other
singularities, in $\bar{\mathbb{C}}_{0}$. For example,
$P_{i}(s)=s/(s+1+s\mathrm{e}^{-s})$ has no singularities in
$\bar{\mathbb{C}}_{0}$, but nonetheless does not belong to $H_{\infty}$, see
Partington and Bonnet (2004). The proof still applies in this case, and all we
need is to replace (5) with the assumption that there is a sequence
$\\{\lambda_{j}\\}$ in $\mathbb{C}_{0}$ such that
$\inf_{\\{\lambda_{j}\\}}v^{\top}M_{i}(\lambda_{j})=0$, or its dual version,
holds for all $i\in\mathbb{N}_{\nu}$ and some $v\neq 0$.

####  3.2.4 Time-varying $K$

The main result also extends to the case of time-varying controllers. This is
particularly relevant for varying interconnection topologies, i.e. where
$E_{\mathcal{G}(t)}=E(t)$ is the incidence matrix of the time-varying graph
$\mathcal{G}(t)$. Still, the condition $\mathbb{1}^{\top}E(t)$ holds for any
topology, rendering the denominator in (7) not stably invertible. We can then
use (Verma, 1988, Theorem (i)) to show that under no choice of $K_{\text{e}}$
the system is stabilizable, at least in the finite-dimensional case, whenever
either one of the conditions in (5) holds.

##  4 Finite-dimensional agents

If the agents $P_{i}$ are finite dimensional, the result of the previous
section can be reformulated in a more insightful way. This is due to the
ultimate connection between stability and pole locations, as well as clear
definitions of cancellations in this case. So we proceed with assuming that
all transfer functions $P_{i}(s)$ are real rational and proper
($\boldsymbol{\mathcal{A}}_{\text{\hskip 0.75pt\bf\ref{ass:Picf}}}$ always
holds then).

Let $\mathrm{pdir_{i}}\\!\left(G,\lambda\right)$ and
$\mathrm{pdir_{o}}\\!\left(G,\lambda\right)$ denote input and output direction
of a pole $\lambda$ in $G(s)$, see AppendixB for details and other related
definitions. The result below reformulates the conditions of Theorem 3.1 via
pole directions of agents.

###### Proposition 4.1

If $P_{i}(s)$ are real rational and proper, then (5a) and (5b) are equivalent
to the existence of $\lambda\in\bar{\mathbb{C}}_{0}$ such that

$\displaystyle\bigcap_{i=1}^{\nu}\,\mathrm{pdir_{i}}\\!\left(P_{i},\lambda\right)\neq\\{0\\}$
(12a) and
$\displaystyle\bigcap_{i=1}^{\nu}\,\mathrm{pdir_{o}}\\!\left(P_{i},\lambda\right)\neq\\{0\\},$
(12b)

respectively.

###### Proof 3

Because $\lambda\in\bar{\mathbb{C}}_{0}$ is not a pole of $M_{i}(s)$, Lemma
B.2 applies and (5a) reads
$\cap_{i=1}^{\nu}\,\mathrm{zdir_{o}}\\!\left(M_{i},\lambda\right)\neq\\{0\\}$.
Then (12a) follows by Lemma B.3. The proof for (12b) is similar.

In other words, for the system in Fig. 2 to not be stabilizable, the agents
should not only have a common unstable pole, but also a common nontrivial
direction of such a pole. Directions are obviously matched in the uniform and
SISO cases addressed in Corollaries 3.2 and 3.3, respectively. But the MIMO
heterogeneous case may be less trivial.

###### Example 1

Consider a system with $\nu=2$ first-order agents

$P_{1}(s)=\left[\begin{array}[]{cccccc}1/s&0\\\
0&1\end{array}\right]\quad\text{and}\quad
P_{2}(s)=\left[\begin{array}[]{cccccc}1\\\
\alpha\end{array}\right]\frac{1}{s}\left[\begin{array}[]{cccccc}1&\beta\end{array}\right].$

Directions of their pole at the origin are

$\displaystyle\mathrm{pdir_{i}}\\!\left(P_{1},0\right)=\mathrm{pdir_{o}}\\!\left(P_{1},0\right)=\operatorname{Im}\left[\begin{array}[]{cccccc}1\\\
0\end{array}\right],$
$\displaystyle\mathrm{pdir_{i}}\\!\left(P_{2},0\right)=\operatorname{Im}\left[\begin{array}[]{cccccc}1\\\
\beta\end{array}\right],\quad\text{and}\quad\mathrm{pdir_{o}}\\!\left(P_{2},0\right)=\operatorname{Im}\left[\begin{array}[]{cccccc}1\\\
\alpha\end{array}\right].$

There are nontrivial intersections between input and output directions of the
agents if and only if $\beta=0$ and $\alpha=0$, respectively. The incidence
matrix is $E=\bigl{[}\begin{smallmatrix}1\\\ -1\end{smallmatrix}\bigr{]}$ in
this case. Choose the edge controller (there is only one edge in this example)
as

$K_{\text{e}}(s)=\left[\begin{array}[]{cccccc}(\alpha-\beta)\beta&-\alpha\\\
\beta&0\end{array}\right].$

The closed-loop characteristic polynomial, understood as the lowest common
denominator of elements of $T_{4}(s)$ in (6), is then
$(s+\alpha^{2})(s+\beta^{2})$. Thus, the closed-loop system is stable unless
$\alpha=0$ or $\beta=0$, which agrees with (12).

Also worth emphasizing is that conditions (12a) and (12b) might not be
equivalent for MIMO agents, as illustrated by the example below.

###### Example 2

Consider another system with $\nu=2$ agents, now

$P_{1}(s)=\left[\begin{array}[]{cccccc}s/(s+1)&0\\\
1/s&1\end{array}\right]\quad\text{and}\quad
P_{2}(s)=\left[\begin{array}[]{cccccc}1/s&0\\\ 1&s/(s+1)\end{array}\right]$

(both are second order). Directions associated with the unstable pole at the
origin are

$\displaystyle\mathrm{pdir_{i}}\\!\left(P_{1},0\right)=\mathrm{pdir_{i}}\\!\left(P_{2},0\right)=\operatorname{Im}\left[\begin{array}[]{cccccc}1\\\
0\end{array}\right],$ but
$\displaystyle\mathrm{pdir_{o}}\\!\left(P_{1},0\right)=\operatorname{Im}\left[\begin{array}[]{cccccc}0\\\
1\end{array}\right]\neq\operatorname{Im}\left[\begin{array}[]{cccccc}1\\\
0\end{array}\right]=\mathrm{pdir_{o}}\\!\left(P_{2},0\right).$

Thus, in this case (12a) holds, whereas (12b) does not.

Another outcome of the finite dimensionality is that the formulation of
Corollary 3.2 can be strengthened to an “if and only if” statement.

###### Corollary 4.2

If the agents are homogeneous, i.e. $P_{i}=P_{0}$ for all
$i\in\mathbb{N}_{\nu}$, and $P_{0}(s)$ is real rational and proper, then an
LTI $K_{\text{e},j}$ can internally stabilize the diffusively-coupled system
in Fig. 2 if and only if $P_{0}$ is stable.

###### Proof 4

If $P_{0}$ is unstable, then it has a pole in $\bar{\mathbb{C}}_{0}$ and
Corollary 3.2 applies. If $P_{0}$ is stable, $K_{\text{e}}=0$ does the job.

One should be careful not to conclude from the proof of Corollary 4.2 that
only $K_{\text{e}}=0$ can be used to guarantee internal stability. Indeed, one
can also consider unstable edge controllers. The case of $K_{\text{e}}=0$
effectively decouples all the agents leading only to a “trivial” coordination
(i.e. all agents converge to the origin). By using an unstable edge
controller, together with an appropriate external input, it is possible to
obtain non-trivial outputs (such as agreement to a non-zero value).

###  4.1 Diffusive control laws and unstable cancellations

The formulation of Proposition 4.1 is more intuitive than that of Theorem 3.1.
Still, neither of them explains _why_ no edge controller can stabilize the
system in Fig. 2 if agents share common unstable dynamics, directions counted.
In this part we aim at offering explanations. We argue that a key property to
this end is intrinsic _unstable cancellations_ between the plant and the
controller.

The cascade (series) interconnection $G_{2}G_{1}$ has cancellations if
$\deg(G_{2}G_{1})<\deg(G_{1})+\deg(G_{2})$. In other words, cancellations mean
that some parts of the dynamics (modes) of either factor disappear in the
cascade. Specifically, we say that a pole of $G_{1}(s)$ and/or $G_{2}(s)$ is
_canceled_ if its multiplicity in $G_{2}(s)G_{1}(s)$ is smaller than the sum
of its multiplicities in $G_{1}(s)$ and $G_{2}(s)$. Cancellations in the SISO
case are always caused by the presence of zeros of $G_{1}(s)$ at the locations
of poles of $G_{2}(s)$, or vice versa. As such, they are termed _pole-zero
cancellations_. The situation is more complex in the MIMO case. For example,
let

$G_{1}(s)=\frac{1}{s}\left[\begin{array}[]{cccccc}1&0\\\
0&1\end{array}\right]\quad\text{and}\quad
G_{2}(s)=\left[\begin{array}[]{cccccc}1&-1\\\ -1&1\end{array}\right],$

with $\deg(G_{1})=2$ (two poles at the origin) and $\deg(G_{2})=0$. The system
$G_{2}$ is static and thus has no zeros. Nevertheless, the transfer function

$G_{2}(s)G_{1}(s)=\frac{1}{s}\left[\begin{array}[]{cccccc}1&-1\\\
-1&1\end{array}\right]$

is first order, meaning that one of the poles of $G_{1}(s)$ is canceled. Such
cancellations, brought on by the normal rank deficiency of $G_{2}(s)$, are a
lesser-known phenomenon.

The result below, proved in §4.2, states that such cancellations are present
between the plant and the controller in Fig. 2 whenever the conditions of
Proposition 4.1 hold.

###### Proposition 4.3

Let $P(s)$ and $K_{\text{e}}(s)$ be real rational and proper and let
$\lambda\in\bar{\mathbb{C}}_{0}$ be a pole of $P(s)$.

  * i)

If (12a) holds, then $\lambda$ is canceled in $P(s)K(s)$.

  * ii)

If (12b) holds, then $\lambda$ is canceled in $K(s)P(s)$.

Unstable pole-zero cancellations between a plant and a controller are a
consensual taboo in feedback control. Textbooks treat them as a kind of a
cardinal sin, which shall be avoided at all costs. The reason is that canceled
dynamics do not really disappear. For example, poles of a SISO plant $P(s)$
canceled by zeros of a controller $K(s)$ always show up in the closed-loop
disturbance sensitivity $T_{\text{d}}(s)$, see (6). This is the very reason to
require internal stability. Unstable cancellations due to deficient normal
rank are less common and less studied. Nevertheless, they cause the same
repercussions. Namely, canceled dynamics shows up in at least one closed-loop
relation, rendering the system prone to the effect of exogenous signals.

Assume, for example, that condition (12a), or (5a), holds for some
$\lambda\in\bar{\mathbb{C}}_{0}$. It follows from the proof of Theorem 3.1
that there is then $v\neq 0$ such that (10) holds. Therefore,

$\left[\begin{array}[]{cccccc}0\\\ \mathbb{1}\otimes
v\end{array}\right]\in\mathrm{zdir_{o}}\\!\left(\left[\begin{array}[]{cccccc}M_{K}&-N_{P}\\\
-N_{K}&M_{P}\end{array}\right],\lambda\right)=\mathrm{pdir_{i}}\\!\left(T_{4},\lambda\right)$

where the equality follows by Lemma B.3 and the fact that the factors in (7)
are right coprime. By Lemma B.1 and (6)

$T_{4}(s)\left[\begin{array}[]{cccccc}0\\\ \mathbb{1}\otimes
v\end{array}\right]=\left[\begin{array}[]{cccccc}T_{\text{d}}(s)\\\
T(s)\end{array}\right](\mathbb{1}\otimes v)$

has an unstable pole at $s=\lambda$. In other words, there is a load
disturbance $d_{u}$ in Fig. 2 such that either $y$ or $u$ or both is
unbounded. Likewise, it can be shown that if (12b) holds, then
$\left[\begin{array}[]{cccccc}S&T_{\text{d}}\end{array}\right]\not\in
H_{\infty}$, i.e. $d_{u}$ or/and $d_{y}$ might cause an unbounded $y$. This
explains why the consensus protocol in §1.1 has an unstable load disturbance
response.

It can be shown that if the consensus discussed in §1.1 can be attained, then
all components of $T_{4}$ but $T_{\text{d}}$ are stable, whereas
$T_{\text{d}}(s)$ has a pole at the origin. This agrees with the situation in
SISO pole-zero cancellations discussed above. However, $T_{\text{d}}$ is not
necessarily unstable in a general MIMO case if either of the conditions in
(12) holds. The example below illustrates a different scenario.

###### Example 3

Return to the agents in Example 2, which satisfy (12a). Select

$K_{\text{e}}(s)=-\frac{1}{3}\left[\begin{array}[]{cccccc}1&0\\\
0&2/s\end{array}\right].$

It is then a matter of routine calculations to see that $S$, $T_{\text{d}}$,
and $T_{\text{c}}$ are stable, each having $(s+2)(2s+1)^{2}(3s+1)$ as the
lowest common denominator of its entries. However, $T(s)$ has a pole at the
origin in addition, rendering the whole $T_{4}$ unstable.

###  4.2 Proof of Proposition 4.3

Bring in _minimal_ realizations

$P_{i}(s)=\left[\begin{array}[]{c|c}A_{i}&B_{i}\\\ \hline\cr
C_{i}&D_{i}\end{array}\right]\quad\text{and}\quad
K(s)=\left[\begin{array}[]{c|c}A_{K}&B_{K}\\\ \hline\cr
C_{K}&D_{K}\end{array}\right]$

so the realization

$P(s)=\left[\begin{array}[]{c|c}A_{P}&B_{P}\\\ \hline\cr
C_{P}&D_{P}\end{array}\right]\coloneq\left[\begin{array}[]{c|c}\operatorname{diag}\\{A_{i}\\}&\operatorname{diag}\\{B_{i}\\}\\\
\hline\cr\operatorname{diag}\\{C_{i}\\}&\operatorname{diag}\\{D_{i}\\}\end{array}\right]$

is also minimal. To prove the first item of the Proposition it is then
sufficient to show that $\lambda$ is an uncontrollable mode of

$P(s)K(s)=\left[\begin{array}[]{cc|c}A_{K}&0&B_{K}\\\
B_{P}C_{K}&A_{P}&B_{P}D_{K}\\\ \hline\cr
D_{P}C_{K}&C_{P}&D_{P}D_{K}\end{array}\right].$

To this end, note that (4) implies $(\mathbb{1}\otimes
I)^{\top}\left[\begin{array}[]{cccccc}C_{K}&D_{K}\end{array}\right]=0$ and
condition (12a) is equivalent to the existence of $0\neq v\in\mathbb{C}^{m}$
such that $v=B_{i}^{\top}\eta_{i}$ for some $\eta_{i}$ such that
$\eta_{i}^{\top}(\lambda I-A_{i})=0$. The latter is equivalent to the
existence of $\eta\neq 0$ such that

$\eta^{\top}(\lambda
I-A_{P})=0\quad\text{and}\quad\eta^{\top}B_{P}=(\mathbb{1}\otimes v)^{\top}$

for some $v\neq 0$. Therefore,

$\left[\begin{array}[]{cccccc}0&\eta^{\top}\end{array}\right]\left[\begin{array}[]{cccccc}A_{K}-\lambda
I&0&B_{K}\\\ B_{P}C_{K}&A_{P}-\lambda I&B_{P}D_{K}\end{array}\right]\\\
=v^{\top}(\mathbb{1}\otimes
I)^{\top}\left[\begin{array}[]{cccccc}C_{K}&0&D_{K}\end{array}\right]=0$

and the PBH test for the realization of $PK$ fails for the mode at $\lambda$,
proving the first item. The second item follows by similar arguments.

##  5 Concluding remarks

In this paper we have studied the internal stability of multi-agent systems
controlled by diffusively coupled laws. We have argued that internal
stability, with entry points of exogenous signals at the connections between
the agents and the controller, is a vital property in multi-agent systems and
have proved that it can never be attained if the agents share common unstable
dynamics, directions counted. In particular, this class always includes the
case of homogeneous unstable agents or heterogeneous SISO agents with a common
unstable pole, like an integral action. We have shown that the underlying
reason for the lack of stabilizability is intrinsic cancellations of aligned
unstable dynamics of agents by the diffusive coupling mechanism.

An immediate outcome of the proposed analysis is that the uniformity must be
broken in the control of unstable multi-agent systems. This is the underlying
reason behind several of the different assumptions mentioned in Section 1.
Introducing a leader, or “virtual” agent, can potentially break the common
instability, while permitting non-relative feedback either locally stabilize
the agents or again, break the uniformity.

## References

  * Belabbas et al. (2021) Belabbas, M.A., Chen, X., and Zelazo, D. (2021).  On structural rank and resilience of sparsity patterns.  _arXiv_.
  * Bullo (2022) Bullo, F. (2022).  _Lectures on Network Systems_.  Kindle Direct Publishing, 1.6 edition.  URL http://motion.me.ucsb.edu/book-lns.
  * Bürger and De Persis (2015) Bürger, M. and De Persis, C. (2015).  Dynamic coupling design for nonlinear output agreement and time-varying flow control.  _Automatica_ , 51, 210–222.
  * Curtain and Zwart (2020) Curtain, R.F. and Zwart, H. (2020).  _Introduction to Infinite-Dimensional Systems Theory: A State-Space Approach_.  Springer-Verlag, New York, NY.
  * Davison et al. (2020) Davison, E.J., Aghdam, A.G., and Miller, D.E. (2020).  _Decentralized Control of Large-Scale Systems_.  Springer-Verlag, New York, NY.
  * Ding (2015) Ding, Z. (2015).  Consensus disturbance rejection with disturbance observers.  _IEEE Transactions on Industrial Electronics_ , 62(9), 5829–5837.
  * Fuhrmann (1968) Fuhrmann, P.A. (1968).  On the corona theorem and its application to spectral problems in Hilbert space.  _Trans. Amer. Math. Soc._ , 132(1), 55–66.
  * Georgiou and Smith (1993) Georgiou, T.T. and Smith, M.C. (1993).  Graphs, causality and stabilizability: linear, shift-invariant systems on $\mathcal{L}_{2}[0,\infty)$.  _Math. Control, Signals and Systems_ , 6, 195–223.
  * Godsil and Royle (2001) Godsil, C.D. and Royle, G.F. (2001).  _Algebraic Graph Theory_.  Springer.
  * Khan et al. (2009) Khan, U.A., Kar, S., and Moura, J.M.F. (2009).  Distributed sensor localization in random environments using minimal number of anchor nodes.  _IEEE Transactions on Signal Processing_ , 57(5), 2000–2016.
  * Mesbahi and Egerstedt (2010) Mesbahi, M. and Egerstedt, M. (2010).  _Graph Theoretic Methods in Multiagent Networks_.  Princeton University Press, Princeton.
  * Mirkin (2019) Mirkin, L. (2019).  Linear Control Systems.  course notes, Faculty of Mechanical Eng., Technion—IIT.  URL http://leo.technion.ac.il/Courses/LCS/LCSnotes.pdf.
  * Mo and Guo (2019) Mo, L. and Guo, S. (2019).  Consensus of linear multi-agent systems with persistent disturbances via distributed output feedback.  _Journal of Systems Science and Complexity_ , 32(3), 835–845.
  * Olfati-Saber et al. (2007) Olfati-Saber, R., Fax, A., and Murray, R.M. (2007).  Consensus and cooperation in networked multi-agent systems.  _Proc. IEEE_ , 95(1), 215–233.
  * Partington and Bonnet (2004) Partington, J.R. and Bonnet, C. (2004).  $H_{\infty}$ and BIBO stabilization of delay systems of neutral type.  _Syst. Control Lett._ , 52(8), 283–288.
  * Ren and Beard (2008) Ren, W. and Beard, R.W. (2008).  _Distributed Consensus in Multi-vehicle Cooperative Control: Theory and Applications_.  Springer-Verlag, London.
  * Rudin (1987) Rudin, W. (1987).  _Real and Complex Analysis_.  McGraw-Hill, New York, NY, 3rd edition.
  * Skogestad and Postlethwaite (2005) Skogestad, S. and Postlethwaite, I. (2005).  _Multivariable Feedback Control: Analysis and Design_.  John Wiley & Sons, Chichester, 2nd edition.
  * Smith (1989) Smith, M.C. (1989).  On stabilization and the existence of coprime factorizations.  _IEEE Trans. Automat. Control_ , 34(9), 1005–1007.
  * Smith and Hadaegh (2005) Smith, R.S. and Hadaegh, F.Y. (2005).  Control of deep-space formation-flying spacecraft; relative sensing and switched information.  _Journal of Guidance, Control, and Dynamics_ , 28(1), 106–114.
  * Sundaram and Hadjicostis (2008) Sundaram, S. and Hadjicostis, C.N. (2008).  Distributed function calculation and consensus using linear iterative strategies.  _IEEE J. Sel. Areas Commun._ , 26(4), 650–660.
  * Verma (1988) Verma, M.S. (1988).  Coprime fractional representations and stability of non-linear feedback systems.  _Int. J. Control_ , 48, 897–918.
  * Vidyasagar (1985) Vidyasagar, M. (1985).  _Control System Synthesis: A Factorization Approach_.  The MIT Press, Cambridge, MA.
  * Wieland et al. (2011) Wieland, P., Sepulchre, R., and Allgöwer, F. (2011).  An internal model principle is necessary and sufficient for linear output synchronization.  _Automatica_ , 47(5), 1068–1074.
  * Yucelen and Egerstedt (2012) Yucelen, T. and Egerstedt, M. (2012).  Control of multiagent systems under persistent disturbances.  In _"Proc. 2012 American Control Conf.,_ , 5264–5269.
  * Zelazo and Mesbahi (2011a) Zelazo, D. and Mesbahi, M. (2011a).  Edge agreement: Graph-theoretic performance bounds and passivity analysis.  _IEEE Transactions on Automatic Control_ , 56(3), 544–555.
  * Zelazo and Mesbahi (2011b) Zelazo, D. and Mesbahi, M. (2011b).  Graph-theoretic analysis and synthesis of relative sensing networks.  _IEEE Transactions on Automatic Control_ , 56(5), 971–982.
  * Zhou et al. (1996) Zhou, K., Doyle, J.C., and Glover, K. (1996).  _Robust and Optimal Control_.  Prentice-Hall, Englewood Cliffs, NJ.

##  Appendix A Coprime factorizations over $\boldsymbol{H_{\infty}}$

In this Appendix, basic coprime factorization results that are required in the
paper are presented. A comprehensive exposition of the subject can be found in
Vidyasagar (1985).

Functions $M\in H_{\infty}^{m\times m}$ and $N\in H_{\infty}^{p\times m}$ are
said to be _right coprime_ if there are $X\in H_{\infty}^{m\times m}$ and
$Y\in H_{\infty}^{m\times p}$ (Bézout coefficients) such that

$XM+YN=I_{m}.$ (13a) Functions $\tilde{M}\in H_{\infty}^{p\times p}$ and
$\tilde{N}\in H_{\infty}^{p\times m}$ are said to be _left coprime_ if there
are $\tilde{X}\in H_{\infty}^{p\times p}$ and $\tilde{Y}\in
H_{\infty}^{m\times p}$ such that
$\tilde{M}\tilde{X}+\tilde{N}\tilde{Y}=I_{p}.$ (13b)

A transfer function $G(s)$ is said to have coprime factorizations over
$H_{\infty}$ if there are right coprime $M_{G},N_{G}\in H_{\infty}$ and left
coprime $\tilde{M}_{G},\tilde{N}_{G}\in H_{\infty}$, known as right and left
coprime factors of $G$, respectively, such that

$G=N_{G}M_{G}^{-1}=\tilde{M}_{G}^{-1}\tilde{N}_{G}.$ (14)

Coprime factors are unique up to post- or pre-multiplication by bi-stable
transfer functions for right and left factors, respectively.

###### Lemma A.1

If $G(s)$ has coprime factorizations, then

$G\in H_{\infty}\iff M_{G}^{-1}\in H_{\infty}\iff\tilde{M}_{G}^{-1}\in
H_{\infty}.$

###### Proof 5

The “if” part of the first equivalence relation is immediate from (14). Its
“only if” part follows from rewriting the Bézout equality (13a) as
$M_{G}^{-1}=X_{G}+Y_{G}G$. The second relation follows by similar arguments.

###### Lemma A.2

Let $G(s)$ have coprime factorizations. If $\lambda\in\bar{\mathbb{C}}_{0}$ is
a pole of $G(s)$, then $M_{G}(\lambda)$ and $\tilde{M}_{G}(\lambda)$ are
singular.

###### Proof 6

Because $\lambda\in\bar{\mathbb{C}}_{0}$, the singularity of $M_{G}(\lambda)$
or $\tilde{M}_{G}(\lambda)$ does not depend on concrete factorizations taken.
If $M_{G}(\lambda)$ is nonsingular, then $N_{G}(\lambda)M_{G}(\lambda)^{-1}$
is bounded, which implies that $\lambda$ cannot be a pole of $G(s)$. The proof
for $\tilde{M}_{G}$ is similar.

##  Appendix B Poles, zeros, and their directions

This Appendixcollects some definitions and facts on poles, zeros, and their
directions for MIMO transfer functions. More details can be found in Skogestad
and Postlethwaite (2005), although we use slightly different definitions of
directions (subspaces, rather than vectors), in line with Mirkin (2019).

Let $G$ be a finite-dimensional LTI system having a proper transfer function
$G(s)$. The system $G$ has a state-space realization

$G(s)=\left[\begin{array}[]{c|c}A&B\\\ \hline\cr C&D\end{array}\right]\coloneq
D+C(sI-A)^{-1}B.$ (15)

The eigenvalues of $A$ are known as _poles_ of the realization (15). The set
of all realization poles, multiplicities counted, coincides with that of the
poles of the transfer function $G(s)$ if and only if the realization is
minimal. _Invariant zeros_ of the realization (15) are defined as the points
$\lambda\in\mathbb{C}$ at which

$\operatorname{rank}\left[\begin{array}[]{cccccc}A-\lambda I&B\\\
C&D\end{array}\right]<\operatorname{n\hskip
0.5ptrank}\left[\begin{array}[]{cccccc}A-sI&B\\\ C&D\end{array}\right]$

(the matrix polynomial of $s$ in the right-hand side is dubbed the Rosenbrock
system matrix). The set of all invariant zeros comprises transmission zeros of
the transfer function $G(s)$ and hidden modes of realization (15).

Poles and zeros have (spatial) directions for MIMO systems. Assume through the
rest of this Appendixthat the realization in (15) is minimal. By _input_ and
_output_ directions of a realization pole $\lambda$ of (15), we understand the
subspaces

$\displaystyle\mathrm{pdir_{i}}\\!\left(G,\lambda\right)$
$\displaystyle\coloneq B^{\top}\ker(\lambda I-A)^{\top}\subset\mathbb{C}^{m}$
(16a) and $\displaystyle\mathrm{pdir_{o}}\\!\left(G,\lambda\right)$
$\displaystyle\coloneq C\ker(\lambda I-A)\subset\mathbb{C}^{p},$ (16b)

respectively. If $\lambda$ is not a pole of $G(s)$, then both definitions in
(16) result in the trivial subspace $\\{0\\}$.

###### Lemma B.1

If $\lambda\in\mathbb{C}$ is a pole of $G(s)$, then

  * i)

$\lambda$ is a pole of $G(s)v$ whenever $0\neq
v\in\mathrm{pdir_{i}}\\!\left(G,\lambda\right)$,

  * ii)

$\lambda$ is a pole of $v^{\top}G(s)$ whenever $0\neq
v\in\mathrm{pdir_{o}}\\!\left(G,\lambda\right)$.

###### Proof 7

Bring in a minimal realization of $G$ as in (15). If $(A,Bv)$ is controllable,
then every eigenvalue of $A$ is a pole of $G(s)v$, by the observability of
$(C,A)$. If $(A,Bv)$ is uncontrollable, without loss of generality we may
assume that

$(A,B)=\left(\left[\begin{array}[]{cccccc}A_{\text{c}}&A_{12}\\\
0&A_{\text{\={c}}}\end{array}\right],\left[\begin{array}[]{cccccc}B_{\text{c}}\\\
B_{\text{\={c}}}\end{array}\right]\right)$

with controllable $(A_{\text{c}},B_{\text{c}}v)$ and $B_{\text{\={c}}}v=0$. In
this case $\lambda$ is not a pole of $G(s)v$ iff
$\lambda\not\in\operatorname{spec}(A_{\text{c}})$. So assume that
$\lambda\not\in\operatorname{spec}(A_{\text{c}})$, which implies that
$\lambda\in\operatorname{spec}(A_{\text{\={c}}})$ and that

$B^{\top}\ker(\lambda
I-A)^{\top}\subset\left[\begin{array}[]{cccccc}B_{\text{c}}^{\top}&B_{\text{\={c}}}^{\top}\end{array}\right]\operatorname{Im}\left[\begin{array}[]{cccccc}0\\\
I\end{array}\right]=\operatorname{Im}B_{\text{\={c}}}^{\top}.$

But then $v\in\mathrm{pdir_{i}}\\!\left(G,\lambda\right)\implies
v\in\operatorname{Im}B_{\text{\={c}}}^{\top}=(\ker B_{\text{\={c}}})^{\perp}$,
which contradicts the condition $B_{\text{\={c}}}v=0$. Hence, $\lambda$ must
be a pole of $G(s)v$. The second item follows by similar arguments.

Input and output directions of an invariant zero $\lambda$ are defined as

$\displaystyle\mathrm{zdir_{i}}\\!\left(G,\lambda\right)$
$\displaystyle\coloneq\left[\begin{array}[]{cccccc}0&I_{m}\end{array}\right]\ker\left[\begin{array}[]{cccccc}A-\lambda
I&B\\\ C&D\end{array}\right]\subset\mathbb{C}^{m}$ (17d) and
$\displaystyle\mathrm{zdir_{o}}\\!\left(G,\lambda\right)$
$\displaystyle\coloneq\left[\begin{array}[]{cccccc}0&I_{p}\end{array}\right]\ker\left[\begin{array}[]{cccccc}A-\lambda
I&B\\\
C&D\end{array}\right]{\vphantom{\left[\begin{array}[]{cccccc}1\\\\[-5.0pt]
1\end{array}\right]}}^{\top}\\!\subset\mathbb{C}^{p},$ (17j)

respectively. With some abuse of notation we use the definitions in (17) also
if $\lambda$ is not an invariant zero of (15), but the normal rank of $G(s)$
is deficient. For example, in our notation

$\mathrm{zdir_{i}}\\!\left(\left[\begin{array}[]{cccccc}1&-1\\\
-1&1\end{array}\right],\lambda\right)=\mathrm{zdir_{o}}\\!\left(\left[\begin{array}[]{cccccc}1&-1\\\
-1&1\end{array}\right],\lambda\right)=\operatorname{Im}\mathbb{1}_{2}$

for all $\lambda\in\mathbb{C}$. In such situations directions are understood
as normal null spaces.

###### Lemma B.2

If $\lambda\not\in\operatorname{spec}(A)$, then it is an invariant zero of $G$
iff $\operatorname{rank}G(\lambda)<\operatorname{n\hskip 0.5ptrank}G(s)$ and

$\mathrm{zdir_{i}}\\!\left(G,\lambda\right)=\ker
G(\lambda)\quad\text{and}\quad\mathrm{zdir_{o}}\\!\left(G,\lambda\right)=\ker\,[G(\lambda)]^{\top}.$

###### Proof 8

Follows from the relations

$\displaystyle\left[\begin{array}[]{cccccc}A-\lambda I&B\\\
C&D\end{array}\right]$ $\displaystyle=\left[\begin{array}[]{cccccc}A-\lambda
I&0\\\ C&G(\lambda)\end{array}\right]\left[\begin{array}[]{cccccc}I&(A-\lambda
I)^{-1}B\\\ 0&I\end{array}\right]$
$\displaystyle=\left[\begin{array}[]{cccccc}I&0\\\ C(A-\lambda
I)^{-1}&I\end{array}\right]\left[\begin{array}[]{cccccc}A-\lambda I&B\\\
0&G(\lambda)\end{array}\right]$

and the assumed invertibility of $A-\lambda I$.

###### Lemma B.3

If $\lambda\in\bar{\mathbb{C}}_{0}$, then it is a pole of $G(s)$ if and only
if it is a zero of the denominators $M_{G}(s)$ and $\tilde{M}_{G}(s)$ of its
coprime factorizations. Moreover,

$\mathrm{pdir_{i}}\\!\left(G,\lambda\right)=\mathrm{zdir_{o}}\\!\left(M_{G},\lambda\right)\quad\\!\\!\text{and}\\!\quad\mathrm{pdir_{o}}\\!\left(G,\lambda\right)=\mathrm{zdir_{i}}\\!\left(\smash{\tilde{M}_{G}},\lambda\right)$

in this case.

###### Proof 9

Follows by (Mirkin, 2019, Prop. 4.16) and the fact that a pole of $G(s)$ in
$\bar{\mathbb{C}}_{0}$ is a zero of all possible denominators.


# Unbalanced multi-drawing urn with random addition matrix II

Rafik Aguech Department of mathematics , University of Monastir, Tunisia,
,University of Monastir, Tunisia<EMAIL_ADDRESS><EMAIL_ADDRESS>Wissem Jedidi⋆ Université de Tunis El Manar, Faculté des
Sciences de Tunis, Département de Mathématiques, Laboratoire d’Analyse
Mathématiques et Applications LR11ES11. 2092 - El Manar I, Tunis, Tunisia
<EMAIL_ADDRESS>Olfa Selmi†

###### Abstract

At at stage $n\geq 1$, we pick out at random $m$ balls, say $k$ white balls
and $m-k$ black balls. We inspect the colors and then we return the balls,
according to a predefined replacement matrix, together with $(m-k)\;X_{n}$
white balls and $k\;Y_{n}$ black balls. Under the assumption that the seqence
$(X_{n},\;Y_{n})$ is bounded and i.i.d. Aguech & Selmi R&O  proved a strong
law of large numbers (SLLN) and a central limit theorem (CLT) on the
proportion of white balls. Here, we extend the last results as follows. In a
first step, we obtain the same results under the assumption that
$(X_{n},\;Y_{n})$ have the same distribution and that
$\mathbb{E}[X_{1}^{2}+Y_{1}^{2}]<\infty$. In a second step, removing the
assumption of identical distribution and assuming that
$\mathbb{E}[X_{n}^{2}+Y_{n}^{2}]<\infty$ for all $n$, we prove the SLLN and
CLT for the total number of balls in the urn.

##  1 Introduction

The following notations will be used throughout the paper. The indicator
function is denoted by $\mathbf{1}_{\\{.\\}}$, the abbreviation $a.s.$ stands
for almost surely and the notations $\stackrel{{\scriptstyle
a.s.}}{{\longrightarrow}}$, $\stackrel{{\scriptstyle d}}{{\longrightarrow}}$
respectively stand for the almost surely convergence and the convergence in
distribution. For a sequence of i.i.d random variables ${(R_{n})_{n}}$, we
denote by

$\mu_{R}=\mathbb{E}[{R_{1}}]\quad\mbox{ and
}\quad\sigma_{R}^{2}=\mathbb{V}[R_{1}],$

respectively the mean and the variance of a random variable $R_{1}$. For two
sequences of real number $x_{n}$ and $y_{n}$, we use the classical Landau
notations $x_{n}\sim y_{n}$ if $\lim_{n}x_{n}/y_{n}=1$, $x_{n}=o(y_{n})$ if
$\lim_{n}x_{n}/y_{n}=0$ and $x_{n}=O(y_{n})$ if
$\limsup_{n}|x_{n}/y_{n}|<\infty$. The mention $a.s.$ is added if the
sequences are random.

The Pólya urn is a simple and powerful model that still widely used since its
appearance in Pólya and Eggenberger Polya . Historically, the classical model
is an urn containing white balls and blue balls. At each discrete time $n\geq
1$, we pick out, uniformly at random, a ball, after inspecting its color, the
composition of the urn is then evolved according to a replacement rule
represented by a matrix given by

$R=\left(\begin{array}[]{cc}a&b\\\ c&d\\\ \end{array}\right),$

where $a,b,c$ and $d$ are integers. Since the mechanism of such a Markov chain
is simple, we find its applications in several fields such as computer
sciences, diseases spreading, finance, random research trees… For more details
about the history and the diversity of the applications of the urns processes
we refer the reader to Kotz&jon ; M.Hist

Afterwards, a generalized urn model has received interest in the literature,
this process evolves in the following way: we fix an integer $m\geq 1$, at
each discrete time step we draw randomly $m$ balls from the urn (either with
or without replacement), the colors are inspected and the balls are reinserted
to the urn together with other balls, depending on the sampled balls and the
addition rule is a matrix $R$ given by

$R=\left(\begin{array}[]{cc}a_{0}&b_{0}\\\ \vdots&\vdots\\\ a_{m-1}&b_{m-1}\\\
a_{m}&b_{m-1}\\\ \end{array}\right).$

Such a model was firstly introduced and studied by Chen & Wei chen&wei , Chen
& Kuba chen&kuba  and Kuba, Mahmoud & Panholzer kuba&mah&al , who considered a
balanced model i.e.

$a_{i}+b_{i}>0,\;\;\mbox{is a constant for all}\;0\leq i\leq m$

for both cases

$a_{i}=c(m-i)\quad\mbox{and}\quad a_{i}=c\,i,\quad\;1\leq i\leq
m,\quad\mbox{(for some integer}\;c).$

This model was further developed by Kuba & Mahmoud Kuba&mahmoud ; Kuba-
Mahmoud2  and Kuba & Sulzbach K&Sulz , who studied a more general model under
the assumptions of balance (i.e. $a_{i}+b_{i}=\sigma>0$) and affinity (the
conditional expectation of the number of white balls in the urn satisfies an
affine relation). They proved that the study can be reduced to the case when
the coefficient of the replacement matrix satisfies itself the affinity
condition given by

$a_{i}=a_{0}+\frac{a_{m}-a_{0}}{m}i,\quad\mbox{for}\;1\leq i\leq m-1.$

The works of Aguech, Lasmar & Selmi A&L&S  and Lasmar, Mailler & Selmi L&M&S
focused on this model by removing some assumptions. The challenge of the pre-
cited works, was to give a description of the behavior of the urn’s
composition, while the urn is neither balanced nor affine. Some of their
adapted stochastic approximation methods also gave consistent results.

Multiple drawing urns with random addition matrix have also been studied by
Aguech & Selmi R&O , who considered the model defined as follows:

  * •

We start with an urn containing white and black balls. Then, we fix an integer
$m\geq 1$ and suppose that at the beginning the urn contains more than $m$
balls (to ensure that the first draw is possible).

  * •

At each discrete time step $n\geq 1$, we pick out at random $m$ balls from the
urn. After inspecting the color of the sample, the balls are replaced to the
urn.

  * •

If the sample is composed by $k$ black balls and $m-k$ white balls, then

we add $(m-k)\;X_{n}$ white balls and $k\;Y_{n}$ black balls, where
$X_{n},\;Y_{n}=0,1,2,\ldots$ (1)

The sequences $(X_{n})_{n}$ and $(Y_{n})_{n}$ are independent. If
$R_{n}=X_{n}$ (respectively $R_{n}=Y_{n}$), then

the r.v.’s $R_{n}$ are independent copies of some integer-valued random
variables $R=X$ (respectively $R=Y$). (2)

  * •

We start with two given integers $W_{0},\;B_{0}$. In order to ensure that the
first draw is possible, the initial composition of the urn should satisfy

$T_{0}:=W_{0}+B_{0}\geq m$ (3)

The composition of the urn, at a time $n\geq 1$, is then given by a vector
$(W_{n},B_{n})$, where

$\displaystyle T_{n}$ $\displaystyle:=$ $\displaystyle\mbox{\it the total
number of balls in the urn},$ (4) $\displaystyle W_{n}$ $\displaystyle:=$
$\displaystyle\mbox{\it the number of white
balls}\in\\{0,1,\ldots,T_{n}\\},\quad B_{n}:=\mbox{\it the number of black
balls,}=T_{n}-W_{n}.$ (5)

It follows that, conditionally on $(W_{n-1},B_{n-1)}$, the probability of
drawing $k$ white balls and $(m-k)$ black balls, is for given, each time
$n\geq 1$, by

$\frac{{{W_{n-1}}\choose{k}}\;{{B_{n-1}}\choose{m-k}}}{{{T_{n-1}}\choose{m}}},\quad\mbox{\it
where}\;{{j}\choose{i}}=\frac{j!}{i!\,(j-i)!}.$

  * •

We denote by

$\displaystyle\xi_{n}$ $\displaystyle:=$ the number of white ball among the
$n^{th}$ sample $\in\\{0,1,\ldots m\\}$, (6) $\displaystyle Z_{n}$
$\displaystyle:=$ $\displaystyle\frac{W_{n}}{T_{n}}=\mbox{\it the proportion
of white balls in the urn after $n$ draws $\in[0,1]$.}$ (7)

Note that the r.v.’s $T_{n}$, $W_{n}$ and $Z_{n}$ are not deterministic, hence
they are of primary interest for studying.

Let $\mathcal{F}_{n}$ be the $\sigma$-field generated by the first $n$ draws.
Then, conditionally on $\mathcal{F}_{n+1}$, the random variable $\xi_{n}$ in
(6) follows the hypergeometric distribution with parameters
($m,W_{n-1},T_{n-1}$). Thus, the mean and the variance of $\xi_{n}$ are given
by

$\mathbb{E}[\xi_{n}|\mathcal{F}_{n-1}]=m\,\frac{W_{n-1}}{T_{n-1}}=m\;Z_{n-1},\quad\mathbb{V}[\xi_{n}|\mathcal{F}_{n-1}]=m\frac{W_{n-1}}{T_{n-1}}\left(1-\frac{T_{n-1}-m}{T_{n-1}-1}\right).$
(8)

Conditioning on the update of the urn at the time $n$, the number of balls in
the urn satisfies the recursive equation

$\left(\begin{array}[]{c}W_{n+1}\\\ B_{n+1}\\\
\end{array}\right)=\left(\begin{array}[]{c}W_{n}\\\ B_{n}\\\
\end{array}\right)+\left(\begin{array}[]{cc}0&X_{n+1}\\\ Y_{n+1}&0\\\
\end{array}\right)\left(\begin{array}[]{c}m-\xi_{n+1}\\\ \xi_{n+1}\\\
\end{array}\right),\quad n\geq 0,$ (9)

and in view of the evolution of the urn process, the total number of balls in
the urn after $n$ draws satisfies

$T_{n}=T_{0}+\sum_{i=1}^{n}X_{i}(m-\xi_{i})+\sum_{i=1}^{n}\xi_{i}Y_{i},\quad\mbox{
a.s}.$ (10)

Under a condition stronger than (2), namely

the sequence $R_{n}=X_{n}$ (respectively $R_{n}=Y_{n}$) is i.i.d and $R_{n}$
is bounded, (11)

Aguech & Selmi R&O  showed that there is a SLLN and a CLT for $Z_{n}$ and for
$T_{n}/n$. The contribution of this paper is to extend the their model. For
instance, in Section 2, we remove the stationary distribution and boundedness
conditions (11) and we obtain the same results if we assume for $R_{n}=X_{n}$
(respectively $R_{n}=Y_{n}$):

$\mbox{\it the sequence $R_{n}$ is i.i.d , $R_{n}$ is bounded below by some
positive constant $L$, and is square integrable}.$ (12)

In Section 3, we extend the last model by removing the assumption of identical
distribution. We assume instead that

the sequence $R_{n}$ is independent and
$\mathbb{E}[X_{n}^{2}+Y_{n}^{2}]<\infty$, for all $n\geq 1$, (13)

and we prove the SLLN and CLT with another normalization of the total number
of balls in the urn $T_{n}$. We also obtain the almost sure asymptotic
behavior of $T_{n}$ and $Z_{n}$ under the additional assumption: that the
sequence $\mathbb{E}[X_{n}]$ and $\mathbb{V}[X_{n}]$ are regularly of orders
$\alpha,\;\gamma>-1$ , i.e.

$\mbox{\it the sequence $\mathbb{E}[X_{n}]$ and $\mathbb{V}[X_{n}]$ are
regularly of orders $\alpha,\;\gamma>-1$},$

i.e.

$\mathbb{E}[X_{n}]=n^{\alpha}\,l_{1}(n),\quad\mathbb{V}[X_{n}]=n^{\gamma}l_{2}(n),\quad
l_{i},\;i=1,2\;\;\mbox{are a slowly varying functions}.$ (14)

(See (35) below for slowly varying functions).

Section 4 is an appendix, where we recall some useful results.

##  2 Results under assumption (12)

In this seection, we provide a SLLN and CLT for the proportion of white balls
and of the total number of balls in the urn.

###  2.1 The SLLN for $Z_{n}$ and $T_{n}$

###### Lemma 2.1

Under assumption (12), the total number $T_{n}$ defined in (38), satisfies

$\sum_{n\geq 0}\frac{1}{T_{n}^{2}}<\infty\quad\text{and}\quad\sum_{n\geq
0}\frac{1}{T_{n}}=\infty,\quad\mbox{a.s}.$

Proof.  From (10), we have $T_{n}\geq T_{0}+m\;n\;\min_{1\leq i\leq
n}(X_{i},Y_{i})\geq T_{0}+m\;n\;L$, then,

$\sum_{n}\frac{1}{T_{n}^{2}}\leq\sum_{n}\frac{1}{(T_{0}+m\;n\;L)^{2}}<+\infty,\quad
a.s.$

On the other hand, since $0\leq\xi_{i}\leq m$ for all $i\geq 1$, then

$\frac{T_{n}}{n}\leq\frac{T_{0}}{n}+\frac{m}{n}\sum_{i=1}^{n}(X_{i}+Y_{i}),\quad
a.s.$

By the SLLN, for all $\varepsilon>0$ and, a.s. for all $\omega\in\Omega$,
there exists $n_{0}(\omega)>0$ such that

$\frac{T_{n}(\omega)}{n}\leq\varepsilon+(\mu_{X}+\mu_{Y})\,m,\quad n\geq
n_{0}(\omega).$

The latter entails that for all $n\geq n(\omega)$

$\frac{1}{T_{n}(\omega)}\geq\frac{1}{n{\left(\varepsilon+\left(\mu_{X}+\mu_{Y}\right)m\right)}},$

and consequently, $\sum_{n}1/{T_{n}(\omega)}=\infty$. $\square$

###### Proposition 2.2

Under the assumption (12), the proportion $Z_{n}$ of white balls after $n$
draws satisfies

$Z_{n}\stackrel{{\scriptstyle
a.s.}}{{\longrightarrow}}z_{\star}:=\frac{\sqrt{\mu_{X}}}{\sqrt{\mu_{X}}+\sqrt{\mu_{Y}}},\quad
a.s.$ (15)

Proof.  Recall that, in view of the recursive equation (9), the number of
white balls $W_{n}$ and the total number of balls in the urn after $n$ draws
satisfy

$W_{n+1}=W_{n}+X_{n+1}(m-\xi_{n+1})\quad\text{and}\quad
T_{n+1}=T_{n}+m\,X_{n+1}+\xi_{n+1}(Y_{n+1}-X_{n+1}).$

Then, the proportion $Z_{n}$ can be described via the stochastic algorithm

$Z_{n+1}=Z_{n}+\gamma_{n+1}\big{(}f(Z_{n})+\epsilon_{n+1}\big{)},$ (16)

where

$f(z)=m\;\big{(}(\mu_{X}-\mu_{Y})\;z^{2}-2\;\mu_{X}\;z+\mu_{X}\big{)},\quad\epsilon_{n+1}:=D_{n+1}-\mathbb{E}[D_{n+1}|\mathcal{F}_{n}],$
(17)

and

$D_{n+1}:=\xi_{n+1}\,\left[Z_{n}\;(X_{n+1}-Y_{n+1})-X_{n+1}\right]+m\,X_{n+1}\,(1-Z_{n}).$

Consider the recursion (16) in the form of (48) in the Appendix, with

$\gamma_{n}:=\frac{1}{T_{n}}\quad\text{and}\quad
f(z):=m\;\big{(}(\mu_{X}-\mu_{Y})\;z^{2}-2\;\mu_{X}\;z+\mu_{X}\big{)}.$ (18)

Let us check the conditions of Theorem 4.1. Recall that in (3), we have
$\gamma_{0}\leq 1/m$. We also have:

  1. (a)

The first condition of Theorem 4.1 is satisfied since he r.v.’s
$Z_{n},\;\epsilon_{n}$ are bounded,
$\mathbb{E}[\epsilon_{n+1}|\mathcal{F}_{n}]=0$, $\gamma_{n}$ is nonnegative,
decreases towards zero, and $\gamma_{0}=1/{T_{0}}>0$ is a deterministic
constant.

  2. (b)

Since $f$ is a second order polynomial, we easily verify that the constant
$z_{\star}$, given by (15), is the unique solution of $f(z)=0$ and
$f^{\prime}(z)<0$.

  3. (c)

The constant $K$ of the condition (c) in Theorem 4.1 corresponds to
$K:=m\;\Big{(}|\mu_{X}-\mu_{Y}|+2\;\mu_{X}\Big{)}$, since for all $z\in[0,1]$,

$\frac{|f(z)|}{m}\leq|\mu_{X}-\mu_{Y}|\;z^{2}+2\;\mu_{X}\;z+\mu_{X}\leq\Big{(}|\mu_{X}-\mu_{Y}|+2\;\mu_{X}\Big{)}\;z+\mu_{X}\leq\Big{(}|\mu_{X}-\mu_{Y}|+2\;\mu_{X}\Big{)}(1+z).$

  4. (d)

Using the expression of $\epsilon_{n+1}$ in (17), the facts $X_{n+1}$ and
$Y_{n+1}$ are independent of $\mathcal{F}_{n}$, we observe that

$\epsilon_{n+1}=\xi_{n+1}\Big{(}Z_{n}\,(X_{n+1}-Y_{n+1})-X_{n+1}\Big{)}+m\,X_{n+1}\,(1-Z_{n})-m\,Z_{n}\,\Big{(}Z_{n}\,(\mu_{X}-\mu_{Y})-\mu_{X}\Big{)}-m\mu_{X}\,(1-Z_{n}\,).$

By (8), recall that $\mathbb{E}[\xi_{n+1}|\mathcal{F}_{n}]=m\,Z_{n}$, then

$\displaystyle\mathbb{E}\left[\epsilon_{n+1}^{2}|\mathcal{F}_{n}\right]$
$\displaystyle=$
$\displaystyle\mathbb{E}\left[\xi_{n+1}^{2}|\mathcal{F}_{n}\right]\;\Big{(}Z_{n}^{2}\left(\mu_{X^{2}}+\mu_{Y^{2}}-2\mu_{X}\mu_{Y}\right)+2\,Z_{n}\left(\mu_{X}\mu_{Y}-\mu_{X^{2}}\right)+\mu_{X^{2}}\Big{)}$
(19)
$\displaystyle-m^{2}Z_{n}^{2}\Big{(}Z_{n}\,(\mu_{X}-\mu_{Y})-\mu_{X}\Big{)}^{2}+m^{2}\,(1-Z_{n})^{2}\,\sigma_{X}^{2}$

Finally, using the facts that $0\leq\xi_{n+1}\leq m$, $Z_{n}\in[0,1]$, and
after elementary computations, we see that there exists a constant
$C_{\epsilon}>0$ such that

$\mathbb{E}\left[\epsilon_{n+1}^{2}|\mathcal{F}_{n}\right]\leq
C_{\epsilon}\Longrightarrow\mathbb{E}[|\epsilon_{n+1}|\big{|}\mathcal{F}_{n}]\leq\sqrt{C_{\epsilon}}.$
(20)

Lemma 2.1 and (20) ensure that, $\gamma_{n}$ given in (18), satisfies

$\sum_{n\geq 0}\gamma_{n}=\infty\quad\text{and}\quad\sum_{n\geq
0}\gamma_{n}^{2}\;\mathbb{E}[\epsilon_{n+1}^{2}|\mathcal{F}_{n}]\leq
C_{\epsilon}\sum_{n\geq 1}\gamma_{n}^{2}<\infty,\quad a.s.$

In conclusion, Theorem 4.1 asserts that $Z_{n}\stackrel{{\scriptstyle
a.s.}}{{\longrightarrow}}z_{\star}$. $\square$

The SLLN on the proportion of black balls of the urn is obtained by
considering $1-Z_{n}$.

###### Proposition 2.3

Under assumption (12), the total number $T_{n}$ of balls and the number of
white balls $W_{n}$ after $n$ draws, satisfy

$\frac{T_{n}}{n}\stackrel{{\scriptstyle
a.s.}}{{\longrightarrow}}m\sqrt{\mu_{X}\mu_{Y}}\quad\mbox{and}\quad\frac{W_{n}}{n}\stackrel{{\scriptstyle
a.s.}}{{\longrightarrow}}\frac{m\;\mu_{X}\;\sqrt{\mu_{Y}}}{\sqrt{\mu_{X}}+\sqrt{\mu_{Y}}}.$
(21)

Proof.  If
$G_{n}:=\sum_{i=1}^{n}\Big{(}\xi_{i}(Y_{i}-X_{i})-\mathbb{E}[\xi_{i}(Y_{i}-X_{i})|\mathcal{F}_{i-1}]\Big{)},$
then (10) gives the representation

$\frac{T_{n}}{n}=\frac{T_{0}}{n}+\frac{m}{n}\sum_{i=1}^{n}X_{i}+\frac{m(\mu_{Y}-\mu_{X})}{n}\sum_{i=1}^{n}Z_{i-1}+\frac{G_{n}}{n}.$
(22)

Since $(X_{i})_{i\geq 1}$ are i.i.d. random variables, the SLLN insures that
$\lim_{n\rightarrow+\infty}\sum_{i=1}^{n}X_{i}/n=\mu_{X}$ and Cesáro’s lemma
yield

$\sum_{i=1}^{n}\frac{Z_{i}}{n}\stackrel{{\scriptstyle
a.s.}}{{\longrightarrow}}z_{\star}.$

It remains to prove $G_{n}/n\stackrel{{\scriptstyle
a.s.}}{{\longrightarrow}}0$. We proceed as follows: the sequence
$(G_{n},\mathcal{F}_{n})_{n\geq 0}$ is a martingale difference whose quadratic
variation is given by

$<G>_{n}:=\sum_{i=1}^{n}\mathbb{E}[\Delta
G_{i}^{2}|\mathcal{F}_{i-1}],\quad\mbox{where}\quad\Delta
G_{n}=G_{n}-G_{n-1}=\xi_{n}(Y_{n}-X_{n})-\mathbb{E}[\xi_{n}(Y_{n}-X_{n})\;|\;\mathcal{F}_{n-1}].$

A simple computation gives

$\lim_{n\rightarrow+\infty}\mathbb{E}[\Delta
G_{n}^{2}|\mathcal{F}_{n-1}]=\left(m\;z_{\star}\;(1-z_{\star})+m^{2}\;{z_{\star}}^{2}\right)(\sigma_{Y}^{2}+\sigma_{X}^{2}),$

where $z_{\star}$ is given in (15). Cesáro’s lemma allows to conclude that

$\lim_{n\rightarrow+\infty}\frac{<G>_{n}}{n}\stackrel{{\scriptstyle
a.s.}}{{\longrightarrow}}\left(m\;z_{\star}\;(1-z_{\star})+m^{2}\;{z_{\star}}^{2}\right)\Longrightarrow\frac{G_{n}}{n}\stackrel{{\scriptstyle
a.s}}{{\longrightarrow}}0.$

The last claim is immediate by writing $W_{n}/n=(W_{n}/T_{n})(T_{n}/n)$.
$\square$

###  2.2 CLT for $Z_{n}$ and $W_{n}-T_{n}z_{\star}$

We give a CLT for the proportion of white balls in the urn.

###### Theorem 2.4

Under the assumptions of Lemma 2.1, the proportion of white balls in the urn
after $n$ draws, $Z_{n}$, satisfies as $n$ tends to infinity

$\sqrt{n}(Z_{n}-z_{\star})\stackrel{{\scriptstyle
d}}{{\longrightarrow}}\mathcal{N}\Big{(}0,\frac{P(z_{\star})}{3\mu_{X}\;\mu_{Y}}\Big{)},\quad\mbox{where}\;\;P(z_{\star})=\left(\sigma_{X}^{2}+\sigma_{Y}^{2}\right)\,z_{\star}^{4}-2\sigma_{X}^{2}\,z_{\star}^{3}+2\sigma_{X}^{2}\,z_{\star}^{2}-2\sigma_{X}^{2}\,z_{\star}+\sigma_{X}^{2}.$
(23)

The number, $W_{n}$, of white balls in the urn after $n$ draws satisfies

$\sqrt{n}\left(\frac{W_{n}}{n}-\frac{T_{n}}{n}\;z_{\star}\right)\stackrel{{\scriptstyle
d}}{{\longrightarrow}}\mathcal{N}\Big{(}0,\frac{m^{2}\,P(z_{\star})}{3}\Big{)}.$
(24)

Proof.  We recall that the sequences $\epsilon_{n},\;\gamma_{n}$ and the
constant $C_{\epsilon}$ are respectively given in (17), (18) and (20). To
prove the claimed statement, we need to check the assumptions $(a),\ldots,(e)$
of Theorem 4.2 in the Appendix, applied on the sequence
$K_{n}:=\sqrt{n}(Z_{n}-z_{\star})$. Observe that the representation (16) could
be rewritten in the form

$Z_{n+1}-z_{\star}=Z_{n}-z_{\star}+\frac{1}{T_{n+1}}\big{(}f(Z_{n})-f(z_{\star})+\epsilon_{n+1}\big{)},$
(25)

and let us denote

$K_{n}:=\sqrt{n}\left(Z_{n}-z_{\star}\right),\quad\alpha_{n}=\sqrt{1+\frac{1}{n}}-1\quad\mbox{and}\quad
g(z):=\frac{f(z)}{z_{\star}-z}.$ (26)

Using the identity
$f(Z_{n})-f(z_{\star})=g(Z_{n})\left(z_{\star}-Z_{n}\right)$, we rewrite (25)
into a recursive equation on $K_{n}$ of the form (49):

$K_{n+1}=\left(1-\frac{\Gamma_{n+1}}{n}\right)\,K_{n}+\frac{V_{n+1}}{\sqrt{n}},$

where

$\Gamma_{n+1}:=\frac{n\;g(Z_{n})}{T_{n+1}}-n\alpha_{n}\left(1-\frac{g(Z_{n})}{T_{n+1}}\right)\quad\mbox{and}\quad
V_{n+1}:=\frac{\epsilon_{n+1}\sqrt{n\left(n+1\right)}}{T_{n+1}}.$ (27)

  1. (a)

Using (10), we may decompose the r.v. $V_{n+1}$ in (27) in the form

$\sqrt{n}V_{n+1}=\frac{n\sqrt{n+1}}{T_{n+1}}\epsilon_{n+1}=n\;\sqrt{n+1}\;\epsilon_{n+1}\;\left(\frac{1}{T_{n+1}}-\frac{1}{T_{n}}+\frac{1}{T_{n}}\right)=n\;\sqrt{n+1}\;\epsilon_{n+1}\;\left(\frac{1}{T_{n}}-\frac{X_{n+1}\;(m-\xi_{n+1})+Y_{n+1}\;\xi_{n+1}}{T_{n+1}\;T_{n}}\right),$

and obtain the inequalities

$-n\sqrt{n+1}\,m\;\left(X_{n+1}+Y_{n+1}\right)\;\frac{|\epsilon_{n+1}|}{T_{n+1}T_{n}}+\frac{n\sqrt{n+1}}{T_{n}}\epsilon_{n+1}\leq\sqrt{n}V_{n+1}\leq
n\sqrt{n+1}\,m\;\left(X_{n+1}+Y_{n+1}\right)\;\frac{|\epsilon_{n+1}|}{T_{n+1}T_{n}}+\frac{n\sqrt{n+1}}{T_{n}}\epsilon_{n+1}.$

Then,

$-\frac{\sqrt{n+1}\;m}{m^{2}\;n\;L^{2}}\;\left(X_{n+1}+Y_{n+1}\right)|\epsilon_{n+1}|+\frac{n\sqrt{n+1}}{T_{n}}\epsilon_{n+1}\leq\sqrt{n}V_{n+1}\leq\frac{\sqrt{n+1}\;m}{m^{2}\;n\;L^{2}}\;\left(X_{n+1}+Y_{n+1}\right)|\epsilon_{n+1}|+\frac{n\sqrt{n+1}}{T_{n}}\epsilon_{n+1}.$

In one hand, since $X_{n+1}$ and $Y_{n+1}$ are independent of $\epsilon_{n+1}$
and $\mathcal{F}_{n}$ and using (20), we obtain

$\mathbb{E}\left[\frac{\sqrt{n+1}\;m}{m^{2}\;n\;L^{2}}\left(X_{n+1}+Y_{n+1}\right)|\epsilon_{n+1}|\;\big{|}\;\mathcal{F}_{n}\right]=\frac{\sqrt{n+1}\;m\big{(}\mu_{X}+\mu_{Y}\big{)}}{m^{2}\;n\;L^{2}}\mathbb{E}\left[|\epsilon_{n+1}|\;\big{|}\;\mathcal{F}_{n}\right]\stackrel{{\scriptstyle
a.s.}}{{\longrightarrow}}0.$

On the other hand,

$\mathbb{E}\left[\frac{n\sqrt{n+1}}{T_{n}}\epsilon_{n+1}\big{|}\mathcal{F}_{n}\right]=\frac{n\sqrt{n+1}}{T_{n}}\;\mathbb{E}\Big{[}\epsilon_{n+1}\big{|}\mathcal{F}_{n}\Big{]}=0,\quad\mbox{for
all}\;n\geq 1.$

All in one, we conclude that

$\mathbb{E}\Big{[}V_{n+1}|\mathcal{F}_{n}\Big{]}=o(n^{-1/2}),\quad a.s.$

  2. (b)

As in a), by (10), we have $T_{n+1}\geq m\;(n+1)\;L$, and then by (20),

$\mathbb{E}[V_{n+1}^{2}|\mathcal{F}_{n}]=\frac{n+1}{n}\mathbb{E}\left[\left(\frac{n+1}{T_{n+1}}\right)^{2}\epsilon_{n+1}^{2}|\mathcal{F}_{n}\right]\leq\frac{3}{2\;m^{2}\;L^{2}}\;\mathbb{E}\left[\epsilon_{n+1}^{2}\big{|}\mathcal{F}_{n}\right]\leq
C:=\frac{3\;C_{\epsilon}}{2\;m^{2}\;L^{2}},\quad n\geq 1.$

  3. (c)

The sequence $(n+1)/T_{n+1}$ is bounded by $(mL)^{-1}$, and by Proposition
2.3, it converges a.s. to $(m\,\sqrt{\mu_{X}\mu_{Y}})^{-1}$. Then, using (19),
we obtain

$\mathbb{E}[V_{n+1}^{2}|\mathcal{F}_{n}]=\frac{n+1}{n}\,\mathbb{E}\left[\left(\frac{n+1}{T_{n+1}}\;\epsilon_{n+1}\right)^{2}|\mathcal{F}_{n}\right]\stackrel{{\scriptstyle
a.s.}}{{\longrightarrow}}\frac{1}{m^{2}\mu_{X}\mu_{Y}}\lim_{n\rightarrow+\infty}\mathbb{E}\left[\epsilon_{n+1}^{2}|\mathcal{F}_{n}\right]=:\sigma^{2}>0,$

where

$\displaystyle\sigma^{2}$ $\displaystyle=$
$\displaystyle\frac{z_{\star}^{2}}{\mu_{X}\mu_{Y}}\left[z_{\star}^{2}\left(\mu_{X^{2}}+\mu_{Y^{2}}-2\mu_{X}\mu_{Y}\right)+2z_{\star}\left(\mu_{X}\mu_{Y}-\mu_{X^{2}}\right)+\mu_{X^{2}}\right]$
$\displaystyle-\frac{z_{\star}^{2}}{\mu_{X}\mu_{Y}}\left[z_{\star}^{2}\left(\mu_{X}-\mu_{Y}\right)^{2}-2z_{\star}\mu_{X}\left(\mu_{X}-\mu_{Y}\right)+\mu_{X}^{2}\right]+\left(1-z_{\star}\right)^{2}\frac{\sigma_{X}^{2}}{\mu_{X}\mu_{Y}}.$

Rearranging the last terms, we obtain the expression of
$P\left(z_{\star}\right)$:

$\mu_{X}\,\mu_{Y}\,\sigma^{2}=\left(\sigma_{X}^{2}+\sigma_{Y}^{2}\right)\,z_{\star}^{4}-2\sigma_{X}^{2}\,z_{\star}^{3}+2\sigma_{X}^{2}\,z_{\star}^{2}-2\sigma_{X}^{2}\,z_{\star}+\sigma_{X}^{2}=:P\left(z_{\star}\right).$
(28)

  4. (d)

The definition of $g$ in (26) gives

$g(Z_{n})\stackrel{{\scriptstyle
a.s.}}{{\longrightarrow}}-f^{\prime}(z_{\star})=2\;m\;\big{(}z_{\star}\left(\mu_{X}-\mu_{Y}\right)-\mu_{X}\big{)}=-2\,(m\sqrt{\mu_{X}}\sqrt{\mu_{Y}}),$

then Proposition 2.3 and $\alpha_{n}=\sqrt{1+\frac{1}{n}}-1=1/2n+O(n^{-2})$,
give

$\frac{n}{T_{n+1}}\stackrel{{\scriptstyle
a.s.}}{{\longrightarrow}}\frac{1}{m\sqrt{\mu_{X}}\sqrt{\mu_{Y}}}.$

By the expression of $\Gamma_{n+1}$ in (27), we retrieve
$\Gamma_{n+1}\stackrel{{\scriptstyle a.s.}}{{\longrightarrow}}3/2:=\Gamma$.

  5. (e)

Since the $X_{n}$’s are i.i.d., we claim that
$X_{n}/\sqrt{n}\stackrel{{\scriptstyle a.s.}}{{\longrightarrow}}0$. Indeed, if
$X_{n}/\sqrt{n}$ does not converge to 0, then reasoning with subsequences, we
will contradict the fact that $\mu_{X}=\sup_{n}\mathbb{E}[X_{n}]<\infty$. The
same holds for $\mu_{Y}$. We can then affirm that

$|D_{n+1}|\leq
3m\,(X_{n+1}+Y_{n+1})\quad\mbox{and}\quad\mathbb{E}\big{[}|D_{n+1}|\;\big{|}\;\mathcal{F}_{n}\big{]}\leq
3\;m\;(\mu_{X}+\mu_{Y})\Longrightarrow\frac{\epsilon_{n+1}}{\sqrt{n}}\stackrel{{\scriptstyle
a.s.}}{{\longrightarrow}}0\Longrightarrow\frac{V_{n+1}^{2}}{n}\stackrel{{\scriptstyle
a.s.}}{{\longrightarrow}}0.$

It follows that

$\lim_{n}\sum_{k=1}^{n}\frac{1}{n}\mathbb{E}\left[V_{k+1}^{2}\mathrm{\hskip
1.99997ptl1}_{\left(V_{k+1}^{2}\geq\varepsilon\,k\right)}\right]=\lim_{n}\frac{1}{n}\mathbb{E}\left[\sum_{k=1}^{n_{0}}\,V_{k+1}^{2}\,\mathrm{\hskip
1.99997ptl1}_{(V_{k+1}^{2}\geq\varepsilon\,k)}\right]=0,\quad a.s.$

After these five steps, we see that Theorem 4.2, then applies and we get (23).
Combining last Theorem with Proposition 2.3 and using the equality

$\sqrt{n}\left(\frac{W_{n}}{n}-\frac{T_{n}}{n}\;z_{\star}\right)=\frac{T_{n}}{n}\;\sqrt{n}\left(Z_{n}-z_{\star}\right),$

we obtain the last claim. $\square$

##  3 Results under assumption (13)

In this section, we also provide a SLLN and a CLT for the total number of ball
in the urn $T_{n}$ under the assumption (13). With the same notations as in
the Section 2, we focus on the urn model evolving under the dynamic (9) with
$X_{n}=Y_{n}$, i.e.:

$\left(\begin{array}[]{c}W_{n+1}\\\ B_{n+1}\\\
\end{array}\right)\stackrel{{\scriptstyle
d}}{{=}}\left(\begin{array}[]{c}W_{n}\\\ B_{n}\\\
\end{array}\right)+\left(\begin{array}[]{cc}X_{n+1}&0\\\ 0&X_{n+1}\\\
\end{array}\right)\,\left(\begin{array}[]{c}\xi_{n+1}\\\ m-\xi_{n+1}\\\
\end{array}\right),\quad n\geq 0.$ (29)

From the recursive equation (29), we have

$T_{n}=W_{n}+B_{n}=T_{0}+m\sum_{k=1}^{n}X_{k},$ (30)

and the number $W_{n}$ of and the proportion $Z_{n}=W_{n}/T_{n}$ of white
balls after $n$ draws, satisfy the recursive equations

$\displaystyle W_{n+1}$ $\displaystyle=$ $\displaystyle
W_{n}+X_{n+1}\,\xi_{n+1},$ (31) $\displaystyle Z_{n+1}$ $\displaystyle=$
$\displaystyle
Z_{n}\,\frac{T_{n}}{T_{n+1}}+\frac{X_{n+1}}{T_{n+1}}\xi_{n+1}=Z_{n}\,\left(1-m\,\frac{X_{n+1}}{T_{n+1}}\right)+\frac{X_{n+1}}{T_{n+1}}\xi_{n+1}.$
(32)

###  3.1 Limit theorems for $T_{n}$

The following Theorem will be useful.

######  Theorem 3.1 (Lindeberg’s Theorem Lindeberg )

Let $(X_{k})_{k}$ be a sequence of independent of square integrable random
variables defined on the same sample space. Let
$s_{n}^{2}:=\sum_{k=1}^{n}\mathbb{V}[X_{k}]>0$ and assume

$\lim_{n\to\infty}\frac{1}{s_{n}^{2}}\;\sum_{k=1}^{n}\mathbb{E}\left[(X_{k}-\mathbb{E}[X_{k}])^{2}\;\mathbf{1}_{\\{|X_{k}-\mathbb{E}[X_{k}]|>\varepsilon
s_{n}\\}}\right]=0,\;\;\mbox{for all}\;\varepsilon>0\quad\mbox{(Lindeberg's
condition)}.$ (33)

Then, the CLT holds with the normalization $s_{n}$, i.e.

$\frac{1}{s_{n}}\sum_{k=1}^{n}(X_{k}-\mathbb{E}[X_{k}])\stackrel{{\scriptstyle
d}}{{\longrightarrow}}N(0,1).$

Observe that the conditions of Theorem 3.1 imply our condition (3). Also
observe that due to (30), we

$\mathbb{E}[T_{n}]=T_{0}+m\sum_{k=1}^{n}\mathbb{E}[X_{k}],\quad\mathbb{V}[T_{n}]=m^{2}\sum_{k=1}^{n}\mathbb{V}[X_{k}],$
(34)

and then an immediate consequence of Theorem i is:

###### Corollary 3.2

Under Lindeberg’s condition (i) for the $X_{n}$’s of (1), we have

$\frac{T_{n}-\mathbb{E}[T_{n}]}{\sqrt{\mathbb{V}[T_{n}]}}\stackrel{{\scriptstyle
d}}{{\longrightarrow}}{\cal N}\Big{(}0,\,1\Big{)}.$

Motivated by the last CLT for the $T_{n}$, we provide an SLLN in next theorem.
We recall that a function $l_{0}:(0,\infty)\to(0,\infty)$ is slowly varying
function if it is measurable and

$\lim_{x\to\infty}\frac{l_{0}(\lambda x)}{l_{0}(x)}=1,\quad\forall\lambda>0.$
(35)

A sequence $c_{n}$ is regularly varying with order $\rho>0$ if

$c_{n}=n^{\rho}\,l_{0}(n),\quad\mbox{and $l_{0}$ is slowly varying function}.$

For the function $l_{0}$ we have the so-called Potter’s bounds provided by
(regu, , Theorem 1.5.6): for all $\delta>0$, there exits $A,\;N>0$ such that

$\frac{1}{A\;n^{\delta}}\leq l_{0}(n)\leq A\;n^{\delta},\quad n\geq N.$ (36)

Applying (regu, , Proposition 1.5.8), with $l(t)$ there equal to $l_{0}([t])$,
we retrieve

$\sum_{k=1}^{n}c_{k}\sim\frac{n\;c_{n}}{\rho+1}=\frac{n^{\rho+1}}{\rho+1}\,l_{0}(n),\quad\mbox{\it
as}\;n\to\infty.$ (37)

###### Theorem 3.3

Under the assumption (14),

$\tilde{T}_{n}:=\theta_{n}\left(\frac{T_{n}}{n\;\mathbb{E}[X_{n}]}-\frac{m}{\alpha+1}\right)\stackrel{{\scriptstyle
a.s.}}{{\longrightarrow}}0,$ (38)

for every deterministic sequence $\theta_{n}$ s.t.

$\sum_{n\geq
1}\frac{\theta_{n}^{2}}{n^{2\alpha-\gamma+1}}\frac{l_{2}(n)}{l_{1}(n)^{2}}<\infty.$
(39)

In particular, the latter holds for $\theta_{n}=1$ and $2\alpha-\gamma>0$.

Proof. By (34) and (39), as $n\to\infty$, we have

$\mathbb{E}[T_{n}]=T_{0}+m\;\sum_{k=1}^{n}\mathbb{E}[X_{k}]\sim\frac{m\,n}{\alpha+1}\mathbb{E}[X_{n}]=\frac{m}{\alpha+1}n^{\alpha+1}\,l_{1}(n)$
(40)

and

$\mathbb{V}[T_{n}]=m^{2}\sum_{k=1}^{n}\mathbb{V}[X_{k}]\sim\frac{m\,n}{\gamma+1}\mathbb{V}[X_{n}]\sim\frac{m}{\gamma+1}n^{\gamma+1}\,l_{1}(n).$

By the last asymptotic, by the condition (39) on $\theta_{n}$ and by Potter’s
bounds (36) applied on $l_{1}$ and $l_{2}$, we retrieve

$\frac{\mathbb{V}[T_{n}]}{(n\,\mathbb{E}[X_{n}]\,)^{2}}\sim\frac{(\alpha+1)^{2}}{m\,(\gamma+1)}\frac{1}{n^{2\alpha-\gamma+1}}\frac{l_{2}(n)}{l_{1}(n)^{2}}\quad\mbox{and
then}\quad\sum_{n\geq
1}\frac{\theta_{n}^{2}\;\mathbb{V}[T_{n}]}{(n\,\mathbb{E}[X_{n}]\,)^{2}}<\infty.$
(41)

Then,

$\frac{T_{n}-\mathbb{E}[T_{n}]}{n\,\mathbb{E}[X_{n}]}=\frac{m}{n\,\mathbb{E}[X_{n}]}\sum_{k=1}^{n}\big{(}X_{k}-\mathbb{E}[X_{k}]\big{)}$

and by Chebyshev’s theorem, we have that for all $\varepsilon\in(0,1)$,

$\mathbb{P}\left(\frac{\big{|}\theta_{n}\;(T_{n}-\mathbb{E}[T_{n}])\big{|}}{n\,\mathbb{E}[X_{n}]}\geq\varepsilon\right)\leq\left(\frac{m}{\varepsilon}\right)^{2}\;\theta_{n}^{2}\;\frac{\mathbb{V}[T_{n}]}{(n\,\mathbb{E}[X_{n}])^{2}}\sim\frac{m^{3}}{\varepsilon^{2}\;(\gamma+1)}\;\frac{\theta_{n}^{2}\;}{n^{2\alpha-\gamma+1}}\frac{l_{1}(n)}{l_{1}(n)^{2}}.$
(42)

Finally, since $2\alpha-\gamma>0$, and due to (41), (42) and by Borel-
Cantelli’s lemma, we conclude that

$\lim_{n}\tilde{T}_{n}=\lim_{n}\theta_{n}\left(\frac{T_{n}}{n\,\mathbb{E}[X_{n}]}-\frac{m}{\alpha+1}\right)=\lim_{n}\theta_{n}\;\frac{T_{n}-\mathbb{E}[T_{n}]}{n\,\mathbb{E}[X_{n}]}=0.$

The case where $\theta_{n}=1$ and $2\alpha-\gamma>0$ is also justified by
Potter’s bounds (36). $\Box$

###### Remark 3.4

  1. (i)

If each $X_{n}$ has a Binomial distribution with parameters
$\mathcal{B}(n,\,p)$, then $T_{n}$, given by (30), satisfies

$\frac{T_{n}-T_{0}}{m}\stackrel{{\scriptstyle
d}}{{=}}\mathcal{B}\left(\frac{n(n+1)}{2},p\right).$

In this case, Lindbergs’ conditions are satisfied, and also the conditions in
(14), with $\;\alpha=\gamma=1$ and $l=p/2$ there. Hence, Corollary 3.2 holds.

  2. (ii)

By the form (40) of $\mathbb{E}[T_{n}]$, one can notice that we always have

$\frac{\mathbb{E}[T_{n}]}{m\sum_{k=1}^{n}\mathbb{E}[X_{k}]}\to
l:=1+\frac{T_{0}}{m\;\lim_{n}\sum_{k=1}^{n}\mathbb{E}[X_{k}]}>0.$

Then, using the form the form (40) of $\mathbb{V}[T_{n}]$, we see that if
condition (14) is replaced by

$\sum_{n}\theta_{n}^{2}\;\frac{\sum_{k=1}^{n}\mathbb{V}[X_{k}]}{(\sum_{k=1}^{n}\mathbb{E}[X_{k}])^{2}}<\infty,$

and if we reproduce the proof of Theorem 3.3, then we arrive to

$\theta_{n}\;\left(\frac{T_{n}}{m\;\sum_{k=1}^{n}\mathbb{E}[X_{k}]}-l\right)\stackrel{{\scriptstyle
a.s.}}{{\longrightarrow}}0.$

###  3.2 The number of white balls under conditions (14)

To study the asymptotic behavior of the number of white balls, we need the
extra condition (14) on the sequence $(X_{n})_{n}$ which will give more
information than the almost sure convergence in (39).

###### Theorem 3.5

Under condition (14), the proportion $Z_{n}$, given by (32), converges almost
surely.

Proof. Denoting

$\delta_{n}:=\frac{X_{n}}{T_{n}}\quad\mbox{and}\quad\tilde{\xi}_{n}:=\xi_{n}-\mathbb{E}[\xi_{n}|\mathcal{F}_{n-1}],$

we see that the recursive equation $Z_{n}$ in (32) takes the form

$Z_{n+1}=Z_{n}+\delta_{n+1}\,\tilde{\xi}_{n+1}\Longrightarrow
Z_{n}=Z_{0}+\sum_{k=1}^{n}\delta_{k}\,\tilde{\xi}_{k}.$ (43)

To study the convergence of the sequence $(Z_{n})_{n}$, we have a problem on
the dependence of $\delta_{n+1}$ on the sigma field $\mathcal{F}_{n+1}$, a
problem that we avoid through the following decomposition:

$\delta_{n}=\tilde{\delta}_{n}+\left(\delta_{n}-\tilde{\delta}_{n}\right),\quad\mbox{where}\;\;\tilde{\delta}_{n}:=\frac{\alpha+1}{m}\frac{X_{n}}{n\;\mathbb{E}[X_{n}]}.$
(44)

From the expression of $T_{n}$ and $\tilde{T}_{n}$ given in (38), we have

$\frac{1}{T_{n}}=\frac{\alpha+1}{m\;n\;\mathbb{E}(X_{n})}\,\left(\frac{1}{1+\frac{\alpha+1}{m}\;\frac{\tilde{T}_{n}}{\theta_{n}}}\right),$

then we retrieve the expressions

$\delta_{n}=\frac{(\alpha+1)X_{n}}{m\;n\;\mathbb{E}(X_{n})}\;\left(\frac{1}{1+\frac{\alpha+1}{m}\,\frac{\tilde{T}_{n}}{\theta_{n}}}\right)\quad\mbox{and}\quad\left|\delta_{n}-\tilde{\delta}_{n}\right|=\tilde{\delta}_{n}\;\left|\,\frac{\frac{\alpha+1}{m}\,\frac{\tilde{T}_{n}}{\theta_{n}}}{1+\frac{\alpha+1}{m}\,\frac{\tilde{T}_{n}}{\theta_{n}}}\right|.$
(45)

Finally, by (43) and (44), we see that $Z_{n}$ can be decomposed into

$Z_{n}=Z_{0}+\sum_{k=1}^{n}\tilde{\delta}_{k}\,\tilde{\xi}_{k}+\sum_{k=1}^{n}\left(\delta_{k}-\tilde{\delta}_{k}\right)\,\tilde{\xi}_{k}=:Z_{0}+M_{n}^{(1)}+M_{n}^{(2)}.$
(46)

Now, observe that the products
$\;\tilde{\delta}_{k}\,\tilde{\xi}_{k},\;k=0,\;1,\;2,\ldots$, are non
correlated and centered r.v.’s, and that $\tilde{\delta}_{k}$ is independent
of $\xi_{k}$. We conclude that
$M_{n}^{(1)}=\sum_{k=1}^{n}\tilde{\delta}_{k}\,\tilde{\xi}_{k}$ is a centred
martingale which is bounded in $L^{2}$, i.e.
$\sup_{n}\mathbb{E}\left[\left(M_{n}^{(1)}\right)^{2}\right]<\infty$.
Actually, using $|\tilde{\xi}_{k}|\leq 2\,m$, the expression (44) of
$\tilde{\delta}_{k}$, then assumption (14) on $\mathbb{E}[X_{k}]$ and
$\mathbb{V}[X_{k}]$, we obtain, as we did for obtaining (41), that

$\mathbb{E}\left[\left(\sum_{k\geq
1}\tilde{\delta}_{k}\,\tilde{\xi}_{k}\right)^{2}\right]=\mathbb{V}\left[\sum_{k\geq
1}\tilde{\delta}_{k}\,\tilde{\xi}_{k}\right]=\sum_{k\geq
1}\mathbb{V}\left[\tilde{\delta}_{k}\,\tilde{\xi}_{k}\right]\leq
4\;m^{2}\sum_{k\geq
1}\mathbb{V}\left[\tilde{\delta}_{k}\right]=4\;(\alpha+1)^{2}\sum_{k\geq
1}\frac{l_{2}(k)}{k^{2\alpha-\gamma+2}l_{1}(k)^{2}}<+\infty.$

Thus, $M_{n}^{(1)}$ converges a.s.

For the rest of this proof, we choose $\lambda\in(0,\alpha-\gamma/2)$ and
$\theta_{n}=n^{\lambda}$. These choices ensure that condition (39) holds and
induces (38). Now, observing that the converging sequence $\tilde{T}_{n}$ is
bounded, we claim that

$\left|\delta_{k}-\tilde{\delta}_{k}\right|\leq\frac{\alpha+1}{m}\;\frac{X_{k}}{k\;\theta_{k}\;\mathbb{E}[X_{k}]},\quad\mbox{for
$k=N,\;N+1,\ldots,\;$ and some r.v. order $N>0$.}$ (47)

The check the latter, use again $|\tilde{\xi}_{k}|\leq 2\,m$, and the fact
that $|\tilde{T}_{k}|\stackrel{{\scriptstyle
a.s.}}{{\longrightarrow}}0,\;|\tilde{T}_{k}|/\theta_{k}\stackrel{{\scriptstyle
a.s.}}{{\longrightarrow}}0$, hence are both smaller than 1/2 for $k$ bigger
than some (random) order $N$. Then, using (45), we may write

$\left|\delta_{k}-\tilde{\delta}_{k}\right|\;|\tilde{\xi}_{k}|\leq
2\;(\alpha+1)\;\tilde{\delta}_{k}\;\left|\,\frac{\frac{\alpha+1}{m}\,\frac{\tilde{T}_{k}}{\theta_{k}}}{1+\frac{\alpha+1}{m}\,\frac{\tilde{T}_{k}}{\theta_{k}}}\right|\leq\frac{4\;(\alpha+1)^{2}}{m}\;\tilde{\delta}_{k}\;\frac{|\tilde{T}_{k}|}{\theta_{k}}\leq\frac{2\;(\alpha+1)^{2}}{m}\;\frac{\tilde{\delta}_{k}}{\theta_{k}}=\frac{\alpha+1}{m}\frac{X_{k}}{k\;\theta_{k}\;\mathbb{E}[X_{k}]},\quad
k\geq N.$

To conclude, use assumption (14) and then (47), write

$\mathbb{E}\left[\sum_{k\geq
1}\frac{X_{k}}{k\;\theta_{k}\;\mathbb{E}[X_{k}]}\right]=\sum_{k\geq
1}\frac{1}{k^{\lambda+1}}<\infty\Longrightarrow\sum_{k\geq
N}\frac{X_{k}}{k\;\theta_{k}\;\mathbb{E}[X_{k}]}<\infty,\;\;a.s.\Longrightarrow\sum_{k\geq
1}\left|\delta_{k}-\tilde{\delta}_{k}\right|\;|\tilde{\xi}_{k}|<\infty,\;\;a.s.$

Since
$M_{n}^{(2)}=\sum_{k=1}^{n}\left(\delta_{k}-\tilde{\delta}_{k}\right)\;\tilde{\xi}_{k}$,
we deduce its $a.s.$ convergence, like the one of $M_{n}^{(1)}$, hence of
$Z_{n}$. $\Box$

###### Example 3.6

As in Remark 3.4 (i), if $X_{n}\stackrel{{\scriptstyle d}}{{=}}B(n,\,p)$, then
all the assumptions of the last theorem are trivially satisfied.

##  4 Appendix: Basic tool of stochastic approximation

The following theorems will be used in our proofs.

######  Theorem 4.1 (Robbins-Monro, Theorem 1.4.26 pp.29, duflo )

Let $f:\mathbb{R}\to\mathbb{R}$ be a continuous function, and let
$Z_{n},\;\epsilon_{n},\;\gamma_{n}$, be sequences of real random variable,
adapted to a filtration $\mathcal{F}_{n}$, and linked by the recursive
equation

$Z_{n+1}=Z_{n}+\gamma_{n}\;\big{(}f(Z_{n})+\epsilon_{n+1}\big{)},\quad
n=0,\;1,\;2\ldots;$ (48)

Further, if the following conditions hold,

  1. (a)

$Z_{n},\;\epsilon_{n}$ is square integrable,
$\mathbb{E}[\epsilon_{n+1}|\mathcal{F}_{n}]=0$, $\gamma_{n}$ is nonnegative,
decreases towards zero, and $\gamma_{0}$ is bounded by a deterministic
constant;

  2. (b)

$f(z^{*})=0$, for some $z_{\star}\in\mathbb{R}$, and the scalar product
$<f(z),z-z^{*}>$ is negative for $z\neq z_{\star}$;

  3. (c)

$|f(z)|\leq K(1+|z|),\;\;$ for some $K>0$;

  4. (d)

$\sum_{n}\gamma_{n}=\infty\;$ and
$\;\sum_{n}\gamma_{n}^{2}\;\mathbb{E}[\epsilon_{n+1}^{2}|\mathcal{F}_{n}]<\infty,\;\;a.s.$;

then, $Z_{n}\stackrel{{\scriptstyle a.s.}}{{\longrightarrow}}z^{*}$.

######  Theorem 4.2 (Renlund renlund )

Suppose $(K_{n})_{n\geq 1}$ is a stochastic process adapted to a filtration
$\\{\mathcal{F}_{n},\;n\geq 1\\}.$ Suppose it follows the recursive equation:

$K_{n+1}=\left(1-\frac{\Gamma_{n+1}}{n}\right)\,K_{n}+\frac{V_{n+1}}{\sqrt{n}},$
(49)

where, for some deterministic quantities $C,\;\sigma^{2},\;\Gamma>0$, the
r.v.’s $\Gamma_{n},V_{n}\in\mathcal{F}_{n}$ satisfy:

  1. (a)

$\mathbb{E}[V_{n+1}|\mathcal{F}_{n}]=o(n^{-1/2}),\;a.s.$;

  2. (b)

for all $n\geq 1$, we have $\mathbb{E}[V_{n+1}^{2}|\mathcal{F}_{n}]\ \leq
C,\;a.s.$

  3. (c)

$\mathbb{E}[V_{n+1}^{2}|\mathcal{F}_{n}]\stackrel{{\scriptstyle
a.s.}}{{\longrightarrow}}\sigma^{2}$;

  4. (d)

$\Gamma_{n}\stackrel{{\scriptstyle a.s.}}{{\longrightarrow}}\Gamma$;

  5. (e)

For all $\varepsilon>0$, $\sum_{k=1}^{n}\mathbb{E}[V_{k+1}^{2}\mathrm{\hskip
1.99997ptl1}_{(V_{k+1}^{2}\geq\varepsilon k)}]\,/n\,\stackrel{{\scriptstyle
a.s.}}{{\longrightarrow}}0.$

Then,

$K_{n}\stackrel{{\scriptstyle
d}}{{\longrightarrow}}\mathcal{N}\left(0,\frac{\sigma^{2}}{2\Gamma}\right).$

## References

  * (1) G. Pólya and F. Eggenberger, G. Póly (1923). Über die statistik verkeletter vorge, Zeitschift für Angewandte Mathematik und Mechanic, 1, pp. 279–289.
  * (2) N.L. Johnson and S. Kotz (1977). _Urn Models and their Applications_ , John Wiley, New York.
  * (3) H. Renlund (2011). Limit theorem for Stochastic approxiamtion algorithm. _arxiv :1102.4741v1_.
  * (4) M. Duflo (1997). _Random iterative models_ , Springer-Verlag, Berlin.
  * (5) R. Aguech and O. Selmi (2019). Unbalanced multi-drawing urn with random addition matrix, _Arab Journal of Mathematical Sciences_. In press, pp. 1–19.
  * (6) H. Mahmoud (2008). _Pólya Urn Models_ , Chapman-Hall, Orlando.
  * (7) M. R Chen and C. Z Wei (2005). A new urn model, _Journal of Applied Probability,_ 42(4), pp. 964–976.
  * (8) M. R Chen and M. Kuba (2013). On generalized Polya urn models, _Journal of Applied Probability Theory_ , 50(4), pp. 1169-1186.
  * (9) M. Kuba, H. Mahmoud and A. Panholzer (2013). Analysis of a generalized Friedman’s urn with multiple drawings, _Discrete Applied Mathematics_ , 161, pp. 2968–2984.
  * (10) M. Kuba and H. Mahmoud. (2015). Two-colour balanced affine urn models with multiple drawings I: Central limit theorem. _arXiv :1503.09069_.
  * (11) M. Kuba and H. Mahmoud (2015). Two-colour balanced affine urn models with multiple drawings II: large-index and triangular urns. _arXiv: 1509.09053_.
  * (12) M. Kuba and H. Sulzbach (2017). On martingale tail sums in affine two color urn models with multiple drawings, _Journal of Applied probability_ , 54, pp. 1–21.
  * (13) R. Aguech, N. Lasmar and O. Selmi (2018). A generalized urn model with multiple drawing and random addition. _Annals of the Institute of Statistical Mathematics_. pp. 1–20.
  * (14) N. Lasmar, C. Mailler and O. Selmi (2018). Multiple drawing multi-color urns by stochastic approximation. Journal of Applied Probability. 55(1), pp. 254–281.
  * (15) J.W. Lindeberg. Eine neue herleitung des exponentialgesetzes in der wahrscheinlichkeit-srechnung. Math. Zeitschr, pages 211-225, 1922.
  * (16) N.H. Bingham, C.M. Goldie, J.L. Teugels (1987). _Regular variation_ , Cambridge University Press, Cambridge.