### Metadata

### Abstract

Motivated by the problem of designing inference-friendly Bayesian nonparametric models in probabilistic programming languages, we introduce a general class of partially exchangeable random arrays which generalizes the notion of hierarchical exchangeability introduced in Austin and Panchenko (2014). We say that our partially exchangeable arrays are DAG-exchangeable since their partially exchangeable structure is governed by a collection of Directed Acyclic Graphs. More specifically, such a random array is indexed by ${\mathbb{N}}^{\left|V\right|}$ for some DAG $G=(V,E)$, and its exchangeability structure is governed by the edge set $E$. We prove a representation theorem for such arrays which generalizes the Aldous-Hoover and Austin–Panchenko representation theorems.

### References

[AAF + 18] On the computability of graphons (2018) (https://arxiv.org/abs/1801.10387)

[Ack15] Representations of Aut(M)-invariant measures: Part I (2015) (https://arxiv.org/abs/1509.06170)

[AFP16] Invariant measures concentrated on countable structures, Forum Math. Sigma, Volume 4 (2016), 17 | MR 3515800 | Zbl 06601292

[Ald81] Representations for partially exchangeable arrays of random variables, J. Multivariate Anal., Volume 11 (1981) no. 4, pp. 581-598 | Article | MR 637937 | Zbl 0474.60044

[Ald85] Exchangeability and related topics, École d’Été de Probabilités de Saint-Flour XIII 1983 (Lecture Notes in Mathematics), Springer, 1985, pp. 1-198 | Zbl 0562.60042

[Ald10] More uses of exchangeability: representations of complex random structures, Probability and mathematical genetics. Papers in honour of Sir John Kingman (London Mathematical Society Lecture Note Series), Volume 378 (2010), pp. 35-63 | Article | MR 2744234 | Zbl 1213.60068

[AP14] A hierarchical version of the de Finetti and Aldous–Hoover representations, Probab. Theory Relat. Fields, Volume 159 (2014) no. 3-4, pp. 809-823 | Article | MR 3230009 | Zbl 1306.60027

[Aus08] On exchangeable random variables and the statistics of large graphs and hypergraphs, Probab. Surv., Volume 5 (2008), pp. 80-145 | Article | MR 2426176 | Zbl 1189.60020

[Aus12] Exchangeable random arrays, 2012 (Notes for IAS workshop,https://www.math.ucla.edu/~tim/ExchnotesforIISc.pdf)

[BR97] Operator Algebras and Quantum Statistical Mechanics. Vol. 2: Equilibrium States Models in Quantum Statistical Mechanics, Texts and Monographs in Physics, Springer, 1997 | Zbl 0903.46066

[CCB16] Edge-exchangeable graphs and sparsity, Advances in Neural Information Processing Systems 29 (NIPS 2016) (2016), pp. 4249-4257

[CD18] Edge exchangeable models for interaction networks, J. Amer. Statist. Assoc., Volume 113 (2018) no. 523, pp. 1311-1326 | Article | MR 3862359 | Zbl 1402.90027

[CF17] Sparse graphs using exchangeable random measures, J. R. Stat. Soc. Ser. B. Stat. Methodol., Volume 79 (2017) no. 5, pp. 1295-1366 | Article | MR 3731666 | Zbl 1381.62072

[CGZ15] Rate-optimal graphon estimation, Ann. Stat., Volume 43 (2015) no. 6, pp. 2625-2652 | MR 3405606 | Zbl 1332.60050

[CT17] Relative exchangeability with equivalence relations, Arch. Math. Logic, Volume 57 (2017) no. 5-6, pp. 1-24 | MR 3828877 | Zbl 06919823

[CT18] Relatively exchangeable structures, J. Symb. Log., Volume 83 (2018) no. 2, pp. 416-442 | Article | MR 3835071 | Zbl 06915707

[DJ08] Graph limits and exchangeable random graphs, Rend. Mat. Appl., Volume 28 (2008) no. 1, pp. 33-61 | MR 2463439 | Zbl 1162.60009

[Fin75] Theory of probability. A critical introductory treatment. Vols 1 and 2, Wiley Series in Probability and Mathematical Statistics, John Wiley & Sons, 1974-1975 (English translation by Antonio Machi and Adrian Smith) | Zbl 0328.60002

[FR12] Computable de Finetti measures, Ann. Pure Appl. Logic, Volume 163 (2012) no. 5, pp. 530-546 | Article | MR 2880271 | Zbl 1247.03098

[GMR + 08] Church: a language for generative models, Proceedings of the Twenty-Fourth Conference on Uncertainty in Artificial Intelligence (2008) (2008)

[GvdV17] Fundamentals of nonparametric Bayesian inference, Cambridge Series in Statistical and Probabilistic Mathematics, 44, Cambridge University Press, 2017 | MR 3587782 | Zbl 1376.62004

[Hoo79] Relations on probability spaces and arrays of random variables, Volume 2, 1979 (Preprint)

[Kal02] Foundations of modern probability, Probability and Its Applications, Springer, 2002 | Article | Zbl 0996.60001

[Kal05] Probabilistic Symmetries and Invariance Principles, Probability and Its Applications, Springer, 2005 | Zbl 1084.60003

[KTG + 06] Learning Systems of Concepts with an Infinite Relational Model, Proceedings of the Twenty-First National Conference on Artificial In-telligence (AAAI-06) (2006), pp. 381-388

[MMYW16] Design and Implementation of Probabilistic Programming Language Anglican, IFL 2016: Proceedings of the 28th Symposium on the Implementation and Application of Functional Programming Languages (2016), 6, pp. 1-12

[MP01] The Bethe lattice spin glass revisited, Eur. Phys. J. B Condens. Matter Phys., Volume 20 (2001) no. 2, pp. 217-233 | MR 1832936

[OR15] Bayesian Models of Graphs, Arrays and Other Exchangeable Random Structures, IEEE Trans. Pattern Anal. Mach. Intell., Volume 37 (2015) no. 2, pp. 437-461 | Article

[Pan15] Hierarchical exchangeability of pure states in mean field spin glass models, Probab. Theory Relat. Fields, Volume 161 (2015) no. 3-4, pp. 619-650 | Article | MR 3334277 | Zbl 1320.60159

[Res14] A probability path, Modern Birkhäuser Classics, Springer, 2014 | Zbl 1280.60001

[SSY + 18] The Beta–Bernoulli Process and Algebraic Effects, 45th International Colloquium on Automata, Languages, and Programming: ICALP 2018 (Leibniz International Proceedings in Informatics), Volume 107 (2018) | MR 3830072

[SYA + 17] Exchangeable random process and data abstraction, 2017 Workshop on Probabilistic Programming Semantics (PPS 2017), available at https://pps2017.luddy.indiana.edu/2017/01/02/exchangeable-random-processes-and-data-abstraction/

[VR15] The Class of Random Graphs Arising from Exchangeable Random Measures (2015) (https://arxiv.org/abs/1512.03099)

[WMM14] A New Approach to Probabilistic Programming Inference, Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics (Proceedings of Machine Learning Research), Volume 33 (2014), pp. 1024-1032

[XTYK06] Infinite hidden relational models, Proceedings of the Twenty-Second Conference on Uncertainty in Artificial Intelligence (2006) (2006), pp. 544-551