Showing that a mapping $d:\{-1,1\}^{\mathbb{N}}\times \{-1,1\}^{\mathbb{N}}\to[0,\infty)$ satisfies the triangle inequality

Question

Define the following mapping $d:\{-1,1\}^{\mathbb{N}}\times \{-1,1\}^{\mathbb{N}}\to[0,\infty)$ by $$d(s^1, s^2)=2^{-\inf\{k\in\mathbb{N}\,: \,s^1_k\neq s^2_k\}}$$ for $s^j=(s^j_1, s^j_2, \ldots), j=1,2$. I am interested in showing that $d$ satisfies the triangle inequality: $$d(s^1, s^2) \le d(s^1, s^3) + d(s^3, s^2)$$ for any sequences $s^j\in\{-1,1\}^{\mathbb{N}}$. I have tried various manipulations but got nowhere because I don't see any nice additive structure in the definition of the metric $d$.

Answer 1

Here is my brute force way approach:

WTS: $$d(s^1,s^2)\leq d(s^1,s^3)+d(s^2,s^3)$$

Suppose $d(s^2,s^3)= 2^{-k}$ and $d(s^1,s^3)= 2^{-l}$. This means that for $n<k$, $s^2_n=s^3_n$ and for $n<l$, $s^1_n=s^3_n$. Let's compute $d(s^1,s^2)$.

Notice for $n<min(k,l)$, $s^1_n=s^2_n$. Thus, $min(k,l)\leq inf\{m:s^1_m\neq s^2_m\}$. Thus $d(s^1,s^2)\leq2^{-min(k,l)}.$ You should be able to finish this one off.

Answer 2

You can just do a brute force case analysis. Pick $x,y,z$.

If $d(x,y) = 0$ there is nothing to be done, so suppose $d(x,y)>0$.

Let $d(x,y) = {1 \over 2^k}$. (In particular, note that $x(k) \neq y(k)$.)

If $d(x,z) = 0$ then $z=x$ and so the result is true, so suppose $d(x,z) >0$.

Let ${1 \over 2^m} = d(x,z)$ and consider $d(x,z)+d(z,y)$.

If $m \le k$ there is nothing to be done.

If $m>k$ then $x(i) = z(i)$ for $i=0,...,m-1$ and so $y(k) \neq z(k)$ and so $z(k) \neq y(k)$ and so $d(z,y) = {1 \over 2^k}$, which gives the desired result.