Explicit information content

We can rewrite this definition in terms that explicitly highlight the information content of this metric.

The set of all partitions of a set form a compact Lattice where the partial order induces two operations, the meet ${\displaystyle \wedge }$ and the join ${\displaystyle \vee }$, where the maximum ${\displaystyle {\overline {\mathrm {1} }}}$ is the partition with only one block, i.e., all elements grouped together, and the minimum is ${\displaystyle {\overline {\mathrm {0} }}}$, the partition consisting of all elements as singletons. The meet of two partitions ${\displaystyle X}$ and ${\displaystyle Y}$ is easy to understand as that partition formed by all pair intersections of one block of, ${\displaystyle X_{i}}$, of ${\displaystyle X}$ and one, ${\displaystyle Y_{i}}$, of ${\displaystyle Y}$. It then follows that ${\displaystyle X\wedge Y\subseteq X}$ and ${\displaystyle X\wedge Y\subseteq Y}$.

Let's define the entropy of a partition ${\displaystyle X}$ as

where ${\displaystyle p_{i}=|X_{i}|/n}$. Clearly, ${\displaystyle H({\overline {\mathrm {1} }})=0}$ and ${\displaystyle H({\overline {\mathrm {0} }})=\log \,n}$. The entropy of a partition is a monotonous function on the lattice of partitions in the sense that ${\displaystyle X\subseteq Y\Rightarrow H(X)\geq H(Y)}$.

Then the VI distance between ${\displaystyle X}$ and ${\displaystyle Y}$ is given by

The difference ${\displaystyle d(X,Y)\equiv |H\left(X\right)-H\left(Y\right)|}$ is a pseudo-metric as ${\displaystyle d(X,Y)=0}$ doesn't necessarily imply that ${\displaystyle X=Y}$. From the definition of ${\displaystyle {\overline {\mathrm {1} }}}$, it is ${\displaystyle \mathrm {VI} (X,\mathrm {1} )\,=\,H\left(X\right)}$.

If in the Hasse diagram we draw an edge from every partition to the maximum ${\displaystyle {\overline {\mathrm {1} }}}$ and assign it a weight equal to the VI distance between the given partition and ${\displaystyle {\overline {\mathrm {1} }}}$, we can interpret the VI distance as basically an average of differences of edge weights to the maximum

For ${\displaystyle H(X)}$ as defined above, it holds that the joint information of two partitions coincides with the entropy of the meet

and we also have that ${\displaystyle d(X,X\wedge Y)\,=\,H(X\wedge Y|X)}$ coincides with the conditional entropy of the meet (intersection) ${\displaystyle X\wedge Y}$ relative to ${\displaystyle X}$.

Triangle inequality

To verify the triangle inequality ${\displaystyle \mathrm {VI} (X;Z)\leq \mathrm {VI} (X;Y)+\mathrm {VI} (Y;Z)}$, expand using the identity ${\displaystyle \mathrm {VI} (X;Y)=H(X|Y)+H(Y|X)}$. It suffices to prove

$${\displaystyle H(X|Z)\leq H(X|Y)+H(Y|Z)}$$

The right side equals ${\displaystyle H(X,Y|Z)}$^{[dubious – discuss]}, which is no less than the left side. This is intuitive, as ${\displaystyle X,Y|Z}$ contains no less randomness than ${\displaystyle X|Z}$.