# How do I show the triangle inequality for average distance $\frac{1}{|A||B|}\sum_{a\in A,b\in B}d(a,b)$?

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: $$$$\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)$$$$

rewriting (1) with a common denominator I get: $$$$\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)$$$$ 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: $$$$\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.$$$$ 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 $$$$\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?$$$$ 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.

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|$$.