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 possiblyrelevant 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 PoissonDirichlet 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
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.003.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 25minute talk
during last 2 weeks of semester.
 Do one of the research/survey projects which will be mentioned in class.
Classbyclass 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 nonobvious 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: HewittSavage 01 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 clustersizes (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 PoissonDirichlet(0,\theta) distribution.
Stickbreaking 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 WrightFisher genealogy
(SC 2.1, 2.2).

 M 2/25: Interval representation of Kingman coalescent (SC 2.3).
 W 2/27: PoissonDirichlet arising from Kingman coalescent and neutral mutations
(SC 2.4).
 [Part 3: Overview of weak convergence on
Polish spaces (link to chapter from FristedtGray)]
 F 3/1: Definition, dual bounded Lipschitz metric, continuous mapping theorem,
convergencedetermining classes, GlivenkoCantelli.

 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; leaflabelled binary). Spanning subtrees
on k random vertices.
 F 3/8: The limit distribution on treeswith edgelengths.
Linebreaking 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 DovbyshSudakov representation for random infinite
symmetric nonnegative matrices.

 M 3/18:
Outline proof of DovbyshSudakov 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 DiaconisFreedman
"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 PoissonDirichlet 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 Lambdacoalescent (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 qanalogue 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 AldousHoover representations.
(Panchenko 2013).
 M 5/6: Joshua Schraiber:
Particle representations for measurevalued population models
(Donnelly  Kurtz (1999).
 W 5/8: Hye Soo Choi:
How edgereinforced 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
(LovaszSzegedy 2010).