Pacific Northwest Probability Seminar

The Fifteenth Northwest Probability Seminar
October 19-20, 2013
Dedicated to the memory of Bob Blumenthal.
Supported by the Pacific Institute for the Mathematical Sciences (PIMS), Microsoft Research and Milliman Fund.

Speaker photographs

The Birnbaum Lecture in Probability will be delivered by Patrick Fitzsimmons (University of California, San Diego) in 2013.
The Schramm-MSR Lecture will be delivered by Noga Alon (Tel Aviv University) in 2013.

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

The Scientific Committee for the NW Probability Seminar 2011 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 Eyal Lubetzky (Microsoft), Yuval Peres (Microsoft) and David Wilson (Microsoft).

If you plan to attend, please let us know so that we can plan for food and make name tags. Also, if you have a probability related demo or open problem to present on Day 2, please let us know. Please send this information to David Wilson at David.Wilson@microsoft.com.

HOTEL INFORMATION

Hotels near Microsoft: Extended Stay America, Silver Cloud Inn.

### Day 1 (University of Washington)

On day 1, the talks will take place in Savery Hall 260. 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 information.

### Schedule

• 10:30 Coffee Savery 260
• 11:00 - 11:50 Zhenqing Chen, University of Washington
Quenched Invariance Principles for Random Walks in Random Media with Boundary
In this talk, I will present recent progress on the study of quenched invariance principles for random walks in random environments with a boundary. In particular, we prove that the random walk on a supercritical percolation cluster or amongst random conductances bounded uniformly from below in a half-space, quarter-space, etc., converges when rescaled diffusively to a reflecting Brownian motion, which had been one of the important open problems in this area. Our approach uses a Dirichlet form extension theorem and two-sided heat kernel estimates. Based on a recent joint work with David Croydon and Takashi Kumagai.
• 12:00 - 2:00 Lunch, catered, HUB 250 (Husky Union Building), including remarks on Bob Blumenthal's contributions to probability by Ron Getoor.
• 2:00 - 2:50 Patrick Fitzsimmons, University of California, San Diego
"Birnbaum Lecture": The Stationary Process Associated with an Excessive Measure of a Markov Process; Applications Old and New
I will discuss the stationary process with random times of birth and death that can be associated with a given strong Markov process and one of its excessive measures. (In the literature this process is commonly referred to as a Kuznetsov process''; the notion is related the quasi-process'' of G.A. Hunt and M. Weil.) I will then examine a number of examples illustrating the usefulness of this process, both as a conceptual device and as a technical tool. These examples will involve applications to Skorokhod stopping, excursion theory, time reversal, capacities, as well as a very recent proof of Kac's scattering length formula.
• 3:00 - 3:50 David Koslicki, Oregon State University
Random substitutions, Martin boundaries, and molecular evolution
In this talk, I will define the concept of a "substitution Markov chain" (SMC) which can be conceptually viewed as a kind of random substitution process. A number of properties will be shown, including the computation of the Martin boundary in a few special cases. As an application, it will also be shown that a certain class of SMC's can be used to accurately model molecular evolution.
• 4:00 - 4:30 Coffee break Savery 260
• 4:30 - 5:20 Balázs Ráth, University of British Columbia
Critical mean field frozen percolation and the multiplicative coalescent with linear deletion
The mean field frozen percolation process is a modification of the dynamical Erdos-Renyi random graph process in which connected components are deleted (frozen) with a rate linearly proportional to their size. It is known that the model exhibits self-organized criticality for a wide range of choices of the freezing rate. The aim of the present talk is to describe the results of our upcoming joint paper with James Martin (Oxford) in which we show that a careful choice of the freezing rate forces the graph to stay in the critical window permanently. In particular, we find that the scaling limit of the evolution of big component sizes is a variant of Aldous' multiplicative coalescent process.
• 6:30 No-host dinner.
• Restaurant: Salmon House, 401 NE Northlake Way, Seattle, WA 98105
• Driving directions from Padelford parking lot
• We will go Dutch, that is, every person will pay for what he/she orders; the entree prices vary significantly.

### Day 2 (Microsoft Research)

On day 2, the talks will take place in Building 99 at Microsoft. Parking at Microsoft is free.

Directions: From the north: Take I-5 south, then I-405 south, then WA-520 east.
From the south: Take I-5 north, then I-405 north, then WA-520 east.
From Seattle: Take WA-520 east.
By airplane: Fly to Seattle's airport, take I-405 north, then WA-520 east.

From WA-520 east, take the 148th Ave NE North exit (this is the second 148th Ave NE exit). Turn right (north) onto 148th Ave NE, proceed a few blocks, and turn right onto NE 36th St. Building 99 will be on the left. The address is 14820 NE 36th St, Redmond, WA 98052-5319. Click here for a map.

### Schedule

• 9:30 Coffee
• 10:00 - 11:00 Noga Alon, Tel Aviv University and IAS, Princeton
"Schramm-MSR Lecture": Random Cayley Graphs
The study of random Cayley graphs of finite groups is related to the investigation of Expanders and to problems in Combinatorial Number Theory and in Information Theory. I will discuss this topic, describing the motivation and focusing on the question of estimating the chromatic number of a random Cayley graph of a given group with a prescribed number of generators.
• 11:30 - 12:20 Fabio Martinelli, Universita di Roma 3
Mixing times for constrained spin models
Consider the following Markov chain on the set of all possible zero-one labelings of a rooted binary tree of depth L: At each vertex $v$ independently, a proposed new label (equally likely to be 0 or 1) is generated at rate 1. The proposed update is accepted iff either $v$ is a leaf or both children of $v$ are labeled "0”. A natural question is to determine the mixing time of this chain as a function of L. The above is just an example of a general class of chains in which the local update of a spin occurs only in the presence of a special ("facilitating") configuration at neighboring vertices. Although the i.i.d. Bernoulli distribution remains a reversible stationary measure, the relaxation to equilibrium of these chains can be extremely complex, featuring dynamical phase transitions, metastability, dynamical heterogeneities and universal behavior. I will report on progress on the mixing times for these models.
• 12:30 - 2:30 Lunch, catered, including probability software demos and open problem session
• 2:30 - 3:10 Ronen Eldan, Microsoft
A Two-Sided Estimate for the Gaussian Noise Stability Deficit
The Gaussian Noise Stability of a set A in Euclidean space is the probability that for a Gaussian vector X conditioned to be in A, a small Gaussian perturbation of X will also be in A. Borel's celebrated Isoperimetric inequality states that a half-space maximizes noise stability among sets with the same Gaussian measure. We will present a novel short proof of this inequality, based on stochastic calculus. Moreover, we prove an almost tight, two-sided, dimension-free robustness estimate for this inequality: We show that the deficit between the noise stability of a set A and an equally probable half-space H can be controlled by a function of the distance between the corresponding centroids. As a consequence, we prove a conjecture by Mossel and Neeman, who used the total-variation distance.
• 3:10 - 3:30 Coffee
• 3:30 - 4:10 Roberto Oliviera, IMPA
Mixing of the symmetric exclusion processes in terms of the corresponding single-particle random walk
We prove an upper bound for the mixing time of the symmetric exclusion process on any graph G, with any feasible number of particles. Our estimate is proportional to the mixing time of the corresponding single-particle random walk times a log |V| term, where |V| is the number of vertices. This bound implies new results for symmetric exclusion on expanders, percolation clusters, the giant component of the Erdos-Renyi random graph and Poisson point processes. Our technical tools include a variant of Morris's chameleon process.