2

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?

passerby51
  • 4,140

1 Answers1

3

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.

joriki
  • 238,052
  • Thanks. That is fine, my main concern is the triangle inequality. I have edited the question. – passerby51 Mar 01 '13 at 22:33
  • Thanks. Could you elaborate on the last sentence you wrote (this part: "since the number of mismatches left...")? Is that supposed to be obvious? – passerby51 Mar 01 '13 at 23:28
  • By the way, do you know if this distance or a variant of it has a name? – passerby51 Mar 01 '13 at 23:31
  • 1
    @passerby51: The minimizing permutation for $d(a,b)$ moves as many elements of $a$ as possible such that they end up matching elements in $b$. Except for the factor $1/n$, your (pseudo)metric counts the number of mismatches between $b$ and the permuted version of $a$. If you now apply the minimizing permutation for $d(b,c)$ to the permuted version of $a$, any elements that had been matched up with $b$ are now matched up with $c$, unless they're among the elements that this second permutation fails to match when permuting $b$ to match $c$. – joriki Mar 01 '13 at 23:42
  • 1
    @passerby51: Regarding a name for the metric, I don't know one; you might call it the multiset metric, or you could check this book, which amazingly consists of definitions and names of various metrics filling $400$ pages. – joriki Mar 01 '13 at 23:45
  • I see. Thanks for the insightful comment and the wonderful link. – passerby51 Mar 02 '13 at 03:31