Task number: 4030

Verify that the Hamming distance satisfies the axioms of the metric.

  • Hint

    We use the definition \(\operatorname{dist}(x,y)=|\{i: x_i\ne y_i\}|\)

    • \(\forall x,y\in \Sigma^n: \operatorname{dist}(x,y)\ge 0\)
      … the cardinality of a finte set is a finite number
    • \(\forall x,y\in \Sigma^n: \operatorname{dist}(x,y)= 0 \Longleftrightarrow x=y \)
      … \(\{i: x_i\ne y_i\}=\emptyset\) if and only if \(x,y\) are identical
    • \(\forall x,y\in \Sigma^n: \operatorname{dist}(x,y)=\operatorname{dist}(y,x)\)
      … \(x_i\ne y_i\) if and only if \(y_i\ne x_i\)
    • \(\forall x,y,z\in \Sigma^n: \operatorname{dist}(x,z)\le \operatorname{dist}(x,y)+\operatorname{dist}(y,z)\)
      … \(x_i\ne z_i \Longrightarrow x_i\ne y_i \lor y_i\ne z_i\) and hence \( \{i: x_i\ne z_i\}\subseteq \{i: x_i\ne y_i\} \cup \{i: y_i\ne z_i\}\)
Difficulty level: Easy task (using definitions and simple reasoning)
Proving or derivation task
Cs translation
Send comment on task by email