2
$\begingroup$

Given a distance $d$ on a (finite) set $S$ satisfying the triangle inequality, I am trying to show that the extended (average) distance

$g(A,B):=\dfrac{1}{|A||B|}\sum_{a\in A, b\in B}d(a,b)$

on non-empty subsets of $S$ also satisfies the triangle inequality.

Q: Is this true, and how then would I show it?


Attempt:

So, I want: \begin{equation} \dfrac{1}{|A||B|}\sum_{a\in A, b\in B}d(a,b)+\dfrac{1}{|B||C|}\sum_{b\in B, c\in C}d(b,c)-\dfrac{1}{|A||C|}\sum_{a\in A, c\in C}d(a,c)\geq0\quad (1) \end{equation}

rewriting (1) with a common denominator I get: \begin{equation} \dfrac{1}{|A||B||C|}(|C|\sum_{a\in A, b\in B}d(a,b)+|A|\sum_{b\in B, c\in C}d(b,c)-|B|\sum_{a\in A, c\in C}d(a,c))\geq 0\quad (2) \end{equation} I get that I should use $d(a,b)+d(b,c)-d(a,c)\geq 0$ since $d$ satisfies TI, but I have the cardinalities in there as well and I can't seem to rewrite it so that I can. I also tried using that

$\dfrac{1}{|A||B|}\sum_{a\in A, b\in B}d(a,b)\geq \dfrac{1}{|A||B|}|A||B|\min\{d(a,b)\}=\min\{d(a,b)\}$, so that

$(1)\geq \min\{d(a,b)\}+\min\{d(b,c)\}-\max\{d(a,c)\}$,

but then I would have to show that

$\max\{d(a,c)\}\leq\min\{d(a,b)\}+\min\{d(b,c)\}$,

and this is just obviously not true just by simple examples such as $A=[1,2],B=[3,100],C=[101,102]$ or similar.

I saw somewhere where they got that (1) simplifies to: \begin{equation} \dfrac{1}{|A||B||C|}(\sum_{a\in A}\sum_{b\in B}\sum_{c\in C}(d(a,b)+d(b,c)-d(a,c))\geq 0. \end{equation} but there were no more details.

I also found this, but did not see that it had to do with average distance.

QUESTION:

Isn't the above equation just equal to \begin{equation} \dfrac{1}{|A||B||C|}(\sum_{a\in A,b\in B}d(a,b)+\sum_{b\in B,c\in C}d(b,c)-\sum_{a\in A,c\in C}d(a,c))\geq 0? \end{equation} But how did they get rid of $|A|,|B|,|C|$ in (2)? Am I missing something here?

Sorry if it seems to simple, I am at beginning undergraduate and am self studying some more advanced stuff.

$\endgroup$

1 Answer 1

2
$\begingroup$

For each triple $(a,b,c) \in P = A \times B \times C$ we have $d(a,b) + d(b,c) \ge d(a,c)$. Therefore

$$\sum_{(a,b,c) \in P}d(a,b) + \sum_{(a,b,c) \in P}d(b,c) \ge \sum_{(a,b,c) \in P}d(a,c) .$$

But we have $$\sum_{(a,b,c) \in P}d(a,b) = \lvert C \rvert \sum_{(a,b) \in A \times B}d(a,b)$$ and similarly for the other two sums. This gives $$\lvert C \rvert \sum_{(a,b) \in A \times B}d(a,b) + \lvert A \rvert \sum_{(b,c) \in B \times C}d(b,c) \ge \lvert B \rvert \sum_{(a,c) \in A \times C}d(a,c) .$$ Now divide by $|A||B||C|$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .