9
$\begingroup$

Is there any reference which studies sets of random variables as independence systems, a type of combinatorial object (see below)?

Motivation: In particular, since independence systems are abstract simplicial complexes, this would allow one to apply homology theory (I think) to study families of random variables. Moreover, one could cross-apply intuition from other types of independence systems to better understand statistical independence.

For example, two things that I have had difficulty understanding intuitively, that statistical independence is not transitive, and that $(n-1)$-wise independence doesn't necessary imply $n$-wise independence, are facts which have geometrically easy to understand analogs in linear algebra.

Note: The closest thing I can think of having seen are treatments of random variables (with finite support) as standard simplices, since each point of the simplex corresponds to a probability distribution such that $p_1 + \dots + p_n = 1$. Also, this. However, these are not what I am looking for: in what I am describing, only the vertices represent random variables -- the higher-order faces do not represent random variables, they represent relationships of statistical independence between random variables (e.g. a $2$-face connecting three vertices corresponds to the statement that the three random variables symbolized by the vertices are mutually statistically independent).

I also don't think I am looking for a treatise on the theory of random graphs or random matroids or random simplicial complexes -- whether or not two given random variables $X$ and $Y$ are statistically independent is supposed to be a deterministic relationship (at least in simple models).

This question on Math.SE comes the closest to discussing the type of phenomenon I am talking about (the statistical independence of a family of random variables being modeled by an independence system, in this case the independence system of linearly independent vectors).

These two questions on Math.SE are also related, perhaps the first more so than than second: (1) (2). These two questions on MathOverflow also seem possibly related, although to be honest I don't feel I understand them well enough to discern that accurately: (1)(2).

Background:
In chapter 2 of Ghrist's Elementary Applied Topology, the author notes that:

Example 2.1 (Statistical Independence) Independence occurs in multiple contexts, including linear independence of a collection of vectors or linear independence of solutions to linear differential equations. More subtle examples include statistical independence of random variables: recall that the random variables $\mathcal{X}=\{X_i\}_1^n$ are statistically independent if their probability densities $f_{X_i}$ are jointly multiplicative, i.e., the probability density $f_{\mathcal{X}}$ of the combined random variable $(X_1, \dots, X_n)$ satisfies $f_{\mathcal{X}} = \prod_i f(X_i)$. The independence complex of a collection of random variables compactly encodes statistical dependencies.

According to Wikipedia, independence systems are equivalent to abstract simplicial complexes. They are a special case of hypergraphs, and more general than matroids.

In section 7.8, p.151 of the same book this idea is referenced once again:

One clever application of this result [use of discrete Morse theory to study evasiveness in decision tree algorithms as in e.g. this paper, Morse Theory and Evasiveness, by Forman] is to independence tests for random variables. Let $\mathcal{X} = \{X_i\}$ be a collection of random variables and recall from Example 2.1 the independence complex $\mathcal{J}_{\mathcal{X}} \subset \Delta^n$ of $\mathcal{X}$. Given an unknown subcollection $\sigma \subset \mathcal{X}$ of the random variables, how many trials of the form "Is $X_i$ a member of $\sigma$" are required to determine if the collection is statistically independent? According to the results cited above, statistical independence is evasive if $\mathcal{J}_{\mathcal{X}}$ is not acyclic: any nontrivial homology class in $\tilde{H}_{\bullet}(\mathcal{J}_{\mathcal{X}})$ is an obstruction to evasiveness of statistical independence. How many such evasive collections of random variables are there? It is at least twice the total dimension of $\tilde{H}_{\bullet}(\mathcal{J}_{\mathcal{X}})$.

Unfortunately, despite the fact that most of the book has ample citations and references to further reading, these examples are not accompanied by any references, so I am not sure how to explore this (to me) interesting idea further. Perhaps the reason why is that there are no references discussing this topic, and it is an original idea of the author.

Pages 4-5 here discussing log-linear models seem like they might be related, although it is hard for me to tell based on what is written and it is not expounded upon in much depth. In any case, like an aforementioned related question on Math.SE, it also suggests a relationship between this topic and Bayesian networks and/or algebraic statistics. However, it is worth noting that the edges in a Bayesian network denote conditional dependence, not independence, so they cannot be directly extended to the type of independence/abstract simplicial complex I am referring to. On the other hand, if one forms a new graph by connecting each node with the complement of its Markov blanket, then perhaps this might work. I.e. in other words Bayesian networks may encode the necessary information about conditional independence relationships for this to work -- on the other hand, it might still not work since "conditional independence" refers to a different (conditional) probability measure for each pair of nodes, while the standard example assumes a single choice of probability measure on the probability space on which all of the random variables are defined (I think). The answer is probably obvious but I need to think about it more.

This other document by Robert Ghrist also seems like it might be relevant, but if it is I can't tell for certain (honestly I don't think so but it's better than nothing so I'm including the link anyway).

I was thinking that perhaps one could use log-likelihoods to construct chain complexes and then homologies on these abstract simplicial complexes, although each time I try to work out the details I hit a roadblock/realize I was misunderstanding something. In any case, using the log-likelihood instead of the likelihood seems analogous to the use of the exponential to turn a (geometric/not abstract) simplex into a vector space as outlined in this blog post. Probably a more viable method for calculating the homologies of these complexes would be to use discrete Morse theory, as implied by Professor Ghrist on p.151 of his aforementioned book.

Also I wonder if there is a relation between all of this and information theory: the phenomenon of information gain in decision tree algorithms is well known and is even used to motivate the entire concept of entropy/information in some books, for example. In particular, Ghrist's remarks on p.151 of his book about Forman's paper seem like they could possibly be interpreted in terms of information theory, and being particularly bold, one could imagine that the homologies of these statistical independence complexes have an information-theoretic interpretation.

Disclaimer: This is a revised version of my now-deleted week-old unanswered question on Math.SE -- perhaps this is a current topic of research, which perhaps is why it was unanswered on Math.SE and why it might be on-topic here. If you disagree, please let me know.

$\endgroup$
3
  • 2
    $\begingroup$ would it be easier to talk about independence of $\sigma$-algebras and the corresponding combinatorics/topology? en.wikipedia.org/wiki/… $\endgroup$ Feb 26, 2017 at 8:08
  • $\begingroup$ @DimaPasechnik Yes, I agree, this would make it much easier to generalize to infinite collections of random variables. Such a reference referring to $\sigma$-algebras would also be appreciated. $\endgroup$ Feb 26, 2017 at 14:31
  • 1
    $\begingroup$ A don't think a theory of independence is that interesting. More appropriate perhaps would be a theory of lack of independence. Then the key combinatorial concept is that of joint cumulant, see e.g. mathoverflow.net/questions/144773/what-is-a-cumulant-really These are related to Moebius inversion in the partition lattice. Since you seem interested in simplicial complexes and topology, and as I learned from Greg Arone, this partition lattice plays an important role in Goodwillie calculus. $\endgroup$ Apr 9, 2020 at 14:27

2 Answers 2

3
$\begingroup$

It is aimless to extend "statistical independence" beyond category of $\sigma$-subalgebras and probability-preserving morphisms on a fixed probability space $\prod,\mathcal{A}$ as pointed out by the comment by @Dima Pasechnik.

We restrict ourselves to the category of $\sigma$-subalgebras, whose objects are the collection $\Lambda$ of all $\sigma$-subalgebras of a given $\sigma$-algebra. Some generalizations can be attained using dilations [Nagel&Palm] if you really want to embed the algebra associated with random variables on $\sigma$-subalgebras into $L^p$.

In such a category, most part of statistics are treating the separable base space, therefore via Rokhlin-Maharam theorem we know that statisticians are treating only $[0,1]\times[0,1]$ up to probability-preserving mappings. Two $\sigma$-subalgebras $\mathcal{A}_1,\mathcal{A}_2$ over the same space $(\prod,\mathcal{A},P)$ are said to be independent if $P(AB)=P(A)P(B),\forall A\in \mathcal{A}_1;B\in \mathcal{A}_2$; if we resort to axiomatic information theory and define an entropy functional $H$, then equivalently we can say these two algebras are independent if $H(\mathcal{A}_1\cap\mathcal{A}_2)=H(\mathcal{A}_1)+H(\mathcal{A}_2)$.

Now consider a probability preserving automorphism $\tau$ on $\prod,\mathcal{A}$, then such an automorphism induces automorphism $\bar{\tau}$ on the lattice $\Lambda$ of all $\sigma$-subalgebras of $\mathcal{A}$. Using the entropy characterization of independence, we must stipulate $H(\mathcal{A}_1 )=H(\bar{\tau}(\mathcal{A}_1)),\forall \mathcal{A}_1\in \Lambda$. This pretty much characterized the statistical independence within the category. This the the grand framework behind [Forman] as I understood.

The problem is that the structure of the dual notion $\Lambda$ of the $\sigma$-subalgebras remains mysterious as far as I know (If you do not even know the structure of this fundamental dual notion there is little hope that you can apply any topological trick). Thus a fuller treatment of the notion of independence is not very realistic unless we got a fuller knowledge of the structure of $\Lambda$, say a classification of all such subalgebras up to probability preserving transformations. There is one [MO] post asked earlier by me which contains some interesting links treating independence from categorical viewpoint. After I gone through it, as you can probably feel, the development is still very primitive.

[Nagel&Palm]Nagel, R. A. I. N. E. R., and Günther Palm. "Lattice dilations of positive contractions on L p-spaces." Canad. Math. Bull 25 (1982): 371-374.

[Forman]Forman, Robin. "Morse theory and evasiveness." Combinatorica 20.4 (2000): 489-504.

[MO]What is the algebraic equivalent of independent elements?

$\endgroup$
9
  • 1
    $\begingroup$ This aimed at explaining why there is not such a treatment existing according to [Forman]'s work as pointed out by OP. $\endgroup$
    – Henry.L
    May 12, 2017 at 15:10
  • 1
    $\begingroup$ Here is a reference for axiomatic information theory in stats. Hope helps! stat.cmu.edu/~cshalizi/350/2008/lectures/06a/lecture-06a.pdf @Chill2Macht $\endgroup$
    – Henry.L
    May 12, 2017 at 16:52
  • 1
    $\begingroup$ It is aimed at addressing [Forman]. (1) As you cited, "any nontrivial homology class in $\tilde{H}_{\bullet}(\mathcal{J}_{\mathcal{X}})$ is an obstruction to evasiveness of statistical independence", would it be easier to calculate it directly or do it via cohomology? Also, it is not natural that we do not know anything about $\Lambda$. (2)Have you tried to calculate for one $\sigma$-algebra? For a bit more complicated, yet regular, $\sigma$-algebra like filtrations of brownian motion, such a computation becomes not tractable for me, @Chill2Macht $\endgroup$
    – Henry.L
    May 12, 2017 at 17:08
  • 1
    $\begingroup$ (3) I do not say a dual $\sigma$-algebra is necessary for Forman's computation, I just pointed out that it is unlike the case in Hilbert spaces where both Hilbert space and its dual are well-structured. We cannot treat homology as summary statistics in any sense, summary statistics is a random variable, which is already an element in the dual $\sigma$-algebra. $\endgroup$
    – Henry.L
    May 12, 2017 at 17:10
  • 1
    $\begingroup$ Read this article to see my comment about how hard it is to compute the $\Lambda$ construction for brownian motion. Yan, Catherine Huafei. "The theory of commuting Boolean sigma-algebras." Advances in Mathematics 144.1 (1999): 94-116. $\endgroup$
    – Henry.L
    May 12, 2017 at 17:12
2
$\begingroup$

This is an old question which already has an accepted answer, but I believe the theory of so-called 'gaussoids' is precisely a combinatorial abstraction of the idea of independence in probability (see e.g. https://arxiv.org/abs/1710.07175).

$\endgroup$
1
  • $\begingroup$ Ooh this looks interesting. Usually anything with Bernd Sturmfels as a coauthor is pretty good (in my opinion). $\endgroup$ Apr 9, 2020 at 20:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.