In probability theory and information theory, the variation of information or shared information distance is a measure of the distance between two clusterings (partitions of elements). It is closely related to mutual information; indeed, it is a simple linear expression involving the mutual information. Unlike the mutual information, however, the variation of information is a true metric, in that it obeys the triangle inequality.

Suppose we have two partitions ${\displaystyle X}$ and ${\displaystyle Y}$ of a set ${\displaystyle A}$, namely ${\displaystyle X=\{X_{1},X_{2},\ldots ,X_{k}\}}$ and ${\displaystyle Y=\{Y_{1},Y_{2},\ldots ,Y_{l}\}}$.

Let:

Then the variation of information between the two partitions is:

This is equivalent to the shared information distance between the random variables i and j with respect to the uniform probability measure on ${\displaystyle A}$ defined by ${\displaystyle \mu (B):=|B|/n}$ for ${\displaystyle B\subseteq A}$.

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