Hamming distance of binary vectors

Question

Heyaa!! I was trying to solve the following questions and i am stuck. I do have an intuition as to how would one solve it, but i don't know how to prove that.

Let $X = \{0, 1\}^n$ be the set of binary vectors of length $n$. For $x = (x_1 , \ldots , x_n )$ and $y = (y_1 , . . . , y_n )$ in $X$, define their Hamming distance to be $d(x, y) =$ # $\{i ∈ \{1, 2, . . . , n\} : x_i \neq y_i\}$,i.e. the number of places where $x$ and $y$ differ. Show that $d$ is a metric on $X$. Is it an ultrametric?

I think the first property $d(x,y) \geq 0$ is fairly obvious since that is the scope, and property 2, $d(x, y) = d(y, x)$ for all $x, y ∈ X$ can be proven using mod and absolute values (not sure how to express it), and i am finding the triangle property hard to figure out. Also, I think it is an ultrametric because the LUB of two intervals (here) would always be greater than the third?

Sorry if it doesn't make a lot of sense i'm just starting to learnt eh topic. I'll really appreciate your help!! Thanks so much!! :)

Answer 1

You should also argue that $d(x,y)=0$ if and only if $x=y$.

Consider three elements $x=(x_{1},x_{2},...,x_{n}),y=(y_{1},y_{2},...,y_{n}),z=(z_{1},z_{2},...,z_{n})$ in $X$. If $i$ is such that $x_{i}\neq z_{i}$ then either $x_{i}\neq y_{i}$ or $y_{i}\neq z_{i}$. So the set $\left\{1\leq i\leq n\mid x_{i}\neq z_{i}\right\}$ is a subset of $\left\{1\leq i\leq n\mid x_{i}\neq y_{i}\right\}\cup \left\{1\leq i\leq n\mid y_{i}\neq z_{i}\right\}$. Can you take it from here?

For the ultrametric property, I am not quite sure what interval you mean. The question is whether we can find $x,y,z$ as before such that $x$ differs in more indices with $z$ than $y$ with $z$ or $z$ with $y$. My advice would be to take $n=2$ and write down all elements of $X$ and all distances between them.

Answer 2

This has little to do with $p$-adic or algebraic topology as you labelled.

It is a metric. In fact, if we treat $X$ as the $\mathbb F_2^n$, a vector space over $\mathbb F_2$, or at least an abelian group. Then we may define the Hamming weight $\|x\|=\sum_i |x_i|$ where $|x_i|=1$ if $x_i=\overline 1\in\mathbb F_2$ and $x_i=0$ otherwise. If we can show this is indeed a norm, then we can define $d(x,y):=\|x-y\|=\|x+y\|$ that must be a metric, and clearly this $d(x,y)$ is the same as the Hamming distance.

Indeed, we only need to show $\|x+y\|\le \|x\| + \|y\|$. This is not hard.

It's not a ultrametric when $n\ge 2$. Take $x=(1, 0, 0, \cdots)$ and $y=(0, 1, 0, \cdots)$, we have $d(x,y)=\|x+y\|=2, d(x, 0)=\|x\|=1, d(y, 0)=\|y\|=1$, hence $d(x,y)\le\max\{d(x,0), d(y,0)\}$ doesn't hold.

Of course, it's not strictly necessary to introduce the vector space $\mathbb F_2^n$, but in most cases, this help gain more intuition and simplify the argument (to show $\|a+b\|\le\|a\|+\|b\|$ which involves only two elements is easier than $d(a,c)\le d(a,b)+d(b,c)$ which involves three elements.)