The n-Category Café

Thanks! I didn’t get any answers to the question you quote. But for the question about possible examples to investigate, Nina made the broad suggestion of looking at the uniform measure on spaces coming from networks. I may be slightly mangling what she said, as I’m not at all familiar with the network world, but apparently there are interesting infinite spaces there. Hopefully I’ll be able to find out about that properly sometime — or maybe someone here can help out.

One thing I definitely remember from my time in the network world was people looking at steady-state distributions for diffusion processes. It would be interesting to see how those compare with “uniform measures” in the sense defined here.

OK, thanks. So, is there a compact metric space here? (Maybe it’s the space on which the steady-state distribution is defined.) If so, can you explain what it is? That’s the context for our construction: given a compact metric space, we define the uniform probability measure on it.

The general idea (if I can dust off my brain cells and remember) is to put a particle on a vertex of the graph and have it execute a random walk. For example, the walker might pick an edge at random out of those connected to the current vertex and traverse it. If the choice of edge is made without bias, then the probability of stepping from vertex $i$ to vertex $j$ is then $A_{i j}/k_i$, where $A$ is the adjacency matrix and $k_i$ is the degree of vertex $i$. Thus, we have a discrete-time Markov process. If the graph is connected and not bipartite, this Markov process will have a steady-state distribution with $p_i \propto k_i$, and the inverse of the smallest nonzero eigenvalue of the transition matrix will give the characteristic timescale for approaching that steady-state distribution.

There are, of course, variations on the theme: picking the target node with a bias, adding weights and/or directionality to the edges, etc. In general, though, the probability distribution under consideration will be defined on the set of vertices. As for regarding the graph as a metric space … probably one would use the shortest-path distance between vertices, as in calculating the magnitude of a graph.

Thanks! That first property you mention is interesting, and I don’t immediately see whether or not it holds for our definition of the uniform measure.

The second one definitely doesn’t, because of examples like the one you mention. The uniform measure on a compact subset $X$ of $\mathbb{R}^n$, of nonzero Lebesgue measure, is Lebesgue measure restricted to $X$ and normalized to a probability measure. So if $X$ is something like a lollipop shape in $\mathbb{R}^2$, the uniform measure gives the stick of the lollipop measure zero. Or more formally, as we write in Remark 9.10 of our paper:

the support of the uniform measure […] need not be $X$; that is, some nonempty open sets may have measure zero. Any nontrivial union of an $n$-dimensional set with a lower-dimensional set gives an example.

This fits with the intuition that if you pick a point of the lollipop uniformly at random, the probability it’s on the stick should be zero (assuming, of course, an infinitely thin stick).

I know there are contexts where it’s useful to have a “reference measure” that gives nonzero measure to nonempty open sets. On the other hand, it might feel quite non-uniform if, say, some one-dimensional piece of a space was assigned higher probability than a two-dimensional piece of the space, which is what would happen if the stick of the lollipop didn’t have measure zero.

It’s certainly true that if $A$ and $A'$ are isometric measurable subsets of $X$ and there’s a self-isometry of $X$ mapping $A$ to $A'$ then the uniform measure gives them the same probability. But this is much weaker than the first property you mention.

On further thought, Paolo’s first requirement —

• It assigns the same amount of measure to isometric (measurable or open) subsets of $X$

— is unfulfillable, by our or any other way of defining uniform probability measure. At least, it’s unfulfillable if we take the “measurable” option. For “open”, I don’t know.

Here’s why. If $X$ is countably infinite, there is no probability measure on $X$ that satisfies Paolo’s requirement. For any two singleton subsets are isometric, so all singletons have to be assigned the same probability; but then expressing $X$ as a countable union of singletons and using countable additivity of probabilities gives a contradiction.

So that explains why this requirement can’t possibly be satisfied. But maybe it’s enlightening to look at an example. In Emily’s and my paper (Section 10, question 3), we mention that

$$\{1, 1/2, 1/3, \ldots, 0 \},$$

metrized as a subspace of $\mathbb{R}$, has uniform measure $\delta_0$. Is it reasonable that $\{0\}$ and $\{1\}$, despite being isometric, are assigned different probabilities? It seems to me that it is, because although they themselves are isometric, their immediate neighbourhoods are not.

And this leads naturally to the alternative form of Paolo’s question, where we only ask about open subsets.

It’s a good question!

OK, now I have a proof that if $X$ is a compact metric space and $A$ and $B$ are isometric clopen subsets of $X$, then the uniform measure on $X$ (assuming it exists) gives the same probability to $A$ and $B$.

Clopen sets are obviously much more special than open sets, but baby steps!

The proof goes in two stages:

1. It’s easy enough to work out what the maximizing distribution on a coproduct of spaces is, in terms of the maximizing distribution on the individual components. Passing to the large-scale limit tells us about the uniform measure on a coproduct in terms of the uniform measures on the individual components. And from here, we get the case of the result where $A$ and $B$ are disjoint.

2. To extend to the general case, we can use the same two-copies-of-$X$ trick as here (though in fact, it was in the present context that I first thought of this argument).

Although the clopenness hypothesis is extremely restrictive, there is a useful corollary: in the uniform measure on a compact metric space, all isolated points are assigned the same probability. For example, in the space $\{1, 1/2, 1/3, \ldots, 0\}$ that I mentioned before, every point apart from $0$ is isolated, and there are infinitely many of them, so the uniform measure can only be $\delta_0$.

I like this. Moreover, your property implies mine in case of disjoint subsets: let $Y$ and $Z$ be open subsets of $X$ of positive measure, and suppose they are isometric. Then $Y \cup Z$ is also an open subset of $X$, and so the measure $\mu$ restricts to the uniform measure on $Y\cup Z$ after normalization. Now the isometry $Y \to Z$ does induce a self-isometry of $Y\cup Z$, and so $\mu(Y)=\mu(Z)$.

(Does anyone see a way to make this work if $Y$ and $Z$ are not disjoint?)

I like Mark’s property too, but there’s a difficulty: it talks about uniform measure on a non-compact metric space $Y$, whereas we’ve only defined uniform measure for (some) compact metric spaces.

To briefly recap the definition: one first defines what it means for a probability measure on a compact metric space $A$ to be “maximizing” (i.e. diversity-maximizing).

To define the uniform measure on $A$, we assume that for all sufficiently large $t \gt 0$, the scaled space $t A$ has a unique maximizing measure $\mu_t$, and we also assume that $\mu_t$ has a limit (in the weak${}^\ast$ topology) as $t \to \infty$. That limit is the uniform measure.

I confess, I don’t have a clear idea of exactly where in all this compactness is needed. It was always just a background assumption for me. Maybe it’s possible to get away without it.

Mark’s property does hold when $Y$ is a clopen subset, for what it’s worth.

Interesting question. I don’t know.

What you describe sounds very much like Hausdorff measure, which Emily and I say a little bit about in Section 10 of our paper. I don’t know much about the relationship between uniform and Hausdorff measure, but I suspect it’s complicated, since uniform measure is closely related to Minkowski dimension rather than Hausdorff dimension.

A thought: if the restriction conjecture is true, then it gives a way to extend the notion of uniform measure beyond the compact case. At least on a locally compact metric space $X$, demanding that $\mu_X|_A = \mu_X(A)\mu_A$ for all compact closure-of-open sets $A$ should uniquely determine $\mu_X$ up to scaling. For $X = \mathbb{R}^n$, Lebesgue measure is uniform in this sense by the result in the paper.

Here’s a slightly stronger continuity conjecture:

The function $$\{ \text{compact metric spaces} \} \to \{ \text{metric measure spaces} \}$$ defined by $$(X, d) \mapsto (X, d, \mu_X)$$ is continuous with respect to the Gromov–Hausdorff topology on the domain and the Gromov–Wasserstein topology on the codomain.

Incidentally, I’m pretty sure my proof of continuity of maximum diversity doesn’t actually need positive definiteness (though I haven’t thought about this stuff carefully in a while). That hypothesis was just thrown in everywhere since I was focused on magnitude for positive definite spaces, but all the positivity one needs is automatic when you’re only working with positive measures.

A subset $A\subset X$ of a topological space $X$ whose interior is dense in $A$ is called regular. So a regular closed subset is one that is the closure of its interior.

Here’s what I think is a proof that if the restriction conjecture holds then so does the invariance-for-open-sets conjecture.

As ever, I’ll silently assume where necessary that every compact metric space has a uniform measure (necessarily unique).

Let $X$ be a compact metric space, and let $U$ and $W$ be isometric nonempty open subsets of $X$. Let $f: U \to W$ be an isometry. Then $f$ extends uniquely to an isometry $\overline{f}: \overline{U} \to \overline{W}$ between the closures. Under the isometry $\overline{f}$, the uniform measure $\mu_\overline{U}$ on $\overline{U}$ corresponds to the uniform measure $\mu_{\overline{W}}$ on $\overline{W}$, simply because it’s an isometry. In particular, since $f U = W$,

$$\mu_{\overline{U}}(U) = \mu_{\overline{W}}(W).$$

Now we use restriction. Applied to the closures-of-opens $\overline{U}$ and $\overline{W}$, it gives

$$\mu_X|_{\overline{U}} = \mu_X(\overline{U}) \cdot \mu_{\overline{U}}, \qquad \mu_X|_{\overline{W}} = \mu_X(\overline{W}) \cdot \mu_{\overline{W}},$$

and in particular, $$\mu_X(U) = \mu_X(\overline{U}) \cdot \mu_{\overline{U}}(U), \qquad \mu_X(W) = \mu_X(\overline{W}) \cdot \mu_{\overline{W}}(W).$$

Also, we’ve already seen that restriction implies invariance for closures of open sets, so

$$\mu_X(\overline{U}) = \mu_X(\overline{W}).$$

Putting this all together gives $\mu_X(U) = \mu_X(W)$, as required.

So where are we on these conjectures?

Modulo existence of uniform measures, it seems that the invariance conjectures both follow from the restriction conjecture. I sketched a proof that restriction follows from the continuity conjecture (I mean the weak one that I stated, not the nice strong Gromovy one that Mark stated). If that sketch proof can be made to go through then the remaining challenge is to prove continuity.

The deduction of restriction from continuity might not be as straightforward as my sketch made it look, though. The problem is that convergence in the weak${}^\ast$ topology on the space of probability measures doesn’t imply convergence of probabilities of a particular set. That is, $\nu \to \mu$ doesn’t imply $\nu(A) \to \mu(A)$ for all measurable $A$. This somehow has to be overcome.