Algorithmic barriers to representing conditional independence
| Autor: | Daniel M. Roy, Jason Rute, Jeremy Avigad, Cameron E. Freer, Nathanael L. Ackerman |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
Random graph
Representation theorem Computability 010102 general mathematics Context (language use) 0102 computer and information sciences 01 natural sciences Combinatorics Kernel (algebra) Conditional independence 010201 computation theory & mathematics Adjacency matrix 0101 mathematics Random variable Mathematics |
| Zdroj: | LICS |
| Popis: | We define a represention of conditional independence in terms of products of probability kernels, and ask when such representations are computable. We pursue this question in the context of exchangeable sequences and arrays of random variables, which arise in statistical contexts. Exchangeable sequences are conditionally i.i.d. by de Finetti's theorem. Known results about the computability of de Finetti's theorem imply that these conditional independences are computable. The conditional independences underlying exchangeable arrays are characterized by the Aldous-Hoover theorem. In the special case of adjacency matrices of undirected graphs, i.e., symmetric binary arrays, this representation theorem expresses the conditional independences in terms of graphons. We prove that there exist exchangeable random graphs that can be computably sampled but whose corresponding graphons are not computable as functions or even as $L^{1}$ equivalence classes. We also give results on the approximability of graphons in certain special cases. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|