February 22
Cameron Freer,
Massachusetts Institute of Technology
Computability of exchangeable sequences, arrays, and graphs
A sequence of random variables is exchangeable when its distribution is invariant to reorderings of the sequence. This notion of symmetry and its generalizations to arrays, graphs, and other structures, arise in many statistical contexts. Representation theorems due to de Finetti, Aldous-Hoover, and others, describe how exchangeable structures can be written in a way that exposes conditional independence, which is often important for computational purposes. However, these results are not obviously computable. We will present several positive and negative results examining the computable content of these theorems, and will also describe several implications for the design of probabilistic programming languages. Joint work with Nathanael Ackerman, Jeremy Avigad, Daniel Roy, and Jason Rute.