# Shared Information for a Markov Chain on a Tree††thanks: S. Bhattacharya and
P. Narayan are with the Department of Electrical and Computer Engineering and
the Institute for Systems Research, University of Maryland, College Park, MD
20742, USA. E-mail: {sagnikb<EMAIL_ADDRESS>This work was supported by the
U.S. National Science Foundation under Grants CCF $1910497$ and CCF $2310203$.
A version of this paper was presented in part at the 2022 IEEE International
Symposium on Information Theory [3].

Sagnik Bhattacharya and Prakash Narayan

###### Abstract

Shared information is a measure of mutual dependence among multiple jointly
distributed random variables with finite alphabets. For a Markov chain on a
tree with a given joint distribution, we give a new proof of an explicit
characterization of shared information. The Markov chain on a tree is shown to
possess a global Markov property based on graph separation; this property
plays a key role in our proofs. When the underlying joint distribution is not
known, we exploit the special form of this characterization to provide a
multiarmed bandit algorithm for estimating shared information, and analyze its
error performance.

###### Index Terms:

Global Markov property, Markov chain on a tree, multiarmed bandits, mutual
information, mutual information estimation, shared information.

##  I Introduction

Let $X_{1},\ldots,X_{m}$, $m\geq 2$ be random variables (rvs) with finite
alphabets $\mathcal{X}_{1},\ldots,\mathcal{X}_{m}$, respectively, and joint
probability mass function (pmf) $P_{X_{1}\cdots X_{m}}$. The _shared
information_ $\operatorname{SI}(X_{1},\ldots,X_{m})$ of the rvs
$X_{1},\ldots,X_{m}$ is a measure of mutual dependence among them; and for
$m=2$, $\operatorname{SI}(X_{1},X_{2})$ particularizes to mutual information
$\operatorname{I}(X_{1}\wedge X_{2})$. Consider $m$ terminals, with terminal
$i$ having privileged access to independent and identically distributed
(i.i.d.) repetitions of $X_{i}$, $i=1,\ldots,m$. Shared information
$\operatorname{SI}(X_{1},\ldots,X_{m})$ has the operational meaning of being
the largest rate of _shared common randomness_ that the $m$ terminals can
generate in a distributed manner upon cooperating among themselves by means of
interactive, publicly broadcast and noise-free communication111Our preferred
nomenclature of shared information is justified by its operational meaning..
Shared information measures the maximum rate of common randomness that is
(nearly) independent of the open communication used to generate it.

The (Kullback-Leibler) divergence-based expression for
$\operatorname{SI}(X_{1},\ldots,X_{m})$ was discovered in [21, Example 4],
where it was derived as an upper bound for a single-letter formula for the
“secret key capacity of a source model” with $m$ terminals, a concept defined
by the operational meaning above. The upper bound was shown to be tight for
$m=2$ and $3$. Subsequently, in a significant advance [8, 15, 9], tightness of
the upper bound was established for arbitrary $m$, thereby imbuing
$\operatorname{SI}(X_{1},\ldots,X_{m})$ with the operational significance of
being the mentioned maximum rate of shared secret common randomness. The
potential for shared information to serve as a natural measure of mutual
dependence of $m\geq 2$ rvs, in the manner of mutual information for $m=2$
rvs, was suggested in [34]; see also [35].

A comprehensive and consequential study of shared information, where it is
termed “multivariate mutual information” [11], examines the role of secret key
capacity as a measure of mutual dependence among multiple rvs and derives
important properties including structural features of an underlying
optimization along with connections to the theory of submodular functions.

In addition to constituting secret key capacity for a multiterminal source
model ([21, 8, 15]), shared information also affords operational meaning for:
maximal packing of edge-disjoint spanning trees in a multigraph ([37, 36]; see
also [10, 19], [11] for variant models); optimum querying exponent for
resolving common randomness [42]; strong converse for multiterminal secret key
capacity [42, 43]; and also undirected network coding [9], data clustering
[14], among others.

As argued in [11], shared information also possesses several attributes of
measures of dependence among $m\geq 2$ rvs proposed earlier, including
Watanabe’s total correlation [45] and Han’s dual total correlation [26] (both
mentioned in Section II). For $m=2$ rvs, measures of common information due to
Gács-Körner [23], Wyner [46] and Tyagi [41] have operational meanings;
extensions to $m>2$ rvs merit further study (an exception [32] treats Wyner’s
common information).

For a given joint pmf $P_{X_{1}\cdots X_{m}}$ of the rvs $X_{1},\ldots,X_{m}$,
an explicit characterization of $\operatorname{SI}(X_{1},\ldots,X_{m})$ can be
challenging (see Definition 1 below); exact formulas are available for special
cases (cf. e.g., [21], [37], [11]). An efficient algorithm for calculating
$\operatorname{SI}(X_{1},\ldots,X_{m})$ is given in [11].

Our focus in this paper is on a Markov chain on a tree (MCT) [24]. Tree-
structured probabilistic graphical models are appealing owing to desirable
statistical properties that enable, for instance, efficient algorithms for
exact inference [28], [39]; decoding [33], [28]; sampling [22]; and structure
learning [16]. An MCT can serve as a tractable tree-structured approximation
to a given joint distribution arising in applications such as omniscience and
secrecy generation [21, 13], and signal clustering [12]. The mentioned
tractability facilitates exact calculation of associated rate quantities. We
take the tree structure of our model to be known; algorithms exist already for
learning tree structure from data samples [16, 17]. We exploit the special
form of $P_{X_{1}\cdots X_{m}}$ in the setting of an MCT to obtain a simple
characterization of shared information. When the joint pmf $P_{X_{1}\cdots
X_{m}}$ is not known but the tree structure is, the said characterization
facilitates an estimation of shared information.

In the setting of an MCT [24], our contributions are three-fold. First, we
derive an explicit characterization of shared information for an MCT with a
given joint pmf $P_{X_{1}\cdots X_{m}}$ by means of a direct approach that
exploits tree structure and Markovity of the pmf. A characterization of shared
information had been sketched already in [21]; our new proof does not seek
recourse to a secret key interpretation of shared information, unlike in [21].
Also, our proof differs in a material way from that in prior work [14] with a
similar objective.

Second, we show an equivalence between the (weaker) original definition of an
MCT [24] and a (stronger) global one based on separation in a graph [31,
Section 3.2.1]. When $P_{X_{1},\cdots,X_{m}}$ is assumed to be strictly
positive, the two definitions are equivalent by the Hammersley-Clifford
Theorem [31, Theorem 3.9]. We prove this equivalence even without said
assumption, taking advantage of the underlying tree structure of the MCT; our
proof method potentially is of independent interest.

Third, when $P_{X_{1}\cdots X_{m}}$ is not known, with the mentioned
characterization serving as a linchpin, we provide an approach for estimating
shared information for an MCT. Formulated as a correlated bandits problem [6],
this approach seeks to identify the best arm-pair across which mutual
information is minimal. Using a uniform sampling of arms, redolent of sampling
mechanisms in [5], we provide an upper bound for the probability of estimation
error and associated sample complexity. Our uniform sampling algorithm is
similar to that in [47], [6]; however, our modified analysis takes into
account estimator bias, a feature that is not common in known bandit
algorithms. Also, this approach can accommodate more refined bandit algorithms
as also alternatives to the probability of error criterion such as regret [7].

Section II contains the preliminaries. Useful properties of an MCT are
elucidated in Section III. An explicit characterization of shared information
for an MCT with a given $P_{X_{1}\cdots X_{m}}$ is provided in Section IV.
Section V describes our approach for estimating shared information when
$P_{X_{1}\cdots X_{m}}$ is not known. Section VI contains closing remarks.

##  II Preliminaries

Let $X_{1},\ldots,X_{m}$, $m\geq 2$, be rvs with finite alphabets
$\mathcal{X}_{1},\ldots,\mathcal{X}_{m}$, respectively, and joint pmf
$P_{X_{1}\cdots X_{m}}$. For
$A\subseteq\mathcal{M}=\left\\{{1,\ldots,m}\right\\}$, we write
$X_{A}=(X_{i},i\in A)$ with alphabet $\mathcal{X}_{A}=\prod_{i\in
A}\mathcal{X}_{i}$. Let $\pi=(\pi_{1},\ldots,\pi_{k})$ denote a $k$-partition
of $\mathcal{M}$, $2\leq k\leq m$. All logarithms and exponentiations are with
respect to the base $2$, except $\ln$ and $\exp$ that are with respect to the
base $e$.

######  Definition 1 (Shared information).

The _shared information_ of $X_{1},\ldots,X_{m}$ is defined as

$\displaystyle\operatorname{SI}(X_{\mathcal{M}})$ $\displaystyle=\min_{2\leq
k\leq m}\ \min_{\pi=(\pi_{u},u=1,\cdots,k)}\
\frac{1}{k-1}D(P_{X_{\mathcal{M}}}\;\|\;\prod_{u=1}^{k}P_{X_{\pi_{u}}})$
$\displaystyle=\min_{2\leq k\leq m}\ \min_{\pi=(\pi_{u},u=1,\cdots,k)}\
\frac{1}{k-1}\left[{\sum_{u=1}^{k}\operatorname{H}(X_{\pi_{u}})-\operatorname{H}(X_{\mathcal{M}})}\right].$
(1)

For a partition $\pi$ of $\mathcal{M}$ with $2\leq\left|{\pi}\right|\leq m$
atoms, it will be convenient to denote

$\displaystyle\operatorname{\mathcal{I}\,}(\pi)=\frac{1}{\left|{\pi}\right|-1}D(P_{X_{\mathcal{M}}}\;\|\;\prod_{u=1}^{\left|{\pi}\right|}P_{X_{\pi_{u}}})$
(2)

so that $\operatorname{SI}(X_{\mathcal{M}})=\min_{2\leq\left|{\pi}\right|\leq
m}\operatorname{\mathcal{I}\,}(\pi)$.

######  Example 1.

For $\mathcal{M}=\left\\{{1,2}\right\\}$, we have

$\displaystyle\operatorname{SI}(X_{1},X_{2})=\text{mutual information
}\operatorname{I}(X_{1}\wedge X_{2})$

and for $\mathcal{M}=\left\\{{1,2,3}\right\\}$, it is checked readily that
$\operatorname{SI}(X_{1},X_{2},X_{3})$ is the minimum of
$\operatorname{I}(X_{1}\wedge X_{2},X_{3})$, $\operatorname{I}(X_{2}\wedge
X_{1},X_{3})$, $\operatorname{I}(X_{3}\wedge X_{1},X_{2})$ and

$\displaystyle\frac{1}{2}\left[{\operatorname{H}(X_{1})+\operatorname{H}(X_{2})+\operatorname{H}(X_{3})-\operatorname{H}(X_{1},X_{2},X_{3})}\right],$

and can be inferred from [21, Examples 3,4].

When $X_{1},\ldots,X_{m}$ form a Markov chain
$X_{1}-\\!\\!\circ\\!\\!-\ldots-\\!\\!\circ\\!\\!-X_{m}$, it is seen that
$\operatorname{SI}(X_{\mathcal{M}})=\min_{1\leq i\leq
m-1}\operatorname{I}(X_{i}\wedge X_{i+1})$, the minimum mutual information
between a pair of adjacent rvs in the chain [21].

Shared information possesses several properties befitting a measure of mutual
dependence among multiple rvs. Clearly $\operatorname{SI}(X_{\mathcal{M}})\geq
0$ and equality holds iff $P_{X_{\mathcal{M}}}=P_{X_{A}}P_{X_{A^{c}}}$ for
some $A\subsetneq\mathcal{M}$; the latter follows from [21, Theorem 5] and
[8], [15], [9]. When $X_{1},\ldots,X_{m}$ are bijections of each other, i.e.,
$\operatorname{H}(X_{i}\,|\,X_{j})=0$, $1\leq i\neq j\leq m$, then
$\operatorname{SI}(X_{\mathcal{M}})=\operatorname{H}(X_{1})$, as expected
[11].

Next, the secret key capacity interpretation of
$\operatorname{SI}(X_{\mathcal{M}})$ [21, 8, 15, 9, 35] implies that upon
grouping the rvs $X_{1},\ldots,X_{m}$ into disjoint teams represented by the
atoms of any $k$-partition $\pi=(\pi_{1},\ldots,\pi_{k})$ of $\mathcal{M}$,
$2\leq k\leq m$, the resulting shared information of the teamed rvs
$X_{\pi_{1}},\ldots,X_{\pi_{k}}$ can be only larger, i.e.,

$\displaystyle\operatorname{SI}(X_{\pi_{1}},\ldots,X_{\pi_{k}})\geq\operatorname{SI}(X_{1},\ldots,X_{m}).$
(3)

Suppose that $\pi^{*}=(\pi_{1}^{*},\ldots,\pi_{l}^{*})$, $l\geq 2$, attains
$\operatorname{SI}(X_{\mathcal{M}})>0$ (not necessarily uniquely) in
Definition 1, i.e,

$\displaystyle\operatorname{SI}(X_{\mathcal{M}})=\frac{1}{l-1}D(P_{X_{\mathcal{M}}}\;\|\;\prod_{u=1}^{l}P_{X_{\pi_{u}^{*}}}).$
(4)

A simple but useful observation based on Definition 1, 3 and 4 is that upon
agglomerating the rvs in each atom of an optimum partition
$\pi^{*}=(\pi_{1}^{*},\ldots,\pi_{l}^{*})$, the resulting shared information
$\operatorname{SI}(X_{\pi_{1}^{*}},\ldots,X_{\pi_{l}^{*}})$ of the teams
$X_{\pi_{1}^{*}},\ldots,X_{\pi_{k}^{*}}$ equals the shared information
$\operatorname{SI}(X_{\mathcal{M}})$ of the (unteamed) rvs
$X_{1},\ldots,X_{m}$, i.e, for these special teams 3 holds with equality. This
property has benefited information-clustering applications (cf. e.g., [11],
[14]).

Shared information satisfies the data processing inequality [11]. For
$X_{\mathcal{M}}=(X_{1},\ldots,X_{m})$, consider
$X_{\mathcal{M}}^{\prime}=(X_{1}^{\prime},\ldots,X_{m}^{\prime})$ where for a
fixed $1\leq j\leq m$, $X_{i}^{\prime}=X_{i}$ for
$i\in\mathcal{M}\setminus\left\\{{j}\right\\}$ and $X_{j}^{\prime}$ is
obtained as the output of a stochastic matrix
$W:\mathcal{X}_{j}\rightarrow\mathcal{X}_{j}$ with input $X_{j}$. Then,
$\operatorname{SI}(X_{\mathcal{M}}^{\prime})\leq\operatorname{SI}(X_{\mathcal{M}})$.

It is worth comparing $\operatorname{SI}(X_{\mathcal{M}})$ with two well-known
measures of correlation among $X_{1},\ldots,X_{m}$, $m\geq 2$, of a similar
vein. Watanabe’s _total correlation_ [45] is defined by

$\displaystyle\mathcal{C}(X_{\mathcal{M}})=D(P_{X_{\mathcal{M}}}\;\|\;\prod_{i=1}^{m}P_{X_{i}})=\sum_{i=1}^{m-1}\operatorname{I}(X_{i+1}\wedge
X_{1},\ldots,X_{i})$ (5)

and equals $(m-1)\operatorname{\mathcal{I}\,}(\pi)$ for the partition
$\pi=(\left\\{{1}\right\\},\ldots,\left\\{{m}\right\\})$ of $\mathcal{M}$
consisting of singleton atoms. By 1 and 5, clearly

$\displaystyle\operatorname{SI}(X_{\mathcal{M}})\leq\frac{1}{m-1}\
\mathcal{C}(X_{\mathcal{M}}).$ (6)

Han’s _dual total correlation_ [26] is defined (equivalently) by

$\displaystyle\mathcal{D}(X_{\mathcal{M}})$
$\displaystyle=\sum_{i=1}^{m-1}\mathcal{D}iv{P_{X_{i}}}{P_{X_{i+1}\cdots
X_{m}}}{P_{X_{1}\cdots X_{i-1}}}$
$\displaystyle=\sum_{i=1}^{m}\operatorname{H}(X_{\mathcal{M}\setminus\left\\{{i}\right\\}})-(m-1)\operatorname{H}(X_{\mathcal{M}})$
$\displaystyle=\operatorname{H}(X_{\mathcal{M}})-\sum_{i=1}^{m}\operatorname{H}(X_{i}\,|\,X_{\mathcal{M}\setminus\left\\{{i}\right\\}})$
(7) $\displaystyle=\sum_{i=1}^{m-1}\operatorname{I}(X_{i}\wedge
X_{i+1},\ldots,X_{m}\,|\,X_{1},\ldots,X_{i-1}),$

(with conditioning vacuous for $i=1$) where the expression in 7 is from [1].
By a straightforward calculation, these measures are seen to enjoy the
sandwich

$\displaystyle\frac{\mathcal{C}(X_{\mathcal{M}})}{m-1}\leq\mathcal{D}(X_{\mathcal{M}})\leq(m-1)\
\mathcal{C}(X_{\mathcal{M}})$ (8)

whereby we get from 6 and the first inequality in 8 that

$\displaystyle\operatorname{SI}(X_{\mathcal{M}})\leq\frac{\mathcal{C}(X_{\mathcal{M}})}{m-1}\quad\text{and}\quad\operatorname{SI}(X_{\mathcal{M}})\leq\mathcal{D}(X_{\mathcal{M}}).$
(9)

This makes $\operatorname{SI}(X_{\mathcal{M}})$ a leaner measure of
correlation than $\mathcal{C}(X_{\mathcal{M}})$ (upon setting aside the fixed
constant $1/(m-1)$) or $\mathcal{D}(X_{\mathcal{M}})$. Significantly, the
notion of an optimal partition in $\operatorname{SI}(X_{\mathcal{M}})$ in 1
makes shared information an appealing measure for “local” as well as “global”
dependencies among the rvs $X_{1},\ldots,X_{m}$.

######  Remark 1.

When $\mathcal{M}=\left\\{{1,2}\right\\}$,

$\displaystyle\operatorname{SI}(X_{1},X_{2})=\mathcal{C}(X_{1},X_{2})=\mathcal{D}(X_{1},X_{2})=\operatorname{I}(X_{1}\wedge
X_{2}).$

Our focus is on shared information for a Markov chain on a tree.

Figure 1: Notation for a Markov chain on a tree.

######  Definition 2 (Markov Chain on a Tree).

Let $\mathcal{G}=(\mathcal{M},\mathcal{E})$ be a tree with vertex set
$\mathcal{M}=\left\\{{1,\ldots,m}\right\\}$, $m\geq 2$, i.e., a connected
graph containing no circuits. For $(i,j)$ in the edge set $\mathcal{E}$, let
$\mathcal{B}(i\leftarrow j)$ denote the set of all vertices connected with $j$
by a path containing the edge $(i,j)$. Note that $i\in\mathcal{B}(i\leftarrow
j)$ but $j\notin\mathcal{B}(i\leftarrow j)$. See Figure 1. The rvs
$X_{1},\ldots,X_{m}$ form a _Markov Chain on a Tree_ (MCT) $\mathcal{G}$ if
for every $(i,j)\in\mathcal{E}$, the conditional pmf of $X_{j}$ given
$X_{\mathcal{B}(i\leftarrow j)}=\left\\{{X_{l}:l\in\mathcal{B}(i\leftarrow
j)}\right\\}$ depends only on $X_{i}$. Specifically, $X_{j}$ is conditionally
independent of $X_{\mathcal{B}(i\leftarrow j)\setminus\left\\{{i}\right\\}}$
when conditioned on $X_{i}$. Thus, $P_{X_{\mathcal{M}}}$ is such that for each
$(i,j)\in\mathcal{E}$,

$\displaystyle P_{X_{j}\,|\,X_{\mathcal{B}(i\leftarrow
j)}}=P_{X_{j}\,|\,X_{i}},$ (10)

or, equivalently,

$\displaystyle
X_{j}-\\!\\!\circ\\!\\!-X_{i}-\\!\\!\circ\\!\\!-X_{\mathcal{B}(i\leftarrow
j)\setminus\left\\{{i}\right\\}}.$ (11)

When $\mathcal{G}$ is a chain, an MCT reduces to a standard Markov chain.

######  Remark 2.

With an abuse of terminology, we shall use
$\mathcal{G}=(\mathcal{M},\mathcal{E})$ to refer to a tree and also to the
associated MCT.

######  Example 2.

Let $m=2^{l}-1$ for some positive integer $l$. Consider a balanced binary tree
with $l$ levels. Label the nodes progressively at each level and downwards,
with the root node (at level $1$) being $1$ and the $2^{l-1}$ leaves (at level
$l$) being $2^{l-1},\ldots,2^{l-1}+2^{l-1}-1=2^{l}-1=m$. Let
$X_{1},Z_{1},\ldots,Z_{m-1}$ be mutually independent rvs where
$X_{1}=\mathrm{Ber}(0.5)$ and $Z_{i}=\mathrm{Ber}(p_{i})$ with $0<p_{i}<0.5$,
$i=1,\ldots,m-1$. For $i=2,\ldots,m$, set $X_{i}=X_{\lfloor
i/2\rfloor}+Z_{i-1}$ where “+” denotes addition modulo $2$; note that $X_{i}$
is determined by $(X_{1},Z_{1},\ldots,Z_{i-1})$, and
$P(X_{i}=0)=P(X_{i}=1)=0.5$.

Figure 2: Example 2 of an MCT.

Assign rv $X_{i}$ to vertex $i$, $i=1,\ldots,m$. See Figure 2. Then
$X_{1},\ldots,X_{m}$ form an MCT. Specifically, for any edge $(i,j)$ where $i$
is the parent of $j\geq 2$, we have

$\displaystyle P(X_{j}=x_{j}\,|\,X_{\mathcal{B}(i\leftarrow
j)}=x_{\mathcal{B}(i\leftarrow j)})$
$\displaystyle=P(X_{j}=x_{j}\,|\,X_{i}=x_{i},X_{\mathcal{B}(i\leftarrow
j)\setminus\left\\{{i}\right\\}}=x_{\mathcal{B}(i\leftarrow
j)\setminus\left\\{{i}\right\\}})$
$\displaystyle=P(x_{i}+Z_{j-1}=x_{j}\,|\,X_{i}=x_{i},X_{\mathcal{B}(i\leftarrow
j)\setminus\left\\{{i}\right\\}}=x_{\mathcal{B}(i\leftarrow
j)\setminus\left\\{{i}\right\\}})$ $\displaystyle=P(Z_{j-1}=x_{j}+x_{i})$
$\displaystyle=P(X_{j}=x_{j}\,|\,X_{i}=x_{i})$

where the last two inequalities are by the independence of $Z_{j-1}$ and
$X_{\mathcal{B}(i\leftarrow j)}$, the latter rv being a function of
$X_{1},Z_{\left\\{{1,\ldots,m-1}\right\\}\setminus\left\\{{j-1}\right\\}}$.

##  III Properties of an MCT

We develop properties of an MCT that will play a role in characterizing shared
information, and also are of independent interest. These include the concept
of an agglomerated MCT, and notions of local and global Markov properties.

The main conclusion of this section is that the MCT as defined in 11 has the
global Markov property, which, in turn, implies 11; the proofs in this
section, however, are based on 11.

We begin with agglomeration.

######  Lemma 1.

For the MCT $\mathcal{G}=(\mathcal{M},\mathcal{E})$, for every
$(i,j)\in\mathcal{E}$,

$\displaystyle\operatorname{I}(X_{\mathcal{B}(i\leftarrow j)}\wedge
X_{\mathcal{B}(j\leftarrow i)})=\operatorname{I}(X_{i}\wedge X_{j}),$ (12)

i.e.,

$\displaystyle X_{\mathcal{B}(i\leftarrow
j)\setminus\left\\{{i}\right\\}}-\\!\\!\circ\\!\\!-X_{i}-\\!\\!\circ\\!\\!-X_{j}-\\!\\!\circ\\!\\!-X_{\mathcal{B}(j\leftarrow
i)\setminus\left\\{{j}\right\\}}.$ (13)

###### Proof.

The assertion 12 is proved in Appendix A. Turning to 13, by the chain rule 12
is equivalent to

$\displaystyle X_{\mathcal{B}(i\leftarrow
j)\setminus\left\\{{i}\right\\}}-\\!\\!\circ\\!\\!-$ $\displaystyle
X_{i}-\\!\\!\circ\\!\\!-X_{j}$ $\displaystyle\text{and
}X_{\mathcal{B}(i\leftarrow j)}-\\!\\!\circ\\!\\!-$ $\displaystyle
X_{j}-\\!\\!\circ\\!\\!-X_{\mathcal{B}(j\leftarrow
i)\setminus\left\\{{j}\right\\}}$

which, in turn, are together tantamount to 13. ∎

######  Definition 3 (Agglomerated Tree).

Consider a $k$-partition $\pi=(\pi_{1},\ldots,\pi_{k})$ of $\mathcal{M}$,
$2\leq k\leq m-1$, where each $\pi_{i}$, $1\leq i\leq k$, is connected. The
tree $\mathcal{G}^{\prime}=(\mathcal{M}^{\prime},\mathcal{E}^{\prime})$ with
vertex set $\mathcal{M}^{\prime}=\left\\{{\pi_{1},\ldots,\pi_{k}}\right\\}$
and edge set

$\displaystyle\mathcal{E}^{\prime}=\left\\{{(\pi_{i^{\prime}},\pi_{j^{\prime}}):\exists
i\in\pi_{i^{\prime}},j\in\pi_{j^{\prime}}\text{ s.t.
}(i,j)\in\mathcal{E}}\right\\}$

is termed an agglomerated tree. Note that
$\mathcal{G}^{\prime}=(\mathcal{M}^{\prime},\mathcal{E}^{\prime})$ is a tree
since $\mathcal{G}=(\mathcal{M},\mathcal{E})$ is a tree and each $\pi_{i}$,
$1\leq i\leq k$, is connected.

######  Lemma 2.

Consider the agglomerated tree
$\mathcal{G}^{\prime}=(\mathcal{M}^{\prime},\mathcal{E}^{\prime})$ in
Definition 3. If $X_{1},\ldots,X_{m}$ form an MCT
$\mathcal{G}=(\mathcal{M},\mathcal{E})$, then $X_{\pi_{1}},\ldots,X_{\pi_{k}}$
form an MCT
$\mathcal{G}^{\prime}=(\mathcal{M}^{\prime},\mathcal{E}^{\prime})$.

###### Proof.

By an obvious extension of Definition 2 to the agglomerated tree
$\mathcal{G}^{\prime}=(\mathcal{M}^{\prime},\mathcal{E}^{\prime})$, the lemma
would follow upon showing that for every
$(\pi_{i^{\prime}},\pi_{j^{\prime}})\in\mathcal{E}^{\prime}$, it holds that

$\displaystyle
X_{\pi_{j^{\prime}}}-\\!\\!\circ\\!\\!-X_{\pi_{i^{\prime}}}-\\!\\!\circ\\!\\!-X_{\mathcal{B}(\pi_{i^{\prime}}\leftarrow\pi_{j^{\prime}})\setminus\pi_{i^{\prime}}}.$
(14)

For any $(\pi_{i^{\prime}},\pi_{j^{\prime}})\in\mathcal{E}^{\prime}$, there
exist by Definition 3 $i\in\pi_{i^{\prime}}$, $j\in\pi_{j^{\prime}}$ with
$(i,j)\in\mathcal{E}$. By Lemma 1,

$\displaystyle
X_{\pi_{j^{\prime}}}-\\!\\!\circ\\!\\!-X_{i}-\\!\\!\circ\\!\\!-X_{\mathcal{B}(i\leftarrow
j)\setminus\left\\{{i}\right\\}}$ (15)

which, upon noting that
$X_{\mathcal{B}(\pi_{i^{\prime}}\leftarrow\pi_{j^{\prime}})\setminus\pi_{i^{\prime}}}\subseteq
X_{\mathcal{B}(i\leftarrow j)\setminus\left\\{{i}\right\\}}$ and applying the
chain rule of mutual information to 15, gives 14. ∎

Next, we turn to local and global Markovity of an MCT.

######  Definition 4 (Separation).

For a tree $\mathcal{G}=(\mathcal{M},\mathcal{E})$, let $A$, $B$ and $S$ be
disjoint, nonempty subsets of $\mathcal{M}$. Then $S$ _separates_ $A$ and $B$
if for every $a\in A$ and $b\in B$, the path connecting $a$ and $b$ has at
least one vertex $s=s(a,b)$ in $S$.

The notion of maximally connected subset will be used below:
$A^{\prime}\subseteq A$ is a maximally connected subset of $A$ if $A^{\prime}$
is connected and the addition to $A^{\prime}$ of any vertex $u\in A\setminus
A^{\prime}$ renders $A^{\prime}\cup\left\\{{u}\right\\}$ to be disconnected.
By convention, we shall take singleton elements to be connected. In general,
any connected component of $A$ that is not maximally connected can be enlarged
to absorb vertices outside it in $A$ that do not render the union to be
disconnected.

######  Theorem 3 (Global Markov property).

For an MCT $\mathcal{G}=(\mathcal{M},\mathcal{E})$, let $A$, $B$ and $S$ be
disjoint, nonempty subsets of $\mathcal{M}$ such that $S$ separates $A$ and
$B$. Then

$\displaystyle X_{A}-\\!\\!\circ\\!\\!-X_{S}-\\!\\!\circ\\!\\!-X_{B}.$ (16)

Conversely, if $X_{1},\ldots,X_{m}$ are assigned to the vertices of a tree
$\mathcal{G}=(\mathcal{M},\mathcal{E})$ and satisfy 16 for every such $A$,
$B$, $S$, they form an MCT.

######  Remark 3.

The Hammersley-Clifford Theorem [31, Theorem 3.9] implies the equivalence
above for strictly positive joint pmfs, i.e., with $P(x_{\mathcal{M}})>0$ for
every $x_{\mathcal{M}}\in\mathcal{X}_{\mathcal{M}}$. Theorem 3 shows that for
an MCT, this equivalence holds also for a joint pmf $P_{X_{\mathcal{M}}}$ that
is _not_ strictly positive.

######  Remark 4.

The “global” Markov property 16 [31, Section 3.2.1] clearly implies 10, 11 in
Definition 2. Theorem 3 asserts that for an MCT, 16 is, in fact, equivalent to
10, 11.

Our proof of Theorem 3 in Appendix B relies on showing that an MCT has the
“local Markov property” of Lemma 4 below. The notion of _neighborhood_ is
pertinent. Lemma 4, too, is proved in Appendix B.

######  Definition 5 (Neighborhood).

For each $i\in\mathcal{M}$, its neighborhood is
$\mathcal{N}(i)=\left\\{{j\in\mathcal{M}:(i,j)\in\mathcal{E}}\right\\}$; note
that $i\notin\mathcal{N}(i)$. Similarly, the neighborhood of
$A\subsetneq\mathcal{M}$ is $\mathcal{N}(A)=\cup_{i\in
A}\mathcal{N}(i)\setminus A$.

######  Lemma 4 (Local Markov property).

Consider an MCT $\mathcal{G}=(\mathcal{M},\mathcal{E})$. For each
$i\in\mathcal{M}$,

$\displaystyle
X_{i}-\\!\\!\circ\\!\\!-X_{\mathcal{N}(i)}-\\!\\!\circ\\!\\!-X_{\mathcal{M}\setminus(\left\\{{i}\right\\}\cup\mathcal{N}(i))}.$
(17)

Furthermore, for every $A\subsetneq\mathcal{M}$ with no edge connecting any
two vertices in it,

$\displaystyle
X_{A}-\\!\\!\circ\\!\\!-X_{\mathcal{N}(A)}-\\!\\!\circ\\!\\!-X_{\mathcal{M}\setminus(A\cup\mathcal{N}(A))}.$
(18)

######  Remark 5.

For $A\subsetneq\mathcal{M}$ as in Lemma 4, $\mathcal{N}(A)=\cup_{i\in
A}\mathcal{N}(i)$.

The relationships among the MCT definition 11, and local and global Markov
properties are summarized by the following lemma.

######  Lemma 5.

It holds that
(i) MCT and the global Markov property are equivalent;
(ii) MCT implies the local Markov property;
(iii) the local Markov property implies neither the global Markov property nor
the MCT.

###### Proof.

(i), (ii) The proofs are contained in Theorem 3 and Lemma 4, respectively.
(iii) The following example is used in [31, Example 3.5] to show that local
Markovity does not imply global Markovity. Let $U$ and $Z$ be independent
$\mathrm{Ber}(0.5)$ rvs, and let $W=U$, $Y=Z$ and $X=WY$. Consider the graph

$\displaystyle U-W-X-Y-Z$

which has the local Markov property. Since

$\displaystyle\operatorname{I}(Z\wedge U,W\,|\,X)$
$\displaystyle=\operatorname{I}(Z\wedge U\,|\,UZ)$
$\displaystyle=\operatorname{H}(Z\,|\,UZ)$
$\displaystyle=0.75\,\operatorname{H}(Z\,|\,UZ=0)$
$\displaystyle=0.75\,h(1/3),$

the claim in (iii) is true. ∎

##  IV Shared Information for a Markov Chain on a Tree

We present a new proof of an explicit characterization of
$\operatorname{SI}(X_{\mathcal{M}})$ for an MCT. The expression in Theorem 6
below was obtained first in [21] relying on its secrecy capacity
interpretation. Specifically, it was computed using a linear program for said
capacity and seen to equal an upper bound corresponding to shared information
([21, Examples 4, 7]). The new approach below works directly with the
definition of shared information in Definition 1. Also, it differs materially
from the treatment in [14, Section 4] for a model that appears to differ from
ours.

While the upper bound for $\operatorname{SI}(X_{\mathcal{M}})$ below is akin
to that involving secret key capacity in [21], the proof of the lower bound
uses an altogether new method based on the structure of a “good” partition
$\pi$ in Definition 1.

######  Theorem 6.

Let $\mathcal{G}=(\mathcal{M},\mathcal{E})$ be an MCT with pmf
$P_{X_{\mathcal{M}}}$ in 10. Then

$\displaystyle\operatorname{SI}(X_{\mathcal{M}})=\min_{(i,j)\in\mathcal{E}}\operatorname{I}(X_{i}\wedge
X_{j}).$ (19)

######  Remark 6.

For later use, let $(\bar{i},\bar{j})$ be the (not necessarily unique)
minimizer in the right-side of 19

######  Example 3.

For the MCT in Example 2, $\operatorname{SI}(X_{\mathcal{M}})=1-h(p^{*})$,
where $p^{*}=\max_{1\leq i\leq m-1}p_{i}<0.5$. Thus, the $2$-partition
obtained by cutting the (not necessarily unique) weakest correlating edge
attains the minimum in Definition 1.

###### Proof.

As shown in [21],

$\displaystyle\operatorname{SI}(X_{\mathcal{M}})\leq\min_{(i,j)\in\mathcal{E}}\operatorname{I}(X_{i}\wedge
X_{j})$ (20)

and is seen as follows. For each $(i,j)\in\mathcal{E}$, consider a
$2$-partition of $\mathcal{M}$, viz. $\pi=\pi((i,j))=(\pi_{1},\pi_{2})$ where
$\pi_{1}=\mathcal{B}(i\leftarrow j)$, $\pi_{2}=\mathcal{B}(j\leftarrow i)$.
Then,

$\displaystyle\operatorname{I}(X_{\pi_{1}}\wedge X_{\pi_{2}})$
$\displaystyle=\operatorname{I}(X_{\mathcal{B}(i\leftarrow j)}\wedge
X_{\mathcal{B}(j\leftarrow i)})$ $\displaystyle=\operatorname{I}(X_{i}\wedge
X_{j}),\text{ by \lx@cref{creftypecap~refnum}{lem:mrf-mi}.}$ (21)

Hence,

$\displaystyle\operatorname{SI}(X_{\mathcal{M}})\leq\operatorname{I}(X_{\pi_{1}}\wedge
X_{\pi_{2}})=\operatorname{I}(X_{i}\wedge X_{j}),\qquad(i,j)\in\mathcal{E}$

leading to 20.

Next, we show that

$\displaystyle\operatorname{SI}(X_{\mathcal{M}})\geq\min_{(i,j)\in\mathcal{E}}\operatorname{I}(X_{i}\wedge
X_{j}).$ (22)

This is done in two steps. First, we show that for any $k$-partition $\pi$ of
$\mathcal{M}$, $2\leq k\leq m$, _with (individually) connected atoms_ ,

$\displaystyle\operatorname{\mathcal{I}\,}(\pi)\geq\min_{(i,j)\in\mathcal{E}}\operatorname{I}(X_{i}\wedge
X_{j}).$

Second, we argue that for any $k$-partition $\pi=(\pi_{1},\ldots,\pi_{k})$
containing disconnected atoms, there exists a $k^{\prime}$-partition
$\pi^{\prime}=(\pi^{\prime},\ldots,\pi^{\prime}_{k^{\prime}})$, possibly with
$k^{\prime}\neq k$, and with fewer disconnected atoms such that
$\operatorname{\mathcal{I}\,}(\pi^{\prime})\leq\operatorname{\mathcal{I}\,}(\pi)$.

Step 1: Let $\pi=(\pi_{1},\ldots,\pi_{k})$, $k\geq 2$, be a $k$-partition with
each atom being a connected set. By Lemma 2, $X_{\pi_{1}},\ldots,X_{\pi_{k}}$
form an agglomerated MCT
$\mathcal{G}^{\prime}=(\mathcal{M}^{\prime},\mathcal{E}^{\prime})$ as in
Definition 3. Furthermore, by Lemma 1, if $\pi_{u}$ and $\pi_{v}$ in
$\mathcal{M}^{\prime}$ are connected by an edge
$(\pi_{u},\pi_{v})\in\mathcal{E}^{\prime}$, then there exist $i\in\pi_{u}$,
$j\in\pi_{v}$, say, such that $(i,j)\in\mathcal{E}$, whence

$\displaystyle\operatorname{I}(X_{\pi_{u}}\wedge
X_{\pi_{v}})=\operatorname{I}(X_{i}\wedge X_{j}).$ (23)

Now, let $\pi_{1},\ldots,\pi_{k}$ be an enumeration of the atoms, obtained
from a breadth-first search [18, Ch. 22] run on the agglomerated tree with
$\pi_{1}$ as the root vertex. Then,

$\displaystyle\operatorname{\mathcal{I}\,}(\pi)$
$\displaystyle=\frac{1}{k-1}D(P_{X_{\mathcal{M}}}\;\|\;\prod_{u=1}^{k}P_{X_{\pi_{u}}})$
$\displaystyle=\frac{1}{k-1}\left[{\sum_{u=1}^{k}\left({\operatorname{H}(X_{\pi_{u}})-\operatorname{H}(X_{\pi_{u}}\,|\,X_{\pi_{1}},\ldots,X_{\pi_{u-1}})}\right)}\right]$
$\displaystyle=\frac{1}{k-1}\sum_{u=2}^{k}\operatorname{I}(X_{\pi_{u}}\wedge
X_{\pi_{1}},\ldots,X_{\pi_{u-1}})$
$\displaystyle=\frac{1}{k-1}\sum_{u=2}^{k}\operatorname{I}(X_{\pi_{u}}\wedge
X_{\mathrm{parent}(\pi_{u})})$ (24)
$\displaystyle\geq\min_{(\pi_{u},\pi_{v})\in\mathcal{E}^{\prime}}\operatorname{I}(X_{\pi_{u}}\wedge
X_{\pi_{v}})$
$\displaystyle\geq\min_{(i,j)\in\mathcal{E}}\operatorname{I}(X_{i}\wedge
X_{j}).$

By the breadth-first search algorithm [18, Ch. 22], $\pi_{1},\ldots,\pi_{u-1}$
are either at the same depth as $\pi_{u}$ or are above it (and include
$\mathrm{parent}(\pi_{u})$). This, combined with Theorem 3, gives 24. The last
inequality is by 23.

Step 2: Consider first the case $k=2$. Take any $2$-partition
$\pi=(\pi_{1},\pi_{2})$ with possibly disconnected atoms, where
$\pi_{1}=\cup_{\rho=1}^{r}C_{\rho}$ and
$\pi_{2}=\cup_{\sigma=1}^{s}D_{\sigma}$ are unions of disjoint components.
Since $\pi_{1}$ is connected to $\pi_{2}$, some $C_{\rho}$ and $D_{\sigma}$
must be connected by some edge $(i,j)$ in $\mathcal{E}$, so that

$\displaystyle\operatorname{\mathcal{I}\,}(\pi)=\operatorname{I}(X_{\pi_{1}}\wedge
X_{\pi_{2}})\geq\operatorname{I}(X_{C_{\rho}}\wedge X_{D_{\sigma}})$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\geq\operatorname{I}(X_{i}\wedge
X_{j})\geq\operatorname{I}(X_{\bar{i}}\wedge X_{\bar{j}})$

where the final lower bound, with $\bar{i},\bar{j}$ as in Remark 6, is
achieved by the $2$-partition with connected atoms
$(\mathcal{B}(\bar{i}\leftarrow\bar{j}),\mathcal{B}(\bar{j}\leftarrow\bar{i}))$
as in 21.

Next, consider a $k$-partition $\pi=(\pi_{1},\ldots,\pi_{k})$, $k\geq 3$, and
suppose that the atom $\pi_{1}$ is not connected. Without loss of generality,
assume $\pi_{1}$ to be the (disjoint) union of maximally connected subsets
$A_{1},\ldots,A_{t}$, $t\geq 2$, of $\pi_{1}$ (which, at an extreme, can be
the individual vertices constituting $\pi_{1}$).

Take any $A_{l}$, say $A_{l}=A_{\bar{l}}$, and consider all its boundary
edges, namely those edges for which one vertex is in $A_{\bar{l}}$ and the
other outside it. As $A_{\bar{l}}$ is maximally connected in $\pi_{1}$, for
each boundary edge the outside vertex cannot belong to $\pi_{1}$ and so must
lie in $\mathcal{M}\setminus\pi_{1}$. Also, every such outside vertex
associated with $A_{\bar{l}}$ must be the root of a subtree and, like
$A_{\bar{l}}$, every $A_{l}$, $l\neq\bar{l}$, too, must be a subset of one
such subtree linked to $A_{\bar{l}}$ – owing to connectedness within
$A_{\bar{l}}$. Furthermore, since $A_{1},\ldots,A_{t}$ are connected, and only
through the subtrees rooted in $\mathcal{M}\setminus\pi_{1}$, there must exist
at least one $A_{l}$ such that all $A_{l^{\prime}}$s, $l^{\prime}\neq l$, are
subsets of one subtree linked to $A_{l}$. In other words, denoting this
$A_{l}$ as $A$, we note that $A$ has the property that

$\pi_{1}\setminus
A=\bigcup_{\begin{subarray}{c}l\in\left\\{{1,\cdots,t}\right\\}:\\\ A_{l}\neq
A\end{subarray}}A_{l}$

is contained entirely in a subtree rooted at an outside vertex associated with
$A$ and lying in $\mathcal{M}\setminus\pi_{1}$. Let this vertex be
$j\in\mathcal{M}\setminus\pi_{1}$, and let $\pi_{u}\in\pi$ be the atom that
contains $j$. Since vertex $j$ separates $A$ from $\pi_{1}\setminus A$, so
does $\pi_{u}$. By Theorem 3, it follows that

$\displaystyle A-\\!\\!\circ\\!\\!-\pi_{u}-\\!\\!\circ\\!\\!-\pi_{1}\setminus
A$

whereby, using the data processing inequality,

$\displaystyle\operatorname{I}(X_{A}\wedge X_{\pi_{1}\setminus
A})\leq\operatorname{I}(X_{\pi_{u}}\wedge X_{\pi_{1}\setminus
A})\leq\operatorname{I}(X_{\pi_{u}}\wedge X_{\pi_{1}}).$ (25)

Next, consider the $(k-1)$-partition $\pi^{\prime}$ and the $(k+1)$-partition
$\pi^{\prime\prime}$ of $\mathcal{M}$, defined by

$\displaystyle\pi^{\prime}$
$\displaystyle=\left({\pi_{1}\cup\pi_{u},\left\\{{\pi_{v}}\right\\}_{v\neq
1,v\neq u}}\right),$ (26) $\displaystyle\pi^{\prime\prime}$
$\displaystyle=\left({\pi_{1}\setminus
A,A,\pi_{u},\left\\{{\pi_{v}}\right\\}_{v\neq 1,v\neq u}}\right).$ (27)

Then,

$\displaystyle\operatorname{\mathcal{I}\,}(\pi)$
$\displaystyle=\frac{1}{k-1}\Bigg{[}\operatorname{H}(X_{\pi_{1}})+\operatorname{H}(X_{\pi_{u}})$
$\displaystyle\qquad\qquad\qquad\qquad+\sum_{v\neq 1,v\neq
u}\operatorname{H}(X_{\pi_{v}})-\operatorname{H}(X_{\mathcal{M}})\Bigg{]},$
$\displaystyle\operatorname{\mathcal{I}\,}(\pi^{\prime})$
$\displaystyle=\frac{1}{k-2}\Bigg{[}\operatorname{H}(X_{\pi_{1}\cup\pi_{u}})+\sum_{v\neq
1,v\neq u}\operatorname{H}(X_{\pi_{v}})$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad-\operatorname{H}(X_{\mathcal{M}})\Bigg{]},$
$\displaystyle\operatorname{\mathcal{I}\,}(\pi^{\prime\prime})$
$\displaystyle=\frac{1}{k}\Bigg{[}\operatorname{H}(X_{\pi_{1}\setminus
A})+\operatorname{H}(X_{A})+\operatorname{H}(X_{\pi_{u}})$
$\displaystyle\qquad\qquad\qquad\qquad+\sum_{v\neq 1,v\neq
u}\operatorname{H}(X_{\pi_{v}})-\operatorname{H}(X_{\mathcal{M}})\Bigg{]}.$

We claim that

$\displaystyle\operatorname{\mathcal{I}\,}(\pi)\geq\min\left\\{{\operatorname{\mathcal{I}\,}(\pi^{\prime}),\operatorname{\mathcal{I}\,}(\pi^{\prime\prime})}\right\\}.$
(28)

Referring to 26 and 27, we can infer from the claim 28 that for a given
$k$-partition $\pi$ with a disconnected atom $\pi_{1}$ as above, merging a
disconnected atom with another atom (as in 26) or breaking it to create a
connected atom (as in 27), lead to partitions $\pi^{\prime}$ or
$\pi^{\prime\prime}$, of which at least one has a lower
$\operatorname{\mathcal{I}\,}$-value than $\pi$. This argument is repeated
until a final partition with connected atoms is reached that has the following
form: considering the set of all maximally connected components of the atoms
of $\pi=(\pi_{1},\ldots,\pi_{k})$, the final partition will consist of
_connected_ unions of such components. (A connected $\pi_{i}$ already
constitutes such a component.)

It remains to show 28. Suppose 28 were not true, i.e.,

$\displaystyle\operatorname{\mathcal{I}\,}(\pi)<\min\left\\{{\operatorname{\mathcal{I}\,}(\pi^{\prime}),\operatorname{\mathcal{I}\,}(\pi^{\prime\prime})}\right\\}.$

Then,

$\displaystyle\operatorname{\mathcal{I}\,}(\pi)<\operatorname{\mathcal{I}\,}(\pi^{\prime})$
$\displaystyle\Leftrightarrow(k-2)\operatorname{\mathcal{I}\,}(\pi)<(k-2)\operatorname{\mathcal{I}\,}(\pi^{\prime})$
$\displaystyle\Leftrightarrow\operatorname{I}(X_{\pi_{u}}\wedge
X_{\pi_{1}})<\operatorname{\mathcal{I}\,}(\pi),$ (29)

and similarly,

$\displaystyle\operatorname{\mathcal{I}\,}(\pi)<\operatorname{\mathcal{I}\,}(\pi^{\prime\prime})$
$\displaystyle\Leftrightarrow
k\operatorname{\mathcal{I}\,}(\pi)<k\operatorname{\mathcal{I}\,}(\pi^{\prime\prime})$
$\displaystyle\Leftrightarrow\operatorname{\mathcal{I}\,}(\pi)<\operatorname{I}(X_{\pi_{1}\setminus
A}\wedge X_{A})$ (30)

where the second equivalences in 29 and 30 are obtained by straightforward
manipulation. By 29 and 30,

$\displaystyle\operatorname{I}(X_{\pi_{u}}\wedge
X_{\pi_{1}})<\operatorname{I}(X_{\pi_{1}\setminus A}\wedge X_{A})$

which contradicts 25. Hence, 28 is true. ∎

##  V Estimating $\operatorname{SI}(X_{\mathcal{M}})$ for an MCT

We consider the estimation of $\operatorname{SI}(X_{\mathcal{M}})$ when the
pmf $P_{X_{\mathcal{M}}}$ of $X_{\mathcal{M}}=(X_{1},\ldots,X_{m})$ is unknown
to an “agent” who, however, is assumed to know the tree
$\mathcal{G}=(\mathcal{M},\mathcal{E})$. We assume further in this section
that $\mathcal{X}_{1}=\cdots=\mathcal{X}_{m}=\mathcal{X}$, say, and also that
the minimizing edge $(\bar{i},\bar{j})$ on the right side of 19 is unique. By
Theorem 6, $\operatorname{SI}(X_{\mathcal{M}})$ equals the minimum mutual
information across an edge in the tree $\mathcal{G}$. Treating the
determination of this edge as a correlated bandits problem of best arm pair
identification, we provide an algorithm to home in on it, and analyze its
error performance and associated sample complexity. _The estimate of shared
information is taken to be the mutual information across the best arm-pair
thus identified._ Our estimation procedure is motivated by the form of
$\operatorname{SI}(X_{\mathcal{M}})$ in Theorem 6.

###  V-A Preliminaries

As stated, estimation of $\operatorname{SI}(X_{\mathcal{M}})$ for an MCT will
entail estimating $\operatorname{I}(X_{i}\wedge X_{j})$,
$(i,j)\in\mathcal{E}$. We first present pertinent tools that will be used to
this end.

Let $(X_{t},Y_{t})_{t=1}^{n}$ be $n\geq 1$ independent and identically
distributed (i.i.d.) repetitions of rv $(X,Y)$ with (unknown) pmf $P_{XY}$ of
_assumed full support_ on $\mathcal{X}\times\mathcal{Y}$, where $\mathcal{X}$
and $\mathcal{Y}$ are finite sets. For $(\mathbf{x},\mathbf{y})$ in
$\mathcal{X}^{n}\times\mathcal{Y}^{n}$, let $Q_{\mathbf{x}\mathbf{y}}^{(n)}$
represent its joint type on $\mathcal{X}\times\mathcal{Y}$ (cf. [20, Ch. 2,
3]). Also, let $Q_{\mathbf{x}}^{(n)}$ (resp. $Q_{\mathbf{y}}^{(n)}$) represent
the (marginal) type of $\mathbf{x}$ (resp. $\mathbf{y}$).

A well-known estimator for $\operatorname{I}(X\wedge
Y)=\operatorname{I}_{P_{XY}}(X\wedge Y)$ on the basis of
$(\mathbf{x},\mathbf{y})$ in $\mathcal{X}^{n}\times\mathcal{Y}^{n}$ is the
_empirical mutual information_ (EMI) estimator
${\operatorname{I}}_{\mathsf{EMI}}^{(n)}$, based on EMI [25], [20, Ch. 3],
defined by

$\displaystyle{\operatorname{I}}_{\mathsf{EMI}}^{(n)}(\mathbf{x}\wedge\mathbf{y})=\operatorname{H}(Q^{(n)}_{\mathbf{x}})+\operatorname{H}(Q^{(n)}_{\mathbf{y}})-\operatorname{H}(Q^{(n)}_{\mathbf{x}\mathbf{y}}).$
(31)

Throughout this section, $(\mathbf{X},\mathbf{Y})$ will represent $n$ i.i.d.
repetitions of the rv $(X,Y)$.

######  Lemma 7 (Bias of EMI estimator).

The bias

$\displaystyle\operatorname{Bias}({\operatorname{I}}_{\mathsf{EMI}}^{(n)}(\mathbf{X}\wedge\mathbf{Y}))\triangleq\mathbb{E}_{P_{XY}}\left[{{\operatorname{I}}_{\mathsf{EMI}}^{(n)}(\mathbf{X}\wedge\mathbf{Y})}\right]-\operatorname{I}(X\wedge
Y)$

satisfies

$\displaystyle-\log\left({1+\frac{\left|{\mathcal{X}}\right|-1}{n}}\right)\left({1+\frac{\left|{\mathcal{Y}}\right|-1}{n}}\right)$
$\displaystyle\qquad\qquad\leq\operatorname{Bias}({\operatorname{I}}_{\mathsf{EMI}}^{(n)}(\mathbf{X}\wedge\mathbf{Y}))\leq\log\left({1+\frac{\left|{\mathcal{X}}\right|\left|{\mathcal{Y}}\right|-1}{n}}\right).$

###### Proof.

The proof follows immediately from [38, Proposition 1]. ∎

A concentration bound for the estimator
${\operatorname{I}}_{\mathsf{EMI}}^{(n)}$ in 31 using techniques from [2], is
given by

######  Lemma 8.

Given $\epsilon>0$ and for every $n\geq 1$,

$\displaystyle
P_{XY}\left({{\operatorname{I}}_{\mathsf{EMI}}^{(n)}(\mathbf{X}\wedge\mathbf{Y})-\mathbb{E}_{P_{XY}}\left[{{\operatorname{I}}_{\mathsf{EMI}}^{(n)}(\mathbf{X}\wedge\mathbf{Y})}\right]\geq\epsilon}\right)$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad\leq\exp\left({-\frac{2n\epsilon^{2}}{36\log^{2}n}}\right).$

The same bound applies upon replacing
${\operatorname{I}}_{\mathsf{EMI}}^{(n)}(\mathbf{X}\wedge\mathbf{Y})$ by
$-{\operatorname{I}}_{\mathsf{EMI}}^{(n)}(\mathbf{X}\wedge\mathbf{Y})$ above.

###### Proof.

The empirical mutual information
${\operatorname{I}}_{\mathsf{EMI}}^{(n)}:\mathcal{X}^{n}\times\mathcal{Y}^{n}\rightarrow\mathbb{R}^{+}\cup\left\\{{0}\right\\}$
satisfies the bounded differences property, namely

$\displaystyle\max_{\begin{subarray}{c}(\mathbf{x},\mathbf{y})\in\mathcal{X}^{n}\times\mathcal{Y}^{n}\\\
(x_{i}^{\prime},y_{i}^{\prime})\in\mathcal{X}\times\mathcal{Y}\end{subarray}}\bigg{|}{\operatorname{I}}_{\mathsf{EMI}}^{(n)}(\mathbf{x}\wedge\mathbf{y})$
$\displaystyle\qquad-{\operatorname{I}}_{\mathsf{EMI}}^{(n)}((x_{1}^{i-1},x_{i}^{\prime},x_{i+1}^{n})\wedge(y_{1}^{i-1},y_{i}^{\prime},y_{i+1}^{n}))\bigg{|}\leq\frac{6\log
n}{n}$ (32)

for $1\leq i\leq n$, where for $l<k$,
$x_{l}^{k}=(x_{l},x_{l+1},\ldots,x_{k})$.

To see this, we note that changing

$\displaystyle(\mathbf{x},\mathbf{y})=((x_{1},\ldots,x_{n}),(y_{1},\ldots,y_{n}))$
$\displaystyle\qquad\qquad\qquad\rightarrow((x_{1}^{i-1},x_{i}^{\prime},x_{i+1}^{n}),(y_{1}^{i-1},y_{i}^{\prime},y_{i+1}^{n}))$

amounts to changing at most two components in the joint type
$Q_{\mathbf{x}\mathbf{y}}^{(n)}$ and marginal types $Q_{\mathbf{x}}^{(n)}$ and
$Q_{\mathbf{y}}^{(n)}$; in each of these three cases, the probability of one
symbol or one pair of symbols decreases by $1/n$ and that of another increases
by $1/n$. The difference between the corresponding empirical entropies is
given in each case by the sum of two terms. For instance, one such term for
the joint empirical entropy is given by

$\displaystyle\bigg{|}\ Q^{(n)}_{\mathbf{x}\mathbf{y}}(x_{i},y_{i})\log
Q^{(n)}_{\mathbf{x}\mathbf{y}}(x_{i},y_{i})$
$\displaystyle\qquad\qquad-\left({Q^{(n)}_{\mathbf{x}\mathbf{y}}(x_{i},y_{i})-\frac{1}{n}}\right)\log\left({Q^{(n)}_{\mathbf{x}\mathbf{y}}(x_{i},y_{i})-\frac{1}{n}}\right)\bigg{|}.$

Each of these terms is $\leq\log n/n$, using the inequality [2]

$\displaystyle\left|{\frac{j+1}{n}\log\frac{j+1}{n}-\frac{j}{n}\log\frac{j}{n}}\right|\leq\frac{\log
n}{n},\qquad 0\leq j<n.$

The bound in 32 is obtained upon applying the triangle inequality twice in
each of the three mentioned cases. The claim of the lemma then follows by a
standard application of McDiarmid’s Bounded Differences Inequality [44,
Theorem 2.9.1]. ∎

Since we seek to identify the edge with the smallest mutual information across
it, we next present a technical lemma that bounds above the probability that
the estimates of the mutual information between two pairs of rvs are in the
wrong order. Our proof uses Lemma 8. Let $(X,Y)$ and $(X^{\prime},Y^{\prime})$
be two pairs of rvs with pmfs $P_{XY}$ and $P_{X^{\prime}Y^{\prime}}$,
respectively, on the (common) alphabet $\mathcal{X}\times\mathcal{Y}$, such
that $\operatorname{I}(X\wedge Y)<\operatorname{I}(X^{\prime}\wedge
Y^{\prime})$. Let

$\displaystyle\Delta=\operatorname{I}(X^{\prime}\wedge
Y^{\prime})-\operatorname{I}(X\wedge Y)>0.$ (33)

By Lemma 7, ${\operatorname{I}}_{\mathsf{EMI}}^{(n)}$ is asymptotically
unbiased and, in particular, we can make
$\operatorname{Bias}(\operatorname{I}_{\mathsf{EMI}}^{(n)}(\mathbf{X}\wedge\mathbf{Y})),\operatorname{Bias}(\operatorname{I}_{\mathsf{EMI}}^{(n)}(\mathbf{X}^{\prime}\wedge\mathbf{Y}^{\prime}))<\Delta/2$
by choosing $n$ large enough, for instance,

$\displaystyle
n>\max\left\\{{\frac{\left|{\mathcal{X}}\right|^{2}-1}{2^{\Delta/2}-1},\frac{\left|{\mathcal{X}}\right|-1}{2^{\Delta/4}-1}}\right\\}.$
(34)

The upper bound on the probability of ordering error depends on the bias of
${\operatorname{I}}_{\mathsf{EMI}}^{(n)}$ and decreases with decreasing bias.

######  Lemma 9.

With $(X,Y)$, $(X^{\prime},Y^{\prime})$ and $n$ as in 34,

$\displaystyle
P\left({\operatorname{I}^{(n)}_{\mathsf{EMI}}(\mathbf{X}\wedge\mathbf{Y})\geq\operatorname{I}^{(n)}_{\mathsf{EMI}}(\mathbf{X}^{\prime}\wedge\mathbf{Y}^{\prime})}\right)$
$\displaystyle\leq
2\max\left\\{\exp\left({-\frac{2n\left({{\Delta}/{2}-\operatorname{Bias}\left({\operatorname{I}^{(n)}_{\mathsf{EMI}}(\mathbf{X}\wedge\mathbf{Y})}\right)}\right)^{2}}{36\log^{2}n}}\right),\right.$
$\displaystyle\qquad\qquad\left.\exp\left({-\frac{2n\left({{\Delta}/{2}-\operatorname{Bias}\left({\operatorname{I}^{(n)}_{\mathsf{EMI}}(\mathbf{X}^{\prime}\wedge\mathbf{Y}^{\prime})}\right)}\right)^{2}}{36\log^{2}n}}\right)\right\\}.$

###### Proof.

Recalling 33, we have

$\displaystyle
P\left({\operatorname{I}^{(n)}_{\mathsf{EMI}}(\mathbf{X}\wedge\mathbf{Y})\geq\operatorname{I}^{(n)}_{\mathsf{EMI}}(\mathbf{X}^{\prime}\wedge\mathbf{Y}^{\prime})}\right)$
$\displaystyle=P\left(\operatorname{I}^{(n)}_{\mathsf{EMI}}(\mathbf{X}\wedge\mathbf{Y})\right.$
$\displaystyle\left.\qquad\qquad-\operatorname{I}(X\wedge
Y)-\operatorname{I}^{(n)}_{\mathsf{EMI}}(\mathbf{X}^{\prime}\wedge\mathbf{Y}^{\prime})+\operatorname{I}(X^{\prime}\wedge
Y^{\prime})\geq\Delta\right)$ $\displaystyle\leq
P\left({\operatorname{I}^{(n)}_{\mathsf{EMI}}(\mathbf{X}\wedge\mathbf{Y})-\operatorname{I}(X\wedge
Y)\geq\Delta/2}\right)$
$\displaystyle\qquad\quad+P\left({\operatorname{I}^{(n)}_{\mathsf{EMI}}(\mathbf{X}^{\prime}\wedge\mathbf{Y}^{\prime})-\operatorname{I}(X^{\prime}\wedge
Y^{\prime})\leq-\Delta/2}\right)$ (35)

Using Lemma 8, and in view of 33, 34,

$\displaystyle
P\left({\operatorname{I}^{(n)}_{\mathsf{EMI}}(\mathbf{X}\wedge\mathbf{Y})-\operatorname{I}(X\wedge
Y)\geq\Delta/2}\right)$
$\displaystyle=P\Big{(}\operatorname{I}^{(n)}_{\mathsf{EMI}}(\mathbf{X}\wedge\mathbf{Y})-\mathbb{E}\left[{\operatorname{I}^{(n)}_{\mathsf{EMI}}(\mathbf{X}\wedge\mathbf{Y})}\right]$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\geq\Delta/2-\operatorname{Bias}\left({\operatorname{I}^{(n)}_{\mathsf{EMI}}(\mathbf{X}\wedge\mathbf{Y})}\right)\Big{)}$
$\displaystyle\leq\exp\left({-\frac{2n\left({{\Delta}/{2}-\operatorname{Bias}\left({\operatorname{I}^{(n)}_{\mathsf{EMI}}(\mathbf{X}\wedge\mathbf{Y})}\right)}\right)^{2}}{36\log^{2}n}}\right),$
(36)

and similarly,

$\displaystyle P\left({\operatorname{I}(X^{\prime}\wedge
Y^{\prime})-\operatorname{I}^{(n)}_{\mathsf{EMI}}(\mathbf{X}^{\prime}\wedge\mathbf{Y}^{\prime})\geq\Delta/2}\right)$
$\displaystyle\leq\exp\left({-\frac{2n\left({{\Delta}/{2}-\operatorname{Bias}\left({\operatorname{I}^{(n)}_{\mathsf{EMI}}(\mathbf{X}^{\prime}\wedge\mathbf{Y}^{\prime})}\right)}\right)^{2}}{36\log^{2}n}}\right).$
(37)

The claimed bound follows by using 36 and 37 in 35. ∎

###  V-B Bandit algorithm for estimating $\operatorname{SI}(X_{\mathcal{M}})$

The following bandit-based method identifies the best arm pair corresponding
to the edge of the MCT across which mutual information is minimal. For an
introduction to the fundamentals of bandit algorithms, see [30].

In the parlance of banditry, the environment has $m$ arms, one arm
corresponding to each vertex in $\mathcal{G}=(\mathcal{M},\mathcal{E})$. The
agent can pull, in any step, two arms that are connected by an edge in
$\mathcal{E}$. Each action of the agent is specified by the pair $(i,j)$,
$1\leq i<j\leq m$, $(i,j)\in\mathcal{E}$, with associated reward being the
realizations $(X_{i}=x_{i},X_{j}=x_{j})$. The agent is allowed to pull a total
of $N$ pairs of arms, say, using _uniform sampling_ , where $N$ will be
specified below. A pulling of a pair of arms can be viewed also as pulling the
corresponding connecting edge, thereby rendering it a traditional stochastic
bandit problem. We resort to a uniform sampling strategy for the sake of
simplicity.

######  Definition 6 (Uniform sampling).

In uniform sampling, pairs of rvs corresponding to edges of the tree are
sampled equally often. Specifically, each pair of rvs $(X_{i},X_{j})$,
$(i,j)\in\mathcal{E}$, is sampled $n$ times over nonoverlapping time instants.
Hence, an agent pulls a total of $N$ pairs of arms, where
$N=\left|{\mathcal{E}}\right|n$.

By means of these actions, the agent seeks to form estimates of all two-
dimensional marginal pmfs $P_{X_{i}X_{j}}$ and of the corresponding
$\operatorname{I}(X_{i}\wedge X_{j})$ for $(i,j)$ as above, and subsequently
identify $(\bar{i},\bar{j})\in\mathcal{E}$ (see Remark 6). Let
$X_{\mathcal{M}}^{N}$ denote $N$ i.i.d. repetitions of
$X_{\mathcal{M}}=(X_{1},\ldots,X_{m})$. Specifically, the agent must produce
an estimate $\hat{e}_{N}=\hat{e}_{N}(X_{\mathcal{M}}^{N})\in\mathcal{E}$ of
$(\bar{i},\bar{j})\in\mathcal{E}$ at the conclusion of $N$ steps so as to
minimize the error probability $P(\hat{e}_{N}\neq(\bar{i},\bar{j}))$. The
following notation is used. Write

$\displaystyle\operatorname{I}(i\wedge j)=\operatorname{I}(X_{i}\wedge
X_{j}),\quad(i,j)\in\mathcal{E}$

for simplicity, and let

$\displaystyle{\operatorname{I}}_{\mathsf{EMI}}^{(n)}(i\wedge
j)\triangleq{\operatorname{I}}_{\mathsf{EMI}}^{(n)}(\mathbf{X}_{i}\wedge\mathbf{X}_{j})$

be the estimate of $\operatorname{I}(i\wedge j)$. At the end of
$N=\left|{\mathcal{E}}\right|n$ steps, set

$\displaystyle\hat{e}(X_{\mathcal{M}}^{N})=\arg\min_{(i,j)\in\mathcal{E}}{\operatorname{I}}_{\mathsf{EMI}}^{(n)}(i,j)=(i^{*},j^{*}),\text{
say}$ (38)

with ties being resolved arbitrarily. Correspondingly, the estimate of shared
information is

$\displaystyle\operatorname{SI}_{\mathsf{EMI}}^{(N)}(X_{\mathcal{M}}^{N})\triangleq{\operatorname{I}}_{\mathsf{EMI}}^{(n)}(i^{*}\wedge
j^{*}).$ (39)

Denote

$\displaystyle\Delta_{ij}=\operatorname{I}(X_{i}\wedge
X_{j})-\operatorname{I}(X_{\bar{i}},X_{\bar{j}}),\qquad(i,j)\in\mathcal{E}$

and

$\displaystyle\Delta_{1}=\min_{\begin{subarray}{c}(i,j)\in\mathcal{E}\\\
(i,j)\neq(\bar{i},\bar{j})\end{subarray}}\operatorname{I}(X_{i}\wedge
X_{j})-\operatorname{I}(X_{\bar{i}}\wedge X_{\bar{j}}),$

where the latter is the difference between the second-lowest and lowest mutual
information across edges in $\mathcal{E}$. Note that $\Delta_{1}>0$ by the
assumed uniqueness of the minimizing edge $(\bar{i},\bar{j})$.

The shared information estimate
$\operatorname{SI}_{\mathsf{EMI}}^{(N)}(X_{\mathcal{M}}^{N})$ converges almost
surely and in the mean. This is shown in Theorem 11 below. To that end, we
first provide an upper bound for the probability of arm misidentification with
uniform sampling.

######  Proposition 10.

For uniform sampling, the probability of error in identifying the optimal pair
of arms is

$\displaystyle
P\left({\hat{e}_{N}(X_{\mathcal{M}}^{N})\neq(\bar{i},\bar{j})}\right)\leq
2\left|{\mathcal{E}}\right|\exp\left({\frac{-(N/\left|{\mathcal{E}}\right|)\Delta_{1}^{2}}{648\log^{2}(N/\left|{\mathcal{E}}\right|)}}\right)$

for all

$\displaystyle
N>\left|{\mathcal{E}}\right|\max\left\\{{\frac{\left|{\mathcal{X}}\right|^{2}-1}{2^{\Delta_{1}/3}-1},\frac{\left|{\mathcal{X}}\right|-1}{2^{\Delta_{1}/6}-1}}\right\\}.$
(40)

###### Proof.

With $N=\left|{\mathcal{E}}\right|n$, let $x_{\mathcal{M}}^{N}$ represent a
realization of $X_{\mathcal{M}}^{N}$. For each $(i,j)\in\mathcal{E}$, the
agent computes the empirical mutual information estimate
$\operatorname{I}_{\mathsf{EMI}}^{(n)}(\mathbf{x}_{i}\wedge\mathbf{x}_{j})$ of
$\operatorname{I}(X_{i}\wedge X_{j})$. Note that the sampling of arm pairs
occurs over nonoverlapping time instants. By Lemma 7 and 34

$\displaystyle\left|{\operatorname{Bias}(\operatorname{I}_{\mathsf{EMI}}^{(n)}(i\wedge
j))}\right|$
$\displaystyle\leq\frac{\Delta_{1}}{3}\leq\frac{\Delta_{ij}}{3}<\frac{\Delta_{ij}}{2}\quad\text{for
$(i,j)\neq(\bar{i},\bar{j})$},$

for all $N$ as in 40. Then, we have

$\displaystyle
P\left({\hat{e}_{N}(X_{\mathcal{M}}^{N})\neq(\bar{i},\bar{j})}\right)$
$\displaystyle=P\left({\operatorname{I}^{(n)}_{\mathsf{EMI}}(\bar{i}\wedge\bar{j})\geq\operatorname{I}^{(n)}_{\mathsf{EMI}}({i}\wedge{j})\text{
for some $(i,j)\neq(\bar{i},\bar{j})$}}\right)$
$\displaystyle\leq\sum_{(i,j)\neq(\bar{i},\bar{j})}P\left({\operatorname{I}^{(n)}_{\mathsf{EMI}}(\bar{i}\wedge\bar{j})\geq\operatorname{I}^{(n)}_{\mathsf{EMI}}({i}\wedge{j})}\right)$
$\displaystyle\leq\sum_{(i,j)\neq(\bar{i},\bar{j})}2\exp\left({\frac{-n\Delta_{ij}^{2}}{648\log^{2}n}}\right),\qquad\text{by
\lx@cref{creftypecap~refnum}{lem:estim}}$ $\displaystyle\leq
2\left|{\mathcal{E}}\right|\exp\left({\frac{-(N/\left|{\mathcal{E}}\right|)\Delta_{1}^{2}}{648\log^{2}(N/\left|{\mathcal{E}}\right|)}}\right).\qed$

######  Theorem 11.

For uniform sampling (as in Definition 6), the estimate
$\operatorname{SI}_{\mathsf{EMI}}^{(N)}(X_{\mathcal{M}}^{N})$ converges as
$N\rightarrow\infty$ to $\operatorname{SI}(X_{\mathcal{M}})$ almost surely and
in the mean.

###### Proof.

Let $0<\epsilon<\Delta_{1}$. By 34, we can choose $n$ large enough such that
$\operatorname{Bias}(\operatorname{I}_{\mathsf{EMI}}^{(n)}(\bar{i}\wedge\bar{j}))<\epsilon/2$
(see Remark 6). For all such $n$,

$\displaystyle
P\left({\left|{\operatorname{SI}_{\mathsf{EMI}}^{(N)}(X_{\mathcal{M}})-\operatorname{SI}(X_{\mathcal{M}})}\right|>\epsilon}\right)$
$\displaystyle\leq
P\left({\left|{\operatorname{SI}_{\mathsf{EMI}}^{(N)}(X_{\mathcal{M}}^{N})-\operatorname{I}(\bar{i}\wedge\bar{j})}\right|>\epsilon,\hat{e}_{N}(X_{\mathcal{M}}^{N})=(\bar{i},\bar{j})}\right)$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad+P\left({\hat{e}_{N}(X_{\mathcal{M}}^{N})\neq(\bar{i}\wedge\bar{j})}\right)$
$\displaystyle\leq
P\left({\left|{\operatorname{I}_{\mathsf{EMI}}^{(n)}(\bar{i}\wedge\bar{j})-\operatorname{I}(\bar{i}\wedge\bar{j})}\right|>\epsilon}\right)+P\left({\hat{e}_{N}(X_{\mathcal{M}}^{N})\neq(\bar{i},\bar{j})}\right)$
$\displaystyle=P\bigg{(}\bigg{|}\operatorname{I}_{\mathsf{EMI}}^{(n)}(\bar{i}\wedge\bar{j})-\mathbb{E}\left[{{\operatorname{I}_{\mathsf{EMI}}^{(n)}(\bar{i}\wedge\bar{j})}}\right]$
$\displaystyle\qquad\qquad\qquad\qquad+\mathbb{E}\left[{{\operatorname{I}_{\mathsf{EMI}}^{(n)}(\bar{i}\wedge\bar{j})}}\right]-\operatorname{I}(\bar{i}\wedge\bar{j})\bigg{|}>\epsilon\bigg{)}$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad+P\left({\hat{e}_{N}(X_{\mathcal{M}}^{N})\neq(\bar{i},\bar{j})}\right)$
$\displaystyle\leq
P\bigg{(}\left|{\operatorname{I}_{\mathsf{EMI}}^{(n)}(\bar{i}\wedge\bar{j})-\mathbb{E}\left[{{\operatorname{I}_{\mathsf{EMI}}^{(n)}(\bar{i}\wedge\bar{j})}}\right]}\right|$
$\displaystyle\qquad\qquad\qquad\qquad+\left|{\operatorname{Bias}\left({\operatorname{I}_{\mathsf{EMI}}^{(n)}(\bar{i}\wedge\bar{j})}\right)}\right|>\epsilon\bigg{)}$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad+P\left({\hat{e}_{N}(X_{\mathcal{M}}^{N})\neq(\bar{i},\bar{j})}\right)$
$\displaystyle\leq\exp\left({\frac{-2(N/\left|{\mathcal{E}}\right|)(\epsilon/2)^{2}}{36\log^{2}(N/\left|{\mathcal{E}}\right|)}}\right)$
$\displaystyle\qquad\qquad\qquad\qquad+2\left|{\mathcal{E}}\right|\exp\left({\frac{-(N/\left|{\mathcal{E}}\right|)\Delta_{1}^{2}}{648\log^{2}(N/\left|{\mathcal{E}}\right|)}}\right)$
(41)

by Lemma 8 and Proposition 10. Almost sure convergence follows from 41 and the
Borel-Cantelli Lemma (cf. e.g., [29, Lemma 7.3]); and furthermore, since
$\operatorname{SI}_{\mathsf{EMI}}^{(N)}(X_{\mathcal{M}}^{N})\leq\log\left|{\mathcal{X}}\right|$
for all $N$, almost sure convergence implies convergence in the mean by the
Dominated Convergence Theorem (cf. e.g., [29, Theorem 3.27]). ∎

The following corollary specifies the sample complexity of
$\operatorname{SI}^{(N)}_{\mathsf{EMI}}$ in terms of a minimum requirement on
$N$ for which the estimation error is small with high probability.

######  Corollary 12.

For $0<\epsilon<1/2$ and $\delta<1/e$, we have

$\displaystyle
P\left({\left|{\operatorname{SI}_{\mathsf{EMI}}^{(N)}(X_{\mathcal{M}}^{N})-\operatorname{SI}(X_{\mathcal{M}})}\right|>\epsilon}\right)\leq\delta$

for sample complexity $N=N(\epsilon,\delta)$ that obeys222The approximate form
of 42 considers only the significant terms depending on
$\left|{\mathcal{X}}\right|$, $\left|{\mathcal{E}}\right|$, $\Delta_{1}$,
$\epsilon$ and $\delta$.

$\displaystyle N$
$\displaystyle\gtrsim\left|{\mathcal{E}}\right|\left[\frac{\left|{\mathcal{X}}\right|}{\epsilon}+\frac{1}{\epsilon^{2}}\ln\left({\frac{1}{\delta}}\right)\log^{2}\left({\frac{1}{\epsilon^{2}}\ln\left({\frac{1}{\delta}}\right)}\right)\right.$
$\displaystyle\qquad\left.+\frac{1}{\Delta_{1}^{2}}\ln\left({\frac{\left|{\mathcal{E}}\right|}{\delta}}\right)\log\left({\frac{1}{\Delta_{1}^{2}}\ln\left({\frac{\left|{\mathcal{E}}\right|}{\delta}}\right)}\right)\right.$
$\displaystyle\qquad\left.+\frac{1}{\Delta_{1}^{2}}\ln\left({\frac{\left|{\mathcal{E}}\right|}{\delta}}\right)\log^{2}\left({\frac{1}{\Delta_{1}^{2}}\ln\left({\frac{\left|{\mathcal{E}}\right|}{\delta}}\right)}\right)\right].$
(42)

The proof of the corollary relies on the following technical lemma, which is
similar in spirit to [40, Lemma A.1].

######  Lemma 13.

It holds that

$\displaystyle x\geq c\ln^{2}x,\quad c\geq 1,\ x\geq\max\left\\{{1,4c\ln
2c+16c\ln^{2}c}\right\\}.$

###### Proof.

See Appendix C. ∎

###### Proof of Corollary 12.

From 41,

$\displaystyle
P\left({\left|{\operatorname{SI}_{\mathsf{EMI}}^{(N)}(X_{\mathcal{M}}^{N})-\operatorname{SI}(X_{\mathcal{M}})}\right|>\epsilon}\right)\leq\delta,$

for $n=N/\left|{\mathcal{E}}\right|$ satisfying

$\displaystyle n\geq\frac{\left|{\mathcal{X}}\right|}{\epsilon},\
\frac{n}{\log^{2}n}\geq\frac{1}{\epsilon^{2}}\ln\left({\frac{1}{\delta}}\right),\
\frac{n}{\log^{2}n}\geq\frac{1}{\Delta_{1}^{2}}\ln\left({\frac{\left|{\mathcal{E}}\right|}{\delta}}\right)$
(43)

up to numerical constant factors. Each of the inequalities in 43 yields one or
more lower bounds for $n=N/\left|{\mathcal{E}}\right|$; the first does so
directly, and the latter two upon writing them as $n\geq c\log^{2}n$ (where
$c$ does not depend on $n$) and using Lemma 13. The conditions on $\epsilon$
and $\delta$ in Corollary 12, allow us to drop one of the bounds since it is
always weaker than another. Combining all the lower bounds obtained from 43
and using $N=\left|{\mathcal{E}}\right|n$ finally results in 42. ∎

##  VI Closing Remarks

While the Hammersley-Clifford Theorem [31, Theorem 3.9] can be used to show
the equivalence in Theorem 3 between the MCT definition and the global Markov
property, when the joint pmf of $X_{\mathcal{M}}$ is strictly positive, we
show for an MCT that it holds even for pmfs that are _not_ strictly positive.
The tree structure plays a material role in our proof. In particular,
agglomeration of connected subsets of an MCT form an MCT as in Definition 3
and Lemma 2. The MCT property only involves verifying the Markov condition 10
or 11 for each edge in the tree, and therefore is easier to check than the
global Markov property 16. Joint pmfs that are not strictly positive arise in
applications such as function computation when a subset of rvs are determined
by another subset.

Theorem 6 shows that for an MCT, a simple 2-partition achieves the minimum in
Definition 1. While the result in Theorem 6 was known [21], our proof uses new
techniques and further implies that for _any_ partition $\pi$ with
disconnected atoms, there is a partition with connected atoms that has
$\operatorname{\mathcal{I}\,}$-value (see 2) less than or equal to that of
$\pi$. This structural property is stronger than that needed for proving
Theorem 6.

Our proof technique for Theorem 6 can serve as a stepping stone for analyzing
SI for more complicated graphical models in which the underlying graph is not
a tree; see [4]. In particular, the tree structure was used in the proof of
Theorem 6 only in Step 1 and 25 in Step 2.

In Section V, we have presented an algorithm for best-arm identification with
biased (and asymptotically unbiased) estimates. A uniform sampling strategy
and the empirical mutual information estimator were chosen for simplicity.
Using bias-corrected estimators like the Miller-Madow or jack-knifed estimator
for mutual information [38] would improve the bias performance of the
algorithm. However, it hurts the constant in the bounded differences
inequality that appears in Lemma 8. Polynomial approximation-based estimators
[27] could also improve sample complexity. Moreover, a successive rejects
algorithm [47], [6] could yield a better sample complexity than uniform
sampling for a fixed estimator, as hinted by [47], [6] in different settings.
The precise tradeoff afforded by the choice of a better estimator remains to
be understood, as does the sample complexity of more refined algorithms for
best arm identification in our setting. Both demand a converse result that
needs to take into account estimator bias; this remains under study in our
current work. A converse would also settle the question of optimality of the
$\exp(-O(N/\log^{2}N))$ decay in the probability of error in Proposition 10.

##  Appendix A Proof of Lemma 1

We have

$\displaystyle\operatorname{I}(X_{\mathcal{B}(i\leftarrow j)}\wedge
X_{\mathcal{B}(j\leftarrow i)})$ $\displaystyle=\operatorname{I}(X_{i}\wedge
X_{j})+\operatorname{I}(X_{i}\wedge X_{\mathcal{B}(j\leftarrow
i)\setminus\left\\{{j}\right\\}}\,|\,X_{j})$
$\displaystyle\qquad\qquad+\operatorname{I}(X_{\mathcal{B}(i\leftarrow
j)\setminus\left\\{{i}\right\\}}\wedge X_{j}\,|\,X_{i})$
$\displaystyle\qquad\qquad\qquad+\operatorname{I}(X_{\mathcal{B}(i\leftarrow
j)\setminus\left\\{{i}\right\\}}\wedge X_{\mathcal{B}(j\leftarrow
i)\setminus\left\\{{j}\right\\}}\,|\,X_{i},X_{j})$
$\displaystyle=\operatorname{I}(X_{i}\wedge
X_{j})+\operatorname{I}(X_{\mathcal{B}(i\leftarrow
j)\setminus\left\\{{i}\right\\}}\wedge X_{\mathcal{B}(j\leftarrow
i)\setminus\left\\{{j}\right\\}}\,|\,X_{i},X_{j})$
$\displaystyle=\operatorname{I}(X_{i}\wedge
X_{j})+\operatorname{H}(X_{\mathcal{B}(i\leftarrow
j)\setminus\left\\{{i}\right\\}}\,|\,X_{i})$
$\displaystyle\qquad\qquad\qquad\qquad-\operatorname{H}(X_{\mathcal{B}(i\leftarrow
j)\setminus\left\\{{i}\right\\}}\,|\,X_{i},X_{\mathcal{B}(j\leftarrow i)})$
(44)

where the previous two inequalities are by 11.

The claim of Lemma 1 would follow from 44 upon showing that

$\displaystyle\operatorname{H}(X_{\mathcal{B}(i\leftarrow
j)\setminus\left\\{{i}\right\\}}\,|\,X_{i},X_{\mathcal{B}(j\leftarrow
i)})=\operatorname{H}(X_{\mathcal{B}(i\leftarrow
j)\setminus\left\\{{i}\right\\}}\,|\,X_{i}).$ (45)

Without loss of generality, set $j$ to be the root of the tree; this defines a
_directed_ tree whose leaves are from among the vertices (in $\mathcal{M}$)
with no descendants. Denote the parent of $i^{\prime}$ in the (directed) tree
by $p(i^{\prime})$. Note that $p(i)=j$ in 45. We shall use induction on the
_height_ of $i^{\prime}$, i.e., the maximum distance of $i^{\prime}$ from a
leaf of the directed tree, to show that

$\displaystyle\operatorname{H}(X_{\mathcal{B}(i^{\prime}\leftarrow
p(i^{\prime}))\setminus\left\\{{i^{\prime}}\right\\}}\,|\,X_{i^{\prime}},X_{\mathcal{B}(p(i^{\prime})\leftarrow
i^{\prime})})$
$\displaystyle\qquad\qquad\qquad\qquad\qquad=\operatorname{H}(X_{\mathcal{B}(i^{\prime}\leftarrow
p(i^{\prime}))\setminus\\{i^{\prime}\\}}\,|\,X_{i^{\prime}}),$ (46)

which proves 45 upon setting $i^{\prime}=i$ and $p(i^{\prime})=p(i)=j$.

First, assume that $i^{\prime}$ is a leaf. Then
$\mathcal{B}(i^{\prime}\leftarrow
p(i^{\prime}))\setminus\left\\{{i^{\prime}}\right\\}=\varnothing$ and 46 holds
trivially.

Figure 3: Schematic for proof of 46.

Next, assume the induction hypothesis that 46 is true for all vertices at
height $<h$, and consider a vertex $i^{\prime}$ at height $h$. Let
$i^{\prime}$ have children $1,\ldots,t$; each of these vertices is the root of
subtree $T_{\tau}=\mathcal{B}(\tau\leftarrow i^{\prime})$, $1\leq\tau\leq t$.
See Figure 3. Further, each vertex $\tau$, $1\leq\tau\leq t$, has height $<h$.
Then in 46,

$\displaystyle\operatorname{H}(X_{\mathcal{B}(i^{\prime}\leftarrow
p(i^{\prime}))\setminus\left\\{{i^{\prime}}\right\\}}\,|\,X_{i^{\prime}},X_{\mathcal{B}(p(i^{\prime})\leftarrow
i^{\prime})})$
$\displaystyle=\operatorname{H}\left({(X_{T_{\tau}\setminus\left\\{{\tau}\right\\}},X_{\tau})_{1\leq\tau\leq
t}\,|\,X_{i^{\prime}},X_{\mathcal{B}(p(i^{\prime})\leftarrow
i^{\prime})}}\right)$
$\displaystyle=\sum_{\tau=1}^{t}\left[\operatorname{H}\left({X_{\tau}\,|\,\left({X_{T_{\sigma}}}\right)_{1\leq\sigma\leq\tau-1},X_{i^{\prime}},X_{\mathcal{B}(p(i^{\prime})\leftarrow
i^{\prime})}}\right)\right.$
$\displaystyle\left.+\operatorname{H}\left({X_{T_{\tau}\setminus\left\\{{\tau}\right\\}}\,|\,X_{\tau},\left({X_{T_{\sigma}}}\right)_{1\leq\sigma\leq\tau-1},X_{i^{\prime}},X_{\mathcal{B}(p(i^{\prime})\leftarrow
i^{\prime})}}\right)\right].$ (47)

In 47, for each $\tau$, $1\leq\tau\leq t$, the first term within
$\left[{\cdot}\right]$ is

$\displaystyle\operatorname{H}\left({X_{\tau}\,|\,\left({X_{T_{\sigma}}}\right)_{1\leq\sigma\leq\tau-1},X_{i^{\prime}},X_{\mathcal{B}(p(i^{\prime})\leftarrow
i^{\prime})}}\right)$
$\displaystyle\qquad=\operatorname{H}(X_{\tau}\,|\,X_{i^{\prime}})=\operatorname{H}\left({X_{\tau}\,|\,\left({X_{T_{\sigma}}}\right)_{1\leq\sigma\leq\tau-1},X_{i^{\prime}}}\right)$
(48)

by 11 since

$\displaystyle\left({\bigcup_{\sigma=1}^{\tau-1}T_{\sigma},\mathcal{B}(p(i^{\prime})\leftarrow
i^{\prime})}\right)\subseteq\mathcal{B}(i^{\prime}\leftarrow\tau)$

(see Figure 3). In the second term in $\left[{\cdot}\right]$, we apply the
induction hypothesis to vertex $\tau$ which is at height $h-1$. Note that
$p(\tau)=i^{\prime}$. Since

$\displaystyle
X_{T_{\tau}\setminus\left\\{{\tau}\right\\}}=X_{\mathcal{B}(\tau\leftarrow
p(\tau))\setminus\left\\{{\tau}\right\\}}$
$\displaystyle\quad\text{and}\left({\left({X_{T_{\sigma}}}\right)_{1\leq\sigma\leq\tau-1},X_{i^{\prime}},X_{\mathcal{B}(p(i^{\prime})\leftarrow
i^{\prime})}}\right)\subseteq\mathcal{B}(p(\tau)\leftarrow\tau),$

by the induction hypothesis at vertex $\tau$, we get

$\displaystyle\operatorname{H}\left({X_{T_{\tau}\setminus\left\\{{\tau}\right\\}}\,|\,X_{\tau},\left({X_{T_{\sigma}}}\right)_{1\leq\sigma\leq\tau-1},X_{i^{\prime}},X_{\mathcal{B}(p(i^{\prime})\leftarrow
i^{\prime})}}\right)$
$\displaystyle=\operatorname{H}\left({X_{T_{\tau}\setminus\left\\{{\tau}\right\\}}\,|\,X_{\tau}}\right)$
$\displaystyle=\operatorname{H}\left({X_{T_{\tau}\setminus\left\\{{\tau}\right\\}}\,|\,X_{\tau},\left({X_{T_{\sigma}}}\right)_{1\leq\sigma\leq\tau-1},X_{i^{\prime}}}\right)$
(49)

with the last equality being due to 11. Substituting 48, 49 in 47, we obtain

$\displaystyle\operatorname{H}(X_{\mathcal{B}(i^{\prime}\leftarrow
p(i^{\prime}))\setminus\left\\{{i^{\prime}}\right\\}}\,|\,X_{i^{\prime}},X_{\mathcal{B}(p(i^{\prime})\leftarrow
i^{\prime})})$
$\displaystyle=\sum_{\tau=1}^{t}\left[\operatorname{H}\left({X_{\tau}\,|\,\left({X_{T_{\sigma}}}\right)_{1\leq\sigma\leq\tau-1},X_{i^{\prime}}}\right)\right.$
$\displaystyle\left.\qquad\qquad\qquad+\operatorname{H}\left({X_{T_{\tau}\setminus\left\\{{\tau}\right\\}}\,|\,X_{\tau},\left({X_{T_{\sigma}}}\right)_{1\leq\sigma\leq\tau-1},X_{i^{\prime}}}\right)\right]$
$\displaystyle=\sum_{\tau=1}^{t}\operatorname{H}\left({X_{T_{\tau}}\,|\,\left({X_{T_{\sigma}}}\right)_{1\leq\sigma\leq\tau-1},X_{i^{\prime}}}\right)$
$\displaystyle=\operatorname{H}(X_{\mathcal{B}(i^{\prime}\leftarrow
p(i^{\prime}))\setminus\\{i^{\prime}\\}}\,|\,X_{i^{\prime}})$

(see Figure 3) which is 46. ∎

##  Appendix B Proof of Lemma 4 and Theorem 3

###### Proof of Lemma 4.

Considering first 17, suppose that vertex $i\in\mathcal{M}$ has $k$ neighbor,
with $\mathcal{N}(i)=\left\\{{i_{1},\ldots,i_{k}}\right\\}$, $1\leq k\leq
m-1$. Then

$\displaystyle\mathcal{M}\setminus(\left\\{{i}\right\\}\cup\mathcal{N}(i))=\bigcup_{l=1}^{k}\mathcal{B}(i_{l}\leftarrow
i)\setminus\left\\{{i_{l}}\right\\}.$

The claim of the lemma is

$\displaystyle X_{i}-\\!\\!\circ\\!\\!-\left({X_{i_{u}}}\right)_{1\leq u\leq
k}-\\!\\!\circ\\!\\!-\left({X_{\mathcal{B}(i_{l}\leftarrow
i)\setminus\left\\{{i_{l}}\right\\}}}\right)_{1\leq l\leq k}.$ (50)

We have

$\displaystyle\operatorname{I}\left({X_{i}\wedge\left({X_{\mathcal{B}(i_{l}\leftarrow
i)\setminus\left\\{{i_{l}}\right\\}}}\right)_{1\leq l\leq
k}\,\big{|}\,\left({X_{i_{u}}}\right)_{1\leq u\leq k}}\right)$
$\displaystyle=\sum_{l=1}^{k}\operatorname{I}\left(X_{i}\wedge
X_{\mathcal{B}(i_{l}\leftarrow
i)\setminus\left\\{{i_{l}}\right\\}}\,\big{|}\,\left({X_{\mathcal{B}(i_{j}\leftarrow
i)\setminus\left\\{{i_{j}}\right\\}}}\right)_{1\leq j\leq l-1},\right.$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\left.\left({X_{i_{u}}}\right)_{1\leq
u\leq k}\right)$
$\displaystyle\leq\sum_{l=1}^{k}\operatorname{I}\Big{(}\left[{X_{i},\left({X_{\mathcal{B}(i_{j}\leftarrow
i)\setminus\left\\{{i_{j}}\right\\}}}\right)_{1\leq j\leq
l-1},\left({X_{i_{u}}}\right)_{1\leq u\neq l\leq k}}\right]$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\wedge
X_{\mathcal{B}(i_{l}\leftarrow
i)\setminus\left\\{{i_{l}}\right\\}}\,\big{|}\,X_{i_{l}}\Big{)}.$ (51)

For each $l$, $1\leq l\leq k$, the rvs within $\left[{\cdot}\right]$ above
have indices that lie in $\mathcal{B}(i\leftarrow
i_{l})\setminus\left\\{{i_{l}}\right\\}$. Hence, by Lemma 1 (specifically 13),
each term in the sum in 51 equals zero. This proves 50. See Figure 4.

Figure 4: Schematic for the proof of Lemma 4.

Turning to 18, we have

$\displaystyle\operatorname{I}\left({X_{A}\wedge
X_{\mathcal{M}\setminus(A\cup\mathcal{N}(A))}\,|\,\mathcal{N}(A)}\right)$
$\displaystyle=\operatorname{I}\left({(X_{i},i\in A)\wedge
X_{\mathcal{M}\setminus\bigcup_{u\in
A}\left({\left\\{{u}\right\\}\cup\mathcal{N}(u)}\right)}\,\big{|}\,X_{\bigcup_{v\in
A}\mathcal{N}(v)}}\right)$ $\displaystyle\leq\sum_{i\in
A}\operatorname{I}\left(X_{i}\wedge X_{\bigcup_{j\in
A\setminus\left\\{{i}\right\\}}(\left\\{{j}\right\\}\cup\mathcal{N}(j))},\right.$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\left.X_{\mathcal{M}\setminus\bigcup_{u\in
A}\left({\left\\{{u}\right\\}\cup\mathcal{N}(u)}\right)}\,\big{|}\,X_{\mathcal{N}(i)}\right)$
$\displaystyle=\sum_{i\in A}\operatorname{I}\left(X_{i}\wedge
X_{\left({\bigcup_{j\in
A\setminus\left\\{{i}\right\\}}(\left\\{{j}\right\\}\cup\mathcal{N}(j))}\right)\setminus\mathcal{N}(i)},\right.$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\left.X_{\mathcal{M}\setminus\bigcup_{u\in
A}\left({\left\\{{u}\right\\}\cup\mathcal{N}(u)}\right)}\,\big{|}\,X_{\mathcal{N}(i)}\right)$
$\displaystyle=0$

by 17 since for each $i\in A$,

$\displaystyle\left({\left({\bigcup_{j\in
A\setminus\left\\{{i}\right\\}}(\left\\{{j}\right\\}\cup\mathcal{N}(j))}\right)\setminus\mathcal{N}(i)}\right)$
$\displaystyle\qquad\cup\left({\mathcal{M}\setminus\bigcup_{u\in
A}\left({\left\\{{u}\right\\}\cup\mathcal{N}(u)}\right)}\right)\subseteq\mathcal{M}\setminus(\left\\{{i}\right\\}\cup\mathcal{N}(i)).\qed$

###### Proof of Theorem 3.

The converse claim is immediately true upon choosing: for every
$(i,j)\in\mathcal{E}$, $A=\mathcal{B}(i\leftarrow
j)\setminus\left\\{{i}\right\\}$, $S={i}$, $B=\left\\{{j}\right\\}$.

Turning to the first claim, let

$\displaystyle A=\bigsqcup_{\alpha=1}^{a}A_{\alpha},\quad
B=\bigsqcup_{\beta=1}^{b}B_{\beta},\quad S=\bigsqcup_{\sigma=1}^{s}S_{\sigma}$

be representations in terms of maximally connected subsets of $A$, $B$ and
$S$, respectively. With $N=\mathcal{M}\setminus(A\cup B\cup S)$, let
$N=\sqcup_{\nu=1}^{n}N_{\nu}$ be a decomposition into maximally connected
subsets of $N$. Denote

$\displaystyle\mathcal{A}=\left\\{{A_{\alpha},1\leq\alpha\leq
a}\right\\},\quad\mathcal{B}=\left\\{{B_{\beta},1\leq\beta\leq b}\right\\},$
$\displaystyle\quad\mathcal{S}=\left\\{{S_{\sigma},1\leq\sigma\leq
s}\right\\},\quad\mathcal{N}=\left\\{{N_{\nu},1\leq\nu\leq n}\right\\}.$

Referring to Definition 3 and recalling Lemma 2, the tree
$\mathcal{G}^{\prime}=(\mathcal{M}^{\prime},\mathcal{E}^{\prime})$ with vertex
set
$\mathcal{M}^{\prime}=\mathcal{A}\cup\mathcal{B}\cup\mathcal{S}\cup\mathcal{N}$
and edge set in the manner of Definition 3 constitutes an agglomerated MCT.

Next, we observe that since each $N_{\nu}\in\mathcal{N}$, $1\leq\nu\leq n$, is
maximally connected in N, the neighbors of $N_{\nu}$ in $\mathcal{G}^{\prime}$
cannot be in $\mathcal{N}$. Therefore, neighbors of a given $N_{\nu}$ in
$\mathcal{G}^{\prime}$ that are not in $\mathcal{S}$ must be in $\mathcal{A}$
or $\mathcal{B}$. However, $N_{\nu}$ cannot have a non$\mathcal{S}$ neighbor
in $\mathcal{A}$ and also one in $\mathcal{B}$, for then $A$ and $B$ would not
be separated by $S$ in $\mathcal{G}$. Accordingly, for _each_ $N_{\nu}$ in
$\mathcal{N}$, if its non$\mathcal{S}$ neighbors in $\mathcal{G}^{\prime}$ are
only in $\mathcal{A}$, add $N_{\nu}$ to $\mathcal{A}$; let $N^{\prime}$ be the
union of all such $N_{\nu}$s. Consider $A^{\prime}=A\cup N^{\prime}$ and write
$A^{\prime}=\sqcup_{\alpha=1}^{a^{\prime}}A_{\alpha}^{\prime}$ where the
$A_{\alpha}^{\prime}$s are maximally connected subsets of $A^{\prime}$. Let
$\mathcal{A}^{\prime}=\left\\{{A_{\alpha}^{\prime},1\leq\alpha\leq
a^{\prime}}\right\\}$.

Now note that $\mathcal{A}^{\prime}$ and $\mathcal{B}$ are separated in
$\mathcal{G}^{\prime}$ by $\mathcal{S}$. Thus, to establish 16, it suffices to
show the (stronger) assertion

$\displaystyle
X_{\mathcal{A}^{\prime}}-\\!\\!\circ\\!\\!-X_{\mathcal{S}}-\\!\\!\circ\\!\\!-X_{\mathcal{B}}.$
(52)

By the description of $\mathcal{A}^{\prime}$, each of its components (maximal
subsets of $A^{\prime}$) has its neighborhood in $\mathcal{G}^{\prime}$ that
is contained _fully_ in $\mathcal{S}$. Let
$\tilde{\mathcal{S}}\subseteq\mathcal{S}$ denote the union of all such
neighborhoods. Then, by Lemma 4 (18) applied to the agglomerated tree
$\mathcal{G}^{\prime}$, since there is no edge in $\mathcal{G}^{\prime}$ that
connects any two elements of $\mathcal{A}^{\prime}$,

$\displaystyle
X_{\mathcal{A}^{\prime}}-\\!\\!\circ\\!\\!-X_{\tilde{\mathcal{S}}}-\\!\\!\circ\\!\\!-X_{\mathcal{M}^{\prime}\setminus(\mathcal{A}^{\prime}\cup\tilde{\mathcal{S}})}$

so that

$\displaystyle 0$
$\displaystyle=\operatorname{I}(X_{\mathcal{A}^{\prime}}\wedge
X_{\mathcal{M}^{\prime}\setminus(\mathcal{A}^{\prime}\cup\tilde{\mathcal{S}})}\,|\,X_{\tilde{\mathcal{S}}})$
$\displaystyle=\operatorname{I}(X_{\mathcal{A}^{\prime}}\wedge
X_{\mathcal{M}^{\prime}\setminus(\mathcal{A}^{\prime}\cup\tilde{\mathcal{S}})},X_{\mathcal{S}\setminus\tilde{\mathcal{S}}}\,|\,X_{\tilde{\mathcal{S}}})$
$\displaystyle\geq\operatorname{I}(X_{\mathcal{A}^{\prime}}\wedge
X_{\mathcal{M}^{\prime}\setminus(\mathcal{A}^{\prime}\cup\mathcal{S})}\,|\,X_{\mathcal{S}})$
(53)

since $\tilde{\mathcal{S}}\subseteq\mathcal{S}$. Finally, 53 implies 52 as
$\mathcal{B}\subseteq\mathcal{M}^{\prime}\setminus(\mathcal{A}^{\prime}\cup\mathcal{S})$.
∎

##  Appendix C Proof of Lemma 13

###### Proof.

For $1\leq c\leq 1.2$, $x\geq c\ln^{2}x$ holds unconditionally; so assume that
$c\geq 1.2$. Consider the function $f(x)=x-c\ln^{2}x$. Then, using [40, Lemma
A.1], $x\geq 4c\ln 2c$ implies $x\geq 2c\ln x$ which, in turn, implies
$f^{\prime}(x)\geq 0$. Therefore, for $x\geq 4c\ln c$, $f(x)$ is increasing in
$x$. It is easy to check numerically that $f(16c\ln^{2}c)$ is positive for
$c\geq 1.2$. Thus, for all $x\geq\max\\{4c\ln 2c,16c\ln^{2}c\\}$, $f(x)\geq 0$
and so $x\geq c\ln^{2}x$. ∎

## References

  * [1] S. A. Abdallah and M. D. Plumbley, “A measure of statistical complexity based on predictive information,” _ArXiv_ , vol. abs/1012.1890, 2010.
  * [2] A. Antos and I. Kontoyiannis, “Convergence properties of functional estimates for discrete distributions,” _Random Structures & Algorithms_, vol. 19, no. 3‐4, pp. 163–193, 2001.
  * [3] S. Bhattacharya and P. Narayan, “Shared information for a Markov chain on a tree,” in _2022 IEEE International Symposium on Information Theory_ , 2022, pp. 3049–3054.
  * [4] ——, “Shared information for the cliqueylon graph,” in _2023 IEEE International Symposium on Information Theory (ISIT)_. IEEE, Jun. 2023.
  * [5] V. P. Boda and P. Narayan, “Universal sampling rate distortion,” _IEEE Transactions on Information Theory_ , vol. 64, no. 12, pp. 7742–7758, Dec. 2018\.
  * [6] V. P. Boda and L. A. Prashanth, “Correlated bandits or: How to minimize mean-squared error online,” in _Proceedings of the 36th International Conference on Machine Learning_ , vol. 97. PMLR, 6 2019, pp. 686–694.
  * [7] N. Cesa-Bianchi and G. Lugosi, _Prediction, Learning, and Games_. Cambridge University Press, 2006.
  * [8] C. Chan, “On tightness of mutual dependence upperbound for secret-key capacity of multiple terminals,” _ArXiv_ , vol. abs/0805.3200, 2008.
  * [9] ——, “The hidden flow of information,” _2011 IEEE International Symposium on Information Theory Proceedings_ , pp. 978–982, 2011.
  * [10] ——, “Linear perfect secret key agreement,” in _2011 IEEE Information Theory Workshop_ , 2011, pp. 723–726.
  * [11] C. Chan, A. Al-Bashabsheh, J. B. Ebrahimi, T. Kaced, and T. Liu, “Multivariate mutual information inspired by secret-key agreement,” _Proceedings of the IEEE_ , vol. 103, no. 10, pp. 1883–1913, 2015.
  * [12] C. Chan, A. Al-Bashabsheh, and Q. Zhou, “Agglomerative info-clustering: Maximizing normalized total correlation,” _IEEE Transactions on Information Theory_ , vol. 67, no. 3, pp. 2001–2011, 2021.
  * [13] C. Chan, A. Al-Bashabsheh, Q. Zhou, N. Ding, T. Liu, and A. Sprintson, “Successive omniscience,” _IEEE Transactions on Information Theory_ , vol. 62, no. 6, pp. 3270–3289, 2016.
  * [14] C. Chan, A. Al-Bashabsheh, Q. Zhou, T. Kaced, and T. Liu, “Info-clustering: A mathematical theory for data clustering,” _IEEE Transactions on Molecular, Biological and Multi-Scale Communications_ , pp. 64–91, 2016.
  * [15] C. Chan and L. Zheng, “Mutual dependence for secret key agreement,” in _2010 44th Annual Conference on Information Sciences and Systems (CISS)_ , 2010, pp. 1–6.
  * [16] C. Chow and C. Liu, “Approximating discrete probability distributions with dependence trees,” _IEEE Transactions on Information Theory_ , pp. 462–467, 1968.
  * [17] C. Chow and T. Wagner, “Consistency of an estimate of tree-dependent probability distributions (corresp.),” _IEEE Transactions on Information Theory_ , vol. 19, pp. 369–371, 1973.
  * [18] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, _Introduction to Algorithms, Third Edition_ , 3rd ed. The MIT Press, 2009.
  * [19] T. A. Courtade and T. R. Halford, “Coded cooperative data exchange for a secret key,” _IEEE Transactions on Information Theory_ , vol. 62, pp. 3785–3795, 2016.
  * [20] I. Csiszár and J. Körner, _Information Theory: Coding Theorems for Discrete Memoryless Systems_. Cambridge University Press, 2011.
  * [21] I. Csiszár and P. Narayan, “Secrecy capacities for multiple terminals,” _IEEE Transactions on Information Theory_ , vol. 50, no. 12, pp. 3047–3061, Dec. 2004.
  * [22] W. Feng, N. K. Vishnoi, and Y. Yin, “Dynamic sampling from graphical models,” _Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing_ , 2019.
  * [23] P. Gács and J. Körner, “Common information is far less than mutual information,” _Problems of Control and Information Theory_ , vol. 2, 01 1973\.
  * [24] H.-O. Georgii, _Gibbs Measures and Phase Transitions_. De Gruyter, 2011.
  * [25] V. D. Goppa, “Nonprobabilistic mutual information without memory,” _Problems of Control and Information Theory_ , vol. 4, pp. 97–102, 1975.
  * [26] T. S. Han, “Nonnegative entropy measures of multivariate symmetric correlations,” _Information and Control_ , vol. 36, no. 2, pp. 133–156, 1978\.
  * [27] J. Jiao, K. Venkat, Y. Han, and T. Weissman, “Minimax estimation of functionals of discrete distributions,” _IEEE Transactions on Information Theory_ , vol. 61, no. 5, pp. 2835–2885, 2015.
  * [28] D. Koller and N. Friedman, _Probabilistic Graphical Models: Principles and Techniques - Adaptive Computation and Machine Learning_. The MIT Press, 2009.
  * [29] L. Koralov, Y. Sinai, and Â. Sinaj, _Theory of Probability and Random Processes_ , ser. Universitext (Berlin. Print). Springer, 2007.
  * [30] T. Lattimore and C. Szepesvari, “Bandit algorithms,” 2017.
  * [31] S. L. Lauritzen, _Graphical Models_. Oxford University Press, 1996.
  * [32] W. Liu, G. Xu, and B. Chen, “The common information of n dependent random variables,” _2010 48th Annual Allerton Conference on Communication, Control, and Computing (Allerton)_ , pp. 836–843, 2010.
  * [33] D. J. C. MacKay, _Information Theory, Inference & Learning Algorithms_. USA: Cambridge University Press, 2002.
  * [34] P. Narayan, “Omniscience and secrecy,” 2012, plenary Talk, _IEEE International Symposium on Information Theory_ , Cambridge, MA.
  * [35] P. Narayan and H. Tyagi, “Multiterminal secrecy by public discussion,” _Foundations and Trends in Communications and Information Theory_ , vol. 13, no. 2-3, pp. 129–275, 2016.
  * [36] S. Nitinawarat and P. Narayan, “Perfect omniscience, perfect secrecy, and Steiner tree packing,” _IEEE Transactions on Information Theory_ , vol. 56, pp. 6490–6500, 2010.
  * [37] S. Nitinawarat, C. Ye, A. Barg, P. Narayan, and A. Reznik, “Secret key generation for a pairwise independent network model,” _IEEE Transactions on Information Theory_ , vol. 56, no. 12, p. 6482–6489, 12 2010\.
  * [38] L. Paninski, “Estimation of entropy and mutual information,” _Neural Computation_ , vol. 15, no. 6, p. 1191–1253, 6 2003.
  * [39] J. Pearl, “Reverend Bayes on inference engines: A distributed hierarchical approach,” in _Proceedings of the Second AAAI Conference on Artificial Intelligence_ , ser. AAAI’82. AAAI Press, 1982, p. 133–136.
  * [40] S. Shalev-Shwartz and S. Ben-David, _Understanding Machine Learning - From Theory to Algorithms._ Cambridge University Press, 2014.
  * [41] H. Tyagi, “Common information and secret key capacity,” _IEEE Transactions on Information Theory_ , vol. 59, pp. 5627–5640, 2013.
  * [42] H. Tyagi and P. Narayan, “How many queries will resolve common randomness?” _IEEE Transactions on Information Theory_ , vol. 59, no. 9, pp. 5363–5378, 2013.
  * [43] H. Tyagi and S. Watanabe, “Converses for secret key agreement and secure computing,” _IEEE Transactions on Information Theory_ , vol. 61, pp. 4809–4827, 2015.
  * [44] R. Vershynin, _High-Dimensional Probability: An Introduction with Applications in Data Science_ , ser. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2018.
  * [45] S. Watanabe, “Information theoretical analysis of multivariate correlation,” _IBM Journal of Research and Development_ , vol. 4, no. 1, pp. 66–82, 1960\.
  * [46] A. Wyner, “The common information of two dependent random variables,” _IEEE Transactions on Information Theory_ , vol. 21, no. 2, pp. 163–179, 1975\.
  * [47] J. yves Audibert, S. Bubeck, and R. Munos, “Best arm identification in multi-armed bandits,” in _Proceedings of the Twenty-Third Annual Conference on Learning Theory_ , 2010, pp. 41–53.

Sagnik Bhattacharya received the Bachelor of Technology in Electrical
Engineering from the Indian Institute of Technology Kanpur, India, in 2019. He
is currently a PhD candidate in the Department of Electrical and Computer
Engineering at the University of Maryland, College Park. His research
interests are in information theory, statistical learning, and their practical
applications.
---
Prakash Narayan received the Bachelor of Technology degree in Electrical
Engineering from the Indian Institute of Technology, Madras in $1976$. He
received the M.S. degree in Systems Science and Mathematics in $1978$ and the
D.Sc. degree in Electrical Engineering in $1981$, both from Washington
University, St. Louis, MO. He is Professor of Electrical and Computer
Engineering at the University of Maryland, College Park, with a joint
appointment at the Institute for Systems Research. His research interests are
in network information theory, coding theory, communication theory,
communication networks, statistical learning, and cryptography.
---