TransWikia.com

Non Case Analysis Proof of Triangle Inequality for Hamming Distance

Mathematics Asked by Henry Powell on November 24, 2021

I’ve written a proof for the triangle inequality for the Hamming distance metric on ordered triplets of ones and zeroes. I wanted to try to come up with a proof that didn’t use case analysis (which I can see is more straightforward). I’d appreciate some feedback on whether the proof is correct, how it can be improved etc.

Proof:
First note that the Hamming distance between two ordered triples of zeros and ones is equivalent to subtracting the two vectors and then squaring the Euclidean norm of the resulting vector i.e.

begin{equation}
d(x,y) = |(vec{x}- vec{y})|^{2}
end{equation}

Where $|(vec{x}- vec{y})|$ denotes the Euclidean norm. Proving the triangle inequality for this metric is thus equivalent to proving:

begin{equation}
|(vec{x}-vec{y})|^{2} leq |(vec{x}-vec{z})|^{2} + |(vec{z}-vec{y})|^{2}
end{equation}

The set $X$ of ordered triples of zeroes and ones is a subset of $mathbb{R}^{3}$ and therefore $(X, d’)$ (where $d’$ is the Euclidean norm) is a metric space and subsequently:

begin{multline}
sqrt{(vec{x}_{1}-vec{y}_{1})^{2}+(vec{x}_{2}-vec{y}_{2})^{2}+(vec{x}_{3}-vec{y}_{3})^{2}} leq \ sqrt{(vec{x}_{1}-vec{z}_{1})^{2}+(vec{x}_{2}-vec{z}_{2})^{2}+(vec{x}_{3}-vec{z}_{3})^{2}} + \ sqrt{(vec{z}_{1}-vec{y}_{1})^{2}+(vec{z}_{2}-vec{y}_{2})^{2}+(vec{z}_{3}-vec{y}_{3})^{2}}
end{multline}

by the triangle inequality for the Euclidean distance on $mathbb{R}^{3}$.

Next note that the squared terms underneath the square roots are the equivalent to the first, second, and third elements of the vectors produced by subtracting the corresponding vectors in each term. We can thus rewrite (2) as:

begin{multline}
sqrt{(vec{x}-vec{y})_{1}^{2}+(vec{x}-vec{y})_{2}^{2}+(vec{x}-vec{y})_{3}^{2}} leq \ sqrt{(vec{x}-vec{z})_{1}^{2}+(vec{x}-vec{z})_{2}^{2}+(vec{x}-vec{y})_{3}^{2}} + \ sqrt{(vec{z}-vec{y})_{1}^{2}+(vec{z}-vec{y})_{2}^{2}+(vec{z}-vec{y})_{3}^{2}}
end{multline}

or:

begin{equation}
|(vec{x}-vec{y})| leq |(vec{x}-vec{z})| + |(vec{z}-vec{y})|
end{equation}

Squaring both sides of this inequality yields

begin{equation}
|(vec{x}-vec{y})|^{2} leq (|(vec{x}-vec{z})| + |(vec{z}-vec{y})|)^{2}
end{equation}

And since

begin{equation}
(|(vec{x}-vec{z})| + |(vec{z}-vec{y})|)^{2} leq |(vec{x}-vec{z})|^{2} + |(vec{z}-vec{y})|^{2}
end{equation}

We have:
begin{equation}
|(vec{x}-vec{y})|^{2} leq |(vec{x}-vec{z})|^{2} + |(vec{z}-vec{y})|^{2}
end{equation}

as required.

One Answer

Here is a correct end of proof (without cases), after you've squared the inequality.

Denote $x,y,z$ the coordinates (of same rank) of $vec x,vec y,vec z$. It sufficed to prove the corresponding i,nequality for these cooordinates, i.e. $$(x-y)^2le (x-z)^2+(z-y)^2.$$ Writing $x-y=(x-z)+(z-y)$, it amounts to proving that $$(x-y)^2+2(x-z)(z-y)+(y-z)^2le (x-z)^2+(z-y)^2.$$ begin{align} &text{i.e.}qquad&2(z-x)(z-y)=2(z^2-(x+y)z+xy)&ge 0 &&qquad end{align} This means the polynomial $P(z)=z^2-(x+y)z+xy$ takes nonnegative values for $z=0,1$. Now $P(0)=xyin{0,1}$ and $$P(1)=xy-(x+y)+1=(x-1)(y-1) ge 0$$ since $x,yin{0,1}$.

Answered by Bernard on November 24, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP