A movement is accomplished in six stages

And the seventh brings return.

The seven is the number of the young light

It forms when darkness is increased by one.
Change returns success

Going and coming without error.

Action brings good fortune.

Sunset, sunrise.

Syd Barrett, Chapter 24 (Pink Floyd).

§ INTRODUCTION

We consider the problem of perfectly reconstructing a discrete random variable $X$, based on the knowledge of a finite set $X_{1}$, $X_{2}$,..., $X_{n}$ of deterministic processings or transformations of $X$, denoted $f_i$ such that $X_i = f_i (X)$.
Intuitively, the components $X_i$ are assumed to carry only a partial amount of the “information” present in $X$ and perfect reconstruction of $X$ would only be possible if the combination of the “informations” in $X_{1}$, $X_{2}$,..., $X_{n}$ is enough to contain all the original “information” in $X$.
Such intuitive considerations expressed in the language of information is very common in signal processing and in many other scientific fields; but they were never mathematically formalized  as far as the authors know.
This article aims at formalizing precisely this trivial and vague intuition. Such a task implies, in particular, an accurate definition of “information”.

The classical Shannon's 1948 information theory [17] cannot really answer this question as it is rather a theory of the measure of information rather than of the information itself.
Fortunately, a “true information” theory has also been developed by Claude Shannon in a relatively unknown 1953 article [19], that is not what is generally referred to as “Shannon's information theory.”
Said briefly, the information is there defined as an equivalence class of discrete random variables. A partial order on a set of classes allows one to build a lattice structure called the information lattice, which is made metric by the introduction of two related entropic distances.

“Claude [Shannon] did not like the term `information theory'” recalls Robert Fano, a colleague of Shannon's working at MIT, who died almost century-old just seven years ago. In one of his last interviews [5], he says: “You see, the term 'information theory' suggests that it's a theory about information, but it's not. It's about the transmission of information, not the information. Many people just didn't understand that.”
Fano is of course referring to Shannon's famous theory in his 1948 seminal paper [17] which he entitled “ a mathematical theory of  communication ” – not information.
But very early on, it is the term “information” that prevails. The entropy  $H(X)$ of a discrete random variable  $X$ is presented as the measure of  “information contained in  $X$”, and the notion of mutual information $I(X;Y)$ between two variables $X$ and $Y$, introduced precisely by the same Robert Fano in his course at MIT [4], quickly became central to the teaching of the theory.
Moreover, the very first historical article on the theory, barely three years after its birth (!) is entitled “A history of the theory of information” [2].

This sudden craze for “information” in the early 1950s eventually became somewhat of a bore for Shannon, who in 1956, in his famous editorial The Bandwagon [20] warned against the excesses of such popularity: “It will be all too easy for our somewhat artificial prosperity to collapse overnight when we realize that the use of a few exciting words like information, entropy, redundancy, does not solve all our problems. ”

Under these conditions, it is understandable that Shannon wanted to go further: If several, unrelated, random variables can have the same quantity of information $H$, how can information itself be defined? Shannon presented a very brief summary of his findings (without proofs) at the international congress of mathematicians (ICM) in 1950 [18] and in a small, relatively unknown article [19] published in 1953 in the very first issue of what was to become the IEEE Transactions on information theory.

The remainder of this article is organized as follows.
Section <ref> presents in detail the Shannon theory of the lattice of information with complete proofs,
and Section <ref> does the same for the two entropic distances proposed respectively by Shannon and Rajski.
The corresponding geometric point of view is further developed in Section <ref>.
Two conditions of perfect reconstruction, a necessary one and a sufficient one, are then derived in Section <ref>.
Finally, the condition is applied to five specific examples in Section <ref>.

Sections <ref>, <ref> and Subsection <ref> are a deepening of the article [16] previously published (in French) by four of the authors.

§ WHAT IS INFORMATION? A DETAILED STUDY OF SHANNON'S INFORMATION LATTICE

For simplicity, we consider with Shannon discrete random variables $X$ which take a finite number of values in some alphabet $\mathcal{X}$.
This amounts to considering all the random variables $X: \Omega\to \mathcal{X}$ defined on a given probability space $(\Omega,\mathcal{P}(\Omega),\P)$ where the underlying universe $\Omega$ is finite and $\mathcal{P}(\Omega)$ is the power set of $\Omega$.

§.§ Definition of the “True” Information

Quite arguably, the information contained in a discrete source or random variable $X$ should not be confused with the “measure of quantity of information” such as the entropy $H(X)$.
Shannon's idea [19] is that this information contained in $X$ should in fact be defined as $X$ itself! Of course, any reversible encoding of $X$ must be regarded as the same information, since one moves from one representation to another without loss of information. This amounts, in modern language, to the following definition:
[“True” Information]
The information (contained in) $X$ is the equivalence class of $X$ for the equivalence relation:

\begin{equation}
X\equiv Y \iff Y=f(X) \text{ and } X=g(Y) \text{ a.s. (almost surely)}
\end{equation}

for two deterministic functions $f$ and $g$.

Relation $\equiv$ is evidently reflexive (take $f$, $g$ be the identity function) and symmetric (by permuting the roles of $f$ and $g$ in the definition). It is also transitive by composition: If $X \equiv Y$ and $Y \equiv Z$, there exists $f$, $g$, $h$ and $k$ such that $Y = f(X)$, $X = g(Y)$ and $Y = h(Z)$, $Z = k(Y)$ a.s.; then $X = g(h(Z)) = g \circ h(Z)$ and $Z = k \circ f(X)$ a.s.

$X \equiv Y$ iff (if and only if) there exists a bijective function $h$ such that $Y = h(X)$ a.s.

If $X \equiv Y$, then there exist two deterministic functions $f$ and $g$ such that, $X = f(Y)$ and $Y = g(X)$ a.s. Thus, $X = f(g(X))$ a.s. Then, for every value $X=x$ with non-zero probability, $f \circ g(x) = x$. Hence, $f\circ g$ coincides with the identity function a.s. Since the problem is symmetric in $X$ and $Y$, $g \circ f$ also coincides with the identity function a.s. Thus, $h=g$ is bijective from the set of values that $X$ can take with non-zero probability to the set of values that $Y$ can take with non-zero probability, and we have $Y = g(X)= h(X)$ a.s.

Conversely, if $Y = h(X)$ a.s. with bijective $h$, then $X = h^{-1}(Y)$ a.s., hence $X \equiv Y$.

As suggested by Rajski [14], the equivalence between $X$ and $Y$ can be characterized by way of their joint probability matrix:

[Matrix Characterization]
If we restrain $\Omega$ to the elements of non-zero probability measure, $X \equiv Y$ iff the matrix of joint probabilities $\mathbb{P}(X=x, Y=y)$ is a permutation matrix.

By Proposition <ref>, $X \equiv Y$ iff there exists a bijective function $h$ such that $Y = h(X)$ a.s.
Thus to each outcome of $X$ corresponds exactly one outcome of $Y$ and vice versa, which is equivalent to saying that the matrix of joint probabilities is a permutation matrix.

In the following, we shall note (without possible confusion) $X$ the equivalence class of the variable $X$, and thus $X=Y$ the equality between the two classes $X$ and $Y$ (rather than $X\equiv Y$).

With this definition, it is clear that the equivalence relation is compatible with any functional relation $Y=f(X)$. If $f$ is not bijective, it is tempting to say that there is less information in $Y$ than in $X$. Hence the following partial order.
[Partial Order]

\begin{equation}
X\geq Y \iff Y=f(X)\vspace*{-.5ex} \text{ a.s.}
\end{equation}

for some deterministic function $f$.

We also write $Y\leq X$. We are not necessarily considering real valued variables, so the order $X\geq Y$ has nothing to do with the order in $\mathbb{R}$.

The relation $\geq$ is indeed a partial order on the set of equivalence classes of the relation $\equiv$ defined above.

We first show that the relation $\equiv$ is compatible with the relation $\geq$.
Let $X_{1}$, $X_{2}$ and $Y_{1}$, $Y_{2}$ be such that $X_{1} \equiv X_{2}$ and $Y_{1} \equiv Y_{2}$. Then if $X_{1} \geq Y_{1}$, there exists a deterministic function $f$ such that $Y_{1} = f(X_{1})$ a.s.. Since $X_{1} \equiv X_{2}$, there exists a bijective $h$ such that $X_{1} = h(X_{2})$ a.s., hence $Y_{1} = f \circ h(X_{2})$ a.s. and $X_{2} \geq Y_{1}$. Likewise, since $Y_{1} \equiv Y_{2}$, there exists a bijective $g$ such that $Y_{2} = g(Y_{1})$ a.s., so $Y_{2} = g \circ f \circ h(X_{2})$ a.s., hence $X_{2} \geq Y_{2}$.
This shows that the relation $\geq$ is well defined on the set of equivalence classes of the relation $\equiv$.

We now show that $\geq$ is indeed a partial order:

* Reflexivity: $X = \Id(X)$ so $X \geq X$.

* Antisymmetry: If $X \geq Y$ and $Y \geq X$, $X = f(Y)$ a.s. and $Y = g(X)$ a.s. for deterministic functions $f$ and $g$, so $X \equiv Y$.

* Transitivity: If $X \geq Y$ and $Y \geq Z$, then there exist two deterministic functions $f$ and $g$ such that: $Z = g(Y)$ a.s. and $Y = f(X)$ a.s. Then $Z = g(f(X))$ a.s., hence $X \geq Z$.

§.§ Structure of the Information Lattice: Joint Information; Common Information

Beyond the partial order, Shannon [19] established the natural mathematical structure of information: It is a lattice, i.e. two variables $X,Y$ always admit a maximum $X\lor Y$ and a minimum $X\land Y$. Let us recall that these quantities (necessarily unique if they exist) are defined by the relations

\begin{equation}%\vspace*{-.5ex}
\begin{split}
(X\leq Z \text{ and }  Y\leq Z) \iff X\lor Y \leq Z,  \\
(X\geq Z \text{ and }  Y\geq Z) \iff X\land Y \geq Z.
\end{split}
\end{equation}

Shannon, in his paper [19], used Boolean notations instead, $X+Y$ for $X\lor Y$ and $X\!\cdot\!Y$ for $X\land Y$.

[Joint Information]
The joint information $X\lor Y$ of $X$ and $Y$ is the random pair $X\lor Y=(X,Y)$.

If $X$ and $Y$ are functions of $Z$, then the pair $(X,Y)$ is also a function of $Z$. Conversely, since $X$ and $Y$ are functions of $(X,Y)$, if $(X,Y)$ is a function of $Z$ then so are $X$ and $Y$.

The definition of $X\wedge Y$ (common information) is more difficult and was not made explicit by Shannon. Following Gács and Körner [6], let us adopt the following definition:

We say that $x\in\mathcal{X}$ and $y\in\mathcal{Y}$ communicate, denoted by $x\sim y$, if there exists a path $x y_1 x_1 y_2 \cdots y_nx_n y$ in which all transitions are of non zero probability: $\P(X=x,Y=y_1)>0$, $\P(Y=y_1, X=x_1)>0$, …, $\P(X=x_n, Y=y)>0$.

The relation $\sim$ is an equivalence relation on the set of pairs $(x,y)$ for which $\mathbb{P}(X = x) > 0$ and $\mathbb{P}(Y = y) > 0$.

Reflexivity is obvious.

* Symmetry: If $x \sim y$, taking the path  $x\ldots y$ in the other direction and we have $y \sim x$.

* Transitivity: If $x_{1} \sim y_{1}$, $y_{1} \sim x_{2}$ and $x_{2} \sim y_{2}$, then there exists a path from $x_{1}$ to $y_{1}$, another from $y_{1}$ to $x_{2}$ and a last one from $x_{2}$ to $y_{2}$, whose transitions are of non-zero probabilities. The concatenated path from $x_{1}$ to $y_{2}$ has non zero transition probabilities, hence $x_{1} \sim y_{2}$.

[Communication Class]
The communication class $C(x,y)$ is the equivalence class of $(x,y)$ where $x\sim y$.

[Common Information]
The common information $X\land Y$ of $X$ and $Y$ is $X\land Y=C(X,Y)$.

If $Z=f(X)=g(Y)$ a.s. then $Z$ is constant for each pair $(x,y)$ such that $x\sim y$; in other words $Z$ is a function of the class $C(X,Y)$.

In order to compute the common information between $X$ and $Y$ in practice, one has to fully determine communication classes, which is only possible if there is a finite number of classes, each of which containing a finite number of elements. In other words, $X$ and $Y$ should take a finite number of values. This is the reason why we restrict ourselves to  finitely valued variables in this paper.

As in any lattice, $X\leq Y$ is equivalent to saying that $X\lor Y=Y$ or that $X\land Y=X$.

§.§ Computing Common Information

As shown in the previous section, the definition of common information is not a simple one, but one can compute it efficiently using the following algorithm. Given two variables $X$ and $Y$, this algorithm turns the joint probability matrix of $(X,Y)$ into a block-diagonal matrix where each block corresponds to each communication class.

Let $X$ and $Y$ be two random variables taking values in $\mathcal{X}$ and $\mathcal{Y}$, respectively. Consider the graph $G = (V,E)$ whose vertices $V$ are $\mathcal{X} \cup \mathcal{Y}$, and such that vertices $x$ and $y$ of $V$ are connected by an edge if and only if $\mathbb{P}(X=x, Y=y) > 0$. Hence, $G$ is fully described by the joint probability matrix $\mathbb{P}_{X,Y}$. Furthermore, this is a bipartite graph (no edge connects two vertices $x_{1}$, $x_{2}$ belonging to $\mathcal{X}$ or two vertices $y_{1}$, $y_{2}$ belonging to $\mathcal{Y}$).

Then, the communication classes $C(X,Y)$ correspond to the connected components of $G$. Indeed, a connected component $C$ is a subset of $V$ such that each of its elements is accessible to all the others by a path in the subgraph $(C,E)$. So for any two vertices $x$, $y$ in the connected component $C$, there exists $y_{1}$, $x_{1}$, …, $y_{k}$, $x_{k}$ such that all the edges $(x,y_{1})$, $(y_{1},x_{1})$,…, $(y_{k},x_{k})$, $(x_{k},y)$ belong to $E$, that is all the transition probabilities between these vertices are non-zero, which is equivalent to saying that they belong to the same communication class.
Now, it is known that the connected components of $G$ can be determined by a depth-first search.

We propose an algorithm, whose pseudo-code is given in Fig. <ref>, that takes as input the joint probability matrix $\mathbb{P}_{X,Y}$ and outputs a bloc-diagonal form of $\mathbb{P}_{X,Y}$ representing the common information $X \wedge Y$, an array storing the permutation of the columns of $\mathbb{P}_{X,Y}$ and an array storing the permutation of the rows $\mathbb{P}_{X,Y}$. Since the matrix $\mathbb{P}_{X,Y}$ is sufficient to fully describe $G$, we adapt the depth-first search algorithm to browse the rows and columns of the matrix $\mathbb{P}_{X,Y}$ to find which of its rows and columns must be swapped in order to write this matrix into a block-diagonal form. In this algorithm (Fig. <ref>), the $i$th row of $\mathbb{P}_{X,Y}$ will be represented by the pair $(r,i)$ and the $j$th column by the pair $(c,j)$.

[1]
input $\mathbb{P}_{X,Y}$: $n_R\times n_C$ matrix   Joint probability matrix
$\sigma_R\gets$  array of integers of length $n_R$  Rows permutation vector
$\sigma_C\gets$ array of integers of length $n_C$ Columns permutation vector
$S\gets$ empty stack Stack contains row indices $(r,i)$ or column indices $(c,j)$
push $(r,0)$ into stack $S$  First row put into stack
$\text{\it bottom}\gets 1$ Bottommost row index not yet assigned
$\text{\it up}\gets n_R-1$ Upmost row index that may have nonzero entries
$\text{\it left}\gets 0$ Leftmost column index not yet assigned
$\text{\it right} \gets n_C-1$ Rightmost column index that may have nonzero entries
There is an unmarked row or column
$S$ is not empty
$(s,i) \gets S.pop()$ The $pop()$ operation removes the top stack element and returns it.
$(s,i)$ is not marked
mark $(s,i)$
$s = r$ Current index $i$ is a row index
$\text{\it left}\leq j \leq \text{\it right}$  Scan all columns
$\mathbb{P}_{X,Y}(i,j) > 0$
push $(c,j)$ into stack $S$
$\sigma_C[j] \gets \text{\it left}$; swap columns $\text{\it left}$ and $j$ in $\mathbb{P}_{X,Y}$
$\text{\it left} \gets \text{\it left}+1$
all entries on $i$th row are zeros
$\sigma_R[i] \gets \text{\it up}$; swap rows $i$ and $\text{\it up}$ in $\mathbb{P}_{X,Y}$
$\text{\it up} \gets \text{\it up} - 1$
Current index $i$ is a column index
$\text{\it bottom} \leq j \leq \text{\it up}$ Scan all rows
$\mathbb{P}_{X,Y}(j,i) > 0$
push $(r,j)$ into stack $S$
$\sigma_R[j] \gets \text{\it bottom}$; swap rows $\text{\it bottom}$ and $j$ in $\mathbb{P}_{X,Y}$
$\text{\it bottom} \gets \text{\it bottom}+1$
all entries on $i$th column are zeros
$\sigma_C[i] \gets \text{\it right}$; swap columns $i$ and $\text{\it right}$ in $\mathbb{P}_{X,Y}$
$\text{\it right} \gets \text{\it right} - 1$
Empty Stack
there is an unmarked $i$th row $(r,i)$
push $(r,i)$ into stack $S$
there is an unmarked $j$th column $(c,j)$
push $(c,j)$ into stack $S$
All rows and columns marked
$\mathbb{P}_{X,Y}$, $\sigma_R$, $\sigma_C$

Algorithm to compute the common information

The complexity of this algorithm can be determined as follows. Let $n = \text{Card}(\mathcal{X}) + \text{Card}(\mathcal{Y})$ be the sum of the alphabet sizes on which $X$ and $Y$ take their values, i.e. the sum of the number of rows of $\mathbb{P}_{X,Y}$ and the number of columns of $\mathbb{P}_{X,Y}$.
The algorithm passes through each row and column at most once. Indeed, for the index of a row or column to enter the stack, it must be unmarked, but as soon as we put it on the stack, we mark it. Then, each time the index of a row or a column is unstacked, we look at each coefficient of the corresponding row or column.
Therefore, our algorithm looks at each coefficient of the joint probability matrix $\mathbb{P}_{X,Y}$ exactly once.
Four elementary operations are performed each time we cross a nonzero coefficient. Thus, the algorithm complexity is quadratic in $n$.

Notice that the output of our algorithm gives a visualization of the common information: The stochastic matrix $\P(X=x,Y=y)$ is written, after permutation of rows/columns, in the "block diagonal" form

\begin{equation}\label{eq-matrix}
\P_{X,Y} =
\begin{pmatrix}
C_1   \\
& C_2 &            &  {\text{\Large \bf 0}}\\
&         & \ddots \\
{\text{\Large \bf 0}}  &         &           & C_k  \\
&   &   &   & 0 \\
&   &   &   &   & \ddots \\
& & & & &  & 0\\

\end{pmatrix}
\end{equation}

where $k$, the number of blocks, is maximal. The $k$ rectangular matrices then represent the $k$ different equivalence classes, the probability $\P(C(X,Y)=i)$ being the sum of all entries in block $C_i$.

§.§ Boundedness and Complementedness: Null, Total, and Complementary Information

[Null Information; Total Information]
The information lattice is bounded, i.e., it admits a minimum $0$ and maximum $1$, such that for any $X$, $0\leq X\leq 1$.

* The minimal element $0$ (“null information”) is the equivalence class of all deterministic variables. Thus $X=0$ means that $X$ is a deterministic variable.

* The maximal element $1$ (“total information”) of the lattice is the equivalence class of the identity function $\Id$ on $\Omega$.

If $X$ is any random variable and $Z=c$ a.s. is any deterministic variable, then it is clear that $Z = f(X)$ where $f$ is the constant function $c$. Letting $0$ be the equivalence class of constant variables, one has $0\leq X$ for all $X$.

Also, for any random variable $X$, $X = X \circ \Id$, hence $X \leq \Id$. Letting $1$ be the equivalence class of the identity function on $\Omega$, one has $X\leq 1$ for all $X$.

[Complementary Information]
The information lattice is complemented, i.e., any $X\leq Y$ admits a  complement $Z$ (“complementary information”) such that $X\lor Z=Y$ and $X\land Z=0$.

This $Z$ is the information missing from $X$ to obtain $Y$: It allows $Y$ to be reconstructed from $X$ without requiring more information than necessary. Shannon in [19] did not say how to determine it. The following proof gives an explicit construction:

Since $X\leq  Y$, we simply have $X=X\land Y = C(X,Y)$. Thus, a given class $C(X,Y)=x$ has only one value $X=x$ per class, corresponding in general to several values of $Y$, say, $y^x_1,y^x_2, \ldots,y^x_{k_x}$. Now let $Z\in\{1,\ldots,k_X\}$ be the unique index such that $Y=Y^X_Z$.

By construction, $Z\leq X\lor Y=Y$, and since $X\leq Y$, one also has $X\lor Z\leq Y$. But the formula $Y=Y^X_Z$ shows that $Y\leq X\lor Z$, hence equality $X\lor Z=Y$ holds.

Finally, the value $Z=1$ connects each pair $(x,z)$, so there is only one class according to $(X,Z)$, i.e. $X\land Z=0$.

This construction can be visualized on the stochastic tensor of $(X,Y,Z)$ described in Fig. <ref>.

Construction of the complementary information $Z$ allowing to pass from $X$ to $Y$. The stochastic tensor of $(X,Y,Z)$ representing $\P_{X,Y,Z}$ has nonzero entries marked in red. The distribution $\P_Z$ of $Z$ is obtained by marginalizing the tensor on the $Z$ axis.

The complementary information $Z$ is not uniquely determined by $X$ and $Y$.
In the above construction, it depends on how the values of $Y$ are indexed by the class $X=x$.

§.§ Computing the Complementary Information

Given $X \leq Y$, the algorithm of Fig. <ref> determines a random variable $Z$ corresponding to the complementary information from $X$ to $Y$.

This algorithm takes as input the joint probability matrix $\mathbb{P}_{X,Y}$ in its bloc-diagonal form and outputs the tensor of the joint probability $\mathbb{P}_{X,Y,Z}$ where $X\lor Z=Y$ and $X\land Z=0$.
The tensor is built by spreading the non-zero coefficients of the joint probability matrix $\mathbb{P}_{X,Y}$ on the $Z$-axis as shown in Fig. <ref>.

[1]
input $\mathbb{P}_{X,Y}$: $n_R\times n_C$ matrix Joint probability matrix
$k \gets 0$ Z index

$0 \leq i < nR$
$0 \leq j < nC$
$\mathbb{P}_{X,Y}(i,j) > 0$
$\mathbb{P}_{X,Y,Z}(i,j,k) \gets \mathbb{P}_{X,Y}(i,j)$
$k \gets k+1$
$k \gets 0$

Algorithm for computing the complementary information

The algorithm looks at each coefficient of the joint probability matrix $\mathbb{P}_{X,Y}$ exactly once and performs at most two elementary operations for each coefficient it processes. Therefore, it is quadratic in $n = \text{Card}(\mathcal{X}) + \text{Card}(\mathcal{Y})$ (since the number of coefficients in the matrix $\mathbb{P}_{X,Y}$ is quadratic in $n$).

§.§ Is the Information Lattice a Boolean Algebra?

Interestingly, it was Shannon who, as early as 1938 in his master's thesis, used the Boolean algebra to study relay-based circuits – “the most important master's thesis of the century” for which Shannon received the Alfred Noble prize (not to be confused with the Alfred Nobel Prize!) in 1940. But alas, as Shannon noted, his information lattice is not a Boolean algebra. It would have been one if it were distributive ($\land$ distributive with respect to $\lor$ or vice versa), since a Boolean algebra is, by definition, a distributive complemented bounded lattice.  However:

The information lattice is not distributive.

In any Boolean algebra, the complement is unique. As seen above, this is not the case for the information lattice.

As a direct second proof, we provide an explicit counterexample to distributivity. Consider the probability space $(\Omega,\mathcal{P}(\Omega),\P)$, where $\Omega = \{0, 1, 2, 3\}$ and $\P$ is the uniform probability measure, and define

$X(\omega)=0$ if $\omega$ is even, $X(\omega)=1$ otherwise.

Now let $Z_{1}$, $Z_{2}$ be given as in Table <ref> below.

As we read in the table, $(X\wedge Z_{1}) \vee (X \wedge Z_{2})=0$ is constant while $X \wedge (Z_{1} \vee Z_{2})$ is not. Therefore, $(X\wedge Z_{1}) \vee (X \wedge Z_{2}) \not = X \wedge (Z_{1} \vee Z_{2})$, and  the information lattice is not distributive.

Computation of $X\wedge (Z_{1} \vee Z_{2})$ and of $(X\wedge Z_{1}) \vee (X \wedge Z_{2})$.

$\omega$     0     1     2     3

$X$     0     1     0     1

$Z_{1}$     1     1     2     2

$Z_{2}$     2     1     1     2

$Z_{1}\vee Z_{2}$     (1,2)     (1,1)     (2,1)     (2,2)

$X \wedge (Z_{1}\vee Z_{2})$     0     1     0     1

$X \wedge Z_{1}$     0     0     0     0

$X \wedge Z_{2}$     0     0     0     0

$(X\wedge Z_{1}) \vee (X \wedge Z_{2})$     (0,0)     (0,0)     (0,0)     (0,0)

§ METRIC PROPERTIES OF THE INFORMATION LATTICE

§.§ Information and Information Measures

First of all, it is immediate to check the compatibility of the information lattice with respect to the entropy or the mutual information as measures of information.

Entropy, conditional entropy and mutual information are compatible with the definition of information as an equivalence class.

* Entropy: If $X \equiv Y$, there exist functions $f$ and $g$ such that $Y = f(X)$ a.s., hence $H(Y) \leq H(X)$, and $X = g(Y)$ a.s., hence $H(X) \leq H(Y)$. Thus, $H(X) = H(Y)$.

* Conditional entropy: Let $X_{1} \equiv X_{2}$ with $f$ and $g$ two functions such that $X_{1} = f(X_{2})$ and $X_{2} = g(X_{1})$ a.s. Then $H(X_{1}|Y) = H(f(X_{2})|Y) \leq H(X_{2}|Y)$. Similarly, $H(X_{2}|Y) = H(g(X_{1})|Y) \leq H(X_{1}|Y)$. Therefore $H(X_{1}|Y) = H(X_{2}|Y)$. Finally, if $Y_{1} \equiv Y_{2}$ with  two functions $h$ and $k$ such that $Y_{1} = h(Y_{2})$ and $Y_{2} = k(Y_{1})$ a.s., then, $H(X|Y_{1}) = H(X|h(Y_{2})) \geq H(X|Y_2,h(Y_{2}))=H(X|Y_{2})$ and likewise $H(X|Y_{2}) = H(X|k(Y_{1})) \geq H(X|Y_1,k(Y_{1}))=H(X|Y_{1})$. Therefore $H(X|Y_{1}) = H(X|Y_{2})$.

* Mutual information: Since $I(X;Y) = H(X) - H(X|Y)$, compatibility follows from the two previous cases.

We then have some obvious connections:
[Partial Order and Conditional Entropy]

\begin{equation}
X\leq Y \iff H(X|Y)=0
\end{equation}

In particular, $H$ is “order-preserving” (greater information implies higher entropy):

\begin{equation}
X\leq Y \implies H(X)\leq H(Y).
\end{equation}

Also, $X\leq Y$ with $H(X) = H(Y)$ implies $X = Y$.

Finally $H(X)\geq 0$ for all $X$, with equality $H(X)=0$ iff $X=0$.

$H(X|Y)=0$ means that $H(X|Y=y)=0$ for all $y\in\mathcal{Y}$, which amounts to saying that $X$ is deterministic equal to $f(y)$ given $Y=y$. In other words $X=f(Y)$ a.s.

We then have $H(X)=H(X)-H(X|Y)=I(X;Y)=H(Y)-H(Y|X)\leq H(Y)$.

Next, suppose that $X\leq Y$ and $H(X) = H(Y)$.
By the chain rule, $H(X,Y)= H(X) + H(Y|X)= H(Y) + H(X|Y)$.

Therefore, it follows from the equality $H(X) = H(Y)$ that $H(Y|X) = H(X|Y)$. But since $X\leq Y$, $H(X|Y) = 0$, hence $H(Y|X) = 0$ also, that is, $Y \leq X$. This shows equivalence $Y = X$.

Finally, since $X\geq 0$ for all $X$, $H(X)\geq H(0)=0$ and it is well known that the entropy $H(X)$ is zero if and only if the variable $X$ is deterministic, that is, $X=0$.

§.§ Common Information vs. Mutual Information

The entropy of the joint information is the joint entropy, i.e. $H(X \vee Y) = H(X,Y)$.

Obvious since $X \vee Y = (X,Y)$.

One may wonder by analogy with the usual Venn diagram in information theory (Fig. <ref>) if the entropy of joint information is equal to the mutual information: is it true that $H(X\land Y)=I(X;Y)$?
The answer is no, as shown next. Proposition <ref> is implicit in [6], and made explicit by Wyner in [21] who credits a private communication from Kaplan.

$H(X\land Y)\leq I(X;Y)$ always, with equality $H(X\land Y)= I(X;Y)$ iff one can write $X=(U,W)$ and $Y=(V,W)$ where $U$ and $V$ are conditionally independent given $W$.

Let $W=X\land Y$. Since $W\leq X$ and $W\leq Y$, by complementarity we can write $X=W\lor U=(U,W)$ and $Y=W\lor V=(V,W)$. By the chain rule for mutual information, $I(X;Y)=I(U,W;V,W)=I(W;V,W)+I(U;V,W|W)=H(W)+I(U;V|W)\geq H(W)$ with equality iff $U$ and $V$ are conditionally independent given $W$.

In particular, if $X$ and $Y$ are independent, they have a null common information $X\land Y=0$. However,  common information $H(X\land Y)$ can be far less [6] than mutual information $I(X;Y)$.

Notice that the case of equality corresponds to the case where the matrix blocks $C_i$ in (<ref>) are stochastic matrices of two independent variables $X,Y$ knowing $W=i$, i.e. matrices of rank $1$.

Shannon's notion of common information should not be confused with the well known Wyner's acception of “common information”, which is defined as the maximum of $I(X,Y;W)$ when $X$ and $Y$ are conditionally independent knowing $W$. This quantity is not less but greater than the mutual information $I(X;Y)$ [21].

§.§ Submodularity of Entropy on the Information Lattice

From the results in [12] we can show that entropy is submodular on the information lattice:

[Submodularity of entropy]
$H(X \vee Y) + H(X \wedge Y) \leq H(X) + H(Y)$.

Since $X\wedge Y\leq Y$, $H(Y)=H(Y, X\wedge Y) =H(X\wedge Y)+H(Y|X\wedge Y)$.
But since $X\wedge Y\leq X$, $H(Y|X\wedge Y)\geq H(Y|X\wedge Y,X)=H(Y|X)=H(X \vee Y) -H(X)$.
Combining gives the announced inequality.

Submodularity is in fact equivalent to the inequality $H(X \wedge Y)\leq I(X;Y)$ of Proposition <ref>, since  $H(X) + H(Y) - H(X \vee Y) =H(X) + H(Y) - H(X,Y)=I(X;Y)$.

The submodularity property of entropy that is generally studied in the information theory literature is with respect to the set lattice (or algebra), where the entropy is that of a collection of random variables indexed by some index set (thus considered as a set function).
Such considerations have been greatly developed in recent years, see, e.g., [22].
By contrast, it is the information lattice that is considered here.
It can be easily shown using Proposition <ref> that the two notions of submodularity coincide for collections of independent random variables.

§.§ Two Entropic Metrics: Shannon Distance; Rajski Distance

Since $X=Y \iff (X\leq Y \text{ and } X\geq Y)$, according to Prop. <ref>, it suffices that $H(X|Y)+H(Y|X)=0$ in order for $X$, $Y$ to be equivalent: $X=Y$. Shannon [19] noted that this defines a distance which makes the information lattice a metric space:

[Shannon's Entropic Distance]
$D(X,Y)=H(X|Y)+H(Y|X)$ is a distance over the information lattice.

* Positivity: As just noted above, $D(X,Y) \geq 0$ vanishes only when $X = Y$.

* Symmetry: $D(X,Y) = D(Y,X)$ is obvious by commutativity of addition.

* Triangular inequality: First note that $H(X|Z) \leq H(X,Y|Z) = H(X|Y,Z) + H(Y|Z) \leq H(X|Y) + H(Y|Z)$. By permuting $X$ and $Z$, we also obtain that $H(Z|X) \leq H(Z|Y) + H(Y|X)$. Summing up the two inequalities, we obtain the triangular inequality $D(X,Z)=H(X|Z) + H(Z|X) \leq H(X|Y) + H(Y|X) + H(Y|Z) + H(Z|Y)=D(X,Y)+D(Y,Z)$.

It is interesting to note that this is not the only distance (nor the only topology). By normalizing $D(X,Y)$ by the joint entropy $H(X,Y)$, we obtain another distance metric:
[Rajski's Entropic Distance [14]]
$d(X,Y)=\dfrac{D(X,Y)}{H(X,Y)}$ (with the convention $d(0,0)=0$) is a distance taking values in $[0,1]$.

Notice that normalization by $H(X,Y)$ is valid when $X$ and $Y$ are non-deterministic since $X \not = 0$ and $Y \not = 0$ implies $H(X,Y) > 0$.

First of all, symmetry $d(X,Y)=d(Y,X)$ is obvious and positivity follows from that of $D$.
We follow Horibe [7] to prove the triangular inequality. One may always assume non deterministic random variables.
Observe that:

\begin{equation}\label{eq-rajski-denom-1}
\frac{H(X|Y)}{H(X,Y)} =\frac{H(X|Y)}{H(X|Y) + H(Y)} \geq \frac{H(X|Y)}{H(X|Y) + H(Y,Z)}=\frac{H(X|Y)}{H(X|Y) + H(Y|Z) + H(Z)}
\end{equation}

\begin{equation}\label{eq-rajski-denom-2}
\frac{H(Y|Z)}{H(Y,Z)}=\frac{H(Y|Z)}{H(Y|Z) + H(Z)} \geq \frac{H(Y|Z)}{H(X|Y) + H(Y|Z) + H(Z)}.
\end{equation}

Summing (<ref>) and  (<ref>)

\begin{equation}
\frac{H(X|Y)}{H(X,Y)} + \frac{H(Y|Z)}{H(Y,Z)} \geq \frac{H(X|Y) + H(Y|Z)}{H(X|Y) + H(Y|Z) + H(Z)}.
\end{equation}

Now, from the above proof of the triangular inequality of $D$, one has $H(X|Y) + H(Y|Z) \geq H(X|Z)$. Noting  that  $a \geq b > 0$ and $c \geq 0$ imply $\frac{a}{a+c} \geq \frac{b}{b+c}$, we obtain

\begin{equation}%\label{demo-ineq-triangulaire-1}
%\frac{H(X|Y)}{H(X,Y)} + \frac{H(Y|Z)}{H(Y,Z)} &\geq
\frac{H(X|Y) + H(Y|Z)}{H(X|Y) + H(Y|Z) + H(Z)} %\\
\geq \frac{H(X|Z)}{H(X|Z) + H(Z)} \label{demo-ineq-triangulaire-2}
= \frac{H(X|Z)}{H(X,Z)}. %\label{demo-ineq-triangulaire-3}
\end{equation}

\begin{equation} \label{eq:a}
\frac{H(X|Y)}{H(X,Y)} + \frac{H(Y|Z)}{H(Y,Z)} \geq \frac{H(X|Z)}{H(X,Z)}.
\end{equation}

Permuting the roles of $X$ and $Z$ gives

\begin{equation} \label{eq:b}
\frac{H(Y|X)}{H(X,Y)} + \frac{H(Z|Y)}{H(Y,Z)} \geq \frac{H(Z|X)}{H(X,Z)}.
\end{equation}

Summing (<ref>) and (<ref>), we conclude that $d(X, Y) + d(Y, Z) \geq d(X,Z)$.

Rajski's distance between two variables $X$ and $Y$ can be visualized as the Jaccard distance between the region corresponding to $X$ and the region corresponding to $Y$ in the Venn diagram of Fig. <ref>.

The Jaccard (or Jaccard-Tanimoto) distance [9] between two sets $A$ and $B$ is defined by $d_{J}(A,B) = \frac{|A \Delta B|}{|A \cup B|}$, where $\Delta$ is the symmetric difference between $A$ and $B$. Thus, if $A$ and $B$ are respectively the regions corresponding to $X$ and to $Y$ in the Venn diagram, we have: $H(X,Y) = |A \cup B|$, $H(X|Y) = |A\backslash B|$ and $H(Y|X) = |B\backslash A|$. Thus $\frac{H(X|Y) + H(Y|X)}{H(X,Y)} = \frac{|(A\backslash B)\cup(B\backslash A)|}{A\cup B} = \frac{|A \Delta B|}{|A \cup B|}$.

every node=[font=]
[, line width=0.8pt ] (5,11.25) circle (3.75cm);
[, line width=0.8pt ] (10,11.25) circle (3.75cm);
[font=] at (2,6.25) $H(X)$;
[font=] at (13.25,6.25) $H(Y)$;
[font=] at (7.5,16.5) $H(X,Y)$;
[font=] at (7.5,11.25) $I(X;Y)$;
[font=] at (4,11.25) $H(X|Y)$;
[font=] at (11.25,11.25) $H(Y|X)$;
[ line width=0.8pt, -Stealth] (2.25,7) – (3,8);
[ line width=0.8pt, -Stealth] (13,7) – (12.25,8);
[ line width=0.8pt, -Stealth] (7.5,16.25) – (8.75,15);
[ line width=0.8pt, -Stealth] (7.5,16.25) – (6.25,15);

Usual Venn diagram in information theory.

§.§ Dependency Coefficient

From the Rajski distance, we can define a quantity which measures the dependence between two non-deterministic (i.e., nonzero)  random variables $X$ and $Y$.

[Dependency Coefficient]
For all non-zero elements $X$, $Y$ of the information lattice, their dependency coefficient is
$\rho(X,Y) = 1 - d(X,Y) \in [0,1]$.

The dependency coefficient can be seen as a normalized mutual information:
$\rho(X,Y) = \dfrac{I(X;Y)}{H(X,Y)}$.

One has $1 - d(X,Y) =  1 - \dfrac{H(X|Y) + H(Y|X)}{H(X,Y)}=\dfrac{H(X,Y) - H(X|Y) - H(Y|X)}{H(X,Y)}$ where the numerator $=H(X) + H(Y|X) - H(X|Y) - H(Y|X)=I(X;Y)$.

For non-deterministic $X$ and $Y$, one has $0 \leq \rho(X,Y) \leq 1$ where $\rho(X,Y)=0$ vanishes (equivalently, $d(X,Y) = 1$)  iff $X$ and $Y$ are independent
and $\rho(X,Y)=1$ (equivalently, $d(X,Y) = 0$) iff $X=Y$ are equivalent.

If $X$ and $Y$ are independent, then $I(X;Y) = 0$, hence $\rho(X,Y) = 0$.
If $X$ and $Y$ are equivalent, then $d(X,Y) = 0$ and $\rho(X,Y) = 1 - d(X,Y) = 1$.
Since $0 \leq I(X;Y) \leq H(X) \leq H(X,Y)$, $0 \leq \rho(X,Y) = \frac{I(X;Y)}{H(X,Y)} \leq 1$.

The property of $\rho$ in proposition <ref> is similar to the usual property of the linear correlation coefficient. However, while two independent random variables have zero correlation (but not conversely),  the corresponding converse property holds for the dependence coefficient since
two  random variables are independent if and only if $\rho(X,Y) = 0$.

§.§ Discontinuity and Continuity Properties

Perhaps the biggest flaw in Shannon's lattice information theory [19] is that the different constructions of elements in the lattice (e.g., common and complementary information) do not actually depend on the values of the probabilities involved, but only on whether they are equal to or different from zero.
Thus, a small perturbation on probabilities can greatly influence the results. As an illustration we have the following
[Discontinuity of common information]
The application $(X,Y)\mapsto X\land Y$ is discontinuous in the metric lattice with distance $D$ (or $d$).

Let $(X_\epsilon,Y_\epsilon)$ be defined by the stochastic matrix

\begin{equation}
\P_{X,Y}=\begin{pmatrix}
\frac{1-\epsilon}{N} & \frac{\epsilon}{N} & 0  & \cdots & 0 \\
0 & \frac{1-\epsilon}{N} & \frac{\epsilon}{N}  &  \cdots & 0\\
%  0 & 0 & \frac{1-\epsilon}{N} & \frac{\epsilon}{N} &  \cdots & 0 \\
\vdots & \vdots & \vdots & \ddots &  \ddots\\
\frac{\epsilon}{N}  & 0 & \cdots & 0 & \frac{1-\epsilon}{N}
\end{pmatrix}.
\end{equation}

Since there is a single class of communication, common information $X_\epsilon\land Y_\epsilon=0$ is zero for every $\epsilon >0$. By contrast, when $\epsilon=0$, $X_\epsilon\land Y_\epsilon$ is uniformly distributed among $N$ communication classes. Consequently, $D(X_\epsilon\land Y_\epsilon,0)=0$ for any $\epsilon>0$ whereas $D(X_0\land Y_0,0)=H(X_0\land Y_0)=\log N$ is arbitrarily large for $\epsilon=0$.

However, it should be noted that the joint information $\vee$ is continuous with respect to Shannon's distance. In fact we have the following

For any $X$, $X'$, $Y$, $Y'$,

\begin{equation}
D(X\vee Y, X'\vee Y') \leq D(X,X') + D(Y,Y').
\end{equation}

One has

\begin{equation}
\begin{aligned}
H(X\vee Y|X'\vee Y') &= H(X,Y|X',Y')\\
&\overset{(a)}{=} H(X|X',Y') + H(Y|X',Y',X) \\
&\overset{(b)}{\leq} H(X|X') + H(Y|Y').
\end{aligned}
\end{equation}

where $(a)$ is the consequence of the chain rule and $(b)$ is due to the fact that conditioning reduces entropy.
Since $X$, $X'$ and $Y$, $Y'$ play a symmetrical role in $(b)$, we can permute the roles of $X$, $X'$ and $Y$, $Y'$, which gives $H(X'\vee Y'|X\vee Y) \leq H(X'|X) + H(Y'|Y)$. Summing both inequalities yields the result.

In particular for $X=X'$, for any $X,Y,Z$,

\begin{equation}
D(X\vee Y, X\vee Z) \leq D(Y,Z).
\end{equation}

In other words joining the same $X$ can only reduce the Shannon distance: In this respect, the joining operator $Y\mapsto X\vee Y$ is a contraction operator.

Furthermore, the entropy, the conditional entropy, and the mutual information are continuous with respect to the entropic distance of Shannon. Indeed, we have the following inequalities (see Problem 3.5 in [3]):

For all $X$, $Y$, $X'$, $Y'$,

1) $|H(X) - H(Y)| \leq D(X,Y)$.

2) $|H(X,Y) - H(X',Y')| \leq D(X,X') + D(Y,Y')$.

3) $|H(X|Y) - H(X'|Y')| \leq D(X,X') + 2D(Y,Y')$.

4) $|I(X;Y) - I(X';Y')| \leq 2(D(X,X')+D(Y,Y'))$.

1) By the chain rule: $H(X) + H(Y|X) =H(X,Y)= H(Y) + H(X|Y)$, hence  $|H(X) - H(Y)| =|H(X|Y) - H(Y|X)| \leq H(X|Y) + H(Y|X) = D(X,Y)$.

Applying inequality 1) to the variables $(X,Y)$ and $(X',Y')$, we obtain $|H(X,Y) - H(X',Y')| \leq D((X,Y),(X',Y'))$.

From the continuity of joint information (Proposition <ref>), one can further bound $D((X,Y),(X',Y')) \leq D(X,X') + D(Y,Y')$.

By the chain rule,
$|H(X|Y) - H(X'|Y')| = |H(X,Y) - H(Y) - (H(X',Y') - H(Y'))| \leq |H(X,Y) - H(X',Y')| + |H(Y') - H(Y)|$.
The conclusion now follows from 1) and 2).

4) By the chain rule,
$|I(X;Y) - I(X';Y')| = |H(X) - H(X') + H(Y) - H(Y') + H(X',Y') - H(X,Y)|
%$. By triangular inequality, we can split this sum in three positive terms: $|I(X;Y) - I(X';Y')|
\leq |H(X) - H(X')| + |H(Y) - H(Y')| + |H(X',Y') - H(X,Y)|$.
The conclusion follows from bounding

each of the three terms in the sum using 1) and 2).

In the remainder of this paper, we only consider quantities that are continuous with respect to the entropic metrics (Shannon and Rajski distance). As a result, the discontinuity of the $\wedge$ operator will not hinder our derivations in the sequel.

§ GEOMETRIC PROPERTIES OF THE INFORMATION LATTICE

§.§ Alignments of Random Variables

Let $\delta$ be any distance on the information lattice. The random variables $X$, $Y$ and $Z$ are said to be aligned with respect to $\delta$ if the triangular inequality is met with equality:

\begin{equation}
\delta(X,Y) + \delta(Y,Z) = \delta(X,Z).
\end{equation}

[Alignment w.r.t. the Shannon distance $D$]
The random variables $X$, $Y$ and $Z$ are aligned w.r.t. $D$ if and only if $X - Y - Z$ is a Markov chain and $Y \leq X\vee Z$.

This alignment condition is illustrated in Fig. <ref>.

every node=[font=]
[line width=.7pt ]  (-2.5,12.5) circle (2.5cm);
[line width=.7pt ]  (1.25,12.5) circle (2.5cm);
[line width=1pt ] (-0.75,12.5) ellipse (2.25cm and 1.65cm);
[font=] at (-2.32,14) $Y$;
[font=] at (-4.84,14) $X$;
[font=] at (3.59,14) $Z$;

Venn diagram illustrating the alignment condition for the Shannon distance.

From the proof of the triangular inequality for $D$ (Proposition <ref>),
equality holds iff equality holds in both inequalities $H(X|Z) \leq H(X,Y|Z) = H(X|Y,Z) + H(Y|Z) \leq H(X|Y) + H(Y|Z)$ and those inequalities obtained by permuting the roles of $X$ and $Z$.

Since $H(X,Y|Z) - H(X|Z) = H(Y|X,Z)$ and $H(X|Y) - H(X|Y,Z) = I(X;Z|Y)$, equality holds iff

$H(Y|X,Z) = 0$ and $I(X;Z|Y) = 0$, both conditions being symmetric in $(X,Z)$.
Now $H(Y|X,Z) = 0$ means that $Y$ is a function of $(X,Z)$, i.e., $Y \leq X\vee Z$. Also $I(X;Z|Y) = 0$ means that $X$ and $Z$ are conditionally independent given $Y$, which characterizes the fact that $X - Y - Z$ forms a Markov chain.

[Alignment w.r.t. Rajski's distance $d$]
The random variables $X$, $Y$ and $Z$ are aligned w.r.t. $d$ if and only if $Y = X\vee Z$.

This alignment condition is illustrated in Fig. <ref>.

every node=[font=]
[line width=1pt ] (5,11.25) circle (3.75cm);
[line width=1pt ] (10,11.25) circle (3.75cm);
[font=] at (2,6.25) $X$;
[font=] at (13.25,6.25) $Z$;
[font=] at (7.5,16.5) $Y$;
[ line width=0.8pt, -Stealth] (2.25,7) – (3,8);
[ line width=0.8pt, -Stealth] (13,7) – (12.25,8);
[ line width=0.8pt, -Stealth] (7.5,16.25) – (8.75,15);
[ line width=0.8pt, -Stealth] (7.5,16.25) – (6.25,15);

Venn diagram illustrating the alignment condition for the Rajski distance.

From the proof of the triangular inequality for $d$ (Proposition <ref>), equality holds iff equality holds in all inequalities (<ref>), (<ref>), and (<ref>), and those inequalities obtained by permuting the roles of $X$ and $Z$.

Now a close inspection of (<ref>) shows it achieves equality iff $H(Z|Y) = 0$, that is, $Z \leq Y$.

Similarly, (<ref>) achieves equality iff $H(X|Y) = 0$, that is $X \leq Y$.
Both conditions write $X\vee Z\leq Y$, which is symmetric in $(X,Z)$.

Finally, (<ref>) achieves equality iff $H(X|Y) + H(Y|Z) = H(X|Z)$ and the corresponding equality obtained by permuting the roles of $X$ and $Z$. This means that $X$, $Y$ and $Z$ are aligned w.r.t. $D$, that is, $X - Y - Z$ is a Markov chain and $Y \leq X\vee Z$.

Overall $Y=X\vee Z$, which already implies that $X$ and $Z$ are conditionally independent given $Y=(X,Z)$, i.e., $X - Y - Z$ is a Markov chain.

Note that if $X$, $Y$ and $Z$ are aligned in the sense of Rajski's distance, then they are also aligned in the sense of Shannon's entropic distance since $Y = (X,Z)$ implies that $X - Y - Z$ is a Markov chain.
Thus, the alignment condition is stronger in the case of the Rajski distance.

The alignment condition w.r.t. the Rajski distance is simpler and expressed

by using only the operators of the information lattice, whereas that w.r.t. the Shannon distance requires the additional notion of Markov chain.
Therefore, in the sequel, we
develop some geometrical aspects of the information lattice based essentially on the Rajski distance.

§.§ Convex Sets of Random Variables in the Information Lattice

Given two random variables $X$ and $Y$, we define the segment $[X,Y]$ of endpoints $X$ and $Y$ as the set of all random variables $Z$ such that $X$, $Z$ and $Y$ are aligned with respect to the Rajski distance, i.e., such that $d(X,Z) + d(Z,Y) = d(X,Y)$.

A set $\mathcal{C}$ of points (random variables) in the information lattice is convex if for all points $X,Y \in \mathcal{C}$, the segment $[X,Y] \subseteq \mathcal{C}$.

If $\mathcal{S}$ is any set of points of the information lattice, its convex envelope is the smallest convex set containing $\mathcal{S}$.

By its very definition, the convex envelope of the two-element set $\{X,Y\}$ is the segment $[X,Y]$.
We have the following simple characterization.

[Segment Characterization]
For any  two elements $X$, $Y$ of the information lattice, the segment $[X,Y]$ is the three-element set $[X,Y]= \bigl\{X,(X,Y),Y\bigr\}$, with respective distances to endpoints given by

$d\bigl(X,(X,Y)\bigr) = \frac{H(Y|X)}{H(X,Y)}$
and $d\bigl(Y,(X,Y)\bigr) = \frac{H(X|Y)}{H(X,Y)}$.

$X$ and $Y$ do belong to the segment $[X,Y]$ since $d(X,X) + d(X,Y) = d(X,Y)$ and $d(X,Y) + d(Y,Y) = d(X,Y)$. Moreover, if $Z \in [X,Y]$, then $X$, $Z$ and $Y$ are aligned with respect to the Rajski distance so that necessarily $Z = (X,Y)$.
One calculates
$d\bigl(X,(X,Y)\bigr) = \frac{H(X|X,Y) + H(X,Y|X)}{H(X,Y)} = \frac{H(Y|X)}{H(X,Y)}$, and similarly for $d\bigl(Y,(X,Y)\bigr)$ by permuting the roles of $X$ and $Y$.

By the above Proposition, segments in the information lattice are intrinsically discrete objects.
In the case where $X \leq Y$ or $Y \leq X$, then the segment $[X,Y]$ contains only two distinct points, $X$ and $Y$.

Obviously, if $X = Y$, then $[X,Y]$ is a singleton.
This gives three possible cases as illustrated in Fig. <ref>.

(1,1) node$\bullet$;
(1,1) node[below left]$X$;

(3.25,3.25) node$\bullet$;
(3.25,3.25) node[above left]$X \vee Y$;

(4,4) node$\bullet$;
(4,4) node[above left]$Y$;

[black] (1,1) [stealth-stealth] – node[below right]$\frac{H(Y|X)}{H(X,Y)}$ (3.25,3.25);
[black] (3.25,3.25) [stealth-stealth] – node[below right]$\frac{H(X|Y)}{H(X,Y)}$ (4,4);

Arbitrary $X$ and $Y$

(1,1) node$\bullet$;
(1,1) node[below left]$X$;
(4,4) node$\bullet$;
(4,4) node[above left]$Y = X\vee Y$;
[black] (1,1) [stealth-stealth] – node[below right]$\frac{H(Y|X)}{H(Y)}$ (4,4) ;

$X \leq Y$

(1,1) node$\bullet$;
(1,1) node[above]$X = Y = X \vee Y$;

$X = Y$

Visualization of the segment $[X,Y]$ for three possible cases.

As a result of this characterization, four or more distinct points cannot be aligned w.r.t. the Rajski distance, because a segment cannot contain more than three distinct points.

$\mathcal{C}$ is convex iff it is closed under the $\vee$ operator.

$\mathcal{C}$ is convex iff for all $X,Y \in \mathcal{C}$, $[X,Y] \subseteq \mathcal{C}$, that is, $X$, $Y$ and $(X,Y) = X \vee Y \in  \mathcal{C}$.

Beyond the case of a two-element set, we now characterize the convex envelope of any $n$-element set in the information lattice, that is, the convex envelope of $n$ random variables $X_{1}$, $X_{2}$,..., $X_{n}$.

We adopt the following usual convention.
For any $n$-tuple of indices $I = (i_{1},i_{2},...,i_{n})$, the random vector $(X_{i_{1}},X_{i_{2}},...,X_{i_{n}})=X_{i_{1}}\vee X_{i_{2}}\vee \cdots \vee X_{i_{n}}$ is denoted by
$X_{I}$. Again by convention, for the empty set, $X_{\emptyset} = 0$, so that one always have $X_{I\cup J}=X_I\vee X_J$ for any two finite sets of indices $I$ and $J$.

Let $I$ be a finite index set and $(X_{i})_{i \in I}$ be random variables. The convex envelope of $(X_{i})_{i \in I}$ is $ \{ \vee_{j \in J}X_{j} \mid \emptyset\not=J \subseteq I \}=
%As, for any set $J$, $\vee_{j \in J}X_{j} = X_{J}$, we can also write that the convex envelope of $(X_{i})_{i \in I}$ is $
\{ X_{J} \mid \emptyset\not=J \subseteq I  \}$, that is, the set of all sub-tuples of the $X_i$.

With every $X_i$ ($i \in I$), the convex envelope in question should be closed by the $\vee$ operator, hence contain any tuple $\vee_{j \in J}X_{j}$ for any nonempty $J\subseteq I$. Now
$\mathcal{C} = \{  \vee_{j \in J}X_{j}=X_{J} \mid \emptyset\not=J \subseteq I  \}$ contains all $X_{i}$ for $i \in I$ and is already convex. Indeed, for all $X_{J} \in \mathcal{C}$ and $X_{K} \in \mathcal{C}$, $X_{J} \vee X_{K} = X_{J \cup K} \in \mathcal{C}$.

Given a finite set $I$ of index of cardinality $|I| =n$, the convex envelope of $(X_{i})_{i \in I}$ contains at most $2^{n} - 1$ distinct elements, since there are $2^{n}-1$ nonempty subsets of $I$. The number $2^n-1$ is only an upper bound since it might happen that two different subsets $J$ and $K$ of $I$ are such that $X_{J} = X_{K}$.

An example of the convex envelope of a family of three random variables is shwon in Fig. <ref>.

every node=[font=]

(0,0) node$\bullet$;
(0,0) node[left]$X_{1}$;

(1,1.732) node$\bullet$;
(1,1.732) node[above]$X_{0}$;

(2,0) node$\bullet$;
(2,0) node[right]$X_{2}$;

(1,0) node$\bullet$;
(1,0) node[below]$X_{1} \vee X_{2}$;

(0.5,0.866) node$\bullet$;
(0.5,0.866) node[above left]$X_{0} \vee X_{1}$;

(1.5,0.866) node$\bullet$;
(1.5,0.866) node[above right]$X_{0} \vee X_{2}$;

(1,0.6666) node$\bullet$;
(1,0.6666) node[below]$X_{0} \vee X_{1} \vee X_{2}$;

$7$-element convex envelope of three random variables $X_{0}$, $X_{1}$ and $X_{2}$. These three random variables are represented as vertices of an (equilateral) triangle. The other points in the convex envelope are obtained as intersections of medians and edges, and the common information $X_{0}\vee  X_{1}\vee X_{2}$ is the center of gravity (intersection of the three medians).
Similarly, the 15-element convex envelope of four distinct points can be visualized in a tetrahedron, etc.

It is also interesting to note that any sublattice of the information lattice does have some convexity properties:

Any sublattice of the information lattice (including the information lattice itself) is convex.
With every $X_i$ ($i \in I$), the sublattice also contains the convex envelope of $(X_{i})_{i \in I}$.

With every two points $X,Y$, the sublattice should contain their maximum $X\vee Y$, hence the whole segment $[X,Y]$. It is, therefore, convex. Now every convex set contains the convex enveloppe of any of its subsets.

§.§ The Lattice Generated by a Random Variable

In the sequel, we are interested in all possible deterministic functions of a given random variable $X$. In fact, their set constitutes a sublattice of the information lattice:

[Sublattice generated by a random variable]
Let $X$ be any random variable in the information lattice. The set of all random variables $\leq X$ is a sublattice, which we call lattice generated by $X$, denoted $\langle X \rangle$. It is a bounded lattice with maximum (total information) $X$ and minimum $0$.

Let $Y \leq X$ and $Z \leq X$. There exists deterministic functions $f$ and $g$ such that $Y = f(X)$ a.s. and $Z = g(X)$ a.s.  Clearly

$Y \wedge Z \leq Y \leq X$ and $Y \vee Z = (Y,Z) = (f(X),g(X)) \leq X$.
Therefore, the set of random variables $\leq X$ forms a sublattice. Clearly $X$ is maximum and $0$ (deterministic random variable seen as a constant function of $X$) is minimum.

One may also define the sublattice $\langle X_1,X_2,\ldots,X_n\rangle$ generated by several random variables $X_1,X_2,\ldots,X_n$ simply as the sublattice generated by the variable $X_1\vee X_2 \vee \cdots\vee X_n$. Therefore, it is enough to restrict ourselves to one random variable $X$ as the lattice generator.

$\langle X \rangle$
is a complemented lattice.

Let $Y\leq Z\leq X$, so that both $Y,Z \in \langle X \rangle$. By Proposition <ref>, $Y$ admits at least one complement information $\overline{Y}$ w.r.t. $Z$ in the information lattice, such that

$Y \wedge \overline{Y} = 0$ and $Y \vee \overline{Y} = Z$.
Now $\overline{Y} \leq Z \leq X$, hence the complement $\overline{Y} \in \langle X \rangle$ belongs to the sublattice generated by $X$.

§.§ Properties of Rajski and Shannon Distances in the Lattice Generated by a Random Variable

We now investigate the metric properties of the sublattice $\langle X\rangle$ generated by a random variable $X$.
To avoid the trivial case $\langle 0 \rangle = \{0\}$ we assume that $X$ is nondeterministic.
First of all, we observe that the entropy of a element of the sublattice increases as it is closer to $X$ (in terms of either Shannon's or Rajski's distance):

For any $Y \in \langle X \rangle$, one has
$D(X,Y)=H(X|Y)=H(X)-H(Y)$ and
$d(X,Y) %= \dfrac{D(X,Y)}{H(X)}
= \dfrac{H(X|Y)}{H(X)} = 1 - \dfrac{H(Y)}{H(X)}$.
In particular maximum distance $d(X,Y) =1$ is achieved iff $Y=0$.

One has

\begin{equation}
\begin{aligned}
d(X,Y) &= \frac{D(X,Y)}{H(X,Y)}= \frac{H(X|Y) + H(Y|X)}{H(X)} \\
&\overset{(a)}{=} \frac{H(X|Y)}{H(X)}
\overset{(b)}{=} \frac{H(X) - H(Y)}{H(X)}
= 1 - \frac{H(Y)}{H(X)}.
\end{aligned}
\end{equation}

where $(a)$ is because $Y \leq X$, and $(b)$ is a consequence of the chain rule: $H(X) = H(X,Y) = H(Y) + H(X|Y)$.

In the language of data compression, $d(X,Y) %= \dfrac{D(X,Y)}{H(X)}
= \dfrac{H(X)-H(Y)}{H(X)} = 1 - \dfrac{H(Y)}{H(X)}$ can be seen as the relative entropic redundancy of $X$ when it is represented (“encoded”) by $Y$.

The maximum distance case in the Proposition can be stated as follows: The only random variables $Y$ that can be obtained as functions of $X$ ($Y\in\langle X \rangle$) while being also independent of $X$ ($d(X,Y)=1$) are the constant (deterministic) random variables.

In Euclidean geometry, Apollonius's theorem allows one to calculate the length of the median of a triangle $XYZ$ given the length of its other three sides. In the information lattice context, $Y\vee Z$ denotes the median of the segment $[Y,Z]$ (the only possible point in the segment that is not an endpoint). Thus, Apollonius's theorem gives a formula for distance $D(X,Y\vee Z)$ in terms of $D(X,Y)$, $D(X,Z)$, and $D(Y,Z)$.

The following Proposition is the analogue of Apollonius's theorem for the Shannon distance in the information lattice generated by $X$:

[Apollonius's theorem in $\langle X\rangle$]

For any $Y,Z\in\langle X \rangle$,

\begin{equation}
D(X,Y\vee Z) = \frac{D(X,Y) + D(X,Z) - D(Y,Z)}{2}.
\end{equation}

This can also be written as

\begin{equation}
D(X,Y)+D(X,Z)=D(Y,Z) + 2 D(X,Y\vee Z)
\end{equation}

This is illustrated in Fig. <ref>.
Note that when $X=Y\vee Z$ one recovers that $Y,X,Z$ (in this order) are aligned.

[label=right:$X$] (X) at (4,2);
[label=above:$Y$] (Y) at (2,4);
[label=left:$Z$] (Z) at (0,0);
[label=left:$Y\vee Z$] (D) at (1.5,3);

(4,2) node$\bullet$;
(2,4) node$\bullet$;
(0,0) node$\bullet$;
(1.5,3) node$\bullet$;

[green] (X) [<->] – (Y);
[blue] (Y) [<->] – (Z);
[green] (Z) [<->] – (X);
[red] (X) [<->] – (D);

[below=6pt](D,X)$D(X,Y\vee Z)$

Graphical representation of Apollonius's theorem (Lemma <ref>).

From Proposition <ref>, $D(X,Y)=H(X)-H(Y)$ for any $Y\in\langle X \rangle$, in particular
$D(X,Z)=H(X)-H(Z)$ and $D(X,Y\vee Z)=H(X)-H(Y,Z)$ also.

Therefore, $D(X,Y)+D(X,Z)- 2 D(X,Y\vee Z) = 2H(Y,Z)-H(Y)-H(Z)=H(Z|Y)+H(Y|Z)=D(Y,Z)$.

From Lemma <ref> we derive the following

For any $Y,Z\in\langle X \rangle$,

\begin{equation}
%    d(X,X_{I}) + d(X,X_{J}) \leq d(X,X_{I \cup J}) + 1
d(X,Y)+d(X,Z) \leq d(X,Y\vee Z) +1
\end{equation}

with equality if and only if $Y$ and $Z$ are independent.

Observe that $D(Y,Z) + D(X,Y\vee Z)=H(Y|Z)+H(Z|Y) + H(X|Y\vee Z)\leq H(Y)+H(Z|Y) + H(X|Y,Z)=H(Y,Z) + H(X|Y,Z)=H(X,Y,Z)=H(X)$ since $Y,Z\in\langle X \rangle$, with equality iff $Y$ and $Z$ are independent.
Now by Lemma <ref>, $D(X,Y)+D(X,Z)=D(Y,Z)+2$$D(X,Y\vee Z)\leq D(X,Y\vee Z)$$+H(X)$.
Dividing by $H(X)=H(X,Y)=H(X,Z)=H(X,Y,Z)$ yields the announced inequality.

In the other direction we have the following

For any $Y,Z\in\langle X \rangle$,

\begin{equation}
d(X,Y\vee Z) \leq d(X,Y) + d(X,Z)
\end{equation}

with equality if and only if $X=Y=Z$.

By the triangular inequality, $d(X,Y\vee Z)\leq d(X,Y)+d(Y,Y\vee Z)$ with equality iff $Y=X\vee Y\vee Z=X$ by the alignment condition. Similarly, $d(X,Y\vee Z)\leq d(X,Z)+d(Z,Y\vee Z)$ with equality iff $Z=X\vee Y\vee Z=X$. Summing the two inequalities, $2d(X,Y\vee Z)\leq d(X,Y)+d(X,Z) + d(Y,Y\vee Z)+d(Z,Y\vee Z)$ where
$d(Y,Y\vee Z)+d(Z,Y\vee Z)=d(Y,Z)\leq d(X,Y)+d(X,Z)$ with equality iff $X=Y\vee Z$. Combining yields the announced inequality.

In the course of the proof, we have proved the following stronger inequality: for any $Y,Z\in\langle X \rangle$,

\begin{equation}
d(X,Y\vee Z) \leq \frac{d(X,Y)+d(Y,Z) +d(Z,X)}{2}
\end{equation}

with the same equality condition $X=Y=Z$.

By Lemmas <ref> and <ref>, we see that in terms of Rajski distances to the generator $X$, $d(X,Y\vee Z)$ lies between $d(X,Y)+d(X,Z)-1$ and $d(X,Y)+d(X,Z)$, where the lower and upper bounds differ by $1$ and the minimum value is achieved in the case of independence. These two Lemmas are instrumental in the derivations of the next section.

§ THE PERFECT RECONSTRUCTION PROBLEM

§.§ Problem Statement

Suppose one is faced with the following reconstruction problem. We are given a (discrete) source of information $X$ (e.g., a digital signal, some text document, or any type of data), which is processed using deterministic functions into several “components”:

\begin{equation}
X_1=f_1(X), \quad X_2=f_2(X),  \quad\ldots, \quad X_n=f_n(X)
\end{equation}

(e.g., different filtered versions of the signal at various frequencies, translated parts of the document, or some nonlinear transformations of the data). The natural question is: Did one loose information when processing $X$ into its $n$ components $X_1,X_2,\ldots,X_n$? Or else, can we perfectly reconstruct the original $X$ from its $n$ components using some (unknown) deterministic function $X=f(X_1,\ldots,X_n)$?

We emphasize that all involved functions must be deterministic (no noise is involved), otherwise perfect reconstruction (without error) would not be possible. Yet we do not require any precise form for the reconstruction function $f$, only that such a reconstruction exists.
To our knowledge, the first occurence of such a problem (for $n=2$) is an Exercise 6 of the textbook [15].

Stated in the information lattice language, the perfect reconstruction problem is as follows. Suppose we are given $X_1,X_2,\ldots,X_n$ in $\langle X\rangle$, the sublattice generated by $X$. Is it true that $X\leq X_1\vee X_2\vee\cdots\vee X_n$? Since the sublattice is convex (Proposition <ref>), i.e., stable by the $\vee$ operator (Proposition <ref>), one always has, by assumption, that $X_1\vee X_2\vee\cdots\vee X_n\in \langle X\rangle$, i.e., $X_1\vee X_2\vee\cdots\vee X_n\leq X$. Therefore, in the reconstruction problem, it is equivalent to determine whether $X= X_1\vee X_2\vee\cdots\vee X_n$ or $X\not= X_1\vee X_2\vee\cdots\vee X_n$.

Geometrically, by Proposition <ref>, determining whether $X\leq X_1\vee X_2\vee\cdots\vee X_n$ or not is equivalent to determining whether $X$ is in the convex envelope of the $(X_{i})_{i =1,\ldots,n}$.

Thus, when $n=2$, perfect reconstruction is possible iff $X$ lies in the segment $[X_1,X_2]$.
When $n=3$, perfect reconstruction is possible iff for every distinct indices

$i,j,k\in\{1,2,3\}$, $X_{i}$, $X$ and $X_{j,k}$ are aligned w.r.t. the Rajski distance as illustrated in Fig. <ref>.

[label=left:$X_{2}$] (A) at (0,0);
[label=above:$X_{1}$] (B) at (1,1.732051);
[label=right:$X_{3}$] (C) at (2,0);

[label=below:$X_{2,3}$] (D) at (1,0);
[label=left:$X_{1,2}$] (E) at (0.5,0.86603);
[label=right:$X_{1,3}$] (F) at (1.5,0.86603);

[label=right:$X$] (G) at (1,0.57735);

(H) at (1.01,0.57);
(I) at (0.99,0.57);
(J) at (1,0.58);

(A) – (B) – (C) – cycle;
[red] (C) – (E);
[red] (A) – (F);
[red] (B) – (D);

Geometric Illustration of the Three-Component Reconstruction Problem.

Intuitively, the processed components $X_i$ should not (on the whole) be too “far away” from the original source $X$ in order that perfect reconstruction be possible. In other words, at least some of the distances $d(X,X_i)$ should not be too high. Such distances can be, in principle, evaluated when processing the source $X$ into each of its components. In the following Subsection, we give a simple necessary condition on the sum $d(X,X_1)+d(X,X_2)+\cdots+d(X,X_n)$ to allow for perfect reconstruction.

§.§ A Necessary Condition for Perfect Reconstruction

The main result of this paper is the following

[Necessary Condition for Perfect Reconstruction]

Let $X$ be a random variable and let $X_1,X_2,\ldots,X_n\in\langle X\rangle$. If perfect reconstruction is possible: $X= X_1\vee X_2\vee\cdots\vee X_n$, then

\begin{equation}\label{eq-possible?}
\sum_{i=1}^{n}d(X,X_{i}) \leq n-1
\end{equation}

with equality iff  $X_1,X_2,\ldots,X_n$ are independent.

By repeated use of Lemma <ref>, each joining operation of two components in the sum—e.g., passing from $d(X,X_i)+d(X,X_j)$ to $d(X,X_i\vee X_j)$—decreases this sum by at most $1$. Thus,

\begin{equation}
\begin{aligned}
\sum_{i=1}^{n}d(X,X_{i}) &\leq  \sum_{i=1}^{n-2}d(X,X_{i})+ d(X,X_{n-1}\vee X_n) + 1 \\
&\leq \sum_{i=1}^{n-3}d(X,X_{i})+ d(X,X_{n-2}\vee X_{n-1}\vee X_n) + 2\\
&\leq d(X,X_1\vee X_2\vee\cdots\vee X_n) + n-1 = n-1.
\end{aligned}
\end{equation}

Equality holds iff all the above $n-1$ inequalities are equalities. By the equality condition of Lemma <ref>, this means by induction that $X_1$ is independent from $X_2\vee \cdots \vee X_{n}$, where $X_2$ is independent from
$X_3\vee \cdots \vee X_{n}$, and so on until $X_{n-1}$ is independent from $X_n$. Overall this is equivalent to saying that all components $X_1,X_2,\ldots,X_n$ are mutually independent.

To illustrate Theorem <ref>, consider a uniformly distributed two-bit random variable $X$ (i.e., the result of two independent coin flips) and let $X_1$ be the result of the first coin toss and $X_2$ be that of the second coin toss. Clearly, reconstruction is possible since $X=(X_1,X_2)$. Now a simple calculation gives $d(X,X_1)=\frac{H(X|X_1)}{H(X)} = \frac{\log 2 }{ \log 4} =\frac{1}{2}$, and similarly $d(X,X_2)=\frac{1}{2}$, which shows that (<ref>) is achieved with equality: $d(X,X_1)+d(X,X_2)=2-1=1$. This is not surprising since $X_1$ and $X_2$ are independent, as can be checked directly.

Now consider $X_3=0$ or $1$ depending on whether $X_1=X_2$ or not. Clearly, $X$ can be also reconstructed from $X_1,X_2,X_3$ since it can already be reconstructed from $X_1,X_2$. Again one computes $d(X,X_3)=\frac{\log 2 }{ \log 4} =\frac{1}{2}$ so in this case, the sum of distances to $X$ is now $d(X,X_1)+d(X,X_2)+d(X,X_3)=\frac{3}{2}<3-1=2$. This shows that (<ref>) is still satisfied, but not with equality. In fact, it can easily be proved that even though $X_1,X_2,X_3$ are pairwise independent, they are not mutually independent.

In practice, Theorem <ref> gives an impossibility condition for perfect reconstruction of the random variable $X$ from components $X_1,X_2,\ldots,X_n$. Indeed, if the latter are such that

\begin{equation}\label{eq-impossible}
\sum_{i=1}^{n}d(X,X_{i}) > n-1
\end{equation}

then perfect reconstruction is impossible, however complex the reconstruction function $f$ could have been. In other words, $X< X_1\vee X_2\vee\cdots\vee X_n$, information was lost by processing.

That perfect reconstruction is impossible does not mean that it would never be possible to deduce one particular value of $X$ from some particular values of $X_1,X_2,\ldots,X_n$. It means that such a deduction is not possible in general, for every possible values taken by $X_1,X_2,\ldots,X_n$. In other words, there is at least one set of values $X_1=x_1$, $X_2=x_2$, …, $X_n=x_n$ for which $X$ cannot be reconstructed unambiguously.

Another look at Theorem <ref>  can be made using the dependency coefficient $\rho=1-d$ in place of the Rajski distance.  Then the impossibility condition (<ref>) simply writes

\begin{equation}\label{eq-imprho}
\sum_{i=1}^{n}\rho(X,X_{i})<1.
\end{equation}

In other words, perfect reconstruction can only occur if the components are (as a whole) sufficiently dependent on the original $X$. Otherwise (<ref>) precludes perfect reconstruction.

Since the Rajski distance is always upper bounded by $1$, if the impossibility condition (<ref>) is met, then the actual value of the sum $\sum_{i=1}^{n}d(X,X_{i})$ necessarily lies in the interval $(n-1,n]$.

In the worse situation $\sum_{i=1}^{n}d(X,X_{i})=n$,  all terms should equal one: $d(X,X_{i})=1$. This means that all components are independent from $X$. By Proposition <ref>, the components $X_i=0$ are all constants: In this case, all information is lost.

By Theorem <ref>, for perfect reconstruction to be possible, the components $X_i$ should be (at least slightly) tightened around $X$ in the sense that (<ref>) is satisfied.
The example of Remark <ref> shows that under this condition (even when the inequality is strict), it may be actually possible to reconstruct $X$.
However, proximity may not be enough: The necessary condition of Theorem <ref> is not sufficient in general.

To see this, consider $X$ uniformly distributed in the integer interval $\{0,1,\ldots,11\}$ and define $X_1=k$ if $X=2k$ or $2k+1$ and $X_2=\ell$ if $X=3\ell$, $3\ell+1$ or $3\ell+2$. In other words $X_1$ is the integer division of $X$ by $2$ and $X_2$ is the integer division of $X$ by $3$. One easily computes

\begin{equation}
d(X,X_1)+d(X,X_2)=\frac{H(X|X_1)+H(X|X_2)}{H(X) }= \frac{\log 2+\log 3}{\log 12}= \frac{\log 6}{\log 12}<1.
\end{equation}

While the necessary condition (<ref>) of Theorem <ref>  is met, the value of $X$ cannot be unambiguously determined from those of $X_1$ and $X_2$. For example, $X_1=X_2=0$ leaves two possibilities $X=0$ or $1$. Therefore, perfect reconstruction is not possible.

Another way to see this is to observe that perfect reconstruction is equivalent to saying that $X_1,X,X_2$ are aligned, which in terms of the Shannon distance would write $D(X_{1},X_{2}) = D(X,X_{1}) + D(X,X_{2})$.
But while $D(X,X_{1}) + D(X,X_{2})=\log 6$, one has

\begin{equation}
D(X_1,X_2)= H(X_1|X_2)+H(X_2|X_1)= \bigl( \frac{1}{3}\log 3 + \frac{2}{3}\log \frac{3}{2}\bigr)+ \frac{2}{6}\log 2=\log 3 - \frac{\log 2}{3}
\end{equation}

which is clearly less than $\log 6$.
Therefore, perfect reconstruction is impossible in our example, because $X_{1}$ and $X_{2}$ are too close together, i.e., there is too much redundant information between them.

A slight modification of the above example where $X$ takes values in $\{0, 1, \ldots, 12m-1\}$ for abitraily large $m$ shows that the sum $d(X,X_1)+d(X,X_2)=\frac{\log 6}{\log(12m)}$ can actually be as small as desired, while perfect reconstruction is still impossible.  Therefore, there can be no condition of the form
$\sum_{i=1}^{n}d(X,X_{i})<c$ (or any condition based only on the value of this sum) to ensure perfect reconstruction. Such a sufficient condition cannot be established without assuming some other property of the components $X_i$, as seen in the next Subsection.

§.§ A Sufficient Condition for Perfect Reconstruction

For independent components $X_1,X_2,\ldots,X_n$ (with no redundant information between them), the necessary condition of Theorem <ref> becomes also a sufficient condition:

[Sufficient Condition for Perfect Reconstruction]

Let $X$ be a random variable and let $X_1,X_2,\ldots,X_n\in\langle X\rangle$ be independent.
If inequality (<ref>) holds, then it necessarily holds with equality:

\begin{equation}
\sum_{i=1}^{n}d(X,X_{i}) = n-1
\end{equation}

and perfect reconstruction is possible:  $X= X_1\vee X_2\vee\cdots\vee X_n$.

A closer look at the proof of Theorem <ref> shows that we have established (without the perfect reconstruction assumption) the general inequality

\begin{equation}\label{eq-general-cond}
\sum_{i=1}^{n}d(X,X_{i}) \leq  d(X,X_1\vee X_2\vee\cdots\vee X_n) + n-1
\end{equation}

which holds with equality iff $X_1,X_2,\ldots,X_n$ are independent. Therefore, by the independence assumption, (<ref>) writes $ \sum_{i=1}^{n}d(X,X_{i}) =  d(X,X_1\vee X_2\vee\cdots\vee X_n) + n-1\leq n-1$. Since the distance is nonnegative, this necessarily implies that the inequality holds with equality and that $d(X,X_1\vee X_2\vee\cdots\vee X_n)=0$, that is, $X= X_1\vee X_2\vee\cdots\vee X_n$.

Following Remark <ref>, we see that for independent $X_1,X_2,\ldots,X_n$, the sum of distances to $X$: $\sum_{i=1}^{n}d(X,X_{i})$  can only take values in the interval $[n-1,n]$, with two possibilities:

* Either $\sum_{i=1}^{n}d(X,X_{i}) =n-1$, perfect reconstruction is possible;

* or $\sum_{i=1}^{n}d(X,X_{i}) >n-1$, perfect reconstruction is impossible.

In other words, independent components cannot be arbitrarily tightly packed around $X$.

Following Remark <ref>, in terms of dependency coefficients, for independent $X_1,X_2,\ldots,X_n$,

* Either $\sum_{i=1}^{n}\rho(X,X_{i}) =1$, perfect reconstruction is possible;

* or $\sum_{i=1}^{n}\rho(X,X_{i}) <1$, perfect reconstruction is impossible.

Following Remark <ref> and Fig. <ref>  in the case of three independent components $X_{1},X_{2},X_{3}$, one should have $d(X,X_{1}) + d(X,X_{2}) + d(X,X_{3}) = 2$ for perfect reconstruction to hold. Incidentally, the graphical Euclidean illustration of Fig. <ref> is faithful in this case, since for an equilateral triangle $X_{1}X_{2}X_{3}$ with sides of length 1, the sum of Euclidean distances equals $d(X,X_{1}) + d(X,X_{2}) + d(X,X_{3}) = \frac{2}{3} + \frac{2}{3} + \frac{2}{3}= 2$.

§.§ Approximate Reconstruction

Suppose we encode the information source $X$ by $n$ components $X_1,X_2,\ldots,X_n$ but do not particularly insist that perfect reconstruction is possible. Rather, we assume that the encoding removes a fraction of redundancy in $X$ equal to

\begin{equation}\label{eq-redundancy}
d(X,X_1\vee X_2\vee\cdots\vee X_n) = \delta
\end{equation}

(see Remark <ref>). Since the case $\delta=0$ corresponds to the previous case of perfect reconstruction ($X= X_1\vee X_2\vee\cdots\vee X_n$), we assume that $\delta>0$ in the sequel. Thus, in what follows, reconstruction of $X$ can only be approximate (up to a certain distance tolerance $\delta$). We then have the following

[Approximate Reconstruction]
Let $X$ be a random variable and let $X_1,X_2,\ldots,X_n\in\langle X\rangle$ such that (<ref>) holds with redundancy $=\delta>0$. Then

\begin{equation}\label{eq-delta}
\delta< \sum_{i=1}^{n}d(X,X_{i}) \leq n-1 +\delta.
\end{equation}

with equality in the second inequality iff the components $X_1,X_2,\ldots,X_n$ are independent.

The rightmost inequality in (<ref>) is just (<ref>) (with the announced case of equality), which was established by repeated application of Lemma <ref>.
Similarly, repeated application of Lemma <ref> gives

\begin{equation}
d(X,X_1\vee X_2\vee\cdots\vee X_n)\leq   \sum_{i=1}^{n}d(X,X_{i})
\end{equation}

with equality iff all $X_i=X$ ($i=1,\ldots,n$). But such an equality condition would yield $\delta=d(X,X)=0$, contrary to the assumption $\delta>0$. This shows the leftmost inequality in (<ref>) is strict.

Similarly as in the above two Subsections,  one can deduce from Theorem <ref> that for independent components $X_1,X_2,\ldots,X_n$, one necessarily has $\sum_{i=1}^{n}d(X,X_{i}) = n-1 +\delta$, and that in general, approximate reconstruction within distance tolerance $\leq\delta$ will be impossible if $\sum_{i=1}^{n}d(X,X_{i}) > n-1 +\delta$.

§ EXAMPLES AND APPLICATIONS

In this Section, we develop five examples of applications of the theorems of Section <ref>.

§.§ Reconstruction from Sign and Absolute Value

Consider a real-valued random variable $X$ and assume that it is symmetric ($X$ is identically distributed as $-X$) and that $\P(X=0)=0$.

Now define $X_{1} = |X|$ (absolute value) and $X_{2}=\mathrm{sgn}(X)\in\{-1,1\}$ (sign of $X$).
Clearly, if $X$ follows probability distribution $p$, then  $X_1$ has probability distribution $2p(x)$ for $x>0$. Also, $X_2$ is Rademacher distributed (equiprobable $\pm 1$).

One easily computes $H(X_1)=\sum_{x>0} 2p(x)\log \frac{1}{2p(x)} = H(X) - \log 2$ and $H(X_2)=\log 2$ (equiprobable $\pm1$), hence $d(X,X_1)=1-\frac{H(X_1)}{H(X)}=\frac{\log 2}{H(X)}$ and $d(X,X_2)=1-\frac{H(X_2)}{H(X)}=1-\frac{\log 2}{H(X)}$. Therefore,
$d(X,X_1)+d(X,X_2) = 1$: Inequality (<ref>) is satisfied with equality.

Of course, in this trivial example, perfect reconstruction is possible since $X=|X|\mathrm{sgn}(X)=X_1X_2$.
Then by Theorem <ref>, we deduce that $X_1$ and $X_2$ are independent. This is easily checked directly since  by the symmetry assumption, $\mathbb{P}(X_{1} = x_{1}\mid X_{2} = \pm1) = \mathbb{P}(X_{1} = x_{1})$.
Notice that from this independence, by Theorem <ref>, we find anew that perfect reconstruction of $X$ is possible from $X_1$ and $X_2$.

This example can be easily generalized to the case of a “symmetric” complex-valued random variable $X$ with modulus $X_1=|X|$ and argument $X_2=\arg(X)$, where $X_1$ is independent of $X_2$ and $X_2$ is uniformly distributed over $M$ possible values. Then $H(X_2)=\log M$, $H(X_1)=H(X)-\log M$ by symmetry, and similar conclusions hold.

Of course, perfect reconstruction $X=X_1X_2$ is always possible even in the case where $X$ is not symmetric, in which case $X_1$ and $X_2$ are not independent and, therefore, by the alignement condition, $d(X,X_1)+d(X,X_2) =d(X_1,X_2)<1$.

§.§ Linear Transformation over a Finite Field

Consider $X$ uniformly distributed over $\mathbb{F}_{q}^{k}$, where $\mathbb{F}_{q}$ be the field with $q$ elements. Suppose $X$ is linearly transformed using some matrix $\mathbf{G}$ to obtain

\begin{equation}
(X_{1},X_{2},...,X_{n})=X\cdot \mathbf{G}
\end{equation}

in row vector notation, where $\mathbf{G}\in \mathbb{F}^{k\times n}_{q}$ has $k$ rows and $n$ columns.
For example, $X$ may represent information symbols to be transmitted over a channel, and $(X_{1},X_{2},...,X_{n})$ would be the associated codeword using an $(n,k)$ linear code over $\mathbb{F}_{q}$ with generator matrix $\mathbf{G}$.

If the $i$th column of $\mathbf{G}$ is not the all-zero vector, then it is easily checked that since $X$ is uniformly distributed over $\mathbb{F}_{q}^{k}$, $X_i$ is likewise uniformly distributed over $\mathbb{F}_{q}$.

\begin{equation}
=1- \frac{H(X_i)}{H(X)} = 1- \frac{\log q}{\log q^k}
%=\frac{H(X|X_i)}{H(X)}= \frac{\log q^{k-1} }{ \log q^k}
= 1- \frac{1}{k}.
\end{equation}

When the $i$th column of $\mathbf{G}$ is all zero, however, $d(X,X_i)=d(X,0)=1$. Summing up,

\begin{equation}
\sum_{i=1}^n  d(X,X_i) = n - \frac{n'}{k}
\end{equation}

where $n'\leq n$ is the number of nonzero columns in $\mathbf{G}$.

By Theorem <ref>, if $n-\frac{n'}{k}>n-1$, that is, $n'<k$, then perfect reconstruction is impossible. This is quite natural since in this case, $(X_{1},...,X_{n})$ entails less $q$-ary symbols than the vector $X$, so that it is impossible to reconstruct $X$ from the $n'$ actual symbols in $(X_{1},...,X_{n})$.

In general, if $\mathbf{G}$ has rank $r\leq \min(k,n')$, then since $X$ is uniformly distributed over $\mathbb{F}_{q}^{k}$, the vector $(X_{1},...,X_{n})$ is also uniformly distributed over a subspace of $\mathbb{F}_{q}^{n}$ of dimension $r$.

Now as we have just seen,  if the $i$th column of $\mathbf{G}$ is not the all-zero vector,  then $X_i$ is uniformly distributed over $\mathbb{F}_{q}$.
Since uniformly distributed components of a discrete random vector are independent iff the vector is itself uniformly distributed, the only possibility for components $X_{1},...,X_{n}$ to be independent as in Theorem <ref> is that $(X_{1},...,X_{n})$ is  uniformly distributed over $\mathbb{F}_{q}^{n'}$, that is, $r=n'=k$. In this case $\sum_{i=1}^n  d(X,X_i) =n-1$ and by Theorem <ref>, perfect reconstruction is possible.
Of course, from linear algebra, we known that $X$ can be reconstructed from $(X_{1},...,X_{n})$ as soon as $\mathbf{G}$ has rank $r=k\leq n'$.

Due to the power of linear algebra, this example may appear quite trivial.
It would be interesting to generalize it, however, to the case where the vector $(X_{1},...,X_{n})$
is obtained by a nonlinear transformation, i.e., each $X_i$ are boolean functions over $\mathbb{F}_q$ of the components of vector $X$, e.g. described in algebraic normal form.

§.§ Integer Prime Factorization

Consider an integer-valued random variable $X$, uniformly distributed over $\{1,2,\ldots,m\}$, and let $n=\pi(m)$ be the number of primes not exceeding $m$. For every such prime $p$, let $X_p$ be the $p$-adic valuation of $X$, that is, the largest exponent of $p$ such that $p^{X_p}$ divides $X$.
We know by the fundamental theorem of arithmetic that the prime factorization of $X$ always exists and is unique: $X=\prod_p p^{X_p}$, hence $X$ can be reconstructed from the $X_p$'s.

There are $\lfloor\frac{m}{p^{k}}\rfloor$ values of $X$ divisible by $p^k$ and, therefore,
$\lfloor\frac{m}{p^{k}}\rfloor\!\!-\!\!\lfloor\frac{m}{p^{k+1}}\rfloor$ values of $X$  such that $X_p=k$.
Thus, $H(X|X_p=k)=\log \bigl(\lfloor\frac{m}{p^{k}}\rfloor\!\!-\!\!\lfloor\frac{m}{p^{k+1}}\rfloor \bigr)\leq \log \frac{m}{p^{k}}=\log m - k\log p
$, $H(X|X_p)\leq \log m - \mathbb{E}(X_p)\log p$, and

\begin{equation}
\sum_{p\text{ prime }\leq m} d(X,X_p) =
\sum_{p\text{ prime }\leq m} \frac{H(X|X_p)}{H(X)}
\leq \sum_{p\text{ prime }\leq m} \frac{\log m - \mathbb{E}(X_p)\log p}{\log m}
=n - \frac{\log m!}{m\log m}.
\end{equation}

In the latter equality we have used the exact value $\sum_{p} \mathbb{E}(X_p)\log p = \frac{\log m!}{m}$. This can be easily checked from the reconstruction formula itself (!), since

\begin{equation}
\sum_{p\text{ prime }\leq m} \mathbb{E}(X_p)\log p =
\mathbb{E} \log \prod_{p\text{ prime }\leq m} p^{X_p} = \mathbb{E} \log X = \frac{\log m!}{m}.
\end{equation}

Since $\log m! \leq m\log m$, the above upper bound is not tight enough to prove inequality (<ref>) of Theorem <ref>.
It is only satisfied asymptotically as $m\to+\infty$ since then $\frac{\log m!}{m\log m}\to 1$.
Likewise, the independence assumption of Theorem <ref> is only true asymptotically: In fact,
since for distinct primes $p_1,\ldots,p_\ell$,

\begin{equation}
\mathbb{P}\bigl(X_{p_1}\geq k_1,\ldots,X_{p_\ell}\geq k_\ell\bigr)   = \frac{1}{m} \biggl\lceil \frac{m}{p_1^{k_1}\cdots p_\ell^{k_\ell}}\biggr\rceil \to \frac{1}{p_1^{k_1}\cdots p_\ell^{k_\ell}}
\end{equation}

it follows that the $X_p$ converge in distribution toward independent geometric variables with respective parameters $1-\frac{1}{p}$.

§.§ Chinese Remainder Theorem

Consider an integer-valued random variable $X$, uniformly distributed over $\{0,1,\ldots,k-1\}$ where
$k = \prod_{i=1}^{n}k_{i}$ is the product of $n$ pairwise coprime factors $>1$, and define the following remainders modulo these factors:

\begin{equation} \label{equation-crm}
\begin{cases}
X_{1} &\equiv X \bmod k_{1} \\
X_{2} &\equiv X\bmod k_{2}\\
&\vdots \\
X_{n} &\equiv X \bmod k_{n}.
\end{cases}
\end{equation}

By the well known Chinese remainder theorem, this system of equations has a unique solution in $\{0,1,\ldots,k-1\}$, i.e.. perfect reconstruction of $X$ is possible.

Clearly, since $X$ is uniformly distributed, $X_i$ is likewise uniformly distributed over $\{0,1,\ldots k_i-1\}$ so that $H(X_i)=\log k_i$, $d(X,X_i)=1-\frac{H(X_i)}{H(X)}= 1- \frac{\log k_i}{\log k}$ and

\begin{equation}
\sum_{i=1}^{n}d(X,X_{i})=   \sum_{i=1}^{n}\bigl(1- \frac{\log k_i}{\log k}\bigr) = n- \frac{\log  \prod_{i=1}^{n} k_i}{\log k} = n-1.
\end{equation}

Thus, inequality (<ref>) of Theorem <ref> is achieved with equality, which proves that $X_1,X_2,\ldots,X_n$ are independent.
Had we proved directly this independence, Theorem <ref> would have shown that perfect reconstruction is possible. Thus, a information theoretic proof of the Chinese remainder theorem using this method amounts to proving such an independence. But this can be done quite similarly as the Chinese remainder theorem is classically proved.

With our present method, however, it can be easily seen that perfect reconstruction would not be possible if we do not use all components $X_1,X_2,\ldots,X_n$. Indeed, suppose without loss of generality that one tries to reconstruct $X$ only from $X_1,X_2,\ldots,X_{n-1}$.
Then by the above calculation,

\begin{equation}
\sum_{i=1}^{n-1}d(X,X_{i})=   \sum_{i=1}^{n-1}\bigl(1- \frac{\log k_i}{\log k}\bigr) = n-1- \frac{\log  \prod_{i=1}^{n-1} k_i}{\log k} = n-2 + \frac{\log k_n}{\log k} >n-2
\end{equation}

which shows by Theorem <ref> that perfect reconstruction of $X$ from less than $n$ remainders is impossible.

§.§ Optimal Sort

In this Subsection, we provide a new information theoretic proof of the following

Any pairwise comparison-based sorting algorithm has worst-case computational complexity $\geq \log_2 k! = \Omega(k\log_2 k)$ where $k$ is the cardinality of the list to be sorted.

Consider a finite, totally ordered list of $k$ elements. It can be seen as a permutation of the uniquely sorted elements, and sorting this list amounts to finding this permutation.
Let $X = (X_{1},X_{2},...,X_{k})$ be a (uniformly chosen) random permutation on $\{1,2,\ldots,k\}$.

For $i,j \in \{1,\ldots,k\}$ with $i \not= j$, let $X_{i,j}$ be the binary random variable taking the value $1$ if $X_{i} < X_{j}$ and $0$ otherwise. Clearly $X_{i,j}\leq X$ for any $i,j$.

Since there are as many permutations such that $X_{i} < X_{j}$  as such that $X_{i} > X_{j}$,
every $X_{i,j}$ is a Bernoulli ($1/2$) variable (equiprobable bit). Therefore,

\begin{equation}
d(X,X_{i,j})=1-\frac{\log 2}{\log k! } = 1-\frac{1}{\log_2 k! }.
\end{equation}

Assuming $n$ pairwise comparisons are made to sort the complete list, this gives

\begin{equation}
\sum_{i,j \text{ ($n$ terms)}} d(X,X_{i,j})= n-\frac{n}{\log_2 k! }.
\end{equation}

By Theorem <ref>, it is necessary that this value does not exceed $n-1$, i.e., $n\geq \log_2 k!$ for perfect reconstruction to hold. In other words, the wort-case complexity to achieve the complete sort for any possible realization of the initial unsorted list requires at least $\lceil\log_2 k!\rceil$ pairwise comparisons.

This example illustrates a method to find a lower bound on the worst-case complexity of a problem. The first step is to express the instance of the problem as a random variable $X$. Second, one determines which pieces of information one is allowed to extract from $X$, and models them as “observed” random variables $X_{i} \leq X$. Third, for each $i$, we compute the Rajski distance $d(X,X_{i})$. Finally, we use Theorem <ref> to find a lower bound on the number of “observed” variables $X_{i}$ that 	are required to reconstruct $X$.
We feel that such a method is interesting because it is often harder to find a lower bound on the complexity of a problem than to find an upper bound on it.

§ CONCLUSION AND PERSPECTIVES

It is an understatement to say that
the “true” information theory of 1953 was not as popular as the classical theory of 1948.
John Pierce, a colleague of Shannon, wrote that
“apparently the structure was not good enough to lead to anything of great value” [13].
We find two possible reasons for this pessimism: the fact that the lattice is not Boolean, which does not facilitate the calculations; and the discontinuous nature of the common informtion with respect to the entropy metric.

However, as we have shown in this paper, this lattice structure is quite helpful to understand reconstruction problems. As shown in Section <ref>, the implications of the resolution of perfect reconstruction problems go beyond signal processing, since the concept of information is pervasive in all fields of mathematics and of science. Thus, we believe it is important to deepen this theory, defining information per se, and to further generalize the reconstruction problems. It would indeed be of great interest to find a simple sufficient condition to reconstruct a variable $X$ from (not necessarily independent) components $X_1,X_2,\ldots,X_n$.

One may legitimately argue that most examples (except in Subsection <ref>) assume uniform distributions, where the entropy is just a logarithmic measure of the alphabet size, and since all considered processings are deterministic, the essence of the present reconstruction problem appears more combinatorial than probabilistic. Indeed, a desirable perspective is to go beyond perfect reconstruction of discrete quantities by considering the possibility of noisy reconstruction of discrete and/or continuous sources of information.

In a perspective closer to computer science, we have used our theorems to find a lower bound on the complexity of the comparison-based sorting problem. It would be interesting to find other problems for which a lower bound on complexity can be found using our technique, especially for decision problems that are not known to be in P.

Finally, as another practical perspective for security problems, one may assume that
$X$ models all the possible values that can take a secret key in a given cryptographic device, and that an attacker can observe $k$ random values that are deterministically obtained from $X$. Such important problems have been studied e.g., in [10] to evaluate information leakage in the execution of deterministic programs. One may use the theorems of Section <ref> to find a lower bound on $k$ for the attacker to be able to reconstruct the secret.

[2]
E. C. Cherry, “A history of the theory of information,” in Proc. Inst. Electrical Engineering (London), vol. 98, no. 55, pp. 383–393, Sept. 1951.

[3]
I. Csiszár and J. Körner, Information Theory. Coding Theorems for DiscreteMemoryless Systems. Cambridge University Press, 2nd edition, 2011.

[4]
R. M. Fano, Class notes for course 6.574 : Transmission of Information, MIT, Cambridge, MA, 1952.

[5]
—, “Interview by Aftab, Cheung, Kim, Thkkar, Yeddanapudi, 6.933 Project History, Massachusetts Institute of Technology,” Nov. 2001.

[6]
P. Gács and  J. Körner, “Common information is far less than mutual information,” Problems of Control and Information Theory, vol. 2, no. 2, pp. 149–162, Jan. 1973.

[7]
Y. Horibe, “A note on entropy metrics,” Information and Control, vol. 22, no. 4, pp. 403–403, May 1973.

[9]
P. Jaccard, “Distribution de la flore alpine dans le bassin des Dranses et dans quelques régions voisines”, Bulletin de la Société Vaudoise des Sciences Naturelles, vol. 37, no. 140, pp. 241–272, 1901.

[10]
P. Malacaria, “Algebraic foundations for quantitative information flow,” Mathematical Structures in Computer Science, vol. 25, no. 2, pp. 404–428, Feb. 2015.

[12]
Y. Nakamura. “Entropy and semivaluations on semilattices,” Kodai Math. Seminar Report, vol. 22, no. 4, pp. 443–468, 1970.

[13]
J.R. Pierce, “The early days of information theory,” IEEE Transactions on Information Theory, vol. 19, no. 1, pp. 3–8, Jan. 1973.

[14]
C. Rajski, “A metric space of discrete probability distributions,” Information and Control, vol. 4, no. 4, pp. 371–377, Dec. 1961.

[15]
O. Rioul, Théorie de l'information et du codage, Hermes Science - Lavoisier: London, 2007.

[16]
O. Rioul, J. Béguinot, V. Rabiet and A. Souloumiac, “La véritable (et méconnue) théorie de l'information de Shannon”, in Proc. 28e Colloque GRETSI 2022, Nancy, France, 6–9 Sept. 2022.

[17]
C. E. Shannon, “A mathematical theory of communication,” Bell Syst. Tech. J., vol. 27, no. 3 & 4, pp. 379–423 & 623–656, July & Oct. 1948.

[18]
—, “Some topics on information theory,” in Proc. Int. Congress Math., AMS, Ed., vol. 2, Aug. 30–Sept. 6, 1950, pp. 262–263.

[19]
—, “The lattice theory of information,” in Transactions of the IRE Professional Group on Information Theory, vol. 1, no. 1, pp. 105–107, Feb. 1953.

[20]
—, “The bandwagon (editorial),” IRE Transactions on Information Theory, vol. 2, no. 1, p. 3, Mar. 1956.

[21]
A. D. Wyner, “The common information of two dependent random variables,” IEEE Transactions on Information Theory, vol. 21, no. 2, pp. 163–179, Mar. 1975.

[22]
R. W. Yeung, Information Theory and Network Coding. Springer, 2008.