Somewhat surprisingly, Jean Bourgain's 1985 theorem about embedding finite metric spaces into Hilbert spaces was not mentioned yet. Since metrics have not mentioned at all in this thread, let me mention this example now.

The topic of representing prescribed, possibly strange finite metric spaces 'as best one can' by non-strange, traditional metric spaces is important e.g. in computational biology. Very briefly, I think the essence of all of this is

not to have to store a table of pairwise distances among any two of a large number of proteins, which after all would take space quadratic in the number of 'specimens', rather label/represent each protein by an element of a traditional metric space, and then calculate a distance the traditional way, from the traditional representatives, on an as-needed-basis.

For this to result in only a small error of approximation (of the 'true' distance w.r.t. some new-fangled 'similarity distance' between proteins), one needs to know how well such 'representations'/'low-distortion embeddings' can be done in principle.

Bougain used the "probabilistic method" to prove a lower bound on how well this can be done.

The publication is Jean Bourgain: On lipschitz embedding of finite metric spaces in Hilbert space. Israel Journal of Mathematics March 1985, Volume 52, Issue 1–2, pp 46–52, and the abstract reads:

"It is shown than any $n$ point metric space is up to $\log n$ lipeomorphic to a subset of Hilbert space. We also exhibit an example of an $n$-point metric space which cannot be embedded in Hilbert space with distortion less than $(\log n)/(\log\log n)$, showing that the positive result is essentially best possible. The methods used are of probabilistic nature. For instance, to construct our example, we make use of random graphs."

(emphasis added)

Somewhat surprisingly, Jean Bourgain's 1985 theorem about embedding finite metric spaces into Hilbert spaces was not mentioned yet. Since metrics have not mentioned at all in this thread, let me mention this example now.

The topic of representing prescribed, possibly strange finite metric spaces 'as best one can' by non-strange, traditional metric spaces is important e.g. in computational biology. Very briefly, I think the essence of all of this is

not to have to store a table of pairwise distances among any two of a large number of proteins, which after all would take space quadratic in the number of 'specimens', rather label/represent each protein by an element of a traditional metric space, and then calculate a distance the traditional way, from the traditional representatives, on an as-needed-basis.

For this to result in only a small error of approximation (of the 'true' distance w.r.t. some new-fangled 'similarity distance' between proteins), one needs to know how well such 'representations'/'low-distortion embeddings' can be done in principle.

Bourgain used the "probabilistic method" to prove a lower bound on how well this can be done.

The publication is Jean Bourgain: On lipschitz embedding of finite metric spaces in Hilbert space. Israel Journal of Mathematics March 1985, Volume 52, Issue 1–2, pp 46–52, and the abstract reads:

"It is shown than any $n$ point metric space is up to $\log n$ lipeomorphic to a subset of Hilbert space. We also exhibit an example of an $n$-point metric space which cannot be embedded in Hilbert space with distortion less than $(\log n)/(\log\log n)$, showing that the positive result is essentially best possible. The methods used are of probabilistic nature. For instance, to construct our example, we make use of random graphs."

(emphasis added)