Una distancia de coincidencia

Question

Considere $\sigma,\sigma' \in \{1,\dots,p\}^n$ y que $$ d(\sigma,\sigma') = \min_{\pi \in S_p} \frac1n \sum_{i=1}^n 1_{\{ \pi(\sigma_i) \neq \sigma'_i \}} $$ donde $S_p$ es el grupo simétrico en $\{1,\dots,p\}$ (el conjunto de permutaciones de ese conjunto). Es $d$ ¿una métrica válida? En particular, ¿se cumple la desigualdad del triángulo?

EDIT: Debería haber planteado la pregunta así: ¿Es esta una pseudo métrica válida?

Answer 1

Esto no es una métrica, ya que la distancia es $0$ para vectores que son permutaciones entre sí.

[ Editar: ]

Sin embargo, es una pseudométrica que desaparece si y sólo si al ignorar el orden de los vectores se obtiene el mismo multiconjunto. Por lo tanto, la identificación métrica de esta pseudométrica considera que los vectores son equivalentes si corresponden al mismo multiconjunto, e induce una métrica sobre el conjunto de multiconjuntos de $n$ de $p$ artículos.

Claramente $d(\sigma,\sigma)=0$ y $d(\sigma,\sigma')=d(\sigma',\sigma)$ por lo que sólo tenemos que comprobar la desigualdad del triángulo para demostrar que efectivamente se trata de una pseudométrica sobre los vectores y una métrica sobre los conjuntos múltiples. Pero la desigualdad del triángulo se cumple ya que para tres vectores $a,b,c\in\{1,\dotsc,p\}^n$ podemos componer las permutaciones minimizadoras para $d(a,b)$ y $d(b,c)$ para obtener una permutación que sea testigo de la desigualdad del triángulo, ya que el número de desajustes que deja la composición es como máximo la suma de los números de desajustes que dejan las permutaciones individuales.