A matching distance Consider $\sigma,\sigma' \in \{1,\dots,p\}^n$, and let
$$
 d(\sigma,\sigma') = \min_{\pi \in S_p} \frac1n \sum_{i=1}^n 1_{\{ \pi(\sigma_i) \neq \sigma'_i \}}
$$
where $S_p$ is the symmetric group on $\{1,\dots,p\}$ (the set of permutations of that set). Is $d$ a valid metric? In particular, does the triangle inequality hold?
EDIT: I should have stated the question as this: Is this a valid pseudo-metric?
 A: This is not a metric, since the distance is $0$ for vectors that are permutations of each other.
[Edit:]
However, it's a pseudometric which vanishes if and only if ignoring the order of the vectors yields the same multiset. Thus the metric identification of this pseudometric considers vectors equivalent if they correspond to the same multiset, and it induces a metric on the set of multisets of $n$ out of $p$ items.
Clearly $d(\sigma,\sigma)=0$ and $d(\sigma,\sigma')=d(\sigma',\sigma)$, so we only have to check the triangle inequality to show that this is indeed a pseudometric on the vectors and a metric on the multisets. But the triangle inequality is fulfilled since for three vectors $a,b,c\in\{1,\dotsc,p\}^n$ we can compose the minimizing permutations for $d(a,b)$ and $d(b,c)$ to obtain a permutation that is a witness for the triangle inequality, since the number of mismatches left by the composition is at most the sum of the numbers of mismatches left by the individual permutations.
