Pacific Northwest Probability Seminar

The Eleventh Northwest Probability Seminar
October 24, 2009
Supported by the Mathematical Sciences Research Institute (MSRI), Pacific Institute for the Mathematical Sciences (PIMS) and Microsoft Research.

Speaker photographs

The Birnbaum Lecture in Probability will be delivered by Persi Diaconis (Stanford University) in 2009.

Northwest Probability Seminars are one-day mini-conferences held at the University of Washington and organized in collaboration with the Oregon State University, the University of British Columbia, the University of Oregon, and the Theory Group at the Microsoft Research. There is no registration fee.

The Scientific Committee for the NW Probability Seminar 2009 consists of Omer Angel (U British Columbia), Chris Burdzy (U Washington), Zhenqing Chen (U Washington), Yevgeniy Kovchegov (Oregon State U), David Levin (U Oregon) and Yuval Peres (Microsoft).

The talks will take place in Savery Hall 260. Savery 264 is also reserved for the conference participants (extra meeting room, extra whiteboards, etc.) See the map the location of Savery Hall and Padelford Hall (the Department of Mathematics is in the Padelford Hall). More campus maps are available at the UW Web site.

Parking on UW campus is free on Saturdays only after noon. See parking fees and general parking information.

### Schedule

• 10:40 Coffee Savery 264
• 11:10 Robert Masson, University of British Columbia
Exponential tail bounds for loop-erased random walk in Z^2
Consider a simple random walk in Z^2 started at the origin and stopped at its first exit of the ball of radius n, and let M_n be the number of steps of its loop-erasure. Kenyon showed that E[M_n] is logarithmically asymptotic to n^{5/4}. In this talk, we give tail bounds on M_n. We establish exponential moments for M_n and thereby show that there exists c > 0 such that for all n and a>1, P(M_n > a E[M_n]) < 2exp(-ca). Using a second moment result for the loop-erasure of a specific conditioned random walk and an iteration argument, we also get the following bound on the lower tail: for all b < 4/5, there exist C and c'>0 such that for all n and a >1, P(M_n < a^{-1} E[M_n]) < C exp(-c a^b). Time permitting, we will discuss applications of this result to volume estimates for the uniform spanning tree in Z^2. Joint work with Martin Barlow.
• 12:00 - 1:15 Lunch, catered, HUB 108.
• 1:15 Persi Diaconis, Stanford University
"Birnbaum Lecture": Graph Limits and Threshold Graphs
What does it mean for a sequence of graphs (random or not) to converge or for one graph to be a good approximation to another? This is the subject of graph limits as developed by Lovasz and many coauthors. It turns our that many of the basic results were anticipated by the multivariate versions of deFinetti's theorem (Aldous-Hoover-Kallenberg). I will explain both sides of this subject and illustrate with random threshold graphs. All of this is joint work with Susan Holmes and Svante Janson.
• 2:15 Coffee break Savery 264
• 2:30 Christopher Sinclair, University of Oregon
Pfaffian Point Processes and Random Matrices
An ensemble of matrices is a set of matrices together with a probability measure. The probability measure induces a point process on the space of eigenvalues of the set of matrices. The point process is called determinantal or Pfaffian if the joint intensities of the point process can be represented as determinants or Pfaffians of certain matrices associated with the ensemble. In this talk, I will give example of some ensembles which induce Pfaffian point processes and show how this structure allows many basic probabilistic quantities to be computed (e.g. the probability that a matrix has no eigenvalues in a given set, and the distribution for the absolute value of the largest eigenvalue). New ensembles and applications will be discussed within this framework.
• 3:20 David Aldous, U.C. Berkeley and Microsoft Research
• Spatial random networks
I will give an overview of ongoing research concerning networks linking random vertices in two-dimensional space, emphasizing two aspects.

(1) If we get to choose where to put edges, subject to a given total length, then how efficient can we make the network in the sense of providing routes whose length is not much larger than straight-line distance?

(2) There is a general class of "proximity graphs", defined for arbitrary vertices, which are always connected. Applying to random points gives a class of random networks which are connected and have bounded mean degree. This class has scarcely been studied, but seems an appealing modeling alternative to the classical geometric random graphs for which one cannot have both connectivity and bounded mean degree.

• 4:10 - 4:50 Problem session
• Chair: Yuval Peres (Microsoft Research)
• 6:00 No-host dinner.
• Restaurant: Chiang's Gourmet. 7845 Lake City Way NE, Seattle, WA 98115, Tel: (206) 527-8888