# Real-World Concentration of Measure

Some of my recent work has led me to think about the concentration of measure phenomenon. The standard example for concentration of measure is that most of the surface area of a (high dimensional) planet is close to the equator. This led me to try to think of real-world examples of the phenomenon. There are plenty of realistic situations supporting the phenomenon, but I’m looking for more striking examples. More precisely, I would like an example where people have noticed the “unusually high” concentration and have sought or proposed explanations when there really isn’t much to explain.

The most obvious would be the fact that most of the world’s population lives around the equator. However, this has a completely different valid explanation (as witnessed by the concentration of population in Canada) related to weather and similar issues. Population density doesn’t appear to be nicely distributed along meridians either, mostly because humans tend to live on land rather than water. Looking for examples in terms of population density looks like a dead end.

Concentration of measure also occurs in graphs. On the vertices of the unit $n$-cube, concentration of measure says that most vertices are nearly half-way between $(0,\dots,0)$ and its antipodal point $(1,\dots,1)$. (Indeed, the central limit theorem predicts that most vertices have equally many $0$‘s and $1$‘s with an error proportional to $1/\sqrt{n}$.) One real world graph is the so-called social web of human connections. The small world phenomenon says that any two people are at most 6 steps apart in the social web. Could this be a manifestation of the concentration of measure phenomenon?

I’m not sure. I always thought that the numbers for the small world phenomenon didn’t add up. (Though that strongly depends on which numbers you decide to use.) Looking at the small world phenomenon as a manifestation of concentration of measure seems to give enough wiggle room for the numbers to fit together, but this is just circumstantial evidence. Is there any concrete evidence that supports this point of view?

Filed under Combinatorics, Puzzle

### 5 Responses to Real-World Concentration of Measure

1. Sorry I do not get what you say? Are you talking about a proof for the six degrees of separation theory? Or is it more general what you are saying?

2. The basic question is to find a real-world example of concentration of measure. This is a well-understood phenomenon that happens in high-dimensional probability spaces, but I couldn’t find a good real-world example of it.

The “six degrees of separation” phenomenon shows some potential for being a manifestation of this. The problem is that I don’t know if social networks can be viewed as “high-dimensional” under some reasonable hypotheses. If so, concentration of measure would guarantee that almost all people would be almost exactly at the expected distance from any fixed person.

For example, if the expected distance from me in the US social network is, say, 5 then almost all people in the US would be 4 to 6 degrees of separation from me, while almost no one (relative to the US population) would be 1 to 3 degrees separated from me, or 7 or more degrees separated from me.

This interpretation of the small world phenomenon makes more sense than saying that 6 is an empirical upper bound on the diameter of the social network. However, this wouldn’t really “prove” the six degrees of separation theory, it would only give a different interpretation of the observed phenomenon.

3. Concentration of measure occurs naturally in ergodic dynamical systems … but most dynamical systems that engineers care about are not ergodic, but rather are litotic, in the sense that trajectories are concentrated such that compressive reconstruction is possible.

Example: the inner product between two random quantum states is order 1/\sqrt{n} (obviously). But if we choose the two quantum states to be matrix product states, then the distribution is “lumpy” … usually the inner products are very much smaller than ergodic arguments would suggest.

This mathematical phenomenon often is seen in practical quantum system simulation. Our QSE group uses it as an empirical test for compressibility: given a wave function, we plot its cumulative distribution of coefficients, and if that distribution is grossly skewed relative to the random case—as generically is true for open quantum systems—-then we know (empirically) that the states we are working with are algorithmically compressible … which from a quantum systems engineering point of view, is a very important fact to know.

These are the quantum dynamical systems that we call “litotic” (from the greek litotes: plainess, simplicity). We presently have a crude understanding of the dynamical origin of these states, as integral curves of (stochastic) algebraic potential gradients on Kahler manifolds—potentials that act to “focus” quantum trajectories onto litotic regions of phase-space—-but this theory is not very sophisticated.

That’s why it would be great to know whether there presently exists a formal mathematical theory of litotic dynamical systems, as contrasted with ergodic dynamical systems.

4. Here is an explicit example of what François Dorais was looking for: “a real-world example of concentration of measure”. And the example illustrates how subtle this concept can be!

Specifically, here is a link to a graph showing concentration of measure in quantum wave-functions calculated during spin simulations. This is a real-world example in a very literal sense: there is a large community of researchers—mainly in materials science and biomedicine—who calculate such wave functions on a daily basis (using codes such as SIMPSON and SPINEVOLUTION).

In this example we are considering quantum trajectories on a Hilbert space of 18 spins, so our state-space dimension is 2^18 ~ 256,000; large enough so that measure concentration should be easily visible.

The type of measure concentration we observe depends on how we unravel the trajectories. If we unravel the trajectories “ergodically” by modeling thermal noise as … well … noise, then the simulated trajectories fill the state-space uniformly, and we observe precisely the measure concentration that ergodic theory predicts. This is highly gratifying from a theoretical point of view (since it is consistent with our intuition that noisy quantum system dynamics are ergodic) but it is terribly unfortunate from the viewpoint of computing quantum trajectories efficiently (since the computational cost of keeping track of all these coefficients is very high).

On the other hand, if we unravel the trajectories “synoptically”, by modeling thermal noise as equivalent covert measurement, then again we see a concentration of measure, but with most quantum coefficients much smaller. This is the case even though the two simulations are informatically equivalent (as is well-known to the quantum computing community). This suggests that these trajectories are algorithmically compressible … which turns out to be true … for example, all the CS tricks of Candes and Tao work great on these states.

We engineers take these results to indicate that measure concentration is occurring not on the Hilbert space, but on a (nonlinear) subspace … but we don’t really have a very good understanding of what is going on … we only know that our simulations are far more efficient and accurate, on spaces of far smaller dimension, than ergodic theories of measure concentration would predict.

So what we engineers would most like to have, is strong theories of measure concentration on nonlinear spaces, that apply in particular to non-ergodic unraveling of quantum dynamical systems.