Our book has this exercise:
Distance between Boolean vectors. Suppose that $x$ and $y$ are Boolean $n$-vectors, which means that each of their entries is either $0$ or $1$. What is their distance $\|x-y\|?$
I think I've got it, but is there a simpler interpretation?
My attempt:
Whenever $x_i$ and $y_i$ (for $i = 1, 2, \dots, n$) are the same, we end up with a $0$ for $x_i - y_i$. Whenever they are different, we always get a $1$. My interpretation is that it's the square root of the number of bits that differ between $x$ and $y$.
But what is the significance of such a measure? Wouldn't computing the square of the distance be a more meaningful computation? Also, wouldn't it be faster to just do a pairwise bit comparison?
I am going through the same book and exercise at the moment and my interpretation is as per the previous comments on this post. However, it also seems that: $$0 \le ||x-y|| \le \sqrt n$$
i.e. assume that all bits differ, the distance can be at most $\sqrt n$.