Document Open Access Logo

Exchangeability and Realizability: De Finetti Theorems on Graphs

Authors T. S. Jayram, Jan Vondrák

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2014.762.pdf
  • Filesize: 492 kB
  • 17 pages

Document Identifiers

Author Details

T. S. Jayram
Jan Vondrák

Cite As Get BibTex

T. S. Jayram and Jan Vondrák. Exchangeability and Realizability: De Finetti Theorems on Graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 762-778, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.762

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 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 rho 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 rho.

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 lambda_1(G) >= ... >= lambda_n(G) denote the eigenvalues of the adjacency matrix of G.

1. We prove that if rho is G_n-realizable for a sequence of graphs such that lambda_n(G_n) / lambda_1(G_n) tends to 0, then rho is described by a probability matrix that is positive-semidefinite. For random variables on domains of size |D| <= 4, this implies that rho must be an i.i.d. mix.

2. If rho is G_n-realizable for a sequence of (n,d,lambda)-graphs G_n (d-regular with all eigenvalues except for one bounded by lambda in absolute value) such that lambda(G_n) / d(G_n) tends to 0, then rho is an i.i.d. mix.

3. If rho is G_n-realizable for a sequence of directed graphs such that each of them is an arbitrary orientation of an (n,d,lambda)-graph G_n, and lambda(G_n) / d(G_n) tends to 0, then rho is an i.i.d. mix.

Subject Classification

Keywords
  • exchangeability
  • de Finetti’s Theorem
  • spectral graph theory
  • regularity lemma

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Boaz Barak, Fernando G. S. L. Brandão, Aram W. Harrow, Jonathan A. Kelner, David Steurer, and Yuan Zhou. Hypercontractivity, sum-of-squares proofs, and their applications. In Howard J. Karloff and Toniann Pitassi, editors, ACM STOC, pages 307-326. ACM, 2012. Google Scholar
  2. Boaz Barak, Prasad Raghavendra, and David Steurer. Rounding semidefinite programming hierarchies via global correlation. In Rafail Ostrovsky, editor, FOCS, pages 472-481. IEEE, 2011. Google Scholar
  3. Bruno de Finetti. Funzione Caratteristica di un Fenomeno Aleatorio, pages 251-299. 6. Memorie. Academia Nazionale del Linceo, 1931. Google Scholar
  4. Bruno de Finetti. La prévision: ses lois logiques, ses sources subjectives. Annales de l'Institute Henry Poincaré, 7(1):1-68, 1937. Google Scholar
  5. Persi Diaconis. Finite forms of de Finetti’s theorem on exchangeability. Synthese, 36(2):271-281, 1977. Google Scholar
  6. Persi Diaconis and David Freedman. Finite exchangeable sequences. The Annals of Probability, pages 745-764, 1980. Google Scholar
  7. Jair Donadelli and Yoshiharu Kohayakawa. A density result for random sparse oriented graphs and its relation to a conjecture of Woodall. Electr. J. Comb., 9(1), 2002. Google Scholar
  8. Olav Kallenberg. Probabilistic symmetries and invariance principles, volume 9. Springer, 2005. Google Scholar
  9. Tali Kaufman and Alexander Lubotzky. Edge transitive Ramanujan graphs and symmetric LDPC good codes. In Proceedings of the Forty-fourth Annual ACM Symposium on Theory of Computing, pages 359-366, 2012. Google Scholar
  10. Tali Kaufman and Alexander Lubotzky, 2014. personal communication. Google Scholar
  11. Tali Kaufman and Avi Wigderson. Symmetric LDPC codes and local testing. In Andrew Chi-Chih Yao, editor, ICS, pages 406-421. Tsinghua University Press, 2010. Google Scholar
  12. John F.C. Kingman. Uses of exchangeability. The Annals of Probability, pages 183-197, 1978. Google Scholar
  13. Michael Krivelevich and Benny Sudakov. Pseudo-random graphs. Bolyai Society Mathematical Studies, 15:199-262, 2006. Google Scholar
  14. Alexander Lubotzky and Roy Meshulam. A Moore bound for simplicial complexes. Bull. London Math. Soc., 39:353-358, 2007. Google Scholar
  15. John E. Maxfield and Henryk Minc. On the matrix equation X'X = A. Proceedings of the Edinburgh Mathematical Society (Series 2), 13:125-129, 12 1962. Google Scholar
  16. T.S. Motzkin and E.G. Straus. Maxima for graphs and a new proof of a theorem of Turán. Canada J. Math., 17:533-540, 1965. Google Scholar
  17. Jaroslav Nešetřil and Patrice Ossona de Mendez. Sparsity - Graphs, Structures, and Algorithms. Algorithms and Combinatorics 28. Springer, 2012. Google Scholar
  18. Ankit Sharma and Jan Vondrák. Multiway cut, pairwise realizable distributions, and descending thresholds. In David B. Shmoys, editor, STOC, pages 724-733. ACM, 2014. Google Scholar
  19. A. J. Stam. Distance between sampling with and without replacement. Statistica Neerlandica, 32(2):81-91, 1978. Google Scholar
  20. Luca Trevisan. Max cut and the smallest eigenvalue. SIAM J. Comput., 41(6):1769-1786, 2012. Google Scholar
  21. William T. Trotter and Peter Winkler. Ramsey theory and sequences of random variables. Combinatorics, Probability & Computing, 7(2):221-238, 1998. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact