# Mutual information rate and bounds for it

M. S. Baptista1, R. M. Rubinger2, E. R. V. Junior2, J. C. Sartorelli3, U.
Parlitz4, and C. Grebogi1,5 1 Institute for Complex Systems and Mathematical
Biology, SUPA, University of Aberdeen, AB24 3UE Aberdeen, United Kingdom
2 Federal University of Itajuba, Av. BPS 1303, Itajubá, Brazil
3 Institute of Physics, University of São Paulo, Rua do Matão, Travessa R,
187, 05508-090, São Paulo, Brazil
4 Biomedical Physics Group, Max Planck Institute for Dynamics and Self-
Organization, Am Fassberg 17, 37077 Göttingen, Germany
5 Freiburg Institute for Advanced Studies (FRIAS), University of Freiburg,
Albertstr. 19, 79104 Freiburg, Germany

###### Abstract

The amount of information exchanged per unit of time between two nodes in a
dynamical network or between two data sets is a powerful concept for analysing
complex systems. This quantity, known as the mutual information rate (MIR), is
calculated from the mutual information, which is rigorously defined only for
random systems. Moreover, the definition of mutual information is based on
probabilities of significant events. This work offers a simple alternative way
to calculate the MIR in dynamical (deterministic) networks or between two data
sets (not fully deterministic), and to calculate its upper and lower bounds
without having to calculate probabilities, but rather in terms of well known
and well defined quantities in dynamical systems. As possible applications of
our bounds, we study the relationship between synchronisation and the exchange
of information in a system of two coupled maps and in experimental networks of
coupled oscillators.

##  I Introduction

Shannon’s entropy quantifies information shannon . It measures how much
uncertainty an observer has about an event being produced by a random system.
Another important concept in the theory of information is the mutual
information shannon . It measures how much uncertainty an observer has about
an event in a random system X after observing an event in a random system Y
(or vice-versa).

Mutual information is an important quantity because it quantifies not only
linear and non-linear interdependencies between two systems or data sets, but
also is a measure of how much information two systems exchange or two data
sets share. Due to these characteristics, it became a fundamental quantity to
understand the development and function of the brain sporns_TCS2004 ; roland ,
to characterise juergen_EPJ2009 ; palus  and model complex systems
fraser_PRA1986 ; ulrich_kluwer1998 ; kantz_book  or chaotic systems, and to
quantify the information capacity of a communication system haykin_book . When
constructing a model of a complex system, the first step is to understand
which are the most relevant variables to describe its behaviour. Mutual
information provides a way to identify those variables rossi .

However, the calculation of mutual information in dynamical networks or data
sets faces three main difficultiespaninski ; palus ; steuer ; papana . Mutual
information is rigorously defined for random memoryless processes, only. In
addition, its calculation involves probabilities of significant events and a
suitable space where probability is calculated. The events need to be
significant in the sense that they contain as much information about the
system as possible. But, defining significant events, for example the fact
that a variable has a value within some particular interval, is a difficult
task because the interval that provides significant events is not always
known. Finally, data sets have finite size. This prevents one from calculating
probabilities correctly. As a consequence, mutual information can often be
calculated with a bias, only paninski ; palus ; steuer ; papana .

In this work, we show how to calculate the amount of information exchanged per
unit of time [Eq. (3)], the so called mutual information rate (MIR), between
two arbitrary nodes (or group of nodes) in a dynamical network or between two
data sets. Each node representing a d-dimensional dynamical system with $d$
state variables. The trajectory of the network considering all the nodes in
the full phase space is called “attractor” and represented by $\Sigma$. Then,
we propose an alternative method, similar to the ones proposed in Refs.
baptista_PRE2008 ; baptista_PLOSONE2008 , to calculate significant upper and
lower bounds for the MIR in dynamical networks or between two data sets, in
terms of Lyapunov exponents, expansion rates, and capacity dimension. These
quantities can be calculated without the use of probabilistic measures. As
possible applications of our bounds calculation, we describe the relationship
between synchronisation and the exchange of information in small experimental
networks of coupled Double-Scroll circuits.

In previous works of Refs. baptista_PRE2008 ; baptista_PLOSONE2008 , we have
proposed an upper bound for the MIR in terms of the positive conditional
Lyapunov exponents of the synchronisation manifold. As a consequence, this
upper bound could only be calculated in special complex networks that allow
the existence of complete synchronisation. In the present work, the proposed
upper bound can be calculated to any system (complex networks and data sets)
that admits the calculation of Lyapunov exponents.

We assume that an observer can measure only one scalar time series for each
one of two chosen nodes. These two time series are denoted by $X$ and $Y$ and
they form a bidimensional set $\Sigma_{\Omega}=(X,Y)$, a projection of the
“attractor” into a bidimensional space denoted by $\Omega$. To calculate the
MIR in higher-dimensional projections $\Omega$, see Supplementary Information.
Assume that the space $\Omega$ is coarse-grained in a square grid of $N^{2}$
boxes with equal sides $\epsilon$, so $N=1/\epsilon$.

Mutual information is defined in the following way shannon . Given two random
variables, X and Y, each one produces events $i$ and $j$ with probabilities
$P_{X}(i)$ and $P_{Y}(j)$, respectively, the joint probability between these
events is represented by $P_{XY}(i,j)$. Then, mutual information is defined as

$I_{S}=H_{X}+H_{Y}-H_{XY}.$ (1)

$H_{X}$ = $-\sum_{i}P_{X}(i)\log{[P_{X}(i)]}$, $H_{Y}$ =
$-\sum_{j}P_{Y}(j)\log{[P_{Y}(j)]}$, and
$H_{XY}=-\sum_{i,j}P_{XY}(i,j)\log{[P_{XY}(i,j)]}$. For simplification in our
notation for the probabilities, we drop the subindexes X, Y, and XY, by making
$P_{X}(i)=P(i)$, $P_{Y}(j)=P(j)$, and $P_{XY}(i,j)=P(i,j)$. When using Eq. (1)
to calculate the mutual information between the dynamical variables $X$ and
$Y$, the probabilities appearing in Eq. (1) are defined such that $P(i)$ is
the probability of finding points in a column $i$ of the grid, $P(j)$ of
finding points in the row $j$ of the grid, and $P(i,j)$ the probability of
finding points where the column $i$ meets the line $j$ of the grid.

The MIR was firstly introduced by Shannon shannon  as a “rate of actual
transmission” blanc  and later more rigorously redefined in Refs.
dobrushin1959 ; gray1980 . It represents the mutual information exchanged
between two dynamical variables (correlated) per unit of time. To simplify the
calculation of the MIR, the two continuous dynamical variables are transformed
into two discrete symbolic sequences $X$ and $Y$. Then, the MIR is defined by

$MIR=\lim_{n\rightarrow\infty}\frac{I_{S}(n)}{n},$ (2)

where $I_{S}(n)$ represents the usual mutual information between the two
sequences $X$ and $Y$, calculated by considering words of length $n$.

The MIR is a fundamental quantity in science. Its maximal value gives the
information capacity between any two sources of information (no need for
stationarity, statistical stability, memoryless) verdu . Therefore,
alternative approaches for its calculation or for the calculation of bounds of
it are of vital relevance. Due to the limit to infinity in Eq. (2) and because
it is defined from probabilities, the MIR is not easy to be calculated
especially if one wants to calculate it from (chaotic) trajectories of a large
complex network or data sets. The difficulties faced to estimate the MIR from
dynamical systems and networks are similar to the ones faced in the
calculation of the Kolmogorov-Sinai entropy, $H_{KS}$ kolmogorov , (Shannon’s
entropy per unit of time). Because of these difficulties, the upper bound for
$H_{KS}$ proposed by Ruelle ruelle  in terms of the Lyapunov exponents and
valid for smooth dynamical systems ($H_{KS}\leq\sum\lambda^{+}_{i}$, where
$\lambda^{+}_{i}$ represent all the $i$ positive Lyapunov exponents) or the
Pesin’s equality pesin  ($H_{KS}=\sum\lambda^{+}_{i}$) proved in Ref.
ledrapier  to be valid for the large class of systems that possess a SRB
measure, became so important in the theory of dynamical systems. Our upper
bound [Eq. (13)] is a result equivalent to the work of Ruelle.

##  II Main results

One of the main results of this work (whose derivation can be seen in Sec.
III.2) is to show that, in dynamical networks or data sets with fast decay of
correlation, $I_{S}$ in Eq. (1) represents the amount of mutual information
between $X$ and $Y$ produced within a special time interval $T$, where $T$
represents the time for the dynamical network (or data sets) to lose its
memory from the initial state or the correlation to decay to zero. Correlation
in this work is not the usual linear correlation, but a non-linear correlation
defined in terms of the evolution of spatial probabilities, the quantity
$C(T)$ in Sec. III.1. Therefore, the mutual information rate (MIR), between
the dynamical variables $X$ and $Y$ (or two data sets) can be estimated by

$MIR=\frac{I_{S}}{T}$ (3)

In systems that present sensitivity to initial conditions, e.g. chaotic
systems, predictions are only possible for times smaller than this time $T$.
This time has other meanings. It is the expected time necessary for a set of
points belonging to an $\epsilon$-square box in $\Omega$ to spread over
$\Sigma_{\Omega}$ and it is of the order of the shortest Poincaré return time
for a point to leave a box and return to it gao ; baptista_PLA2010 . It can be
estimated by

$T\approx\frac{1}{\lambda_{1}}\log{\left[\frac{1}{\epsilon}\right]}.$ (4)

where $\lambda_{1}$ is the largest positive Lyapunov exponent measured in
$\Sigma_{\Omega}$. Chaotic systems present the mixing property (see Sec.
III.1), and as a consequence the correlation $C(t)$ always decays to zero,
surely after an infinitely long time. The correlation of chaotic systems can
also decay to zero for sufficiently large but finite $t=T$ (see Supplementary
Information). $T$ can be interpreted to be the minimum time required for a
system to satisfy the conditions to be considered mixing. Some examples of
physical systems that are proved to be mixing and have exponentially fast
decay of correlation are nonequilibrium steady-state nonequilibrium , Lorenz
gases (models of diffusive transport of light particles in a network of
heavier particles) sinai_1970 , and billiards young_2001 . An example of a
“real world” physical complex system that presents exponentially fast decay of
correlation is plasma turbulence baptista_PHYSICAA2001 . We do not expect that
data coming from a “real world” complex system is rigorously mixing and has an
exponentially fast decay of correlation. But, we expect that the data has a
sufficiently fast decay of correlation (e.g. stretched exponential decay or
polynomially fast decays), implying that the system has sufficiently high
sensitivity to initial conditions and as a consequence $C(t)\cong 0$, for a
reasonably small and finite time $t=T$.

The other two main results of our work are presented in Eqs. (5) and (7),
whose derivations are presented in Sec. III.3. The upper bound for the MIR is
given by

$I_{C}=\lambda_{1}-\lambda_{2}=\lambda_{1}(2-D),$ (5)

where $\lambda_{1}$ and $\lambda_{2}$ (positive defined) represent the largest
and the second largest Lyapunov exponent measured in $\Sigma_{\Omega}$, if
both exponents are positive. If the $i$-largest exponent is negative, then we
set $\lambda_{i}=0$. If the set $\Sigma_{\Omega}$ represents a periodic orbit,
$I_{C}=0$, and therefore there is no information being exchanged. The quantity
$D$ is defined as

$D=-\frac{\log{(N_{C}(t=T))}}{\log{(\epsilon)}},$ (6)

where $N_{C}(t=T)$ is the number of boxes that would be covered by fictitious
points at time $T$. At time $t=0$, these fictitious points are confined in an
$\epsilon$-square box. They expand not only exponentially fast in both
directions according to the two positive Lyapunov exponents, but expand
forming a compact set, a set with no “holes”. At $t=T$, they spread over
$\Sigma_{\Omega}$.

The lower bound for the MIR is given by

$I_{C}^{l}=\lambda_{1}(2-\tilde{D}_{0}),$ (7)

where $\tilde{D}_{0}$ represents the capacity dimension of the set
$\Sigma_{\Omega}$

$\tilde{D}_{0}={\lim_{\epsilon\rightarrow
0}}\left[-\frac{\log{(\tilde{N}_{C}(\epsilon))}}{\log{(\epsilon)}}\right],$
(8)

where $\tilde{N}_{C}$ represents the number of boxes in $\Omega$ that are
occupied by points of $\Sigma_{\Omega}$.

$D$ is defined in a way similar to the capacity dimension, thought it is not
the capacity dimension. In fact, $D\leq\tilde{D}_{0}$, because $\tilde{D}_{0}$
measures the change in the number of occupied boxes in $\Omega$ as the space
resolution varies, whereas $D$ measures the relative number of boxes with a
certain fixed resolution $\epsilon$ that would be occupied by the fictitious
points (in $\Omega$) after being iterated for a time $T$. As a consequence,
the empty space in $\Omega$ that is not occupied by $\Sigma_{\Omega}$ does not
contribute to the calculation of $\tilde{D}_{0}$, whereas it contributes to
the calculation of the quantity $D$. In addition, $N_{C}\geq\tilde{N}_{C}$
(for any $\epsilon$), because while the fictitious points form a compact set
expanding with the same ratio as the one for which the real points expand
(ratio provided by the Lyapunov exponents), the real set of points
$\Sigma_{\Omega}$ might not occupy many boxes.

##  III Methods

###  III.1 Mixing, correlation decay and invariant measures

Denote by $F^{T}(x)$ a mixing transformation that represents how a point
$x\in\Sigma_{\Omega}$ is mapped after a time $T$ into $\Sigma_{\Omega}$, and
let $\rho(x)$ to represent the probability of finding a point of
$\Sigma_{\Omega}$ in $x$ (natural invariant density). Let $I^{\prime}_{1}$
represent a region in $\Omega$. Then, $\mu(I^{\prime}_{1})=\int\rho(x)dx$, for
$x\in I^{\prime}_{1}$ represents the probability measure of the region
$I^{\prime}_{1}$. Given two square boxes $I^{\prime}_{1}\in\Omega$ and
$I^{\prime}_{2}\in\Omega$, if $F^{T}$ is a mixing transformation, then for a
sufficiently large $T$, we have that the correlation
$C(T)=\mu[F^{-T}(I^{\prime}_{1})\cap
I^{\prime}_{2}]-\mu[I^{\prime}_{1}]\mu[I^{\prime}_{2}]$, decays to zero, the
probability of having a point in $I^{\prime}_{1}$ that is mapped to
$I^{\prime}_{2}$ is equal to the probability of being in $I^{\prime}_{1}$
times the probability of being in $I^{\prime}_{2}$. That is typically what
happens in random processes.

If the measure $\mu(\Sigma_{\Omega})$ is invariant, then
$\mu([F^{-T}(\Sigma_{\Omega})]=\mu(\Sigma_{\Omega})$. Mixing and ergodic
systems produce measures that are invariant.

###  III.2 Derivation of the mutual information rate (MIR) in dynamical
networks and data sets

We consider that the dynamical networks or data sets to be analysed present
either the mixing property or have fast decay of correlations, and their
probability measure is time invariant. If a system that is mixing for a time
interval $T$ is observed (sampled) once every time interval $T$, then the
probabilities generated by these snapshot observations behave as if they were
independent, and the system behaves as if it were a random process. This is so
because if a system is mixing for a time interval $T$, then the correlation
$C(T)$ decays to zero for this time interval. For systems that have some decay
of correlation, surely the correlation decays to zero after an infinite time
interval. But, this time interval can also be finite, as shown in
Supplementary Information.

Consider now that we have experimental points and they are sampled once every
time interval $T$. The probability
$\tilde{P}_{XY}(i,j)\rightarrow\tilde{P}_{XY}(k,l)$ of the sampled trajectory
to follow a given itinerary, for example to fall in the box with coordinates
$(i,j)$ and then be iterated to the box $(k,l)$ depends exclusively on the
probabilities of being at the box $(i,j)$, represented by
$\tilde{P}_{XY}(i,j)$, and being at the box $(k,l)$, represented by
$\tilde{P}_{XY}(k,l)$. Therefore, for the sampled trajectory,
$\tilde{P}_{XY}(i,j)\rightarrow\tilde{P}_{XY}(k,l)=\tilde{P}_{XY}(i,j)\tilde{P}_{XY}(k,l)$.
Analogously, the probability $\tilde{P}_{X}(i)\rightarrow\tilde{P}_{Y}(j)$ of
the sampled trajectory to fall in the column (or line) $i$ of the grid and
then be iterated to the column (or line) $j$ is given by
$\tilde{P}_{X}(i)\rightarrow\tilde{P}_{Y}(j)=\tilde{P}_{X}(i)\tilde{P}_{Y}(j)$.

The MIR of the experimental non-sampled trajectory points can be calculated
from the mutual information $\tilde{I}_{S}$ of the sampled trajectory points
that follow itineraries of length $n$:

$MIR=\lim_{n\rightarrow\infty}\frac{\tilde{I}_{S}(n)}{nT},$ (9)

Due to the absence of correlations of the sampled trajectory points, the
mutual information for these points following itineraries of length $n$ can be
written as

$\tilde{I}_{S}(n)=n[\tilde{H}_{X}(n=1)+\tilde{H}_{Y}(n=1)-\tilde{H}_{XY}(n=1)],$
(10)

where $\tilde{H}_{X}(n=1)$ =
$-\sum_{i}\tilde{P}_{X}(i)\log{[\tilde{P}_{X}(i)]}$, $\tilde{H}_{Y}(n=1)$ =
$-\sum_{j}\tilde{P}_{Y}(j)\log{[\tilde{P}_{Y}(j)]}$, and
$\tilde{H}_{XY}(n=1)=-\sum_{i,j}\tilde{P}_{XY}(i,j)\log{[\tilde{P}_{XY}(i,j)]}$,
and $\tilde{P}_{X}(i)$, $\tilde{P}_{Y}(j)$, and $\tilde{P}_{XY}(i,j)$
represent the probability of the sampled trajectory points to fall in the line
$i$ of the grid, in the column $j$ of the grid, and in the box $(i,j)$ of the
grid, respectively.

Due to the time invariance of the set $\Sigma_{\Omega}$ assumed to exist, the
probability measure of the non-sampled trajectory is equal to the probability
measure of the sampled trajectory. If a system that has a time invariant
measure is observed (sampled) once every time interval $T$, the observed set
has the same natural invariant density and probability measure of the original
set. As a consequence, if $\Sigma_{\Omega}$ has a time invariant measure, the
probabilities $P(i)$, $P(j)$, and $P(i,j)$ (used to calculate $I_{S}$) are
equal to $\tilde{P}_{X}(i)$, $\tilde{P}_{Y}(j)$, and $\tilde{P}_{XY}(i,j)$.

Consequently, $\tilde{H}_{X}(n=1)=H_{X}$, $\tilde{H}_{Y}(n=1)=H_{Y}$, and
$\tilde{H}_{XY}(n=1)=H_{XY}$, and therefore $\tilde{I}_{S}(n)=nI_{S}(n)$.
Substituting into Eq. (9), we finally arrive to

$MIR=\frac{I_{S}}{T}$ (11)

where $I_{S}$ between two nodes is calculated from Eq. (1).

Therefore, in order to calculate the MIR, we need to estimate the time $T$ for
which the correlation of the system approaches zero and the probabilities
$P(i)$, $P(j)$, $P(i,j)$ of the experimental non-sampled experimental points
to fall in the line $i$ of the grid, in the column $j$ of the grid, and in the
box $(i,j)$ of the grid, respectively.

###  III.3 Derivation of an upper ($I_{C}$) and lower ($I_{C}^{l}$) bounds for
the MIR

Consider that our attractor $\Sigma$ is generated by a 2d expanding system
that possess 2 positive Lyapunov exponents $\lambda_{1}$ and $\lambda_{2}$,
with $\lambda_{1}\geq\lambda_{2}$. $\Sigma\in\Omega$. Imagine a box whose
sides are oriented along the orthogonal basis used to calculate the Lyapunov
exponents. Then, points inside the box spread out after a time interval $t$ to
$\epsilon\sqrt{2}\exp^{\lambda_{1}t}$ along the direction from which
$\lambda_{1}$ is calculated. At $t=T$,
$\epsilon\sqrt{2}\exp^{\lambda_{1}T}=L$, which provides $T$ in Eq. (4), since
$L=\sqrt{2}$. These points spread after a time interval $t$ to
$\epsilon\sqrt{2}\exp^{\lambda_{2}t}$ along the direction from which
$\lambda_{2}$ is calculated. After an interval of time $t=T$, these points
spread out over the set $\Sigma_{\Omega}$. We require that for $t\leq T$, the
distance between these points only increases: the system is expanding.

Imagine that at $t=T$, fictitious points initially in a square box occupy an
area of
$\epsilon\sqrt{2}\exp^{\lambda_{2}T}L=2\epsilon^{2}\exp^{(\lambda_{2}+\lambda_{1})T}$.
Then, the number of boxes of sides $\epsilon$ that contain fictitious points
can be calculated by
$N_{C}=2\epsilon^{2}\exp^{(\lambda_{1}+\lambda_{2})T}/2\epsilon^{2}=\exp^{(\lambda_{1}+\lambda_{2})T}$.
From Eq. (4), $N=\exp^{\lambda_{1}T}$, since $N=1/\epsilon$.

We denote with a lower-case format, the probabilities $p(i)$, $p(j)$, and
$p(i,j)$ with which fictitious points occupy the grid in $\Omega$. If these
fictitious points spread uniformly forming a compact set whose probabilities
of finding points in each fictitious box is equal, then $p(i)=1/N$
($=\frac{1}{N_{C}}\frac{N_{C}}{N}$), $p(j)=1/N$, and $p(i,j)=1/N_{C}$. Let us
denote the Shannon’s entropy of the probabilities $p(i,j)$, $p(i)$ and $p(j)$
as $h_{X}$, $h_{Y}$, and $h_{XY}$. The mutual information of the fictitious
trajectories after evolving a time interval $T$ can be calculated by
$I_{S}^{u}=h_{X}+h_{Y}-h_{XY}$. Since, $p(i)=p(j)=1/N$ and $p(i,j)=1/N_{C}$,
then $I_{S}^{u}=2\log{(N)}-\log{(N_{C})}$. At $t=T$, we have that
$N=\exp^{\lambda_{1}T}$ and $N_{C}=\exp^{(\lambda_{1}+\lambda_{2})T}$, leading
us to $I_{S}^{u}=(\lambda_{1}-\lambda_{2})T$. Therefore, defining,
$I_{C}=I_{S}^{u}/T$, we arrive at $I_{C}=\lambda_{1}-\lambda_{2}$.

We defining $D$ as

$D=-\frac{\log{(N_{C}(t=T))}}{\log{(\epsilon)}},$ (12)

where $N_{C}(t=T)$ being the number of boxes that would be covered by
fictitious points at time $T$. At time $t=0$, these fictitious points are
confined in an $\epsilon$-square box. They expand not only exponentially fast
in both directions according to the two positive Lyapunov exponents, but
expand forming a compact set, a set with no “holes”. At $t=T$, they spread
over $\Sigma_{\Omega}$.

Using $\epsilon=\exp^{-\lambda_{1}T}$ and
$N_{C}=\exp^{(\lambda_{1}+\lambda_{2})T}$ in Eq. (12), we arrive at
$D=1+\frac{\lambda_{2}}{\lambda_{1}}$, and therefore, we can write that

$I_{C}=\lambda_{1}-\lambda_{2}=\lambda_{1}(2-D),$ (13)

To calculate the maximal possible MIR, of a random independent process, we
assume that the expansion of points is uniform only along the columns and
lines of the grid defined in the space $\Omega$, i.e., $P(i)=P(j)=1/N$, (which
maximises $H_{X}$ and $H_{Y}$), and we allow $P(i,j)$ to be not uniform
(minimising $H_{XY}$) for all $i$ and $j$, then

$I_{S}(\epsilon)=-2\log{(\epsilon)}+\sum_{i,j}P(i,j)\log{[P(i,j)]}.$ (14)

Since $T(\epsilon)=-1/\lambda_{1}\log{(\epsilon)}$, dividing $I_{S}(\epsilon)$
by $T(\epsilon)$, taking the limit of $\epsilon\rightarrow 0$, and reminding
that the information dimension of the set $\Sigma_{\Omega}$ in the space
$\Omega$ is defined as $\tilde{D}_{1}$=$\lim_{\epsilon\rightarrow
0}\frac{\sum_{i,j}P(i,j)\log{[P(i,j)]}}{\log{(\epsilon)}}$, we obtain that the
MIR is given by

$I_{S}/T=\lambda_{1}(2-\tilde{D}_{1}).$ (15)

Since $\tilde{D}_{1}\leq\tilde{D}_{0}$ (for any value of $\epsilon$), then
$\lambda_{1}(2-\tilde{D}_{1})\geq\lambda_{1}(2-\tilde{D}_{0})$, which means
that a lower bound for the maximal MIR [provided by Eq. (15)] is given by

$I_{C}^{l}=\lambda_{1}(2-\tilde{D}_{0}),$ (16)

But $D\leq\tilde{D}_{0}$ (for any value of $\epsilon$), and therefore $I_{C}$
is an upper bound for $I_{C}^{l}$.

To show why $I_{C}$ is an upper bound for the maximal possible MIR, assume
that the real points $\Sigma_{\Omega}$ occupy the space $\Omega$ uniformly. If
$\tilde{N}_{C}>N$, there are many boxes being occupied. It is to be expected
that the probability of finding a point in a line or column of the grid is
$P(i)=P(j)\cong 1/N$, and $P(i,j)\cong 1/\tilde{N}_{C}$. In such a case,
$MIR\cong I_{C}^{l}$, which implies that $I_{C}\geq MIR$. If
$\tilde{N}_{C}<N$, there are only few boxes being sparsely occupied. The
probability of finding a point in a line or column of the grid is
$P(i)=P(j)\cong 1/\tilde{N}_{C}$, and $P(i,j)\cong 1/\tilde{N}_{C}$. There are
$\tilde{N}_{C}$ lines and columns being occupied by points in the grid. In
such a case, $I_{S}\cong
2\log{(\tilde{N}_{C})}-\log{(\tilde{N}_{C})}\cong\log{(\tilde{N}_{C})}$.
Comparing with $I_{S}^{u}=2\log{(N)}-\log{(N_{C})}$, and since
$\tilde{N}_{C}<N$ and $N_{C}\geq\tilde{N}_{C}$, then we conclude that
$I_{S}^{u}\geq I_{S}$, which implies that $I_{C}\geq MIR$.

Notice that if $P(i,j)=p(i,j)=1/N_{C}$ and $\tilde{D}_{1}=\tilde{D}_{0}$, then
$I_{S}/T=I_{C}^{l}=I_{C}$.

###  III.4 Expansion rates

In order to extend our approach for the treatment of data sets coming from
networks whose equations of motion are unknown, or for higher-dimensional
networks and complex systems which might be neither rigorously chaotic nor
fully deterministic, or for experimental data that contains noise and few
sampling points, we write our bounds in terms of expansion rates defined in
this work by

$e_{k}(t)=1/\tilde{N}_{C}\sum_{i=1}^{\tilde{N}_{C}}\frac{1}{t}log{[L_{k}^{i}(t)]},$
(17)

where we consider $k=1,2$. $L^{i}_{1}(t)$ measures the largest growth rate of
nearby points. In practice, it is calculated by
$L^{i}_{1}(t)=\frac{\Delta}{\delta}$, with $\delta$ representing the largest
distance between pair of points in an $\epsilon$-square box $i$ and $\Delta$
representing the largest distance between pair of the points that were
initially in the $\epsilon$-square box but have spread out for an interval of
time $t$. $L^{i}_{2}(t)$ measures how an area enclosing points grows. In
practice, it is calculated by $L^{i}_{2}(t)=\frac{A}{\epsilon^{2}}$, with
$\epsilon^{2}$ representing the area occupied by points in an
$\epsilon$-square box, and $A$ the area occupied by these points after
spreading out for a time interval $t$. There are $\tilde{N}_{C}$ boxes
occupied by points which are taken into consideration in the calculation of
$L_{k}^{i}(t)$. An order-$k$ expansion rate, $e_{k}(t)$, measures on average
how a hypercube of dimension $k$ exponentially grows after an interval of time
$t$. So, $e_{1}$ measures the largest growth rate of nearby points, a quantity
closely related to the largest finite-time Lyapunov exponent celso1994 . And
$e_{2}$ measures how an area enclosing points grows, a quantity closely
related to the sum of the two largest positive Lyapunov exponents. In terms of
expansion rates, Eqs. (4) and (13) read
$T=\frac{1}{e_{1}}\log{\left[\frac{1}{\epsilon}\right]}$ and
$I_{C}={e_{1}}(2-D)$, respectively, and Eqs. (12) and (16) read
$D(t)=\frac{e_{2}(t)}{e_{1}(t)}$ and $I_{C}^{l}=e_{1}(2-\tilde{D}_{0})$,
respectively.

From the way we have defined expansion rates, we expect that
$e_{k}\leq\sum_{i=1}^{k}\lambda_{i}$. Because of the finite time interval and
the finite size of the regions of points considered, regions of points that
present large derivatives, contributing largely to the Lyapunov exponents,
contribute less to the expansion rates. If a system has constant derivative
(hyperbolic) and has constant natural measure, then
$e_{k}=\sum_{i=1}^{k}\lambda_{i}$.

There are many reasons for using expansion rates in the way we have defined
them in order to calculate bounds for the MIR. Firstly, because they can be
easily experimentally estimated whereas Lyapunov exponents demand huge
computational efforts. Secondly, because of the macroscopic nature of the
expansion rates, they might be more appropriate to treat data coming from
complex systems that contains large amounts of noise, data that have points
that are not (arbitrarily) close as formally required for a proper calculation
of the Lyapunov exponents. Thirdly, expansion rates can be well defined for
data sets containing very few data points: the fewer points a data set
contains, the larger the regions of size $\epsilon$ need to be and the shorter
the time $T$ is. Finally, expansion rates are defined in a similar way to
finite-time Lyapunov exponents and thus some algorithms used to calculate
Lyapunov exponents can be used to calculate our defined expansion rates.

##  IV Applications

###  IV.1 MIR and its bounds in two coupled chaotic maps

To illustrate the use of our bounds, we consider the following two
bidirectionally coupled maps

$\displaystyle X^{(1)}_{n+1}$ $\displaystyle=$ $\displaystyle
2X^{(1)}_{n}+\rho X^{(1)^{2}}_{n}+\sigma(X^{(2)}_{n}-X^{(1)}_{n}),\mbox{mod
1}$ $\displaystyle X^{(2)}_{n+1}$ $\displaystyle=$ $\displaystyle
2X^{(2)}_{n}+\rho X^{(2)^{2}}_{n}+\sigma(X^{(1)}_{n}-X^{(2)}_{n}),\mbox{mod
1}$ (18)

where $X_{n}^{(i)}\in[0,1]$. If $\rho=0$, the map is piecewise-linear and
quadratic, otherwise. We are interested in measuring the exchange of
information between $X^{(1)}$ and $X^{(2)}$. The space $\Omega$ is a square of
sides 1. The Lyapunov exponents measured in the space $\Omega$ are the
Lyapunov exponents of the set $\Sigma_{\Omega}$ that is the chaotic attractor
generated by Eqs. (18).

The quantities $I_{S}/T$, $I_{C}$, and $I_{C}^{l}$ are shown in Fig. 1 as we
vary $\sigma$ for $\rho=0$ (A) and $\rho=0.1$ (B). We calculate $I_{S}$ using
in Eq. (1) the probabilities $P(i,j)$ in which points from a trajectory
composed of $2,000,000$ samples fall in boxes of sides $\epsilon$=1/500 and
the probabilities $P(i)$ and $P(j)$ that the points visit the intervals
$[(i-1)\epsilon,i\epsilon[$ of the variable $X_{n}^{(1)}$ or
$[(j-1)\epsilon,j\epsilon[$ of the variable $X_{n}^{(2)}$, respectively, for
$i,j=1,\ldots,N$. When computing $I_{S}/T$, the quantity $T$ was estimated by
Eq. (4). Indeed for most values of $\sigma$, $I_{C}\geq I_{S}/T$ and
$I_{C}^{l}\leq I_{S}/T$.

Figure 1: [Color online] Results for two coupled maps. $I_{S}/T$ [Eq. (11)] as
(green online) filled circles, $I_{C}$ [Eq. (13)] as the (red online) thick
line, and $I_{C}^{l}$ [Eq. (16)] as the (brown online) crosses. In (A)
$\rho=0$ and in (B) $\rho=0.1$. The units of $I_{S}/T$, $I_{C}$, and
$I_{C}^{l}$ are [bits/iteration].

For $\sigma=0$ there is no coupling, and therefore the two maps are
independent from each other. There is no information being exchanged. In fact,
$I_{C}=0$ and $I_{C}^{l}\cong 0$ in both figures, since $D=\tilde{D}_{0}=2$,
meaning that the attractor $\Sigma_{\Omega}$ fully occupies the space
$\Omega$. This is a remarkable property of our bounds: to identify that there
is no information being exchanged when the two maps are independent. Complete
synchronisation is achieved and $I_{C}$ is maximal, for $\sigma>0.5$ (A) and
for $\sigma\geq 0.55$ (B). A consequence of the fact that $D=\tilde{D}_{0}=1$,
and therefore, $I_{C}=I_{C}^{l}=\lambda_{1}$. The reason is because for this
situation this coupled system is simply the shift map, a map with constant
natural measure; therefore $P(i)=P(j)$ and $P(i,j)$ are constant for all $i$
and $j$. As usually happens when one estimates the mutual information by
partitioning the phase space with a grid having a finite resolution and data
sets possessing a finite number of points, $I_{S}$ is typically larger than
zero, even when there is no information being exchanged ($\sigma=0$). Even
when there is complete synchronisation, we find non-zero off-diagonal terms in
the matrix for the joint probabilities causing $I_{S}$ to be smaller than it
should be. Due to numerical errors, $X^{(1)}\cong X^{(2)}$, and points that
should be occupying boxes with two corners exactly along a diagonal line in
the subspace $\Omega$ end up occupying boxes located off-diagonal and that
have at least three corners off-diagonal. The estimation of the lower bound
$I_{C}^{l}$ suffers from the same problems.

Our upper bound $I_{C}$ is calculated assuming that there is a fictitious
dynamics expanding points (and producing probabilities) not only exponentially
fast but also uniformly. The “experimental” numerical points from Eqs. (18)
expand exponentially fast, but not uniformly. Most of the time the trajectory
remains in 4 points: (0,0), (1,1), (1,0), (0,1). That is the main reason of
why $I_{C}$ is much larger than the estimated real value of the $MIR$, for
some coupling strengths. If a two nodes in a dynamical network, such as two
neurons in a brain, behave in the same way the fictitious dynamics does, these
nodes would be able to exchange the largest possible amount of information.

We would like to point out that one of the main advantages of calculating
upper bounds for the MIR ($I_{S}/T$) using Eq. (13) instead of actually
calculating $I_{S}/T$ is that we can reproduce the curves for $I_{C}$ using
much less number of points (1000 points) than the ones ($2,000,000$) used to
calculate the curve for $I_{S}/T$. If $\rho=0$, $I_{C}=-\ln{(1-\sigma)}$ can
be calculated since $\lambda_{1}=\ln{(2)}$ and $\lambda_{2}=\ln{(2-2\sigma)}$.

###  IV.2 MIR and its bounds in experimental networks of Double-Scroll
circuits

We illustrate our approach for the treatment of data sets using a network
formed by an inductorless version of the Double-Scroll circuit
inductorless_chua . We consider four networks of bidirectionally diffusively
coupled circuits. Topology I represents two bidirectionally coupled circuits,
Topology II, three circuits coupled in an open-ended array, Topology III, four
circuits coupled in an open-ended array, and Topology IV, coupled in an closed
array. We choose two circuits in the different networks (one connection apart)
and collect from each circuit a time-series of 79980 points, with a sampling
rate of $\delta=80.000$ samples/s. The measured variable is the voltage across
one of the circuit capacitors, which is normalised in order to make the space
$\Omega$ to be a square of sides 1. Such normalisation does not alter the
quantities that we calculate. The following results provide the exchange of
information between these two chosen circuits. The values of $\epsilon$ and
$t$ used to course-grain the space $\Omega$ and to calculate $e_{2}$ in Eq.
(17) are the ones that minimises $|N_{C}(T,e_{2})-\tilde{N}_{C}(\epsilon)|$
and at the same time satisfy $N_{C}(T,e_{2})\geq\tilde{N}_{C}(\epsilon)$,
where $N_{C}(T,e_{2})=\exp^{Te_{2}(t)}$ represents the number of fictitious
boxes covering the set $\Sigma_{\Omega}$ in a compact fashion, when $t=T$.
This optimisation excludes some non-significant points that make the expansion
rate of fictitious points to be much larger than it should be. In other words,
we require that $e_{2}$ describes well the way most of the points spread. We
consider that $t$ used to calculate $e_{k}$ in Eq. (17) is the time for points
initially in an $\epsilon$-side box to spread to 0.8$L$. That guarantee that
nearby points in $\Sigma_{\Omega}$ are expanding in both directions within the
time interval $[0,T]$. Using $0.4L<t<0.8L$ produces already similar results.
If $t>0.8L$, the set $\Sigma_{\Omega}$ might not be only expanding. $T$ might
be overestimated.

Figure 2: [Color online] Results for experimental networks of Double-Scroll
circuits. On the left-side upper corner pictograms represent how the circuits
(filled circles) are bidirectionally coupled. $I_{S}/T_{k}$ as (green online)
filled circles, $I_{C}$ as the (red online) thick line, and $I_{C}^{l}$ as the
(brown online) squares, for a varying coupling resistance $R$. The unit of
these quantities shown in these figures is (kbits/s). (A) Topology I, (B)
Topology II, (C) topology III, and (D) Topology IV. In all figures,
$\tilde{D}_{0}$ increases smoothly from 1.25 to 1.95 as $R$ varies from
0.1k$\Omega$ to 5k$\Omega$. The line on the top of the figure represents the
interval of resistance values responsible to induce almost synchronisation
(AS) and phase synchronisation (PS).

$I_{S}$ has been estimated by the method in Ref. kraskov . Since we assume
that the space $\Omega$ where mutual information is being measured is 2D, we
will compare our results by considering in the method of Ref. kraskov  a 2D
space formed by the two collected scalar signals. In the method of Ref.
kraskov  the phase space is partitioned in regions that contain 30 points of
the continuous trajectory. Since that these regions do not have equal areas
(as it is done to calculate $I_{C}$ and $I_{C}^{l}$), in order to estimate $T$
we need to imagine a box of sides $\epsilon_{k}$, such that its area
$\epsilon_{k}^{2}$ contains in average 30 points. The area occupied by the set
$\Sigma_{\Omega}$ is approximately given by $\epsilon^{2}\tilde{N}_{C}$, where
$\tilde{N}_{C}$ is the number of occupied boxes. Assuming that the 79980
experimental data points occupy the space $\Omega$ uniformly, then on average
30 points would occupy an area of $\frac{30}{79980}\epsilon^{2}\tilde{N}_{C}$.
The square root of this area is the side of the imaginary box that would
occupy 30 points. So,
$\epsilon_{k}=\sqrt{\frac{30}{79980}\tilde{N}_{C}}\epsilon$. Then, in the
following, the “exact” value of the MIR will be considered to be given by
$I_{S}/T_{k}$, where $T_{k}$ is estimated by
$T_{k}=-\frac{1}{e_{1}}\log{(\epsilon_{k})}$.

The three main characteristics of the curves for the quantities $I_{S}/T_{k}$,
$I_{C}$, and $I_{C}^{l}$ (appearing in Fig. 2) with respect to the coupling
strength are that (i) as the coupling resistance becomes smaller, the coupling
strength connecting the circuits becomes larger, and the level of
synchronisation increases followed by an increase in $I_{S}/T_{k}$, $I_{C}$,
and $I_{C}^{l}$, (ii) all curves are close, (iii) and as expected, for most of
the resistance values, $I_{C}>I_{S}/T_{k}$ and $I_{C}^{l}\leq I_{S}/T_{k}$.
The two main synchronous phenomena appearing in these networks are almost
synchronisation (AS) femat_PLA1999 , when the circuits are almost completely
synchronous, and phase synchronisation (PS) juergen_book . For the circuits
considered in Fig. 2, AS appears for the interval $R\in[0,3]$ and PS appears
for the interval $R\in[3,3.5]$. Within this region of resistance values the
exchange of information between the circuits becomes large. PS was detected by
using the technique from Refs. baptista_PHYSICAD2006 ; pereira_PRE2007 .

###  IV.3 MIR and its upper bound in stochastic systems

To analytically demonstrate that the quantities $I_{C}$ and $I_{S}/T$ can be
well calculated in stochastic systems, we consider the following stochastic
dynamical toy model illustrated in Fig. 3. In it points within a small box of
sides $\epsilon$ (represented by the filled square in Fig. 3(A)) located in
the centre of the subspace $\Omega$ are mapped after one iteration of the
dynamics to 12 other neighbouring boxes. Some points remain in the initial
box. The points that leave the initial box go to 4 boxes along the diagonal
line and 8 boxes off-diagonal along the transverse direction. Boxes along the
diagonal are represented by the filled squares in Fig. 3(B) and off-diagonal
boxes by filled circles. At the second iteration, the points occupy other
neighbouring boxes, as illustrated in Fig. 3(C), and at the time $n=T$ the
points do not spread any longer, but are somehow reinjected inside the region
of the attractor. We consider that this system is completely stochastic, in
the sense that no one can precisely determine the location of where an initial
condition will be mapped. The only information is that points inside a smaller
region are mapped to a larger region.

At the iteration $n$, there will be $N_{d}=2^{1+n}+1$ boxes occupied along the
diagonal (filled squares in Fig. 3) and $N_{t}=2nN_{d}-C(\tilde{n})$ (filled
circles in Fig. 3) boxes occupied off-diagonal (along the transverse
direction), where $C(\tilde{n})=0$ for $\tilde{n}$=0, and $C(\tilde{n})>0$ for
$\tilde{n}\geq 1$ and $\tilde{n}=n-T-\alpha$. $\alpha$ is a small number of
iterations representing the time difference between the time $T$ for the
points in the diagonal to reach the boundary of the space $\Omega$ and the
time for the points in the off-diagonal to reach this boundary. The border
effect can be ignored when the expansion along the diagonal direction is much
faster than along the transverse direction.

Figure 3: (A) A small box representing a set of initial conditions. After one
iteration of the system, the points that leave the initial box in (A) go to 4
boxes along the diagonal line [filled squares in (B)] and 8 boxes off-diagonal
(along the transverse direction) [filled circles in (B)]. At the second
iteration, the points occupy other neighbouring boxes as illustrated in (C)
and after an interval of time $n=T$ the points do not spread any longer (D).

At the iteration $n$, there will be
$N_{C}=2^{1+n}+1+(2^{1+n}+1)2n-C(\tilde{n})$ boxes occupied by points. In the
following calculations we consider that $N_{C}\cong 2^{1+n}(1+2n)$. We assume
that the subspace $\Omega$ is a square whose sides have length 1, and that
$\Sigma\in\Omega$, so $L=\sqrt{2}$. For $n>T$, the attractor does not grow any
longer along the off-diagonal direction. The time $n=T$, for the points to
spread over the attractor $\Sigma$, can be calculated by the time it takes for
points to visit all the boxes along the diagonal. Thus, we need to satisfy
$N_{d}\epsilon\sqrt{2}=\sqrt{2}$. Ignoring the 1 appearing in the expression
for $N_{d}$ due to the initial box in the estimation for the value of $T$, we
arrive that $T>\frac{\log{(1/\epsilon)}}{\log{(2)}}-1$. This stochastic system
is discrete. In order to take into consideration the initial box in the
calculation of $T$, we pick the first integer that is larger than
$\frac{\log{(1/\epsilon)}}{\log{(2)}}-1$, leading $T$ to be the largest
integer that satisfies

$T<-\frac{\log{(\epsilon)}}{\log{(2)}}.$ (19)

The largest Lyapunov exponent or the order-1 expansion rate of this stochastic
toy model can be calculated by $N_{d}(n)\exp^{\lambda_{1}}=N_{d}(n+1)$, which
take us to

$\lambda_{1}=\log{(2)}.$ (20)

Therefore, Eq. (19) can be rewritten as
$T=-\frac{\log{(\epsilon)}}{\lambda_{1}}$.

The quantity $D$ can be calculated by $D=\frac{\log{(N_{C})}}{\log{(N)}}$,
with $n=T$. Neglecting $C(\tilde{n})$ and the 1 appearing in $N_{C}$ due to
the initial box, we have that $N_{C}\cong 2^{1+T}[1+2^{T}]$. Substituting in
the definition of $D$, we obtain
$D=\frac{(1+T)\log{(2)}+\log{(1+2^{T})}}{-\log{(\epsilon)}}$. Using $T$ from
Eq. (19), we arrive at

$D=1+r,$ (21)

where

$r=-\frac{\log{(2)}}{\log{(\epsilon)}}-\frac{\log{(1+2^{T})}}{\log{(\epsilon)}}$
(22)

Placing $D$ and $\lambda_{1}$ in $I_{C}=\lambda_{1}(2-D)$, give us

$I_{C}=\log{(2)}(1-r).$ (23)

Let us now calculate $I_{S}/T$. Ignoring the border effect, and assuming that
the expansion of points is uniform, then $P(i,j)=1/N_{C}$ and
$P(i)=P(j)=1/N=\epsilon$. At the iteration $n=T$, we have that
$I_{S}=-2\log{(\epsilon)}-\log{(N_{C})}$. Since $N_{C}\cong 2^{1+T}[1+2^{T}]$,
we can write that $I_{S}=-2\log{(\epsilon)}-(1+T)\log{(2)}-\log{(1+2^{T})}$.
Placing $T$ from Eq. (19) into $I_{S}$ takes us to
$I_{S}=-\log{(2)}-\log{(\epsilon)}-\log{(1+2^{T})}$. Finally, dividing $I_{S}$
by $T$, we arrive that

$\displaystyle\frac{I_{S}}{T}$ $\displaystyle=$
$\displaystyle\log{(2)}\left[1+\frac{\log{(2)}}{\log{(\epsilon)}}+\frac{\log{(1+2^{T})}}{\log{(\epsilon)}}\right]$
(24) $\displaystyle=$ $\displaystyle\log{(2)}(1-r).$

As expected from the way we have constructed this model, Eq. (24) and (23) are
equal and $I_{C}=\frac{I_{S}}{T}$.

Had we included the border effect in the calculation of $I_{C}$, denote the
value by $I_{C}^{b}$, we would have typically obtained that $I_{C}^{b}\geq
I_{C}$, since $\lambda_{2}$ calculated considering a finite space $\Omega$
would be either smaller or equal than the value obtained by neglecting the
border effect. Had we included the border effect in the calculation of
$I_{S}/T$, denote the value by $I_{S}^{b}/T$, typically we would expect that
the probabilities $P(i,j)$ would not be constant. That is because the points
that leave the subspace $\Omega$ would be randomly reinjected back to
$\Omega$. We would conclude that $I_{S}^{b}/T\leq I_{S}/T$. Therefore, had we
included the border effect, we would have obtained that $I_{C}^{b}\geq
I_{S}^{b}/T$.

The way we have constructed this stochastic toy model results in $D\cong 1$.
This is because the spreading of points along the diagonal direction is much
faster than the spreading of points along the off-diagonal transverse
direction. In other words, the second largest Lyapunov exponent,
$\lambda_{2}$, is close to zero. Stochastic toy models which produce larger
$\lambda_{2}$, one could consider that the spreading along the transverse
direction is given by $N_{t}=N_{d}2^{\alpha n}-C(\tilde{n})$, with
$\alpha\in[0,1]$.

###  IV.4 Expansion rates for noisy data with few sampling points

In terms of the order-1 expansion rate, $e_{1}$, our quantities read
$I_{C}={e_{1}}(2-D)$,
$T=\frac{1}{e_{1}}\log{\left[\frac{1}{\epsilon}\right]}$, and
$I_{C}^{l}=e_{1}(2-\tilde{D}_{0})$. In order to show that our expansion rate
can be used to calculate these quantities, we consider that the experimental
system is uni-dimensional and has a constant probability measure. Additive
noise is assumed to be bounded with maximal amplitude $\eta$, and having
constant density.

Our order-1 expansion rate is defined as

$e_{1}(t)=1/\tilde{N}_{C}\sum_{i=1}^{\tilde{N}_{C}}\frac{1}{t}\log{[L_{1}^{i}(t)]}.$
(25)

where $L_{1}^{i}(t)$ measures the largest growth rate of nearby points. Since
all it matters is the largest distance between points, it can be estimated
even when the experimental data set has very few data points. Since, in this
example, we consider that the experimental noisy points have constant uniform
probability distribution, $e_{1}(t)$ can be calculated by

$e_{1}(t)=\frac{1}{t}\log{\left[\frac{\Delta+2\eta}{\delta+2\eta}\right]}.$
(26)

where $\delta+2\eta$ represents the largest distance between pair of
experimental noisy points in an $\epsilon$-square box and $\Delta+2\eta$
represents the largest distance between pair of the points that were initially
in the $\epsilon$-square box but have spread out for an interval of time $t$.
The experimental system (without noise) is responsible to make points that are
at most $\delta$ apart from each other to spread to at most to $\Delta$ apart
from each other. This points spread out exponentially fast according to the
largest positive Lyapunov exponent $\lambda_{1}$ by

$\Delta=\delta\exp^{\lambda_{1}t}.$ (27)

Substituting Eq. (27) in (26), and expanding $\log$ to first order, we obtain
that $e_{1}=\lambda_{1}$, and therefore, our expansion rate can be used to
estimate Lyapunov exponents.

##  V Supplementary Information

###  V.1 Decay of correlation and First Poincaré Returns

As rigorously shown in young , the decay with time of the correlation, $C(t)$,
is proportional to the decay with time of the density of the first Poincaré
recurrences, $\rho(t,\epsilon)$, which measures the probability with which a
trajectory returns to an $\epsilon$-interval after $t$ iterations. Therefore,
if $\rho(t,\epsilon)$ decays with $t$, for example exponentially fast, $C(t)$
will decay with $t$ exponentially fast, as well. The relationship between
$C(t)$ and $\rho(t)$ can be simply understood in chaotic systems with one
expanding direction (one positive Lyapunov exponent). As shown in
baptista_CHAOS2009 , the “local” decay of correlation (measured in the
$\epsilon$-interval) is given by
$C(t,\epsilon)\leq\mu(\epsilon)\rho(t,\epsilon)-\mu(\epsilon)^{2}$, where
$\mu(\epsilon)$ is the probability measure of a chaotic trajectory to visit
the $\epsilon$-interval. Consider the shift map $x_{n+1}=2x_{n},\mbox{mod 1}$.
For this map, $\mu(\epsilon)=\epsilon$ and there are an infinite number of
possible intervals that makes $C(t,\epsilon)=0$, for a finite $t$. These
intervals are the cells of a Markov partition. As recently demonstrated by [P.
Pinto, I. Labouriau, M. S. Baptista], in piecewise-linear systems as the shift
map, if $\epsilon$ is a cell in an order-$t$ Markov partition and
$\rho(t,\epsilon)>0$, then $\rho(t,\epsilon)=2^{-t}$ and by the way a Markov
partition is constructed we have that $\epsilon=2^{-t}$. Since that
$\epsilon=\mu(\epsilon)=2^{-t}$, we arrive at that $C(t,\epsilon)\leq 0$, for
a special finite time $t$. Notice that $\epsilon=2^{-t}$ can be rewritten as
$-\ln{(\epsilon)}=t\ln{(2)}$. Since for this map, the largest Lyapunov
exponent is equal to $\lambda_{1}=\ln{(2)}$, then
$t=-\frac{1}{\lambda_{1}}\ln{(\epsilon)}$, which is exactly equal to the
quantity $T$, the time interval responsible to make the system to lose its
memory from the initial condition and that can be calculated by the time that
makes points inside an initial $\epsilon$-interval to spread over the whole
phase space, in this case $[0,1]$.

###  V.2 $I_{C}$, and $I_{C}^{l}$ in larger networks and higher-dimensional
subspaces $\Sigma_{\Omega}$

Imagine a network formed by $K$ coupled oscillators. Uncoupled, each
oscillator possesses a certain amount of positive Lyapunov exponents, one
zero, and the others are negative. Each oscillator has dimension $d$. Assume
that the only information available from the network are two $Q$ dimensional
measurements, or a scalar signal that is reconstructed to a $Q$-dimensional
embedding space. So, the subspace $\Sigma_{\Omega}$ has dimension $2Q$, and
each subspace of a node (or group of nodes) has dimension $Q$. To be
consistent with our previous equations, we assume that we measure
$M_{\Omega}=2Q$ positive Lyapunov exponents on the projection
$\Sigma_{\Omega}$. If $M_{\Omega}\neq 2Q$, then in the following equations
$2Q$ should be replaced by $M_{\Omega}$, naturally assuming that
$M_{\Omega}\leq 2Q$.

In analogy with the derivation of $I_{C}$ and $I_{C}^{l}$ in a bidimensional
projection, we assume that if the spreading of initial conditions is uniform
in the subspace $\Omega$. Then, $P(i)=\frac{1}{N^{Q}}$ represents the
probability of finding trajectory points in $Q$-dimensional space of one node
(or a group of nodes) and $P(i,j)=\frac{1}{N_{C}}$ represents the
probabilities of finding trajectory points in the $2Q$-dimensional composed
subspace constructed by two nodes (or two groups of nodes) in the subspace
$\Omega$. Additionally, we consider that the hypothetical number of occupied
boxes $N_{C}$ will be given by
$N_{C}(T)=\exp^{T(\sum_{i=1}^{2Q}\lambda_{i})}$. Then, we have that
$T=1/\lambda_{1}\log{(N)}$, which lead us to

$I_{C}=\lambda_{1}(2Q-D).$ (28)

Similarly to the way we have derived $I_{C}^{l}$ in a bidimensional
projection, if $\Sigma_{\Omega}$ has more than 2 positive Lyapunov exponents,
then

$I_{C}^{l}=\lambda_{1}(2Q-\tilde{D}_{0}).$ (29)

To write Eq. (28) in terms of the positive Lyapunov exponents, we first extend
the calculation of the quantity $D$ to higher-dimensional subspaces that have
dimensionality 2Q,

$D=1+\sum_{i=2}^{2Q}\frac{\lambda_{i}}{\lambda_{1}},$ (30)

where $\lambda_{1}\geq\lambda_{2}\geq\lambda_{3}\ldots\geq\lambda_{2Q}$ are
the Lyapunov exponents measured on the subspace $\Omega$. To derive this
equation we only consider that the hypothetical number of occupied boxes
$N_{C}$ is given by $N_{C}(T)=\exp^{T(\sum_{i=2}^{2Q}\lambda_{i})}$.

We then substitute $D$ as a function of these exponents (Eq. (30)) in Eq.
(28). We arrive at

$I_{C}=(2Q-1)\lambda_{1}-\sum_{i=2}^{2Q}\lambda_{i}.$ (31)

###  V.3 $I_{C}$ as a function of the positive Lyapunov exponents of the
network

Consider a network whose attractor $\Sigma$ possesses $M$ positive Lyapunov
exponents, denoted by $\tilde{\lambda}_{i}$, $i=1,\ldots,M$. For a typical
subspace $\Omega$, $\lambda_{1}$ measured on $\Omega$ is equal to the largest
Lyapunov exponent of the network. Just for the sake of simplicity, assume that
the nodes in the network are sufficiently well connected so that in a typical
measurement with a finite number of observations this property holds, i.e.,
$\tilde{\lambda}_{1}=\lambda_{1}$. But, if measurements provide that
$\tilde{\lambda}_{1}>>\lambda_{1}$, the next arguments apply as well, if one
replaces $\tilde{\lambda}_{1}$ appearing in the further calculations by the
smallest Lyapunov exponent, say, $\tilde{\lambda_{k}}$, of the network that is
still larger than $\lambda_{1}$, and then, substitute $\tilde{\lambda}_{2}$ by
$\tilde{\lambda_{k+1}}$, and so on. As before, consider that $M_{\Omega}=2Q$.

Then, for an arbitrary subspace $\Omega$,
$\sum_{i=2}^{2Q}\lambda_{i}\leq\sum_{i=2}^{2Q}\tilde{\lambda}_{i}$, since a
projection cannot make the Lyapunov exponents larger, but only smaller or
equal.

Defining

$\tilde{I}_{C}=(2Q-1)\lambda_{1}-\sum_{i=2}^{2Q}\tilde{\lambda}_{i}.$ (32)

Since $\sum_{i=2}^{2Q}\lambda_{i}\leq\sum_{i=2}^{2Q}\tilde{\lambda}_{i}$, it
is easy to see that

$\tilde{I}_{C}\leq I_{C}.$ (33)

So, $I_{C}$, measured on the subspace $\Sigma_{\Omega}$ and a function of the
$2Q$ largest positive Lyapunov exponents measured in $\Sigma_{\Omega}$, is an
upper bound for $\tilde{I}_{C}$, a quantity defined by the $2Q$ largest
positive Lyapunov exponents of the attractor $\Sigma$ of the network.
Therefore, if the Lyapunov exponents of a network are know, the quantity
$\tilde{I}_{C}$ can be used as a way to estimate how much is the MIR between
two measurements of this network, measurements that form the subspace
$\Omega$.

Notice that $I_{C}$ depends on the projection chosen (the subspace $\Omega$)
and on its dimension, whereas $\tilde{I}_{C}$ depends on the dimension of the
subspace $\Sigma_{\Omega}$ (the number 2Q of positive Lyapunov exponents). The
same happens for the mutual information between random variables that depend
on the projection considered.

Equation (32) is important because it allows us to obtain an estimation for
the value of $I_{C}$ analytically. As an example, imagine the following
network of coupled maps with a constant Jacobian

$X^{(i)}_{n+1}=2X^{(i)}_{n}+\sigma\sum_{j=1}^{K}{\mathbf{A}}_{ij}(X^{(j)}_{n}-X^{(i)}_{n}),\mbox{mod
1},$ (34)

where $X\in[0,1]$ and ${\mathbf{A}}$ represents the connecting adjacent
matrix. If node $j$ connects to node $i$, then ${\mathbf{A}}_{ij}=1$, and 0
otherwise.

Assume that the nodes are connected all-to-all. Then, the $K$ positive
Lyapunov exponents of this network are: $\tilde{\lambda}_{1}=\log{(2)}$ and
$\tilde{\lambda}_{i}=\log{2[1+\sigma]}$, with $i=2,K$. Assume also that the
subspace $\Omega$ has dimension $2Q$ and that $2Q$ positive Lyapunov exponents
are observed in this space and that $\tilde{\lambda}_{1}=\lambda_{1}$.
Substituting these Lyapunov exponents in Eq. (32), we arrive at

$\tilde{I}_{C}=(2Q-1)\log{(1+\sigma)}.$ (35)

We conclude that there are two ways for $\tilde{I}_{C}$ to increase. Either
one considers larger measurable subspaces $\Omega$ or one increases the
coupling between the nodes. This suggests that the larger the coupling
strength is the more information is exchanged between groups of nodes.

For arbitrary topologies, one can also derive analytical formulas for
$\tilde{I}_{C}$ in this network, since $\tilde{\lambda}_{i}$ for $i>2$ can be
calculated from $\tilde{\lambda}_{2}$ baptista_PLA2010c . One arrives at

$\tilde{\lambda}_{i}(\omega_{i}\sigma/2)=\tilde{\lambda}_{2}(\sigma),$ (36)

where $\omega_{i}$ is the $i$th largest eigenvalue (in absolute value) of the
Laplacian matrix
${\mathbf{L}}_{ij}={\mathbf{A}}_{ij}+\mathbb{I}\sum_{j}{\mathbf{A}}_{ij}$.

##  VI Conclusions

Concluding, we have shown a procedure to calculate mutual information rate
(MIR) between two nodes (or groups of nodes) in dynamical networks and data
sets that are either mixing, or present fast decay of correlations, or have
sensitivity to initial conditions, and have proposed significant upper
($I_{C}$) and lower ($I_{C}^{l}$) bounds for it, in terms of the Lyapunov
exponents, the expansion rates, and the capacity dimension. Since our upper
bound is calculated from Lyapunov exponents or expansion rates, it can be used
to estimate the MIR between data sets that have different sampling rates or
experimental resolution (e.g. the rise of the ocean level and the average
temperature of the Earth), or between systems possessing a different number of
events. Additionally, Lyapunov exponents can be accurately calculated even
when data sets are corrupted by noise of large amplitude (observational
additive noise) mera ; gao2006  or when the system generating the data suffers
from parameter alterations (“experimental drift”) stefanski . Our bounds link
information (the MIR) and the dynamical behaviour of the system being observed
with synchronisation, since the more synchronous two nodes are, the smaller
$\lambda_{2}$ and $D_{0}$ will be. This link can be of great help in
establishing whether two nodes in a dynamical network or in a complex system
not only exchange information but also have linear or non-linear
interdependences, since the approaches to measure the level of synchronisation
between two systems are reasonably well known and are been widely used. If
variables are synchronous in a time-lag fashion juergen_book , it was shown in
Ref. blanc  that the MIR is independent of the delay between the two
processes. The upper bound for the MIR could be calculated by measuring the
Lyapunov exponents of the network (see Supplementary Information), which are
also invariant to time-delays between the variables.

Acknowledgments M. S. Baptista was partially supported by the Northern
Research Partnership (NRP) and Alexander von Humboldt foundation. M. S.
Baptista would like to thank A. Politi for discussions concerning Lyapunov
exponents. R.M. Rubinger, E.R. V. Junior and J.C. Sartorelli thanks the
Brazilian agencies CAPES, CNPq, FAPEMIG, and FAPESP.

## References

  * (1) Shannon CE (1948) Bell System Technical Journal 27: 379-423.
  * (2) Strong SP, Koberle R, de Ruyter van Steveninck RR, Bialek W (1998) Phys. Rev. Lett. 80: 197-200.
  * (3) Sporns O, Chialvo DR, Kaiser M, Hilgetag CC (2004) Trends in Cognitive Sciences 8: 418-425.
  * (4) Palus M, Komárek V, Procházka T, et al. (2001) IEEE Engineering in Medicice and Biology Sep/Oct: 65-71.
  * (5) Donges JF, Zou Y, Marwan N, and Kurths J (2009) Eur. Phys. J. 174: 157-179.
  * (6) Fraser AM and Swinney HL (1986) Phys. Rev. A 33: 1134-1140.
  * (7) Kantz H and Schreiber T (2004) Nonlinear Time Series Analysis, Cambridge University Press.
  * (8) Parlitz U (1998) Nonlinear Time-Series Analysis, in Nonlinear Modelling - Advanced Black-Box techniques, Kluwer Academic Publishers.
  * (9) Haykin S (2001) Communication Systems, John Wiley $\&$ Sons.
  * (10) Rossi F, Lendasse A, François D, Wertz V, and Verleysen M (2006) Chemometrics and Intellingent Laboratory Systems, 80: 215-226.
  * (11) Paninski L (2003) Neural Computation 15: 1191-1253.
  * (12) Steuer R, Kurths J, Daub CO, et al. (2002) Bioinformatics 18: S231-S240.
  * (13) Papana A, Kugiumtzis D, and Larsson PG (2009) Int. J. Bifurcation and Chaos 19: 4197-4215.
  * (14) Baptista MS and Kurths J (2008) Phys. Rev. E 77: 026205-1-026205-13.
  * (15) Baptista MS, de Carvalho JX, Hussein MS (2008) PloS ONE 3: e3479.
  * (16) Blanc JL, Pezard L, and Lesne A (2011) Phys. Rev. E 84: 036214-1-036214-9.
  * (17) Dobrushin RL (1959) Usp. Mat. Nauk. 14: 3-104; transl: Amer. Math. Soc. Translations, series 2 33: 323-438.
  * (18) Gray RM and Kieffer JC (1980) IEEE Transations on Information theory IT-26: 412-421.
  * (19) Verdú S (1994) IEEE Trans. Information Theory, 40, 1147-1157.
  * (20) Kolmogorov AN (1959) Dokl. Akad. Nauk SSSR 119: 861-864; 124: 754-755.
  * (21) Ruelle D (1978) Bol. Soc. Bras. Mat. 9: 83-87.
  * (22) Pesin YaB (1977) Russ. Math. Surveys 32: 55-114.
  * (23) Ledrappier F and Strelcyn JM (1982) Ergod. Theory Dyn. Syst. 2: 203-219.
  * (24) Gao JB (1999) Phys. Rev. Lett. 83: 3178-3181.
  * (25) Baptista MS, Eulalie N, Pinto PRF, et al. (2010) Phys. Lett. A 374: 1135-1140.
  * (26) Eckmann JP (2003) arXiv:304043.
  * (27) Sinai YaG (1970) Russ. Math. Surv. 25: 137-189.
  * (28) Chernov N and Young LS (2001) Encycl. of Math. Sc., Math. Phys. II, 101: 89-120.
  * (29) Baptista MS, Caldas IL, Heller MVAP, Ferreira AA 301: 150-162.
  * (30) Dawson S, Grebogi C, Sauer T, and Yorke JA (1994) Phys. Rev. Lett. 73: 1927-1930.
  * (31) Albuquerque HA, Rubinger RM, Rech PC, (2007) Physics D 233: 66-72.
  * (32) Kraskov A, Stogbauer H, and Grassberger P (2004) Phys. Rev. E 69: 066138-1-066138-16.
  * (33) Femat R and Solís-Perales G (1999) Phys. Lett. A 262: 50-60.
  * (34) Pikovsky A, Rosenblum M, and Kurths J (2001) Synchronization: A Universal Concept in Nonlinear Sciences, Cambridge University Press.
  * (35) Baptista MS, Pereira T, and Kurths J (2006) Physica D 216: 260-268.
  * (36) Pereira T, Baptista MS, and Kurths J, Phys. Rev. E (2007) 75: 026216-1-026216-12.
  * (37) Mera ME and Morán M (2009) Phys. Rev E 80: 016207-1-016207-8.
  * (38) Gao JB, Hu J, Tung WW, and Cao YH, Phys. Rev. E 74: 066204-1-066204-9.
  * (39) Stefański A (2008) Journal of Theoretical and Applied Mechanics 46: 665-678.
  * (40) Young LS (1999) Israel Journal of Mathematics 110: 153-188.
  * (41) Baptista MS, Maranhão DM, Sartorelli JC (2009) Chaos 19: 043115-1-043115-10.
  * (42) Baptista MS, Kakmeni FM, Magno GL, Hussein MS (2011) Phys. Lett. A 375: 1309-1318.


* GLL [22] Sivakanth Gopi, Yin Tat Lee, and Daogao Liu.  Private convex optimization via exponential mechanism.  In Conference on Learning Theory, pages 1948–1989. PMLR, 2022.
  * GLL+ [23] Sivakanth Gopi, Yin Tat Lee, Daogao Liu, Ruoqi Shen, and Kevin Tian.  Private convex optimization in general norms.  In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 5068–5089. SIAM, 2023.
  * GLL+ [24] Jiuxiang Gu, Chenyang Li, Yingyu Liang, Zhenmei Shi, Zhao Song, and Tianyi Zhou.  Fourier circuits in neural networks: Unlocking the potential of large language models in mathematical reasoning and modular arithmetic.  arXiv preprint arXiv:2402.09469, 2024.
  * [39] Jiuxiang Gu, Yingyu Liang, Zhenmei Shi, Zhao Song, and Chiwun Yang.  Toward infinite-long prefix in transformer.  arXiv preprint arXiv:2406.14036, 2024.
  * [40] Jiuxiang Gu, Yingyu Liang, Zhenmei Shi, Zhao Song, and Yufa Zhou.  Tensor attention training: Provably efficient learning of higher-order transformers.  arXiv preprint arXiv:2405.16411, 2024.
  * [41] Jiuxiang Gu, Yingyu Liang, Zhenmei Shi, Zhao Song, and Yufa Zhou.  Unraveling the smoothness properties of diffusion models: A gaussian mixture perspective.  arXiv preprint arXiv:2405.16418, 2024.
  * GLW [21] Sivakanth Gopi, Yin Tat Lee, and Lukas Wutschitz.  Numerical composition of differential privacy.  Advances in Neural Information Processing Systems, 34:11631–11642, 2021.
  * GS [12] Adityanand Guntuboyina and Bodhisattva Sen.  L1 covering numbers for uniformly bounded convex functions.  In Conference on Learning Theory, pages 12–1. JMLR Workshop and Conference Proceedings, 2012.
  * GSY [23] Yeqi Gao, Zhao Song, and Xin Yang.  Differentially private attention computation.  arXiv preprint arXiv:2305.04701, 2023.
  * GXG+ [23] Yunfan Gao, Yun Xiong, Xinyu Gao, Kangxiang Jia, Jinliu Pan, Yuxi Bi, Yi Dai, Jiawei Sun, and Haofen Wang.  Retrieval-augmented generation for large language models: A survey.  arXiv preprint arXiv:2312.10997, 2023.
  * HKMN [23] Samuel B Hopkins, Gautam Kamath, Mahbod Majid, and Shyam Narayanan.  Robustness implies privacy in statistical estimation.  In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pages 497–506, 2023.
  * HLL+ [24] Sirui Hong, Yizhang Lin, Bangbang Liu, Binhao Wu, Danyang Li, Jiaqi Chen, Jiayi Zhang, Jinlin Wang, Lingyao Zhang, Mingchen Zhuge, et al.  Data interpreter: An llm agent for data science.  arXiv preprint arXiv:2402.18679, 2024.
  * HMT+ [22] Amir Hertz, Ron Mokady, Jay Tenenbaum, Kfir Aberman, Yael Pritch, and Daniel Cohen-Or.  Prompt-to-prompt image editing with cross attention control.  arXiv preprint arXiv:2208.01626, 2022.
  * HY [21] Ziyue Huang and Ke Yi.  Approximate range counting under differential privacy.  In 37th International Symposium on Computational Geometry (SoCG 2021). Schloss-Dagstuhl-Leibniz Zentrum für Informatik, 2021.
  * HZC+ [24] Sirui Hong, Mingchen Zhuge, Jonathan Chen, Xiawu Zheng, Yuheng Cheng, Jinlin Wang, Ceyao Zhang, Zili Wang, Steven Ka Shing Yau, Zijuan Lin, Liyang Zhou, Chenyu Ran, Lingfeng Xiao, Chenglin Wu, and Jürgen Schmidhuber.  MetaGPT: Meta programming for a multi-agent collaborative framework.  In The Twelfth International Conference on Learning Representations, 2024.
  * HZRS [16] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770–778, 2016.
  * JHL+ [24] Haibo Jin, Leyang Hu, Xinuo Li, Peiyan Zhang, Chonghan Chen, Jun Zhuang, and Haohan Wang.  Jailbreakzoo: Survey, landscapes, and horizons in jailbreaking large language and vision-language models.  arXiv preprint arXiv:2407.01599, 2024.
  * JLN+ [19] Christopher Jung, Katrina Ligett, Seth Neel, Aaron Roth, Saeed Sharifi-Malvajerdi, and Moshe Shenfeld.  A new analysis of differential privacy’s generalization guarantees.  arXiv preprint arXiv:1909.03577, 2019.
  * LCL+ [23] Haoran Li, Yulin Chen, Jinglong Luo, Yan Kang, Xiaojin Zhang, Qi Hu, Chunkit Chan, and Yangqiu Song.  Privacy in large language models: Attacks, defenses and future directions.  arXiv preprint arXiv:2310.10383, 2023.
  * LGF+ [23] Haoran Li, Dadi Guo, Wei Fan, Mingshi Xu, Jie Huang, Fanpu Meng, and Yangqiu Song.  Multi-step jailbreaking privacy attacks on chatgpt.  In Findings of the Association for Computational Linguistics: EMNLP 2023, pages 4138–4153, 2023.
  * [56] Ping Li and Xiaoyun Li.  Differential privacy with random projections and sign random projections.  arXiv preprint arXiv:2306.01751, 2023.
  * [57] Xiaoyun Li and Ping Li.  Differentially private one permutation hashing and bin-wise consistent weighted sampling.  arXiv preprint arXiv:2306.07674, 2023.
  * LL [24] Ping Li and Xiaoyun Li.  Smooth flipping probability for differential private sign random projection methods.  Advances in Neural Information Processing Systems, 36, 2024.
  * LLB+ [24] Zhihao Liu, Jian Lou, Wenjie Bao, Zhan Qin, and Kui Ren.  Differentially private zeroth-order methods for scalable large language model finetuning.  arXiv preprint arXiv:2402.07818, 2024.
  * LLH+ [22] Xuechen Li, Daogao Liu, Tatsunori B Hashimoto, Huseyin A Inan, Janardhan Kulkarni, Yin-Tat Lee, and Abhradeep Guha Thakurta.  When does differentially private learning not suffer in high dimensions?  Advances in Neural Information Processing Systems, 35:28616–28630, 2022.
  * LLSY [17] Ninghui Li, Min Lyu, Dong Su, and Weining Yang.  Differential privacy: From theory to practice.  Springer, 2017.
  * LPP+ [20] Patrick Lewis, Ethan Perez, Aleksandra Piktus, Fabio Petroni, Vladimir Karpukhin, Naman Goyal, Heinrich Küttler, Mike Lewis, Wen-tau Yih, Tim Rocktäschel, et al.  Retrieval-augmented generation for knowledge-intensive nlp tasks.  Advances in Neural Information Processing Systems, 33:9459–9474, 2020.
  * LTLH [21] Xuechen Li, Florian Tramer, Percy Liang, and Tatsunori Hashimoto.  Large language models can be strong differentially private learners.  In International Conference on Learning Representations, 2021.
  * LYZ+ [23] Zhiwei Liu, Weiran Yao, Jianguo Zhang, Le Xue, Shelby Heinecke, Rithesh Murthy, Yihao Feng, Zeyuan Chen, Juan Carlos Niebles, Devansh Arpit, et al.  Bolaa: Benchmarking and orchestrating llm-augmented autonomous agents.  arXiv preprint arXiv:2308.05960, 2023.
  * MJW+ [22] Justus Mattern, Zhijing Jin, Benjamin Weggenmann, Bernhard Schölkopf, and Mrinmaya Sachan.  Differentially private language models for secure data sharing.  In Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, pages 4860–4873. Association for Computational Linguistics, 2022.
  * MYH+ [23] Peihua Mai, Ran Yan, Zhe Huang, Youjia Yang, and Yan Pang.  Split-and-denoise: Protect large language model inference with local differential privacy.  arXiv preprint arXiv:2310.09130, 2023.
  * Nar [22] Shyam Narayanan.  Private high-dimensional hypothesis testing.  In Conference on Learning Theory, pages 3979–4027. PMLR, 2022.
  * Nar [23] Shyam Narayanan.  Better and simpler lower bounds for differentially private statistical estimation.  arXiv preprint arXiv:2310.06289, 2023.
  * [69] OpenAI.  Creating a gpt, 2024.  https://help.openai.com/en/articles/8554397-creating-a-gpt.
  * [70] OpenAI.  Video generation models as world simulators, 2024.  https://openai.com/research/video-generation-models-as-world-simulators.
  * ORST [23] Samet Oymak, Ankit Singh Rawat, Mahdi Soltanolkotabi, and Christos Thrampoulidis.  On the role of attention in prompt-tuning.  In International Conference on Machine Learning, pages 26724–26768. PMLR, 2023.
  * Pat [24] Dylan Patel.  Chatgpt system prompt is 1700 tokens?!, 2024.  https://x.com/dylan522p/status/1755086111397863777.
  * PHK+ [23] Natalia Ponomareva, Hussein Hazimeh, Alex Kurakin, Zheng Xu, Carson Denison, H Brendan McMahan, Sergei Vassilvitskii, Steve Chien, and Abhradeep Guha Thakurta.  How to dp-fy ml: A practical guide to machine learning with differential privacy.  Journal of Artificial Intelligence Research, 77:1113–1201, 2023.
  * PX [23] William Peebles and Saining Xie.  Scalable diffusion models with transformers.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 4195–4205, 2023.
  * QRS+ [22] Lianke Qin, Aravind Reddy, Zhao Song, Zhaozhuo Xu, and Danyang Zhuo.  Adaptive and dynamic multi-resolution hashing for pairwise summations.  In 2022 IEEE International Conference on Big Data (Big Data), pages 115–120. IEEE, 2022.
  * RBL+ [22] Robin Rombach, Andreas Blattmann, Dominik Lorenz, Patrick Esser, and Björn Ommer.  High-resolution image synthesis with latent diffusion models.  In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 10684–10695, 2022.
  * SAMB [24] Tanmay Singh, Harshvardhan Aditya, Vijay K Madisetti, and Arshdeep Bahga.  Whispered tuning: Data privacy preservation in fine-tuning llms through differential privacy.  Journal of Software Engineering and Applications, 17(1):1–22, 2024.
  * SCL+ [22] Zhenmei Shi, Jiefeng Chen, Kunyang Li, Jayaram Raghuram, Xi Wu, Yingyu Liang, and Somesh Jha.  The trade-off between universality and label efficiency of representations from contrastive learning.  In The Eleventh International Conference on Learning Representations, 2022.
  * SCS+ [22] Chitwan Saharia, William Chan, Saurabh Saxena, Lala Li, Jay Whang, Emily L Denton, Kamyar Ghasemipour, Raphael Gontijo Lopes, Burcu Karagol Ayan, Tim Salimans, et al.  Photorealistic text-to-image diffusion models with deep language understanding.  Advances in neural information processing systems, 35:36479–36494, 2022.
  * SIB+ [24] Sander Schulhoff, Michael Ilie, Nishant Balepur, Konstantine Kahadze, Amanda Liu, Chenglei Si, Yinheng Li, Aayush Gupta, HyoJung Han, Sevien Schulhoff, et al.  The prompt report: A systematic survey of prompting techniques.  arXiv preprint arXiv:2406.06608, 2024.
  * SSC+ [22] Weiyan Shi, Ryan Shea, Si Chen, Chiyuan Zhang, Ruoxi Jia, and Zhou Yu.  Just fine-tune twice: Selective differential privacy for large language models.  In Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, pages 6327–6340, 2022.
  * SWXL [24] Zhenmei Shi, Junyi Wei, Zhuoyan Xu, and Yingyu Liang.  Why larger language models do in-context learning differently?  arXiv preprint arXiv:2405.19592, 2024.
  * SWYZ [23] Zhao Song, Yitan Wang, Zheng Yu, and Lichen Zhang.  Sketching for first order method: efficient algorithm for low-bandwidth channel and vulnerability.  In International Conference on Machine Learning, pages 32365–32417. PMLR, 2023.
  * SYYZ [23] Zhao Song, Xin Yang, Yuanyuan Yang, and Lichen Zhang.  Sketching meets differential privacy: fast algorithm for dynamic kronecker projection maintenance.  In International Conference on Machine Learning (ICML), pages 32418–32462. PMLR, 2023.
  * Ver [17] Roman Vershynin.  An introduction with applications in data science.  Camb. Ser. Stat. Probab. Math, 47, 2017.
  * VSP+ [17] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  Advances in neural information processing systems, 30, 2017.
  * WMS+ [24] Jiayu Wang, Yifei Ming, Zhenmei Shi, Vibhav Vineet, Xin Wang, and Neel Joshi.  Is a picture worth a thousand words? delving into spatial reasoning for vision language models.  arXiv preprint arXiv:2406.14852, 2024.
  * Woo [14] David P Woodruff.  Sketching as a tool for numerical linear algebra.  Foundations and Trends® in Theoretical Computer Science, 10(1–2):1–157, 2014.
  * WTB+ [22] Jason Wei, Yi Tay, Rishi Bommasani, Colin Raffel, Barret Zoph, Sebastian Borgeaud, Dani Yogatama, Maarten Bosma, Denny Zhou, Donald Metzler, et al.  Emergent abilities of large language models.  arXiv preprint arXiv:2206.07682, 2022.
  * WXJ+ [23] Guanzhi Wang, Yuqi Xie, Yunfan Jiang, Ajay Mandlekar, Chaowei Xiao, Yuke Zhu, Linxi Fan, and Anima Anandkumar.  Voyager: An open-ended embodied agent with large language models.  arXiv preprint arXiv:2305.16291, 2023.
  * WZZ [23] David Woodruff, Fred Zhang, and Samson Zhou.  On robust streaming for learning with experts: algorithms and lower bounds.  Advances in Neural Information Processing Systems, 36:79518–79539, 2023.
  * XSL [24] Zhuoyan Xu, Zhenmei Shi, and Yingyu Liang.  Do large language models have compositional ability? an investigation into limitations and scalability.  In ICLR 2024 Workshop on Mathematical and Empirical Understanding of Foundation Models, 2024.
  * XSW+ [23] Zhuoyan Xu, Zhenmei Shi, Junyi Wei, Fangzhou Mu, Yin Li, and Yingyu Liang.  Towards few-shot adaptation of foundation models via multitask finetuning.  In The Twelfth International Conference on Learning Representations, 2023.
  * YGZ+ [23] Mengmeng Yang, Taolin Guo, Tianqing Zhu, Ivan Tjuawinata, Jun Zhao, and Kwok-Yan Lam.  Local differential privacy and its applications: A comprehensive survey.  Computer Standards & Interfaces, page 103827, 2023.
  * YLH+ [24] Jiahao Yu, Haozheng Luo, Jerry Yao-Chieh Hu, Wenbo Guo, Han Liu, and Xinyu Xing.  Enhancing jailbreak attack against large language models through silent tokens.  arXiv preprint arXiv:2405.20653, 2024.
  * YNB+ [21] Da Yu, Saurabh Naik, Arturs Backurs, Sivakanth Gopi, Huseyin A Inan, Gautam Kamath, Janardhan Kulkarni, Yin Tat Lee, Andre Manoel, Lukas Wutschitz, et al.  Differentially private fine-tuning of language models.  In International Conference on Learning Representations, 2021.
  * YYB+ [24] Fei Yang, Shiqi Yang, Muhammad Atif Butt, Joost van de Weijer, et al.  Dynamic prompt learning: Addressing cross-attention leakage for text-based image editing.  Advances in Neural Information Processing Systems, 36, 2024.
  * ZC [22] Ying Zhao and Jinjun Chen.  A survey on differential privacy for unstructured data content.  ACM Computing Surveys (CSUR), 54(10s):1–28, 2022.
  * ZSZ+ [24] Chunyan Zheng, Keke Sun, Wenhao Zhao, Haibo Zhou, Lixing Jiang, Shaoyang Song, and Chunlai Zhou.  Locally differentially private in-context learning.  In LREC/COLING, 2024.