The n-Category Café

Presumably Alan meant that we can have our two random variables take values in different sets, like a coin toss and a die roll. Then we might say coin tosses are independent of die rolls. But you may prefer to think of the joint distribution over $\{head, tail\} \times \{1, 2, 3, 4, 5, 6\}$, and the event ‘head’ as the subset $\{head\} \times \{1, 2, 3, 4, 5, 6\}$.

So what happens with our old friend the Giry monad?

A distibution over $X \times Y$ is an arrow in the Kleisli category for this monad: $1 \to X \times Y$, (so $1 \to P(X \times Y)$).

Then there are ‘projections’, e.g., the map $X \times Y \to X$, which must be a conditional distribution $P(x' | x, y)$. Looks like the delta function $\delta_{x' x}$.

Then variables $f: 1 \to X$ and $g: 1 \to Y$ are independent if they factor through $(X \times Y)$.

I see, I misinterpreted the word “over”. I was thinking in terms of “a random variable $a$ over a (probability) measure space $\Omega$ is a measurable function $a:\Omega \to X$, where $X$ is some measurable space”, but you were writing in terms of “a random variable $a$ over a measurable space $X$ is a measurable function $a:\Omega \to X$, where $\Omega$ is some probability space.” I can’t make up my mind which of these uses of “over” is closer in sense to its other uses in mathematics.

Actually the most common way to talk about such an object is probably to say $a$ is a random variable on $\Omega$ with values in $\X$.

Either way, the definition of independence requires all the random variables we’re talking about to have the same domain, but whether the codomains are equal or not is immaterial.

Unfortunately the Giry monad is not yet my old friend since I haven’t read those old threads, but I will now - they look intriguing.

The intuition is that there’s some structure similarity going on here between random variables and links. So that something similar occurs when, on the one hand, you form a joint distribution over three variables, and the projection to any two of them yields independent variables, and, on the other hand, from a Borromean link of three circles you project to two unlinked circles (by killing off one of the links?)

Nitpicking, since I didn’t think of writing about this case myself:

The A-infinity structure that Kadeishvili’s theorem deals with is not on the cohomology of a dg-algebra - it’s on the homology of a dg-algebra. The connection to cohomology is that cochains can be made into a dg-algebra, with the prototype of the cup product as the multiplication, and that the homology of THAT dg-algebra really is cohomology.

And retention of all information in the dg-algebra is not, as far as I can tell, contained in Kadeishvili’s minimality theorem. He might have something along those lines later, but at least in non-topological settings (Ext algebras of appropriate algebraic structures), the retention of the full original algebra structure is actually kinda tricky to get to work.

Just looking at your formulation with the collections S and T, this looks very much like the kind of property formulation that gives you a simplicial complex situation for free: unlinkedness is closed under taking subsets, so the property of being unlinked can be made to generate a simplicial complex, the analysis of which might be interesting.

We had a colloquium speaker in Jena last summer who did similar things to give interesting non-constructive arguments in complexity theory. And I know Kozlov et.al. do similar things to generate complexes for graph colorings.

> But a matroid also satisfies other axioms.

Surely each the examples in my original post satisfy additinal axioms not shared by the other examples?

Eg, in database concurrency control, there are axioms that capture the fact that “read” operations commute while “writes” do not. These axioms are not relevant to random variables or topological links. The underlying binary relation P (which represents pairwise interaction), and ternary relation R (which represents mutual interaction) may thus have distinct properties across application domains and such details may in fact play a role in the categorical formalization, I have no intuition on that.

Nevertheless, I am primarily interested in systems where “mutual interaction” is not reducible to the study of “pairwise interaction,” ie, “independence” represents “lack of interaction,” or at least give conditions where it suffices to study pairwise interactions - what do those systems have in common? Surely there are many more examples of mathematical properties that hold pairwise but not mutually?

The problem with matroids (that’s a great example!) is that they are set-theoretical constructs, whereas I require the category’s objects to be general dynamical systems (eg the software processes in the case of transactional databases, or stochastic processes in the case of random variables) and my concept of interaction likewise should be quite abstract (eg RNA-interference)

I’m a bit late to the party, but have only recently come across this stuff through discussions with Pierre Baudot. Maybe having an answer to one of John’s excellent questions will still be of interest to future readers:

I don’t know if random variables and statistical independence gives an example of a matroid!

There’s a sense in which the answer is “yes, but not quite”. First, random variables and statistical independence does not give you a matroid; you can see this by noting that the matroid axioms guarantee that all maximal independent subsets have the same cardinality, but the same property certainly fails in general for subsets of random variables and their independence. (Example: take 2+3 random variables of which the first two and the latter three are independent, but such that you have weak correlations between each one of the first two and each one of the latter three. I think that this can also happen for links and their “independence”, right? Taking 1+2 instead of 2+3 is even easier, actually.)

So, what did I say “yes, but not quite” on whether random variables form a matroid? Because they form a polymatroid! This is defined in terms of a rank function like a matroid, but you generalize the notion of rank by allowing it to be an arbitrary nonnegative number. For a bunch of random variables, you get a polymatroid if you define the “rank” of any subset of these variables to be their joint entropy, et voilà! Two variables $a$ and $b$ are independent if this rank function satisfies $r(a,b) = r(a) + r(b)$, and the “Borromean link” situation therefore corresponds to

$$r(a,b) = r(a) + r(b), \qquad r(b,c) = r(b) + r(c), \qquad r(c,a) = r(c) + r(a),$$

but

$$r(a,b,c) \lt r(a) + r(b) + r(c).$$

I’m a bit late to the party, but have only recently come across this stuff through discussions with Pierre Baudot. Maybe having an answer to one of John’s excellent questions will still be of interest to future readers:

I don’t know if random variables and statistical independence gives an example of a matroid!

There’s a sense in which the answer is “yes, but not quite”. First, random variables and statistical independence does not give you a matroid; you can see this by noting that the matroid axioms guarantee that all maximal independent subsets have the same cardinality, but the same property certainly fails in general for subsets of random variables and their independence. (Example: take 2+3 random variables of which the first two and the latter three are independent, but such that you have weak correlations between each one of the first two and each one of the latter three. I think that this can also happen for links and their “independence”, right? Taking 1+2 instead of 2+3 is even easier, actually.)

So, why did I say “yes, but not quite” on whether random variables form a matroid? Because they form a polymatroid! This is defined in terms of a rank function like a matroid, but you generalize the notion of rank by allowing it to be an arbitrary nonnegative number. For a bunch of random variables, you get a polymatroid if you define the “rank” of any subset of these variables to be their joint entropy, et voilà! Two variables $a$ and $b$ are independent if this rank function satisfies $r(a,b) = r(a) + r(b)$, and the “Borromean link” situation therefore corresponds to

$$r(a,b) = r(a) + r(b), \qquad r(b,c) = r(b) + r(c), \qquad r(c,a) = r(c) + r(a),$$

but

$$r(a,b,c) \lt r(a) + r(b) + r(c).$$

I certainly don’t think that A-infinity algebras and dg-algebras are necessary to formalize the aspects of the Borromean configuration you alluded to above. We just derailed onto them since Massey products show up to capture the exact way in which the appropriate cohomology ring STILL captures the linkedness of the Borromean rings in the knot theoretic context.

I mean, at one level of abstraction higher.

“These are connected hypergraphs with no graph edges.” Meaning that the the Borromean rings, consisting of three topological circles which are linked and form a Brunnian link, i.e., removing any ring results in two unlinked rings, can be mapped one circle to one point, such that the three circles have been mapped to three nodes, and the same transformation maps the topological linkage of two circles to a regular edge, and the Brunnian link of 3 circles to a hyperedge.

We know that that the cohomology of the complement of the Borromean rings supports a non-trivial Massey product.

Equivalently, the hyperedge is a mapping from a hyperbolic link: the complement of the Borromean rings in the 3-sphere admits a complete hyperbolic metric of finite volume.

If this is true to someone who can draw the diagram, we are mostly there. Aren’t we?

yes, I listed the hypergraph as an example in my original post.

However, I require a categorical treatment where the objects are quite general (eg dynamical systems)

Similarly, pairwise and mutual relations also can quite general interactions (eg, feynman diagrams or conditional default probabilities in finance, whatever… - do not attempt to limit the concept of “interaction”, which is completely open-ended. hypergraphs on the other hand are set-theoretical, not categorical)

Good one. Yes, I was perplexed by the “real” “imaginary” “symbolic” triangle in R Guitard’s slide show on the “borromean object.” Not to generalize but the french have a way of melding some of the deepest thoughts with abstract aesthetic gestures.

I assure you that my motivation is pragmatic. For example, what is the meaning of “information.” When John Daugman, who studies iris biometrics states that the the combinatorial complexity of a certain wavelet transform generates 3.2 bits/mm^2, how much of that is due to the intrinsic structure of the iris, and how much of that is due to the interaction between the iris and the measurement protocol and coding algorithm. - these are issues that pervade modern machine learning in the “far heterogeneous domain” with no easy answers. I want to know, what is intrinsic to a “pairwise measurement of interaction” versus a measurement that includes “mutual interaction.”

Related: what is “independent and identically distributed” random variable? - is that a constructive concept?

popmath.org.uk
said `authorization required’
??

Actually, the plain trivalent graph dual to the trefoil (Pauli matrix quandle) is the same as the GHZ graph, and the (zero 3-way entanglement) W state graph is the Borromean link. The point is that the trefoil links up the qubits into a single strand while the Borromean link keeps them separate.

Oh, so THAT’s what Eric Emtander is up to! I’m looking forward to getting back to Stockholm quite a bit now!

(Eric started his PhD studies just as I left Stockholm - and is working on things similar to what I used to work on for my Masters…)

> Did you mean for xSy to be the stronger condition x and y form an unlink; rather than have linking number 0?

From a cursory read, I believed that for a 2-component link, the two statements were equivalent. Can you give a counterexample?

In any case, you are correct that abstract simplicial complex yields examples of Borromean configuration as you described - but this was already noted in my original posting (modulo your observation that such a triangle boundary is the smallest noncontractile. The logical complement of this configuration is the interior of the triangle, which captures the concept of Borromean link directly.

However, I am seeking a categorical treatment of this general phenomenon so that the vertices (objects) may represent, eg, dynamical systems, edges may represent, eg, pairwise process interactions, “triangles” may represent, eg 3-way process interactions, etc.

the motivation for my original posting comes from pattern recogntition and related sciences. Namely, what can be said about higher-order interaction when only pairwise interactions are measured (eg “mutual information” is actually only pairwise interaction. As Mumford pointed out, you cannot use Venn-type diagram and inclusion-exclusion arguments to relate pairwise mutual information with the overall interaction)