Exchangeability and realizability: De finetti theorems on graphs

Abstract

A classic result in probability theory known as de Finetti's theorem states that exchangeable random variables are equivalent to a mixture of distributions where each distribution is determined by an i.i.d. sequence of random variables (an "i.i.d. mix"). Motivated by a recent application in [18] and more generally by the relationship of local vs. global correlation in randomized rounding, we study weaker notions of exchangeability that still imply the conclusion of de Finetti's theorem. We say that a bivariate distribution ρ is G-realizable for a graph G if there exists a joint distribution of random variables on the vertices such that the marginal distribution on each edge equals ρ. We first characterize completely the G-realizable distributions for all symmetric/arc-transitive graphs G. Our main results are forms of de Finetti's theorem for general graphs, based on spectral properties. Let λ1(G) ≥ . . . ≥ λn(G) denote the eigenvalues of the adjacency matrix of G. 1. We prove that if ρ is Gn-realizable for a sequence of graphs such that limn→∞λn(Gn)/λ1(Gn) = 0, then ρ is described by a probability matrix that is positive-semidefinite. For random variables on domains of size |D| ≤ 4, this implies that ρ must be an i.i.d. mix. 2. If ρ is Gn-realizable for a sequence of (n, d, λ)-graphs Gn (d-regular with all eigenvalues except for one bounded by λ in absolute value) such that limn→∞ λ(Gn)/d(Gn) = 0, then ρ is an i.i.d. mix. 3. If ρ is G→n-realizable for a sequence of directed graphs such that each of them is an arbitrary orientation of an (n, d, λ)-graph Gn, and limn→∞ λ(Gn)/d(Gn) = 0, then ρ is an i.i.d. mix.