Exchangeability and related topics

STAT C206B (= MATH C223B) Spring 2013: David Aldous

STAT 206, with catalog description Advanced Topics in Probability and Stochastic Processes, is intended to have a different subject each semester. My subject is

Exchangeability and related topics

See the list of possibly-relevant papers for many more works than are mentioned on this page.

We will first review classical theory, centered upon de Finetti's theorem. In the late 1970s there were several developments, discussed in Aldous (1983) (200 typed pages). In particular we will discuss two topics initiated around that time

Topic 1. The Poisson-Dirichlet distribution on partitions

Topic 2. Representation theorems for partially exchangeable arrays

As one can infer from Google Scholar's time series of citations to that article, the subject remained quiet until around 2005 but has subsequently attracted considerable interest from several opposite directions.

Topic 1. On the one hand this has influenced extensive work concerning prior distributions on categorical data for Bayesian machine learning -- see e.g. Teh at al (2006). Developments on the mathematical side appear in the monograph Feng (2010).

Topic 2. This theory was treated in detail in the monograph Kallenberg (2005). Around that time it was being rediscovered in several "pure math" contexts

dense graph limits, e.g. Diaconis - Janson (2008)
structural results in ergodic theory, e.g. Austin (2008).
isometry classes of metric spaces with probability measures, e.g. Vershik (2004)

My own personal current interest is in the general idea of representations of complex random structures Aldous (2010) via induced substructures on randomly sampled points. In particular there is a challenging project Aldous (2012a) on a conjectured compactification of some finite reversible Markov chains.

Administration

Lecture times: MWF 1.00 - 2.00pm room 344 EVANS

Office Hours: Wednesdays 2.00-3.00 in 351 Evans.

If you email me (aldous@stat.berkeley.edu) put "STAT 206" in subject line.

Requirements for students. Students taking course for credit need to do one of the following.

Read a recent paper and give a 25-minute talk during last 2 weeks of semester.
Do one of the research/survey projects which will be mentioned in class.

Class-by-class schedule

This will mostly be a debriefing of what I have done, rather than a plan for the future......

[Part 1: Lectures based on material from ERT = Aldous (1983)]
W 1/23: Overview (not written up). RVs and PMs. Definition of exchangeability (finite and infinite index sets) and immediate consequences (ERT sec 1).
F 1/25: Correlation inequality, characterization of Gaussian exchangeable (ERT sec 1). Polya urn and other non-obvious instance of exchangeability.
M 1/28: Mixtures of distributions; from calculus to measure theory. Mixtures of IID sequence and their directing random measures (ERT sec 2).
W 1/30: Conditionally IID sequences; first proof of de Finetti's theorem (ERT sec. 3).
F 2/1: Hewitt-Savage 0-1 law; second proof of de Finetti's theorem; conditional independence (ERT sec. 3).
M 2/4: Variants: k sequences, martingale difference sequences (ERT sec. 3)
[Part 2: Lectures based on material from SC = Bertoin (2010)]
W 2/6: Overview of stochastic coalescence. Representations of unordered cluster-sizes (SC 1.1.1 - 1.1.2).
F 2/8: Exchangeable partitions, Kingman paintbox theorem (SC 1.1.3 - 1.2).
M 2/11: No class
W 2/13: Beta and Dirichlet distributions; the gamma subordinator (SC 1.3.1 - 1.3.2).
F 2/15: Dirichlet process and Poisson-Dirichlet(0,\theta) distribution. Stick-breaking representation (SC 1.3.2).
W 2/20: Ewens sampling formula; arising both from Chinese restaurant process and from PD(0,\theta) paintbox (SC 1.3.3).
F 2/22: Kingman coalescent: motivation as limit of Wright-Fisher genealogy (SC 2.1, 2.2).
M 2/25: Interval representation of Kingman coalescent (SC 2.3).
W 2/27: Poisson-Dirichlet arising from Kingman coalescent and neutral mutations (SC 2.4).
[Part 3: Overview of weak convergence on Polish spaces (link to chapter from Fristedt-Gray)]
F 3/1: Definition, dual bounded Lipschitz metric, continuous mapping theorem, convergence-determining classes, Glivenko-Cantelli.
M 3/4: Prohorov's theorem, subsequence device, convergence on S^\infty, weak continuity of representing measure in de Finetti's theorem.
[Part 4. Limits of random trees via the induced substructure technique. Loosely based on Aldous (1991).]
W 3/6: Counting trees (labelled; leaf-labelled binary). Spanning subtrees on k random vertices.
F 3/8: The limit distribution on trees-with edge-lengths. Line-breaking construction of the CRT.
M 3/11: Continuum tree as real tree with a probability distribution. Construction via excursion functions. Brownian CRT.
[Part 5: Lectures based in material from Austin (2012)]
W 3/13 Representation theorem for arrays: background, start proof (Austin sec. 5).
F 3/15: Finish proof. State Dovbysh-Sudakov representation for random infinite symmetric non-negative matrices.
M 3/18: Outline proof of Dovbysh-Sudakov representation.
[Part 6: the paradign of proving convergence via exchangeable substructures]
W 3/20: Dense graph limits.
F 3/22: A conjectured compactification of some finite reversible Markov chains: see Aldous (2012a) .
[Part 7: Lectures based on Greven - Pfaffelhuber - Winter 2009]
M 4/1: Convergence of measured metric spaces: overview.
W 4/3: Convergence of measured metric spaces: compactness criteria.
F 4/5: No class
M 4/8: Convergence of measured metric spaces: compactness criteria.
[Part 8: Lectures based on Diaconis - Rolles 2006]
W 4/10: Linearly reinforced RW on a finite undirected graph; state Diaconis-Freedman "de Finetti's theorem for MCs".
F 4/12: State and outline Big Theorem identifying LRRW with mixture of reversible chains; Bayesian interpretation as conjugate priors over space of MCs.
[Part 9: Lectures based on Buntine - Hutter 2012]
M 4/15: General Poisson-Dirichlet processes and Chinese Restaurant processes.
W 4/17: Distribution and expectation for number of components.
F 4/19: (lecture by Tamara Broderick): Feature allocations, probability functions, and paintboxes (Broderick - Jordan - Pitman 2013).
M 4/22: The Markov moment problem and de Finetti's theorem (from Diaconis - Freedman 2004).
W 4/24: The Lambda-coalescent (from Berestycki 2009).
F 4/26: No class
M 4/29: No class
[Remaining classes for student talks. Max length of talk = 25 minutes]
W 5/1: Sujayam Saha: de Finetti's theorem for Markov chains (Diaconis - Freedman 1980).
W 5/1: Sudeep Kamath: A q-analogue of de Finetti's theorem (Gnedin - Olshanki 2009).
F 5/3: Wenpin Tang: Stochastic flows associated to coalescent processes. (Bertoin - Le Gall 2003).
F 5/3: Riddhipratim Basu: Exchangeable and partially exchangeable random partitions (Pitman 1995).
M 5/6: Yumeng Zhang: A hierarchical version of the de Finetti and Aldous-Hoover representations. (Panchenko 2013).
M 5/6: Joshua Schraiber: Particle representations for measure-valued population models (Donnelly - Kurtz (1999).
W 5/8: Hye Soo Choi: How edge-reinforced random walk arises naturally (Rolles 2003).
W 5/8: Tyler Linderoth: A classification of coalescent processes for haploid exchangeable population models (Mohle - Sagitov 2001)
W 5/8: Geoffrey Schiebinger: Stein's method for concentration inequalities (Chatterjee 2007).
F 5/10: Jonathan Hermon: Graph Limits and Exchangeable Random Graphs (Diaconis - Janson 2008).
F 5/10: Lisha Li: Regularity partitions and the topology of graphons (Lovasz-Szegedy 2010).