# Higher-order Common Information

Jan Østergaard J. Østergaard<EMAIL_ADDRESS>is with the Department of
Electronic Systems, Aalborg University, Aalborg, Denmark.

###### Abstract

We present a new notion $R_{\ell}$ of higher-order common information, which
quantifies the information that $\ell\geq 2$ arbitrarily distributed random
variables have in common. We provide analytical lower bounds on $R_{3}$ and
$R_{4}$ for jointly Gaussian distributed sources and provide computable lower
bounds for $R_{\ell}$ for any $\ell$ and any sources. We also provide a
practical method to estimate the lower bounds on, e.g., real-world time-series
data. As an example, we consider EEG data acquired in a setup with competing
acoustic stimuli. We demonstrate that $R_{3}$ has descriptive properties that
is not in $R_{2}$. Moreover, we observe a linear relationship between the
amount of common information $R_{3}$ communicated from the acoustic stimuli
and to the brain and the corresponding cortical activity in terms of neural
tracking of the envelopes of the stimuli.

##  I Introduction

Computing the common or redundant information $R$ within a set of $n$ random
variables $X_{1},\dotsc,X_{n}$, is an open problem for $n>2$. For the case of
$n=2$, Shannon’s mutual information provides an answer: $R=I(X_{1};X_{2})$
[1]. For $n>2$, the notion of common information could have several meanings.
For example, if it is the amount of pairwise common information shared by
$X_{1},X_{2}$, and $X_{3}$, then one could simply use the minimum pairwise
redundancy, i.e.

$R_{2}\triangleq\min_{i,j}\ \\{I(X_{i};X_{j})\\}.$ (1)

Clearly (1) does not quantify whether it is the _same_ information that is
contained in all variables but only considers the _amount_ of pairwise mutual
information. Wyner [2] and others [3, 4, 5] have studied a different problem
of common information, where the dependency between two random variables
$(X_{1},X_{2})$ is quantified via a third auxiliary random variable $W$. The
variable $W$ is a minimal sufficient statistic for $X_{1}$ with respect to
$X_{2}$ and vice-versa and thereby satisfy the Markov chain $X_{1}-W-X_{2}$.
Formally, Wyner’s common information $C(X_{1},X_{2})$ can be computed as
follows:

$\displaystyle C(X_{1},X_{2})=\inf_{p(w|x_{1},x_{2})}I(X_{1},X_{2};W)$ (2)
$\displaystyle\quad s.t.\quad I(X_{1};X_{2}|W)=0,$

which for the case of two standard normal correlated sources is given by [5]:

$\displaystyle C(X_{1},X_{2})$
$\displaystyle=\frac{1}{2}\log_{2}\bigg{(}\frac{1+|\rho|}{1-|\rho|}\bigg{)}$
(3) $\displaystyle\neq
I(X_{1};X_{2})=\frac{1}{2}\log_{2}\bigg{(}\frac{1}{1-\rho^{2}}\bigg{)}.$ (4)

If one is interested in the redundancy with respect to an additional variable
$Y$, i.e., the information that $X_{1},\dotsc,X_{n}$ share about $Y$, then
this has been considered in e.g., [6, 7, 8], and was recently extended to
processes in [9]. Alternatively, in [10, 11] the unique information that each
variable provides to $Y$ was quantified. If one knows the amount of unique
information, then one can use this knowledge to estimate the redundant
information. A general paradigm seeking to unravel unique, redundant, and
synergistic information in random variables is found in the partial
information decomposition (PID) works, see e.g., [6, 12].

In this paper, we define a new notion of ”mutual” information for $n\geq 2$
variables. We refer to it as _higher-order_ common information, and we denote
it by $R_{\ell}$, where $\ell$ indicates the order. Our aim is to quantify the
common (or shared) information that is contained in $\ell$ arbitrarily
distributed random variables. The second-order common information, called
$R_{2}$, is the minimal information shared by $\ell=2$ out of the $n$
variables. It may be noticed that $R_{2}$ coincides with the pairwise
redundancy given in (1). As we demonstrate in this paper, $R_{2}$ can grossly
overestimate the true amount of common information in $n$ variables. The
meaning of $R_{3}$, the third-order common information, is the minimal
information that is contained in $\ell=3$ out of the $n$ variables. To compute
$R_{\ell}$ for $\ell\geq 3,$ we need to introduce a novel machinery that can
pinpoint common information within the variables. Toward that end, we will
introduce a generalized concept of minimal sufficient statistics, which we
refer to as minimal sufficient common information. For a set of $n$ random
variables, and for each order $\ell$, we define the set $\mathcal{T}_{\ell}$
of minimal sufficient common information. The true amount of common
information $R_{\ell}$ is then lower bounded by the minimal mutual information
between elements in $\mathcal{T}_{\ell-1}$ and $\mathcal{T}_{1}$.

We provide computable analytical bounds for $R_{2},R_{3},$ and $R_{4}$ for the
Gaussian case and, furthermore, devise a practical method to compute lower
bounds on the higher-order common information $R_{\ell}$ for arbitrarily
distributed sources and processes. As a motivating example, we demonstrate on
real-world EEG data, that $R_{3}$ is better than $R_{2}$ for predicting the
correlations between the envelope of the acoustic stimuli and the EEG signals.

###  I-A Notation

We use calligraphic letters such as $\mathcal{X}$ for sets. Let
$\mathcal{X}=\\{X_{1},\dotsc,X_{n}\\}$ denote a set containing $n$ random
variables. Then, for two random variables indexed as $X_{i}$ and $X_{j}$, it
is implicitly assumed throughout the paper that $1\leq i\neq j\leq n$. More
generally, the conditional mutual information $I(X_{i};X_{j}|X_{k})$ refers to
distinct variables of $\mathcal{X}$, i.e., $i\neq j\neq k\neq i$ unless
otherwise specified.

###  I-B Paper organization

In section II, we present an example that demonstrates some problems by using
the conditional mutual information to bound the common information in three or
more variables. In Section III, we present our main idea which is a new notion
of sufficient common information, which makes it possible to lower bound the
common information in $n$ random variables. In Sections IV and V, we consider
Gaussian and discrete sources, respectively, and in Section VI we extend the
results to general sources and processes. Section VII presents a simulation
study on real-world EEG data, and Section VIII describes the limitations. The
conclusions are in Section IX, and proofs of lemmas and theorems are in the
appendix.

##  II Common information via conditional mutual information

In this section, we demonstrate that even in the Gaussian case, it is non-
trivial to come up with a useful lower bound on the common information that
exists within three or more variables.

We begin by introducing the following lemma.

###### Lemma 1

Let $X_{i}=X+N_{i},i=1,\dotsc,n,$ where $X\sim\mathcal{N}(0,\sigma_{X}^{2})$
and $N_{i}\sim\mathcal{N}(0,\sigma_{N}^{2})$ are independent of each other for
all $i$. Moreover, let $\rho\in[-1,1]$ be the pairwise correlation coefficient
$\rho$ of $N_{1},\dotsc,N_{n},$ so that
$\mathbb{E}[X_{i}X_{j}]=\rho\sigma_{N}^{2}$. Then

$\displaystyle
I(X;X_{i})=\frac{1}{2}\log_{2}\bigg{(}\frac{\sigma_{X}^{2}+\sigma_{N}^{2}}{\sigma_{N}^{2}}\bigg{)},$
(5) $\displaystyle
I(X_{i};X_{j})=\frac{1}{2}\log_{2}\bigg{(}\frac{(\sigma_{X}^{2}+\sigma_{N}^{2})^{2}}{\sigma_{N}^{2}(1-\rho)(\sigma_{N}^{2}(1+\rho)+2\sigma_{X}^{2})}\bigg{)},$
(6) $\displaystyle
I(X_{i};X_{j}|X_{k})=\frac{1}{2}\log_{2}\bigg{(}\frac{((1+\rho)\sigma_{N}^{2}+2\sigma_{X}^{2})^{2}}{(\sigma_{X}^{2}+\sigma_{N}^{2})((1+2\rho)\sigma_{N}^{2}+3\sigma_{X}^{2})}\bigg{)}.$
(7)

$\square$

Figure 1: Expression and bounds of Lemma 1 and Theorem 2. Figure 2: The
pairwise ($R_{2}$) common information and lower bounds on the third-
($R_{3}^{\mathrm{lower}}$) and fourth-order ($R_{4}^{\mathrm{lower}}$) common
information for four Gaussian variables: $X_{i}=X+N_{i},\
\mathbb{E}[N_{i}N_{j}]=\rho\sigma_{N}^{2}$.

The (conditional) mutual information expressions of Lemma 1 are shown in Fig.
1 for the case of $\sigma_{X}^{2}=1$ and $\sigma_{N}^{2}=5$. The expression
$I(X_{i};X_{j})$ shows the pairwise mutual information $R_{2}$, which is
always greater than or equal to $R_{3}$, the common information in three
variables.

It could be tempting to use the conditional mutual information to establish a
lower bound on $R_{3}$. For example, in some cases (but not all) one can
interpret $I(X_{1};X_{2}|X_{3})$ as the remaining common information between
$X_{1}$ and $X_{2}$, which is left after removing the information that is also
in $X_{3}$. Thus, the effect of $X_{3}$ is (potentially) removed, and we could
form the difference $I(X_{1};X_{2})-I(X_{1};X_{2}|X_{3})$ as an estimate of
the common information in all three variables.111Note that
$I(X_{1};X_{2})-I(X_{1};X_{2}|X_{3})$ is commonly referred to as the
interaction information [13, 14]. In this particular case, however, when
$\rho<-0.2$, then $I(X_{1};X_{2}|X_{3})>I(X_{1};X_{2})$ in which case we get a
negative lower bound, which is not informative. The fact that the conditional
mutual information can be greater than the unconditional one, is well known in
information theory, and the excess amount of information is usually referred
to as synergistic information [15].

From Fig. 1, it can be observed that it can even happen that
$I(X;X_{i})<I(X_{i};X_{j})$ as is the case here when $\rho>0.3$. This is
possible since the common information between $X_{i}$ and $X_{j}$ is partially
from $X$ and partially from the correlated noises $N_{i},N_{j}$.

##  III Higher-order common information via sufficient common information

Let $\mathcal{X}=(A,B),\mathcal{Y}=(A,C)$, and $\mathcal{Z}=(B,C)$ be three
sets whose intersection is empty, i.e.
$\mathcal{X}\cap\mathcal{Y}\cap\mathcal{Z}=\emptyset$ but their pairwise
intersections are non-empty, e.g., $\mathcal{X}\cap\mathcal{Y}=A$. Now let
$A,B,$ and $C$ be mutually independent and identically distributed discrete
random variables, and let $X=(A,B),Y=(A,C)$, and $Z=(B,C)$. Then, their
pairwise common information is non-zero but since no piece of information is
in all of them, the third-order common information is zero.

It was demonstrated in [9], that in some cases it is possible to quantify the
common information using a notion of sufficient statistics. Specifically, let
$T_{XY}$ be a sufficient statistic of $X$ with respect to $Y$, i.e.,
$I(X;Y)=I(T_{XY};Y)$ and $X-T_{XY}-Y$ forms a Markov chain, which means that
$X$ and $Y$ are conditionally independent of each other given knowledge of
$T_{XY}$ [1]. A minimal sufficient statistic $T^{*}_{XY}$ satisfies [1]:

$\displaystyle T^{*}_{XY}=\arg\min_{T_{XY}}I(T_{XY};X)$ (8) $\displaystyle
s.t.\quad I(T_{XY};Y)=I(X;Y)\ \mathrm{and}\ X-T_{XY}-Y.$ (9)

One may readily verify that in this example we have $T_{XY}=A,T_{XZ}=B$, and
$T_{YZ}=C$. Clearly $I(T_{XY};T_{XZ})=I(T_{XZ};T_{YZ})=I(T_{XY};T_{YZ})=0$
[9]. Thus, by replacing all pairs of variables with their sufficient
statistics, we were able to assess their common information. We can leverage
the above idea to establish lower bounds on the common information in any
number of arbitrarily distributed random variables. Our fundamental idea is to
replace the ”intersection” $X_{1}\cap X_{2}$ with another random variable
$\phi_{1,2}$, which contains no more information about $X_{1},X_{2}$, and
$X_{3}$ than what $X_{1}$ and $X_{2}$ do separately. Specifically, if
$I(\phi_{1,2};X_{\gamma})\leq\min(I(X_{1};X_{\gamma}),I(X_{2};X_{\gamma}))$
for $\gamma=1,2,3$. Then, we could use $I(\phi_{1,2};\phi_{1,3})$ or simply
$I(\phi_{1,2};X_{3})$ as a lower bound on the common information contained in
$X_{1}\cap X_{2}\cap X_{3}$.

We do not necessarily need that $\phi_{1,2}$ is a sufficient statistic for
$X_{1}$ wrt. $X_{2}$. We only need to ensure that the information in
$\phi_{1,2}$ about other variables is not greater than what is in $X_{1}$ and
$X_{2}$. We therefore introduce the terminology that $\phi_{1,2}$ is
_sufficient common information_ for $X_{1}$ wrt. $X_{2}$. This is formally
defined in the following definition.

###### Definition 1

Let $\mathcal{X}=(X_{1},\dotsc,X_{n})$ be arbitrarily jointly distributed.
Then, $\phi_{i,j}$ is said to be sufficient common information (SCI) for
$X_{i}$ wrt. $X_{j}$ if it satisfies:

$\displaystyle I(\phi_{i,j};X_{j})$ $\displaystyle=I(X_{i};X_{j}),$ (10)
$\displaystyle I(\phi_{i,j};X_{\gamma})$
$\displaystyle\leq\min(I(X_{i};X_{\gamma}),I(X_{j};X_{\gamma})),\gamma=1,\dotsc,n.$
(11)

The equality constraint in (10) is necessary to avoid trivial cases such as
letting $\phi_{1,2}=\emptyset$, which clearly satisfies (11). Thus, (10) help
ensuring that the lower bounds will not become too loose.

######  Definition 2 (Sets of minimal sufficient common information)

Let $\mathcal{X}=\\{X_{1},\dotsc,X_{n}\\}$ be $n$ arbitrarily jointly
distributed (not necessarily independent) random variables. We define the
sequence $\mathcal{T}_{1},\dotsc,\mathcal{T}_{n-1}$ of sets of minimal SCIs as
follows:

$\displaystyle\mathcal{T}_{1}$ $\displaystyle\triangleq\mathcal{X},$ (12)
$\displaystyle\mathcal{T}_{\ell}$
$\displaystyle\triangleq\\{S:S=\arg\min_{T}I(T;\phi),$
$\displaystyle\quad\quad s.t.\
\forall\phi\in\mathcal{T}_{\ell-1},\forall\phi^{\prime},\phi^{\prime\prime}\in\mathcal{T}_{1},$
(13) $\displaystyle\quad\quad I(T;\phi^{\prime})=I(\phi;\phi^{\prime})$ (14)
$\displaystyle\quad\quad I(T;\phi^{\prime\prime})\leq
I(\phi;\phi^{\prime\prime}),\phi^{\prime\prime}\neq\phi^{\prime}\\},\quad\ell=2,\dotsc,n-1.$
(15)

Since the same element could occur multiple times in $\mathcal{T}_{\ell}$, we
also define the unique set $\mathcal{T}_{\ell}^{u}$ which only contains the
unique elements of $\mathcal{T}_{\ell}$.

###### Remark 1

The minimization over $T$ in the definition of $\mathcal{T}_{\ell}$ combined
with the constraints (14) – (15) make sure that we can replace pairs of random
variables by their corresponding SCI, and obtain the property that the mutual
information between SCIs is always less than or equal to that of the original
variables.

######  Definition 3 ($\ell$-th order common information $R_{\ell}$)

Let $\mathcal{X}=\\{X_{1},\dotsc,X_{n}\\}$ be $n$ arbitrarily distributed
random variables, and let $I\subseteq\\{1,\dotsc,n\\}$ denote an index set
having $|I|=\ell$ distinct indices. Let $\mathcal{X}_{I}$ denote the elements
of $\mathcal{X}$ indexed by $I$. Then, $r_{I}$ is the minimal information that
the elements in $\mathcal{X}_{I}$ have in common, and $R_{\ell}$ is defined
as:

$R_{\ell}=\min_{\begin{subarray}{c}I\subseteq\\{1,\dotsc,n\\}\\\
|I|=\ell\end{subarray}}r_{I}.$ (16)

We are now in a position to present the main theorem of this section.

###### Theorem 1

For $\mathcal{X}=(X_{1},\dotsc,X_{n})$ arbitrarily jointly distributed:

$\displaystyle R_{\ell}$
$\displaystyle\geq\min_{\begin{subarray}{c}\phi\in\mathcal{T}_{\ell-1}^{u}\\\
\phi^{\prime}\in\mathcal{T}_{1}\end{subarray}}I(\phi;\phi^{\prime}),$ (17)

and

$\displaystyle\min_{\begin{subarray}{c}\phi\in\mathcal{T}_{1}^{u}\phi^{\prime}\in\mathcal{T}_{1}\end{subarray}}I(\phi;\phi^{\prime})\geq\cdots\geq\min_{\begin{subarray}{c}\phi\in\mathcal{T}_{n-1}^{u}\\\
\phi^{\prime}\in\mathcal{T}_{1}\end{subarray}}I(\phi;\phi^{\prime}).$ (18)

$\square$

##  IV Common information — Gaussian sources

In this section, we focus on the Gaussian case and to simplify the notation we
introduce the following definitions:

$\displaystyle\Delta$
$\displaystyle=(\sigma_{X}^{2}+\sigma_{N}^{2}),\quad\Delta_{\rho}=(\sigma_{X}^{2}+\rho\sigma_{N}^{2})$
(19) $\displaystyle\Delta_{1}$
$\displaystyle=\Delta^{2}-\Delta_{\rho}^{2}=\sigma_{N}^{2}(1-\rho)((1+\rho)\sigma_{N}^{2}+2\sigma_{X}^{2}).$
(20) $\displaystyle\Delta_{2}$
$\displaystyle=\Delta^{2}+\Delta_{\rho}^{2}=(1+\rho^{2})\sigma_{N}^{4}+2(1+\rho)\sigma_{X}^{2}\sigma_{N}^{2}+2\sigma_{X}^{4}.$
(21)

The theorem below bounds the 2nd, 3rd, and 4th-order common information.

###### Theorem 2

Let $X_{i}=X+N_{i},i=1,\dotsc,n$, be jointly Gaussian distributed, where
$N_{i}\sim\mathcal{N}(0,\sigma_{N}^{2})$ and $N_{i},N_{j}$ are pairwise
correlated with correlation $\rho\sigma_{N}^{2}$. Moreover,
$X\sim\mathcal{N}(0,\sigma_{X}^{2})$ is independent of $X_{i}$ for all $i$.
Then, the pairwise common information $R_{2}$ is given by:

$\displaystyle
R_{2}=\frac{1}{2}\log_{2}\bigg{(}\frac{\Delta^{2}}{\Delta_{1}}\bigg{)},$ (22)

and $R_{3}\geq R_{3}^{\mathrm{lower}}$ and $R_{4}\geq R_{4}^{\mathrm{lower}}$,
where

$\displaystyle
R_{3}^{\mathrm{lower}}\\!=R_{2}+\frac{1}{2}\log_{2}\bigg{(}\frac{\Delta^{2}}{\Delta_{2}}\bigg{)},$
(23) $\displaystyle
R_{4}^{\mathrm{lower}}\\!=R_{3}^{\mathrm{lower}}+\frac{1}{2}\log_{2}\bigg{(}\frac{1}{2}+\frac{\Delta_{1}\Delta_{2}}{2\Delta^{4}}\bigg{)}.$
(24)

$\square$

Fig. 2 shows $R_{2}$ given by (6) and the bounds on $R_{3}$ and $R_{4}$ given
in (24) as a function of $\sigma_{N}^{2}$ for fixed $\sigma_{X}^{2}=1$.

###### Corollary 1

For the same setup as in Theorem 2, the following asymptotics are true:

$\displaystyle\lim_{\sigma_{N}^{2}\to 0}R_{2}-R_{3}=\frac{1}{2}\
\mathrm{bit},$ (25) $\displaystyle\lim_{\sigma_{N}^{2}\to
0}\frac{R_{2}}{R_{3}}=1,$ (26) $\displaystyle\lim_{\sigma_{N}^{2}\to
0}R_{2}=\lim_{\sigma_{N}^{2}\to 0}R_{3}=\infty,$ (27)
$\displaystyle\lim_{\sigma_{N}^{2}\to\infty}R_{2}=\frac{1}{2}\log_{2}\bigg{(}\frac{1}{1-\rho^{2}}\bigg{)}\mathrm{bits},$
(28)
$\displaystyle\lim_{\sigma_{N}^{2}\to\infty}R_{3}=\frac{1}{2}\log_{2}\bigg{(}\frac{1}{(1-\rho^{2})(1+\rho^{2})}\bigg{)}\mathrm{bits}.$
(29)

$\square$

From Corollary 1, we observe that $R_{3}$ is not everywhere tight. In
particular, in the asymptotical case where $\sigma_{N}^{2}\to\infty$, the
multiplicative rate loss ($R_{2}/R_{3}$) vanishes but the additive rate loss
($R_{2}-R_{3}$) does not. In the non asymptotical case, the next lemma shows
that the additive error of 0.5 bits due to overestimating the true common
information $R_{3}$ in $(X_{1},X_{2},X_{3})$ by estimating it using $R_{2}$
holds in general and not just asymptotically in $\sigma_{N}^{2}$. Thus, using
$R_{2}$ to assess the common information in three Gaussian random variables is
at most $0.5$ bits wrong.

###### Lemma 2

For the problem in Theorem 2, the additive loss of common information
$R_{2}-R_{3}$ is bounded by:

$\sup_{\sigma_{N}^{2},\sigma_{X}^{2}>0,\rho\in(-1,1)}R_{2}-R_{3}=\frac{1}{2}\
\mathrm{bit}.$ (30)

$\square$

##  V Common information — discrete sources

In this section, we present a result for a particular choice of discrete
source, where the higher-order common information can be computed
analytically.

###### Theorem 3

Let $n>2$ and let $\mathcal{Z}=(Z_{1},\dotsc,Z_{n})$ be $n$ mutually
independent and identically distributed discrete random variables having
common finite marginal entropy $H(Z)=H(Z_{i}),\forall i$. For $i=1,\dotsc,n,$
form $X_{i}=(Z_{i_{1}},\dotsc,Z_{i_{n-1}})$ such that $X_{i}$ contains $n-1$
distinct elements of $\mathcal{Z}$, and if $i\neq j$ then $|X_{i}\cap
X_{j}|=n-2$. The elements of $\mathcal{X}=\\{X_{1},\dotsc,X_{n}\\}$ are all
unique, and any $\ell$ elements of $\mathcal{X}$ has $n-\ell$ elements of
$\mathcal{Z}$ in common. Moreover,

$R_{\ell}=\min_{\begin{subarray}{c}\phi\in\mathcal{T}_{\ell-1}^{u}\\\
\phi^{\prime}\in\mathcal{T}_{1}\end{subarray}}I(\phi;\phi^{\prime})=(n-\ell)H(Z).$
(31)

$\square$

###### Remark 2

In Theorem 3, the common information in all $n$ elements of $\mathcal{X}$ is
by construction zero, since the same bit of information is not represented in
all elements. On the other hand, the minimum pairwise mutual information in
the $n$ elements of $\mathcal{X}$ is $\min_{i,j}I(X_{i};X_{j})=(n-2)H(Z)$,
which grossly overestimates the true amount (which is zero).

##  VI Estimating common information in general sources

In this section, we treat the case of general sources. In particular, we
demonstrate how the proof of Theorem 2 can be used constructively to devise a
practical method for assessing the higher-order common information in
arbitrarily distributed time series data.

Let $\bar{X}_{1},\dotsc,\bar{X}_{K}$, be $K$ time-series each of length $N$.
Using any off-the-shelf mutual information estimator, one can obtain an
estimate $\hat{R}_{2}$ of $R_{2}$ by taking the minimum over all estimated
pairwise mutual informations, i.e.:

$\displaystyle\hat{R}_{2}=\min_{i,j\in\\{1,\dotsc,K\\}}\hat{I}(\bar{X}_{i},\bar{X}_{j}).$
(32)

Finding a lower bound on $R_{3}$ is not straightforward. However, the proof of
Theorem 2 suggests an idea. Specifically, let $\bar{Z}_{1,2}\in\mathbb{R}^{N}$
be a sequence of $N$ i.i.d. zero-mean Gaussian distributed random variables
with variance $\sigma_{Z_{1,2}}^{2}$, and which are all independent of
$\bar{X}_{1},\dotsc,\bar{X}_{K}$. Moreover, let
$\bar{T}_{1,2}=\bar{X}_{2}+\bar{Z}_{1,2}$. Thus, $\bar{T}_{1,2}$ can be seen
as a noisy version of $\bar{X}_{2}$. Our idea is to add i.i.d. zero-mean
Gaussian noise to all the components in $\bar{X}_{2}$ in order to obtain
$\bar{T}_{1,2}$, and where we tune the variance $\sigma_{Z_{1,2}}^{2}$
appropriately so that $\bar{T}_{1,2}$ forms a SCI for $\bar{X}_{1}$ wrt.
$\bar{X}_{2}$. To do this, we let $\sigma_{Z_{1,2}}^{2}$ be such that the
following approximation is satisfied:

$\displaystyle I(\bar{T}_{1,2};\bar{X}_{2})\approx
I(\bar{X}_{1};\bar{X}_{2}).$ (33)

For example, this can be done by starting with a small initial
$\sigma_{Z_{1,2}}^{2}\ll 1$ and gradually increasing $\sigma_{Z_{1,2}}^{2}$
until the difference between the mutual information estimates is within some
desired $\epsilon$ accuracy, i.e.,
$|\hat{I}(\bar{T}_{1,2};\bar{X}_{2})-\hat{I}(\bar{X}_{1};\bar{X}_{2})|<\epsilon$.
This procedure is repeated for all pairs $i\neq j\in\\{1,\dotsc,K\\}$, which
results in the set $\mathcal{T}_{2}=\\{\bar{T}_{i,j}\\}$ containing
$\frac{1}{2}(N^{2}-N)$ elements. At this point, one can then compute an
estimate $\hat{R}_{3}^{\mathrm{lower}}$ of the lower bound
$R_{3}^{\mathrm{lower}}$ by letting:

$\displaystyle\hat{R}_{3}^{\mathrm{lower}}$
$\displaystyle=\min_{i,j,k}\hat{I}(\bar{T}_{i,j};\bar{X}_{k})$ (34)
$\displaystyle\quad\mathrm{s.t.}\quad|\hat{I}(\bar{T}_{i,j};\bar{X}_{j})-\hat{I}(\bar{X}_{i};\bar{X}_{j})|<\epsilon.$

The intuition for the above procedure stems from the following. Let
$X_{1}=X+N_{1}$ and $X_{2}=X+N_{2}$ be jointly Gaussian distributed, where
$N_{1},N_{2}$ are correlated with correlation coefficient $\rho$, and variance
$\sigma_{N_{1}}^{2}=\sigma_{N_{2}}^{2}=\sigma_{N}^{2}$. Moreover, let
$X\sim\mathcal{N}(0,\sigma_{X}^{2})$ be independent of $N_{1},N_{2}$. Then, in
the proof of Theorem 2, we found the minimum MSE estimation error
$\epsilon_{j}$ in (63) as the error due to estimating $X_{2}$ from $X_{1}$.
This error has variance $\sigma_{\epsilon_{j}}^{2}$ given by (64). On the
other hand, let $T_{1,2}=X_{2}+Z_{1,2}$, where
$Z_{1,2}\sim\mathcal{N}(0,\sigma_{Z_{1,2}}^{2})$ is independent of
$X_{1},X_{2}$ and where $\sigma_{Z_{1,2}}^{2}$ is chosen such that
$I(T_{1,2};X_{2})=I(X_{1},X_{2})$. To do this we can rewrite
$I(T_{1,2};X_{2})$ as:

$\displaystyle I(T_{1,2};X_{2})$ $\displaystyle=h(T_{1,2})-h(T_{1,2}|X_{2})$
(35) $\displaystyle=h(T_{1,2})-h(Z_{1,2})$ (36)
$\displaystyle=\frac{1}{2}\log_{2}\bigg{(}\frac{\sigma_{X}^{2}+\sigma_{N}^{2}+\sigma_{Z_{1,2}}^{2}}{\sigma_{Z_{1,2}}^{2}}\bigg{)}.$
(37)

Setting the arguments of the logarithms in (37) and (57) equal to each other
and solving for $\sigma_{Z_{1,2}}^{2}$ yields
$\sigma_{Z_{1,2}}^{2}=\frac{\Delta\Delta_{1}}{\Delta_{\rho}^{2}}$, which is
equal to (64). Thus, $Z_{1,2}$ is distributed exactly as $Z_{j}$ in (67),
which was used to form the SCI for $X_{1}$ wrt. $X_{2}$. It follows that
$T_{1,2}$ obtained by the solving the practical optimization problem in (34)
is therefore also a SCI for $X_{1}$ wrt. $X_{2}$.

In the case where $X$ is non-Gaussian, we do not have similar strong proof of
equivalence. However, for $X$ arbitrarily distributed, $Z_{i,j}$ Gaussian
distributed, and $T_{i,j}=X_{j}+Z_{i,j}$, it still follows that
$I(T_{i,j};X_{i})<I(T_{i,j};X_{j})=I(X_{i};X_{j})$ and $I(T_{i,j};X_{k})\leq
I(X_{i};X_{k})$. Thus, $T_{i,j}$ is a SCI for $X_{i}$ wrt. $X_{j}$ and
$I(T_{i,j};X_{i})$ is strictly less than the pairwise common information
$I(X_{i};X_{j})$. It is, therefore, so that also in this case of non-Gaussian
sources, $R_{3}\geq\min_{i,j,k}I(T_{i,j};X_{k})$ and
$R_{4}\geq\min_{i,j,k,m}I(T_{i,j};T_{k,m})$.

Bounds on the higher-order common information $R_{\ell}$, for $\ell>4$, can be
approximated by continuing the above procedure and e.g., letting
$T_{i,j,k}=T_{i,j}+Z_{i,j,k}$ be a SCI for $T_{i,k}$ wrt. $T_{i,j}$.

###  VI-A Approximations to the higher-order common information

We here briefly introduce two approximations to $R_{\ell}$. The first one is
based in the average amount of information in $\mathcal{T}_{\ell}$, and the
second one is given as a deterministic function of $R_{2}$.

Let $\mathcal{X}=\\{X_{1},\dotsc,X_{N}\\}$ be arbitrarily distributed random
variables. Then, we define $\bar{R}_{\ell}$ as the average information in
$\mathcal{T}_{\ell}$, which we estimate as:

$\displaystyle\bar{R}_{\ell}\triangleq\frac{1}{\binom{|\mathcal{T}_{\ell-1}^{u}|}{2}}\sum_{\begin{subarray}{c}\phi\in\mathcal{T}_{\ell-1}^{u}\\\
\phi^{\prime}\in\mathcal{T}_{1}\end{subarray}}I(\phi;\phi^{\prime}).$ (38)

To avoid having to compute SCI, one could compute the pairwise common
information $R_{2}$, and replace the ratio $R_{\ell}/R_{2}=c_{\ell}$ by some
relevant quantity. In particular, for the simple case treated in Section V, we
know that $R_{\ell}=(N-\ell)H(Z)$ from which we let $c_{\ell}=(N-\ell)/(N-2)$.
Thus, we suggest the following approximation:

$\tilde{R}_{\ell}=\frac{N-\ell}{N-2}R_{2}=c_{\ell}R_{2}.$ (39)

##  VII Second and third-order common information in EEG data

As an example on real-world data, we consider 64-channel scalp EEG recordings
from the dataset described in [16]. The data reflects a listening experiment
where normal hearing subjects were exposed to two competing speech audio
streams. The audio streams were presented in simulated rooms and were
spatially separated from each other. The subjects were instructed to pay
attention to one of the audio streams (the target) while ignoring the other
(the distractor). The temporal envelopes [17] of the target $\mathrm{env}_{T}$
and distractor $\mathrm{env}_{D}$ were acquired and downsampled to 64 Hz to
match the sampling frequency of the EEG signals. After pre-processing where
artefacts due to eye-blinks were removed from the EEG signals and low SNR EEG
signals omitted, 15 subjects each having 60 repeated trials were used. The
acoustic envelopes and EEG signals were normalized to be zero-mean and unit
variance.

It has been demonstrated that slow moving cortical oscillations in the delta
and theta bands are modulated by the envelope of the attended sound [18, 19].
Thus, by correlating $\mathrm{env}_{T}$ and $\mathrm{env}_{D}$ with the EEG
electrode signals, it is expected that the correlation is strongest between
$\mathrm{env}_{T}$ and the electrode signals.

We focus on two regions of interests; the left ($\mathcal{LT}$) and right
$(\mathcal{RT}$) temporal areas, which we in this study define as the
electrodes closest to the left and right ear, respectively:

$\displaystyle\mathcal{LT}\triangleq$
$\displaystyle\\{\mathrm{FT}_{7},\mathrm{T}_{7},\mathrm{TP}_{7},\mathrm{CP}_{5},\mathrm{FC}_{5},\mathrm{C}_{5}\\},$
(40) $\displaystyle\mathcal{RT}\triangleq$
$\displaystyle\\{\mathrm{FT}_{8},\mathrm{T}_{8},\mathrm{TP}_{8},\mathrm{CP}_{6},\mathrm{FC}_{6},\mathrm{C}_{6}\\},$
(41)

where the naming of the electrodes refers to the extended 10-20 international
64 channel EEG electrode layout convention [20].

Let $\rho_{\tau}(\mathrm{FT}_{7},\mathrm{env}_{T})$ denote the absolute
correlation at lag $\tau$ between the time-series representation of the EEG
signal recorded by electrode $\mathrm{FT}_{7}$ and the envelope of the
acoustic target signal. There can be varying delays between the acoustic
stimuli and the resulting EEG signals at the different electrodes, and for
each electrode we therefore maximize the correlations over time lags ranging
from 190 – 300 ms in steps of 1/64 = 15.6 ms. For electrode $\mathrm{FT}_{7}$
and target envelope $\mathrm{env}_{T}$, there are 15 subject each having 60
trials resulting in $15\times 60$ correlation values
$\rho_{\tau}(\mathrm{FT}_{7},\mathrm{env}_{T})$. Similarly, correlation values
for the other electrodes with respect to $\mathrm{env}_{T}$ and
$\mathrm{env}_{D}$ were obtained.

We computed the empirical mutual information
$I(\mathrm{FT}_{7};\mathrm{env}_{T})$ for each pair of the $15\times 60$
realizations of $\mathrm{FT}_{7}$ and $\mathrm{env}_{T}$. These mutual
information represents the second-order common information, $r_{2}$, and were
computed on the time-series data by using the TRENTTOOL estimator [21].
Specifically, let $X^{t}=X_{0},\dotsc,X_{t}$ and $Y^{t}=Y_{0},\dotsc,Y_{t}$
denote two time series, then we used the bi-directional transfer entropy
estimator (with a lag of $\ell=3$ samples) as follows:

$\displaystyle I(X^{t};Y^{t})\approx
I(X^{t-1}_{t-\ell};Y_{t})+I(Y^{t-1}_{t-\ell};X_{t}).$ (42)

Thus, we computed the mutual information between the past three samples of $X$
and the current sample of $Y$ and added it to the mutual information of the
past three samples of $Y$ and the current sample of $X$. This was repeated for
the remaining electrodes in $\mathcal{LT}$ and $\mathcal{RT}$. Note that (42)
provides an estimation of the local $r_{2}$. To get an estimate of $R_{2}$ one
needs to minimize over the $r_{2}$’s within a localized region. Specifically,
we estimate $R_{2}$ as follows:

$\displaystyle
R_{2}^{\mathcal{LT}}\approx\min_{\varphi\in\mathcal{LT}}I(\varphi;\mathrm{env}_{T}),\quad
R_{2}^{\mathcal{RT}}\approx\min_{\varphi\in\mathcal{RT}}I(\varphi;\mathrm{env}_{T}).$
(43)

In order to obtain an estimate of the lower bound on the third-order common
information $R_{3}$, we used our practical optimization method in (34).
Specifically, we used the target envelope $\mathrm{env}_{T}$ to form a
sufficient common information $T_{\mathrm{FT}_{7}}=\mathrm{env}_{T}+N$ for
$\mathrm{FT}_{7}$ wrt. $\mathrm{env}_{T}$, where the variance of the Gaussian
noise $N$ was chosen using bisection such that
$I(T_{\mathrm{FT}_{7}};\mathrm{env}_{T})\approx
I(\mathrm{FT}_{7};\mathrm{env}_{T})$. Then, $\hat{r}_{3}\approx
I(T_{\mathrm{FT}_{7}};\mathrm{FT}_{7})$ and the lower bound $\hat{R}_{3}$ is
estimated as:

$\displaystyle\hat{R}_{3}^{\mathcal{LT}}\approx\min_{\varphi,\zeta\in\mathcal{LT}}I(T_{\zeta};\varphi),\quad\hat{R}_{3}^{\mathcal{RT}}\approx\min_{\varphi,\zeta\in\mathcal{RT}}I(T_{\zeta};\varphi),$
(44)

where the minimization is over all $\varphi,\zeta\in\mathcal{LT}$ or
$\varphi,\zeta\in\mathcal{RT}$ depending upon whether we focus on the left or
right temporal region. This was then repeated for the distractor signal
$\mathrm{env}_{D}$. We use the $\hat{}$ notation here to indicate that the
value $\hat{R}_{3}$ is an approximation of the lower bound on $R_{3}$.

The squared error can be written as $\|X-Y\|^{2}=\|X\|^{2}+\|Y\|^{2}-2\langle
X,Y\rangle$. In our case, the electrode and envelope signals have unit norm,
and the squared error between them is therefore a function of only their
correlation. We can interpret the correlation $\rho$ (or more precisely
$1-\rho$) as a ”distortion”, and form rate-correlation or rate-”distortion”
pairs, e.g.,
$(I(\mathrm{FT}_{7};\mathrm{env}_{T}),\rho_{\tau}(\mathrm{FT}_{7},\mathrm{env}_{T}))$.
From these rate-”distortion” pairs, it is interesting to assess whether the
rates and distortions are dependent upon each other. To assess this, we form a
linear regression model and test how well the rate predicts the distortion.
This is done by the fitlm command in Matlab. We test the (multiple) null
hypothesis that the model parameters for all 12 models (electrodes) are zero.
The corresponding $p$-values are reported in Table I. The boldfaced $p$-values
indicate the electrodes for which a linear model of the rates is a
statistically significant predictor for the corresponding distortion
(correlation) values (with a Bonferroni multiple hypothesis testing correction
level of significance of $p=0.05/12=0.0042$). Thus, in these cases, the
statistics suggest that a linear non-zero parameterized model on the rates
fits significantly better the correlation data than a fixed linear model.

Figure 3: The top plot shows the probability density functions of the
correlations values as a function of $\hat{R}_{3}$ for the target and
distractor. The corresponding mean correlation (”distortion”) values as a
function of $\hat{R}_{3}$ for both the target and distractor stimuli are shown
in the the bottom plot.

From Table I (top) it can be observed that significant $p$-values only occur
for $\hat{R}_{3}$. This demonstrates that in terms of linear regression, there
are information available from $\hat{R}_{3}$ which are not directly available
from $\hat{R}_{2}$. Moreover, it suggests a new linear relationship between
the amount of redundant information that is communicated from the acoustic
stimuli and to the brain and the corresponding cortical activity in terms of
neural tracking of the envelopes of the stimuli. Specifically, a greater
absolute correlation between the acoustic envelope of the stimuli and the
electrodes signals in the left and right temporal regions, yields on average a
greater amount of third-order common information. This is in line with what
one would expect from a rate-distortion perspective, i.e., a greater rate
would yield a smaller distortion (higher correlation). To further illustrate
this point, we have shown the mean absolute correlation (distortion) values as
a function of $\hat{R}_{3}$ in Fig. 3 (bottom). This is a global average over
all subjects and all trials and also over all electrodes in $\mathcal{LT}$ and
$\mathcal{RT}$. Due to variability across subjects and trials, the standard
deviation of the mean correlations is quite high; for the $\hat{R}_{3}$ values
$0.004,0.008,0.012,0.016,0.020$, the standard deviations are
$0.0445,0.0524,0.0686,0.0757,0.0798,$ and
$0.0435,0.0519,0.0637,0.0697,0.0674,$ for the target and distractor,
respectively.

It can be noticed that for the target stimuli, there is a linear trend
revealing that an increase in common information from the stimuli to the
electrodes leads to an increase in the correlation between the same stimuli
and electrodes. On the other hand, for the distractor, the correlation does
not appear to be linearly related to the common information. The probability
density functions for the target and distractor are very close to each other
and shown in Fig. 3 (top). The common information is mainly concentrated below
0.01 bits. For comparison, the mean $\hat{R}_{2}$ over all subjects and trials
for the target and distractor are 0.0639 and 0.0645 bits, respectively.

In Table I (bottom), we have shown the $p$-values when fitting a linear model
to the _average_ higher-order common information given by (38) and the
correlations. Again, it shows that the average $\bar{R}_{3}$ is also a
significant predictor for the corresponding correlations.

TABLE I: $p$-values when fitting a linear regression model to the correlation
and the lower bounds ($\hat{R}_{2}$ and $\hat{R}_{3}$) and the averages
($\bar{R}_{2}$ and $\bar{R}_{3}$). Boldfaced $p$-values are significant under
Bonferroni multiple hypothesis testing correction: $0.05/12=0.0042$.

| $\hat{R}_{2}$ | $\hat{R}_{3}$
---|---|---
| $\mathrm{env}_{T}$ | $\mathrm{env}_{D}$ | $\mathrm{env}_{T}$ | $\mathrm{env}_{D}$
$\mathrm{FT}_{7}$ | 0.0085 | 0.4156 | 0.0000 | 0.1390
$\mathrm{T}_{7}$ | 0.0212 | 0.6032 | 0.0000 | 0.2893
$\mathrm{TP}_{7}$ | 0.1560 | 0.0571 | 0.0000 | 0.0012
$\mathrm{CP}_{5}$ | 0.0731 | 0.5446 | 0.0000 | 0.2164
$\mathrm{FC}_{5}$ | 0.0825 | 0.3164 | 0.0000 | 0.3376
$\mathrm{C}_{5}$ | 0.1160 | 0.2376 | 0.0000 | 0.1568
$\mathrm{FT}_{8}$ | 0.2292 | 0.9793 | 0.0000 | 0.1910
$\mathrm{T}_{8}$ | 0.0942 | 0.6319 | 0.0000 | 0.2334
$\mathrm{TP}_{8}$ | 0.0638 | 0.0745 | 0.0001 | 0.0454
$\mathrm{CP}_{6}$ | 0.0346 | 0.5685 | 0.0000 | 0.3380
$\mathrm{FC}_{6}$ | 0.1294 | 0.2671 | 0.0000 | 0.0172
$\mathrm{C}_{6}$ | 0.1191 | 0.5686 | 0.0000 | 0.1317

| $\bar{R}_{2}$ | $\bar{R}_{3}$
---|---|---
| $\mathrm{env}_{T}$ | $\mathrm{env}_{D}$ | $\mathrm{env}_{T}$ | $\mathrm{env}_{D}$
$\mathrm{FT}_{7}$ | 0.0003 | 0.1084 | 0.0000 | 0.0278
$\mathrm{T}_{7}$ | 0.0006 | 0.2424 | 0.0000 | 0.0923
$\mathrm{TP}_{7}$ | 0.0747 | 0.0141 | 0.0000 | 0.0000
$\mathrm{CP}_{5}$ | 0.0084 | 0.2619 | 0.0000 | 0.0141
$\mathrm{FC}_{5}$ | 0.0076 | 0.0980 | 0.0000 | 0.0493
$\mathrm{C}_{5}$ | 0.0118 | 0.1090 | 0.0000 | 0.0163
$\mathrm{FT}_{8}$ | 0.1119 | 0.4529 | 0.0000 | 0.0264
$\mathrm{T}_{8}$ | 0.0793 | 0.2299 | 0.0000 | 0.0383
$\mathrm{TP}_{8}$ | 0.1836 | 0.0345 | 0.0000 | 0.0051
$\mathrm{CP}_{6}$ | 0.0110 | 0.2723 | 0.0000 | 0.0206
$\mathrm{FC}_{6}$ | 0.0502 | 0.0268 | 0.0000 | 0.0008
$\mathrm{C}_{6}$ | 0.0563 | 0.1232 | 0.0000 | 0.0143

##  VIII Limitations

We established lower bounds on the higher-order common information that is
shared between $n\geq 2$ signals. These lower bounds are not always tight and
they can therefore not in general be used to quantify the exact amount of
common information (an exception was our discrete source example, where
$\hat{R}_{3}=R_{3}$). Nevertheless, the proof presented is constructive in the
sense that it demonstrates how to construct sufficient common information
variables that achieves the lower bounds.

The practical method proposed to find the common information in general data
has two short comings. First, it requires the use of existing mutual
information estimators. For high dimensional data, it is well-known that such
estimators suffers from biases and the need of a substantial amount of
observations to guarantee a good estimation accuracy. Any bias or error in the
estimation of the mutual information will directly translate into an error in
the estimate of the common information. We therefore suggests to use the same
estimator when computing $R_{\ell}$ for all $\ell$. This will remove the
relative effect of bias, since then all $R_{\ell}$ suffers from similar
biases. Second, the proposed method involves numerically solving an
optimization problem, which could be computational expensive depending upon
the desired accuracy. The simulation study provided in this paper, used a
bisection technique to find the proper amount of noise to be used when forming
the sufficient information. On average, 4 – 5 iterations in the bisection
search was needed to find the estimate of the noise variance.

##  IX Conclusions

We introduced a new concept of higher-order common information and derived
computable lower bounds. Our results made it possible to bound the amount of
information that $n\geq 2$ random variables (or time series) have in common.
We furthermore presented a practical method to quantify the bounds in
arbitrary data, which lead to a new tool to reveal inherent dependencies in
real-world data. We applied it on EEG data and demonstrated that contrary to
the second-order common information, the third-order common information were
descriptive with respect to the correlations between the envelope of an
acoustic signal and EEG signals captured by electrodes spatially located in
the left and right temporal regions of the scalp.

## References

  * [1] T. Cover and J. Thomas, Elements of Information Theory.  Wiley-Interscience, 2006.
  * [2] A. Wyner, “The common information of two dependent random variables,” IEEE Transactions on Information Theory, vol. 21, no. 2, pp. 163–179, 1975.
  * [3] P. Gacs and J. Korner, “Common information is much less than mutual information,” Problems of control and information theory, vol. 2, pp. 149–162, 1973.
  * [4] H. Witsenhausen, “On sequences of pairs of dependent random variables,” SIAM J. appl. math, vol. 28, pp. 100 – 113, 1975.
  * [5] G. Xu, W. Liu, and B. Chen, “Wyner’s common information for continuous random variables - a lossy source coding interpretation,” Annual Conference on Information Sciences and Systems, 2011.
  * [6] P. L. Williams and R. D. Beer, “Nonnegative decomposition of multivariate information,” CoRR, vol. abs/1004.2515, 2010.
  * [7] M. Harder, C. Salge, and D. Polani, “Bivariate measure of redundant information,” Physical Review E, vol. 87, no. 1, 2013.
  * [8] R. A. A. Ince, “Measuring multivariate redundant information with pointwise common change in surprisal,” Entropy, vol. 19, no. 7, 2017.
  * [9] J. Østergaard, “Directed redundancy in time series,” IEEE International Symposium on Information Theory, 2024.
  * [10] N. Bertschinger, J. Rauh, E. Olbrich, J. Jost, and N. Ay, “Quantifying unique information,” Entropy, vol. 16, p. 2161–2183, 2014.
  * [11] R. G. James and J. P. Crutchfield., “Multivariate dependence beyond shannon information,” Entropy, 2017.
  * [12] A. J. Gutknecht, M. Wibral, and A. Makkeh, “Bits and pieces: Understanding information decomposition from part-whole relationships and formal logic,” Proceedings of the Royal Society A, vol. 477, 2021.
  * [13] F. Fano, Transmission of information: statistical theory of communication.  MIT Press, Cambridge, 1961.
  * [14] W. J. McGill, “Multivariate information transmission,” Psychometrika, vol. 19, 1954.
  * [15] R. Yeung, “A first course in information theory,” Springer, 2002.
  * [16] S. A. Fuglsang, T. Dau, and J. Hjortkjær, “Noise-robust cortical tracking of attended speech in real-life environments,” NeuroImage, vol. 156, pp. 435 – 444, 2017.
  * [17] C. Lorenzi and B. Moore, “Role of temporal envelope and fine structure cues in speech perception: A review,” Proceedings of the International Symposium on Auditory and Audiological Research, 2007.
  * [18] N. Mesgarani and E. F. Chang, “Selective cortical representation of attended speaker in multi-talker speech perception,” Nature, vol. 485, no. 7397, pp. 233–236, 2012.
  * [19] N. Ding, M. Chatterjee, and J. Z. Simon, “Robust cortical entrainment to the speech envelope relies on the spectro-temporal fine structure,” NeuroImage, vol. 88, pp. 41–46, 2014.
  * [20] E. Niedermeyer and F. L. da Silva, Electroencephalography: Basic Principles, Clinical Applications, and Related Fields.  Lippincott Williams & Wilkins, 2004.
  * [21] M. Lindner, R. Vicente, V. Priesemann, and M. Wibral, “Trentool: a matlab open source toolbox to analyse information flow in time series data with transfer entropy,” BMC Neurosci., vol. 12, p. 119, 2011.

###  -A Proof of Lemma 1

We first consider $I(X_{i};X_{j}|X_{k})$, which can be written as:

$\displaystyle I(X_{i};X_{j}|X_{k})$
$\displaystyle=h(X_{i}|X_{j})-h(X_{i}|X_{j},X_{k}).$ (45)

The latter conditional entropy can be written as:

$\displaystyle h(X_{i}|X_{j},X_{k})=h(X+N_{i}|X+N_{j},X+N_{k})$
$\displaystyle=h(X+N_{i}-\beta(2X+N_{j}+N_{k})|X+N_{j},X+N_{k})$
$\displaystyle=h(X(1-2\beta)+N_{1}-\beta(N_{2}+N_{3}))$ (46)
$\displaystyle=h(\mathcal{N}(0,\sigma_{X}^{2}(1-2\beta)^{2}+\sigma_{N}^{2}+\beta^{2}\sigma_{N}^{2}+\beta^{2}\sigma_{N}^{2}$
$\displaystyle\quad-4\beta\rho\sigma_{N}^{2}+2\beta^{2}\rho\sigma_{N}^{2}))$
(47) $\displaystyle=\frac{1}{2}\log_{2}\bigg{(}2\pi
e\frac{(3\sigma_{X}^{2}+(1+2\rho)\sigma_{N}^{2})(1-\rho)\sigma_{N}^{2}}{2\sigma_{X}^{2}+(1+\rho)\sigma_{N}^{2}}\bigg{)},$
(48)

where the conditioning can be removed since the error due to MMSE estimation
is independent of $X_{i}$, and $\beta$ is the coefficient of the best minimum
mean square error (MMSE) estimator given $X_{2}$ and $X_{3}$, i.e.:

$\displaystyle\beta=\frac{\sigma_{X}^{2}+\rho\sigma_{N}^{2}}{2\sigma_{X}^{2}+(1+\rho)\sigma_{N}^{2}}.$
(49)

We proceed with $h(X_{i}|X_{j})$, which can be written as:

$\displaystyle h(X_{i}|X_{j})=h(X+N_{i}-\alpha(X+N_{j}))$ (50)
$\displaystyle=h(X(1-\alpha)+N_{i}-\alpha N_{j})$ (51)
$\displaystyle=h(\mathcal{N}(0,\sigma_{X}^{2}(1-\alpha)^{2}+\sigma_{N}^{2}+\alpha^{2}\sigma_{N}^{2}-2\alpha\rho\sigma_{N}^{2}))$
(52) $\displaystyle=\frac{1}{2}\log_{2}\bigg{(}2\pi
e\frac{(1-\rho)((1+\rho)\sigma_{N}^{2}+2\sigma_{X}^{2})\sigma_{N}^{2}}{\sigma_{X}^{2}+\sigma_{N}^{2}}\bigg{)},$
(53)

where

$\displaystyle\alpha=\frac{\sigma_{X}^{2}+\rho\sigma_{N}^{2}}{\sigma_{X}^{2}+\sigma_{N}^{2}}.$
(54)

Combining the above yields:

$\displaystyle I(X_{i};X_{j}|X_{k})$
$\displaystyle=\frac{1}{2}\log_{2}\bigg{(}\frac{((1+\rho)\sigma_{N}^{2}+2\sigma_{X}^{2})^{2}}{(\sigma_{X}^{2}+\sigma_{N}^{2})((1+2\rho)\sigma_{N}^{2}+3\sigma_{X}^{2})}\bigg{)}.$
(55)

Using the same procedure as above, we obtain:

$\displaystyle I(X_{i};X_{j})=h(X_{i})-h(X_{i}|X_{j})=h(X_{i})-h(X_{i}-\alpha
X_{j}|X_{j})$ $\displaystyle=h(X_{i})-h((1-\alpha)X+N_{i}-\alpha N_{j})$
$\displaystyle=h(\mathcal{N}(0,\sigma_{X}^{2}+\sigma_{N}^{2}))$
$\displaystyle\quad-h(\mathcal{N}(0,(1-\alpha)^{2}\sigma_{X}^{2}+\sigma_{N}^{2}+\alpha^{2}\sigma_{N}^{2}-2\alpha\rho\sigma_{N}^{2}))$
(56)
$\displaystyle=\frac{1}{2}\log_{2}\bigg{(}\frac{(\sigma_{X}^{2}+\sigma_{N}^{2})^{2}}{(1-\rho)\sigma_{N}^{2}((1+\rho)\sigma_{N}^{2}+2\sigma_{X}^{2})}\bigg{)}.$
(57)

$\hfill\square$

###  -B Proof of Theorem 1

The set $\mathcal{T}_{2}$ contains the minimal SCI
$\phi_{i,j}\in\mathcal{T}_{2}$ of $X_{i}$ with respect to $X_{j}$. From (14)
it follows that we have equality $I(X_{j};\phi_{i,j})=I(X_{i};X_{j})$ for all
$i\neq j$. We do therefore not introduce more information in $\phi_{i,j}$
about $X_{j}$ than what is already in $X_{i}$. Thus, the minimal SCI
$\phi_{i,j}$ and $\phi_{j,i}$ do not contain more information about each other
than that contained in $X_{i}$ and $X_{j}$, i.e., $I(X_{i};X_{j})\geq
I(\phi_{i,j};\phi_{j,i})$.

The constraint (15) guarantees that $I(X_{i};X_{k})\geq I(\phi_{i,j};X_{k})$
and $I(X_{j};X_{k})\geq I(\phi_{j,i};X_{k})$. We do therefore not introduce
additional information into $\phi_{i,j}$ about $X_{k}$ than what is already in
$X_{i}$. Thus, the elements in $\mathcal{T}_{2}$ have no more information in
common than what the elements of $\mathcal{T}_{1}=\mathcal{X}$ have in common.
We have thus established the following chain of inequalities:

$\displaystyle R_{2}$
$\displaystyle\geq\min_{\phi,\phi^{\prime}\in\mathcal{T}_{1}}I(\phi;\phi^{\prime})$
(58) $\displaystyle\geq\min_{\begin{subarray}{c}\phi\in\mathcal{T}_{2}\\\
\phi^{\prime}\in\mathcal{T}_{1}\end{subarray}}I(\phi;\phi^{\prime})=\min_{\begin{subarray}{c}\phi\in\mathcal{T}_{2}^{u}\\\
\phi^{\prime}\in\mathcal{T}_{1}\end{subarray}}I(\phi;\phi^{\prime})\geq\min_{\phi,\phi^{\prime}\in\mathcal{T}_{2}}I(\phi;\phi^{\prime}).$
(59)

At this point, we can reiterate the above arguments for
$\mathcal{T}_{3},\dotsc,\mathcal{T}_{\ell}$ and thereby prove that:

$\displaystyle\min_{\begin{subarray}{c}\phi\in\mathcal{T}_{\ell-1}^{u}\\\
\phi^{\prime}\in\mathcal{T}_{1}\end{subarray}}I(\phi;\phi^{\prime})\geq\min_{\begin{subarray}{c}\phi\in\mathcal{T}_{\ell}^{u}\\\
\phi^{\prime}\in\mathcal{T}_{1}\end{subarray}}I(\phi;\phi^{\prime}).$ (60)

We now prove the bound on $R_{\ell}$. Let $\phi_{i,j}\in\mathcal{T}_{2}$ be a
SCI for $X_{i}$ with respect to $X_{j}$. Then
$I(\phi_{i,j};X_{i})=I(X_{j};X_{i})$ and $\phi_{i,j}$ contains as much
information about $X_{j}$ as $X_{i}$ does. Since no additional information
about $X_{k}$ is introduced into $\phi_{i,j}$ than what is already in $X_{i}$
or $X_{j}$, it follows that $I(\phi_{i,j};X_{k})$ lower bounds the common
information in $X_{i},X_{j}$, and $X_{k}$. Thus, it must be that:

$\displaystyle R_{3}\geq\min_{\begin{subarray}{c}\phi\in\mathcal{T}_{2}\\\
\phi^{\prime}\in\mathcal{T}_{1}\end{subarray}}I(\phi;\phi^{\prime}).$ (61)

At this point, we let $\phi_{i,j,k}\in\mathcal{T}_{3}$ denote a minimal SCI
for $\phi_{i,j}\in\mathcal{T}_{2}$ with respect to $X_{k}\in\mathcal{T}_{1}$.
Again, it must be that $I(\phi_{i,j,k};X_{m})$ lower bounds the common
information in $X_{i},X_{j},X_{k}$, and $X_{m}$. Repeatedly applying this
argument proves that:

$\displaystyle
R_{\ell}\geq\min_{\begin{subarray}{c}\phi\in\mathcal{T}_{\ell-1}\\\
\phi^{\prime}\in\mathcal{T}_{1}\end{subarray}}I(\phi;\phi^{\prime})=\min_{\begin{subarray}{c}\phi\in\mathcal{T}_{\ell-1}^{u}\\\
\phi^{\prime}\in\mathcal{T}_{1}\end{subarray}}I(\phi;\phi^{\prime}).$ (62)

This proves the theorem.$\hfill\square$

###  -C Proof of Theorem 2

Let $T^{\prime}_{ij}=\mathbb{E}[X_{j}|X_{i}]=\alpha X_{i}$ be a sufficient
statistic for $X_{i}$ wrt. $X_{j}$, where
$\alpha=\frac{\sigma_{X}^{2}+\rho\sigma_{X}^{2}}{\sigma_{X}^{2}+\sigma_{N}^{2}}.$
Let $\epsilon_{j}$ be the error due to minimum MMSE estimation of $X_{j}$
using $T^{\prime}_{ij}$:

$\displaystyle\epsilon_{j}\triangleq
X_{j}-T^{\prime}_{ij}=X(1-\alpha)+N_{j}-\alpha N_{i},$ (63)

which has variance:

$\displaystyle\sigma_{\epsilon_{j}}^{2}$
$\displaystyle=\sigma_{X}^{2}(1-\alpha)^{2}+\sigma_{N}^{2}(1+\alpha^{2}-2\alpha\rho)$
(64)
$\displaystyle=\frac{(1-\rho)\sigma_{N}^{2}(\sigma_{X}^{2}+\sigma_{N}^{2})((1+\rho)\sigma_{N}^{2}+2\sigma_{X}^{2})}{(\rho\sigma_{N}^{2}+\sigma_{X}^{2})^{2}}$
(65) $\displaystyle=\frac{\Delta\Delta_{1}}{\Delta_{\rho}^{2}}.$ (66)

From (63), we rewrite $T^{\prime}_{ij}$ as
$T^{\prime}_{ij}=X_{j}-\epsilon_{j}$, where $\epsilon_{j}$ is independent of
$X_{j}$ due to the properties of minimum MSE estimation errors of Gaussian
sources [1].

Since $T^{\prime}_{ij}$ is a non-zero deterministic function of $X_{i}$, the
mutual information $I(X_{i};T^{\prime}_{ij})=\infty$, which shows that
$T^{\prime}_{ij}$ is not a _minimal_ sufficient statistic for $X_{i}$, and it
also not a minimal SCI. To circumvent this, our idea is to replace
$T^{\prime}_{ij}$ by another random variable $T_{ij}=X_{j}+Z_{j}$, where
$Z_{j}$ has the same marginal distribution as $\epsilon_{j}$ but is
independent of all other variables. Specifically, let
$Z_{j}\sim\mathcal{N}(0,\sigma_{\epsilon_{j}}^{2})$ be independent of
$\epsilon_{j},X_{i},X_{j},$ and $X_{k}$, and define:

$\displaystyle T_{ij}\triangleq X_{j}+Z_{j}.$ (67)

We note that $T_{ij}$ is not (necessarily) a sufficient statistic for $X_{i}$
wrt. $X_{j}$ but it is a SCI as we will show in the sequel.

It can be verified that $I(X_{i};T_{ij})$ is bounded:

$\displaystyle I(X_{i};T_{ij})=I(X_{j}+Z_{j};X_{i})=I(X+N_{j}+Z_{j};X+N_{i})$
(68) $\displaystyle=h(X+N_{j}+Z_{j})-h(X+N_{j}+Z_{j}|X+N_{i})$
$\displaystyle=h(X+N_{j}+Z_{j})-h(X(1-\alpha)+N_{j}+Z_{j}-\alpha N_{i})$
$\displaystyle=h(\mathcal{N}(0,\sigma_{X}^{2}+\sigma_{N}^{2}+\sigma_{Z_{j}}^{2}))$
$\displaystyle\quad-h(\mathcal{N}(0,(1-\alpha)^{2}\sigma_{X}^{2}+\sigma_{N}^{2}+\sigma_{Z_{j}}^{2}+\alpha^{2}\sigma_{N}^{2}-2\alpha\rho\sigma_{N}^{2})$
(69)
$\displaystyle=R_{2}+\frac{1}{2}\log_{2}\\!\bigg{(}\\!\frac{(\sigma_{X}^{2}+\sigma_{N}^{2})^{2}}{(1+\rho^{2})\sigma_{N}^{4}+2(1+\rho)\sigma_{X}^{2}\sigma_{N}^{2}+2\sigma_{X}^{4}}\\!\bigg{)}$
(70)
$\displaystyle=R_{2}+\frac{1}{2}\log_{2}\bigg{(}\frac{\Delta^{2}}{\Delta_{2}}\bigg{)},$
(71)

To verify that the equality requirement in (14) is satisfied we need to show
that $I(T_{ij};X_{j})=I(X_{i};X_{j})$ as we do below:

$\displaystyle I(X_{j};T_{ij})$
$\displaystyle=I(X_{j}+Z_{j};X_{j})=I(X+N_{j}+Z_{j};X+N_{j})$
$\displaystyle=h(X_{j}+Z_{j})-h(X_{j}+Z_{j}|X_{j})$
$\displaystyle=h(X_{j}+Z_{j})-h(Z_{j}|X_{j})$ (72)
$\displaystyle=h(X_{j}+Z_{j})-h(Z_{j})$ (73)
$\displaystyle=\frac{1}{2}\log_{2}\bigg{(}\frac{\sigma_{X}^{2}+\sigma_{N}^{2}+\sigma_{Z_{j}}^{2}}{\sigma_{Z_{j}}^{2}}\bigg{)}$
(74)
$\displaystyle=\frac{1}{2}\log_{2}\bigg{(}\frac{\Delta^{2}}{\Delta_{1}}\bigg{)},$
(75)

which is equal to (6) as had to be shown. The last equality was obtained by
inserting $\sigma_{Z_{j}}^{2}=\sigma_{\epsilon_{j}}^{2}$ (64).

We have yet to verify that the inequality constraint in (15) is also
satisfied. To see this, notice that
$I(T_{ij};X_{k})=I(X+N_{j}+Z_{j};X+N_{k})=I(T_{ij};X_{i})$, where the last
equality can be seen from (68), since $(X_{i},X_{j})$ and $(X_{j},X_{k})$ have
identical joint distributions. On the other hand, we have that
$I(X_{i};X_{k})=R_{2}$ as given by (6). Thus, in order to show that
$I(X_{i};X_{k})\geq I(T_{ij};X_{k})$, it is sufficient to show that the second
term in (71) is non-positive. This is the case if $\Delta^{2}\leq\Delta_{2}$.
To show this, we note that
$\frac{\partial^{2}}{\partial\rho^{2}}\Delta_{2}=2\sigma_{N}^{4}>0$, which
implies that $\Delta_{2}$ is convex in $\rho$ and that its minimum is achieved
at $\frac{\partial}{\partial\rho}\Delta_{2}=0$. It can readily be seen that
the minimum occurs at $\rho=-\sigma_{X}^{2}/\sigma_{N}^{2}$, and which when
inserted into $\Delta_{2}$ gives
$\Delta_{2}=(\sigma_{X}^{2}+\sigma_{N}^{2})^{2}$. This proves that $T_{ij}$
satisfies the conditions of being a minimal SCI for $X_{i}$ wrt. $X_{j}$, and
that $I(X_{i};T_{ij})$ is the minimum over all relevant $i,j,k$.

The final step of the proof is to establish a lower bound on $R_{4}$. Towards
that end, we seek to form a SCI, say $T_{ijk}$, such that
$I(T_{ijk};X_{k})<I(T_{ij};X_{k}),I(T_{ijk};X_{m})\leq I(X_{k};X_{m})$ and
such that $R_{4}\geq I(T_{ijk};X_{k})$.

We begin by constructing the sufficient statistic $T^{\prime}_{ijk}$ for
$X_{k}$ wrt. $T_{ij}$, that is:

$\displaystyle T^{\prime}_{ijk}$ $\displaystyle=\mathbb{E}[T_{ij}|X_{k}]=\beta
X_{k},\quad\beta=\frac{\sigma_{X}^{2}+\rho\sigma_{N}^{2}}{\sigma_{X}^{2}+\sigma_{N}^{2}}.$
(76)

The estimation error $\epsilon_{k}=T_{ij}-\beta X_{k}$ has variance
$\sigma_{\epsilon_{k}}^{2}=\frac{\Delta_{1}\Delta_{2}}{\Delta\Delta_{\rho}^{2}}$.
We form the new variable $T_{ijk}=T_{ij}+Z_{k}$, where
$Z_{k}\sim\mathcal{N}(0,\sigma_{\epsilon_{k}}^{2})$ is independent of all
other variables. We then clearly have that $I(T_{ijk};X_{k})<I(T_{ij};X_{k})$
since $T_{ijk}$ is a more noisy version of $T_{ij}$ and the noise $Z_{k}$ is
independent of $X_{k}$. Similarly, it must be that $I(T_{ijk};X_{m})\leq
I(X_{k};X_{m})$ since $I(T_{ij};X_{m})\leq I(X_{k};X_{m})$.

We will now compute the mutual (common) information between $X_{k}$ and
$T_{ijk}$:

$\displaystyle I(T_{ijk};X_{k})$
$\displaystyle=I(X+N_{j}+Z_{j}+Z_{k};X+N_{k})$ (77)
$\displaystyle=h(X+N_{j}+Z_{j}+Z_{k})$
$\displaystyle\quad-h(X+N_{j}+Z_{j}+Z_{k}|X+N_{k}),$ (78)

where the latter conditional entropy can be written as:

$\displaystyle h(X+N_{j}+Z_{j}+Z_{k}|X+N_{k})$
$\displaystyle=h(X+N_{j}+Z_{j}+Z_{k}-\beta(X+N_{k}))$
$\displaystyle=h(X(1-\beta)+N_{j}+Z_{j}+Z_{k}-\beta N_{k})$
$\displaystyle=h(\mathcal{N}(0,\sigma_{X}^{2}(1-\beta)^{2}+\sigma_{N}^{2}(1+\beta^{2}-2\beta\rho)+\sigma_{Z_{j}}^{2}+\sigma_{Z_{k}}^{2}))$
(79)
$\displaystyle=h(\mathcal{N}(0,2\frac{\Delta_{1}\Delta_{2}}{\Delta\Delta_{\rho}^{2}})).$
(80)

The unconditonal entropy in (78) can be written as:

$\displaystyle h(X+N_{j}+Z_{j}+Z_{k})$
$\displaystyle=h(\mathcal{N}(0,\sigma_{X}^{2}+\sigma_{N}^{2}+\sigma_{Z_{j}}^{2}+\sigma_{Z_{k}}^{2}))$
$\displaystyle=h(\mathcal{N}(0,\Delta+\frac{\Delta_{1}\Delta_{2}}{\Delta\Delta_{\rho}^{2}})).$
(81)

Thus, by combining (81) and (80), the mutual information in (78) can be
written as:

$\displaystyle I(T_{ijk};X_{k})$
$\displaystyle=\frac{1}{2}\log_{2}\bigg{(}\big{(}\Delta+\frac{\Delta_{1}\Delta_{2}}{\Delta^{3}}\big{)}\big{(}\frac{2\Delta_{1}\Delta_{2}}{\Delta^{3}}\big{)}^{-1}\bigg{)}$
(82)
$\displaystyle=\frac{1}{2}\log_{2}\bigg{(}\frac{\Delta^{4}}{\Delta_{1}\Delta_{2}}\bigg{)}\bigg{(}\frac{1}{2}+\frac{\Delta_{1}\Delta_{2}}{2\Delta^{4}}\bigg{)}$
(83)
$\displaystyle=R_{3}^{\mathrm{lower}}+\frac{1}{2}\log_{2}\bigg{(}\frac{1}{2}+\frac{\Delta_{1}\Delta_{2}}{2\Delta^{4}}\bigg{)}.$
(84)

To verify that $I(T_{ijk};X_{k})\leq I(T_{ijk};X_{m})$, we rewrite
$I(T_{ijk};X_{m})$ as follows:

$\displaystyle I(T_{ijk};X_{m})$
$\displaystyle=h(T_{ijk})-h(T_{ijk}|X+N_{m}),$ (85)

which is identical to (77) since $(N_{k},N_{k})$ and $(N_{m},N_{j})$ have the
same joint distributions. This can also be concluded for $I(T_{ijk};X_{i})$.
We then only need to check $I(T_{ijk};X_{j})$.

$\displaystyle I(X_{j}+Z_{j}+Z_{k};X+N_{j})=h(X+N_{j}+Z_{j}+Z_{k})$
$\displaystyle\quad-h(X+N_{j}+Z_{j}+Z_{k}|X+N_{j}),$ (86)

where the latter conditional entropy can be written as:

$\displaystyle h(X+N_{j}+Z_{j}+Z_{k}|X+N_{j})=h(Z_{j}+Z_{k}|X+N_{j})$
$\displaystyle=h(Z_{j}+Z_{k}),$ (87)

which implies that

$\displaystyle I(T_{ijk};X_{j})$
$\displaystyle=\frac{1}{2}\log_{2}\bigg{(}\frac{\sigma_{X}^{2}+\sigma_{N}^{2}+\sigma_{Z_{j}}^{2}+\sigma_{Z_{k}}^{2}}{\sigma_{Z_{j}}^{2}+\sigma_{Z_{k}}^{2}}\bigg{)}.$
(88)

The ratio of $I(T_{ijk};X_{k})$ and $I(T_{ijk};X_{j})$ can be reduced to:

$\displaystyle\frac{I(T_{ijk};X_{k})}{I(T_{ijk};X_{j})}$
$\displaystyle=\frac{(\rho^{2}+2)\sigma_{N}^{4}+2(\rho+2)\sigma_{X}^{2}\sigma_{N}^{2}+3\sigma_{X}^{4}}{(2\rho^{2}+2)\sigma_{N}^{4}+4(\rho+1)\sigma_{N}^{2}\sigma_{X}^{2}+4\sigma_{X}^{4}}.$
(89)

The difference of the terms in the ratio can be rewritten as:

$\displaystyle(2\rho^{2}+2)\sigma_{N}^{4}+4(\rho+1)\sigma_{N}^{2}\sigma_{X}^{2}+4\sigma_{X}^{4}$
$\displaystyle\quad-((\rho^{2}+2)\sigma_{N}^{4}+2(\rho+2)\sigma_{X}^{2}\sigma_{N}^{2}+3\sigma_{X}^{4})=\Delta_{\rho}^{2}>0.$
(90)

Since the difference is positive, it implies that the ratio (89) is always
less than 1, which proves that $I(T_{ijk};X_{k})<I(T_{ijk};X_{j})$ as was to
be proved. It follows that $R_{4}$ is lower bounded by (84), which proves the
theorem. $\hfill\square$

###  -D Proof of Lemma 2

We first lower bound $R_{3}$ by (24), which implies that the gap is at most
$0.5\log_{2}\frac{\Delta^{2}}{\Delta_{2}}$. The partial derivatives of
$\frac{\Delta^{2}}{\Delta_{2}}$ wrt. $\sigma_{N}^{2}$ and $\rho$ are given by:

$\displaystyle\frac{\partial}{\partial\sigma_{N}^{2}}\frac{\Delta^{2}}{\Delta_{2}}$
$\displaystyle=\frac{2\Delta\Delta_{\rho}\sigma_{X}^{2}(1-\rho)}{\Delta_{2}^{2}},\quad\frac{\partial}{\partial\rho}\frac{\Delta^{2}}{\Delta_{2}}=-\frac{2\Delta^{2}\Delta_{\rho}\sigma_{N}^{2}}{\Delta_{2}^{2}},$
(91)

which have opposite signs determined by the sign of $\Delta_{\rho}$. If
$\rho\geq 0$, then $\Delta_{\rho}>0$, and the minimum of
$\frac{\Delta^{2}}{\Delta_{2}}$ is $\frac{1}{2}$, which is obtained either
when $\sigma_{N}^{2}\to 0$ or $\rho\to 1$ or both.

Let us now assume that $\rho<0$. If $\rho>-\sigma_{X}^{2}/\sigma_{N}^{2}$,
then $\frac{\partial}{\partial\sigma_{N}^{2}}\frac{\Delta^{2}}{\Delta_{2}}>0$.
Thus, $\frac{\Delta^{2}}{\Delta_{2}}$ is increasing in $\sigma_{N}^{2}$, and
the minimum is obtained by letting $\sigma_{N}^{2}\to 0$ for any
$\rho>-\sigma_{X}^{2}/\sigma_{N}^{2}$. Thus, we have the same situation as for
the case where $\rho\geq 0$. On the other hand, if
$\rho<-\sigma_{X}^{2}/\sigma_{N}^{2}$, the minimum is achieved for
$\sigma_{N}^{2}\to\infty$ in which case the minimum is $\frac{1}{2}$.
Similarly, for fixed $\sigma_{N}^{2}$, the minimum is achieved for $\rho\to-1$
in which case the minimum over $\rho$ is:

$\displaystyle\lim_{\rho\to-1}\frac{\Delta^{2}}{\Delta_{2}}=\frac{\Delta^{2}}{2(\sigma_{X}^{2}+\sigma_{N}^{2})}.$
(92)

It can be seen that the minimum of (92) over $\sigma_{X}^{2}$ and
$\sigma_{N}^{2}$ is $\frac{1}{2}$. Since
$-\frac{1}{2}\log_{2}(\frac{1}{2})=\frac{1}{2}$ bits, the lemma is proved.
$\hfill\square$

###  -E Proof of Theorem 3

Since the elements of $\mathcal{Z}$ are mutually independent it becomes
tractable to compute their information overlap, which is simply given by the
intersection of the tuples in question. Since any $\ell$ elements of
$\mathcal{X}$ has $n-\ell$ elements of $\mathcal{Z}$ in common, it readily
follows that the true amount of common information in any $\ell$ elements of
$\mathcal{X}$ is $(n-\ell)H(Z)$.

For convenience, we introduce at this point the binary notation
$X_{1}=(1111\cdots 110)$ to indicate that $X_{1}$ contains $Z_{1}$ to
$Z_{n-1}$ but does not contain $Z_{n}$. Similarly, $X_{2}=(1111\cdots 101)$
indicates that $X_{2}$ contains $Z_{1},\dotsc,Z_{n-2},Z_{n}$ but not
$Z_{n-1}$. The Hamming weights $\omega$ of $X_{1}$ and $X_{2}$ are the same
and given by $\omega(X_{1})=\omega(X_{2})=n-1$. Clearly, there exists
$\binom{n}{n-1}=n$ distinct binary strings of length $n$ that has $n-1$ ones
and one zero. Let $X_{1},\dotsc,X_{n}$ represents these $n$ distinct binary
strings. Let $\odot$ denote the bit-wise logical AND operator. It follows that
$X_{1}\odot X_{2}=(1111\cdots 100)$ and that the Hamming weight is
$\omega(X_{1}\odot X_{2})=n-2$. In fact, $\omega(X_{i}\odot X_{j})=n-2$ for
all $i\neq j$. With this notation, it can be seen that
$\mathcal{T}_{2}\equiv\\{X_{i}\odot X_{j}:i\neq j\\}.$ Consider now the two
distinct elements $\phi\in\mathcal{T}_{2}$ and
$\phi^{\prime}\in\mathcal{T}_{1}$. Clearly $\omega(\phi\odot\phi^{\prime})\leq
n-3$, since at least one zero in $\phi$ must be located at the position of a
one in $\phi^{\prime}$. Moreover, since $\phi$ contains two zeros and
$\phi^{\prime}$ one zero, the resulting string after performing the logical
AND operation can have at most three zeros. Thus,
$\omega(\phi\odot\phi^{\prime})\geq n-3$.

We are now in a position to prove the theorem for $\ell=2$ and $n>2$. It holds
that for any $\phi\in\mathcal{T}_{2}$, we have $\omega(\phi)=n-2$. Thus,
$\phi$ contains $n-2$ independent elements of $\mathcal{Z}$, which means that
$H(\phi)=(n-2)H(Z)$. Moreover, $\phi\in\mathcal{T}_{2}$ and
$\phi^{\prime}\in\mathcal{T}_{1}$ satisfy $\omega(\phi\odot\phi^{\prime})\geq
n-3$. Since $\phi$ and $\phi^{\prime}$ have at least $n-3$ elements in common,
the reduction in entropy of $\phi$ by knowing $\phi^{\prime}$ is at least
$(n-3)H(Z)$. Thus, $H(\phi|\phi^{\prime})\leq H(\phi)-(n-3)H(Z)$. It follows
that

$\displaystyle I(\phi;\phi^{\prime})$
$\displaystyle=H(\phi)-H(\phi|\phi^{\prime})$ (93) $\displaystyle\geq
H(\phi)-(H(\phi)-(n-3)H(Z))$ (94) $\displaystyle=(n-3)H(Z).$ (95)

We now generalize the above arguments to $\ell>2$. Let
$\phi\in\mathcal{T}_{\ell}$ have $k$ zeros and $n-k$ ones and recall that
$\phi^{\prime}\in\mathcal{T}_{1}$ has one zero and $n-1$ ones. Clearly,
$\omega(\phi\odot\phi^{\prime})\geq n-k-1$. Thus, in the worst case we obtain
a bit string with one more zero than the number of zeros in $\phi$. From this,
and since $\omega(\phi)=n-2$ for $\phi\in\mathcal{T}_{2}$ we deduce that for
any $\phi\in\mathcal{T}_{\ell}$ and $\phi^{\prime}\in\mathcal{T}_{1}$ it must
be that $\omega(\phi\odot\phi^{\prime})\geq n-\ell-1$. Thus, $\phi$ and
$\phi^{\prime}$ have at least $n-\ell-1$ elements in common, and the reduction
in entropy of $\phi$ by knowing $\phi^{\prime}$ is therefore at least
$H(\phi|\phi^{\prime})\geq H(\phi)-(n-\ell-1)H(Z)$. Inserting this into (95)
yields $I(\phi;\phi^{\prime})\geq(n-\ell)H(Z)$, since here
$\phi\in\mathcal{T}_{\ell-1}$ and $\phi\in\mathcal{T}_{1}$. $\hfill\square$