# MIT Probability Seminar

### Spring 2009 Tuesday 4:30 - 5:30 pm Room 2-146

Organizers: Lionel Levine, Scott Sheffield and Dan Stroock

### Spring 2009 Schedule:

Gaussian multiplicative chaos revisited

Kahane introduced the theory of Gaussian multiplicative chaos in 1985 to give a rigorous meaning to the Kolmogorov-Obukhov (KO) model of energy dissipation in a 3d turbulent flow. We will first give an outline of the theory and show that it is not sufficient to define the scale invariant version of the KO model. This will lead us to define a revised version of the theory.

Exciting Neurons

Imagine a large number $n$ of neurons. Each has activity level $0$ to $k-1$, with level $k$ a special temporary level. A random neuron is promoted: its level goes up one. From level $k$ it fires, all all other neurons are promoted with independent probability $p=\beta/n$. Those neurons in turn will fire, if from level $k$, and there may and often is a big burst of firings. After the big burst all neurons that have fired return to the lowest level. We are interested in asymptotics with $k,\beta$ fixed ($k=10,\beta=9.7$ is a good example) and $n\rightarrow\infty$.

There are strong analogies to the Erdos-Renyi phase transition. There appear to be three ranges of $\beta$. For $\beta$ small the bursts will be small. For $\beta > k$ there will be a stable periodic behavior consisting of a big burst followed by a recovery time back to nearly the same state. Intriguingly, for $\beta$ slightly less than $k$ there is both the above stable periodic behavior and a second stable periodic behavior in which the neurons are nearly uniformly divided in activity level. Further, the behavior just prior to a big bursts mirrors the critical window of the Erdos-Renyi phase transition. (Joint work with Fabian Kuhn (MIT) et. al.)

Deterministic random walks and their application to rumor spreading

Random walks can be simulated with a simple deterministic process suggested by Jim Propp. Joshua Cooper and Joel Spencer showed that it resembles surprisingly closely the random walk on $Z^d$. I will begin by surveying this and some other results showing a surprising similarity of the deterministic random walk to the classical random walk. As randomness is a crucial component in many efficient algorithms, understanding when it's necessary and when it can be avoided is crucial. In the main part of the talk I will propose and analyze a quasirandom analogue to the broadcasting model for disseminating information in networks. It achieves similar or better broadcasting times with a greatly reduced use of random bits.

Some analytic problems arising from random tilings

Random tiling ensembles, such as dimer packings or the so-called diabolo tilings, have been around since the sixties, though most results in this area are relatively recent. One attack, via generating functions, produces limit statements at a glance. The proofs require considerable analytic work, though it is hoped that this may be collected into a few omnibus results, after which further theorems will roll off the assembly line.

I will begin by surveying some problems and results concerning random tilings and other exactly solvable models. I will then give a five-minute explanation of how one can "read off" the limit behavior from the generating function, giving as examples

(1) The Arctic Circle Theorem for dimer tilings of the Aztec diamond;
(2) The Octic Circle Theorem for diabolo tilings of the diamond;
(3) Some strange and beautiful limit shapes for two-dimensional quantum random walk.

In the last third of the talk, I will discuss some technical aspects of the analysis of these problems.

The Fundamental Solution to the Wright-Fisher Equation

The Wright-Fisher equation

d_t u = x(1 − x)d_x^2 u   in (0, ∞) × (0, 1)

was introduced originally to model demographics with migration. More recently it has been used to model the distribution of alleles in the genome. The problem discussed in this lecture is that of analyzing the fundamental solution to this equation with Dirichlet boundary conditions, the interesting question being how to handle the degeneracy at the end points. In the 1960’s, Kimura expressed this fundamental solution as an eigenfunction expansion. Unfortunately, his expression gives useful information only for large time. The analysis described here attempts to give information for all time.

Mixing time analysis of the Glauber dynamics for the q-states Potts model on the complete graph

We consider the q-colors Potts model on the n-complete graph and use Glauber dynamics to simulate its Gibbs distribution. We analyze the mixing time of the Glauber chain, i.e. the time it takes for the state distribution to converge to stationarity, namely the Potts distribution.

In the disorder phase (\beta < \beta_c), we show the existence of a critical temperature (\beta_m < \beta_c) above which the mixing time is ~1/(2(1-\beta/q)) nlog(n) and below which the mixing time is exponential.

In addition, we show that in the fast mixing regime, the chain exhibits a cutoff phenomena with a window size of O(n), i.e. the state distribution changes from being for from stationary to being close in a windows of O(n) steps, around the \theta(nlog(n)) mixing time.

We also analyze the case when the temperature is exactly critical for mixing and the case when the temperature converges to criticality with n. Formally, if \beta = \beta_m - \delta(n), with \delta(n) going to 0, the mixing time is \theta(n / \sqrt(n) + nlog(n)) with a cutoff window of size O(n + \sqrt(n / \delta^{5/2})) if \delta(n) = \Omega(n^{-2/3}) and \theta(n^{4/3}) with no cutoff if \delta(n) = o(n^{-2/3}). This proof for this part is close (but not yet) to being complete.

This is joint work with Yuval Peres, Paul Cuff, Jian Ding, Eyal Lubetzky and Allan Sly.

A Probabilistic Analysis of Clustering Algorithms for Phylogenetic Inference

Among the many techniques used by biologists to reconstruct the Tree of Life from molecular sequences, so-called distance-matrix methods are typically the fastest. This speed stems from a straightforward, intuitive approach: the repeated agglomeration of the closest clusters of species. In this talk, I will discuss a deep connection between such clustering approaches and the estimation of ancestral sequences – a problem known in probability theory as the reconstruction problem.’’ This new connection leads to a tight analysis of these algorithms. I will prove in particular that, despite their simplicity, distance-matrix methods can be surprisingly accurate.

This is joint work with Yuval Peres.
• March 24: No seminar (spring break)

Heat kernel analysis for semi-infinite Lie groups

We'll talk about heat kernel measure on a class of infinite dimensional Lie groups based on an abstract Wiener space. Heat kernel measure here will be defined as the law of a Brownian motion, constructed as the solution to a stochastic differential equation. We'll discuss results for the heat kernel measure, including a Cameron-Martin type quasi-invariance theorem and a logarithmic Sobolev inequality, as well as some potential applications.

Rotor walks and Markov chains

For any locally finite Markov chain one can construct deterministic "rotor-router" analogues. Such an analogue typically has many of the same properties as the random process it mimics but is more sharply concentrated around its average-case behavior. I will discuss the general theory of derandomization of Markov chains via rotor-routers, as well as the particular example of walk in Z^2. Let p be the probability that a random walk in Z^2 that walks from source vertex s until it hits the finite target set T stops at a particular vertex t in T. If one performs N successive runs of a suitable rotor-router walk in Z^2 from s to T, the number of runs that stop at t is Np plus or minus O(log n). This is joint work with Ander Holroyd.

Slides available at jamespropp.org/probsem09a.html.

Towards a calculus for non-linear spectral gaps.

The spectral gap of a symmetric stochastic matrix is the reciprocal of the best constant in its associated Poincare inequality. This inequality can be formulated in purely metric terms, where the metric is a Hilbertian metric. This immediately allows one to define the spectral gap of a matrix with respect to other, non-Euclidean, geometries: a standard procedure which is used a lot in embedding theory, most strikingly as a method to prove non-embeddability in the coarse category. Motivated by a combinatorial approach to the construction of bounded degree graph families which do not admit a coarse embedding into any uniformly convex normed space (such spaces were first constructed by Lafforgue), we will naturally arrive at questions related to the behavior of non-linear spectral gaps under graph operations such as powering and zig-zag products. We will also discuss the issue of constructing base graphs for these iterative constructions, which leads to new analytic and geometric challenges.

Joint work with Manor Mendel.
• Thursday, April 16 at 4:30 in room 2-131
*note unusual day and room*
: Sourav Chatterjee (Berkeley)

Chaos, Concentration and Multiple Valleys

Disordered systems are an important class of models in statistical mechanics, having the deﬁning characteristic that the energy landscape is a ﬁxed realization of a random ﬁeld. Examples include various models of glasses and polymers. They also arise in other subjects, like ﬁtness models in evolutionary biology. The ground state of a disordered system is the state with minimum energy. The system is said to be chaotic if a small perturbation of the energy landscape causes a drastic shift of the ground state. In this talk I will present a rigorous theory of chaos in disordered systems that conﬁrms long-standing physics intuition about connections between chaos, anomalous ﬂuctuations of the ground state energy, and the existence of multiple valleys in the energy landscape. Combining these results with mathematical tools like hypercontractivity, I will present a proof of the existence of chaos in directed polymers. This is the ﬁrst rigorous proof of chaos in any nontrivial disordered system. Applications to other models like spin glasses, ﬁtness models, and general Gaussian ﬁelds will also be discussed
• Friday, April 17 at 3:00 in room 2-136
*note unusual day/time and room*
: Gideon Amir (Toronto)

The speed process of the Totally Asymmetric Exclusion Process(TASEP)

We study an exclusion process on Z where each particle is assigned a class (number in Z) and each particle tries to swap places with its right neighbor with rate 1 if that neighbor has a higher class number. (Alternatively, each edge of Z is "sorted" with rate 1) With the right starting conditions, the position of each particle (normalized by the time) converges to a constant speed. The speed of each particle is uniform in [-1,1], but there are strong dependencies between the behavior of different particles.

We study this exclusion process and the distribution of its related speed process. We show a new symmetry for the multi-type TASEP, and prove that the joint distribution of the speeds is stationary with respect to the multi-type TASEP dynamics (where the speeds are considered as the classes of the particles). This allows us to utilize known results on stationary measure for the multi-type TASEP to deduce various marginals of the speed process such as the joint distribution of the speeds for 3 consequent particles . Another surprising consequence is the existence of infinite "convoys" – particles (with different classes) all converging to the same speed. Some of our results apply also to the partially asymmetric case as well.

No prior knowledge on exclusion processes is assumed, and all definitions will be given within the lecture.

This is joint work-in-progress with Omer Angel and Benedek Valko from the University of Toronto.

Embedding groups in Hilbert space and rate of escape of random walks.

Simple random walk on the Cayley graph of an infinite group must escape at least diffusively, i.e. the expected distance from the starting point is at least Ct^{1/2} at time t. The only known (unpublished) proof (due to Anna Erschler and Balint Virag) is via Mok's harmonic mapping into Hilbert space. We sharpen this statement to a probability one result via a new martingale inequality and prove a version for finite groups (when t is at most the inverse spectral gap). I will also discuss a general inequality that bounds the compression exponent for embeddings of infinite amenable groups using the escape exponent for random walks. We show the inequality is sharp in lamplighter type groups by using a traveling salesman estimate and stable random walks. (Talk based on joint works with James Lee and Assaf Naor).

Free Brownian motion and applications

Free Brownian motion is an operator-valued process obtained as the renormalized limit of an N by N Hermitian matrix with independent Brownian entries. We will review its properties as a stochastic process and illustrate its use as a probabilistic tool to solve problems from combinatorics (e.g enumeration of complicated graphs) and operator algebras.

Using multiple SLE to explain a certain observable in the 2d Ising model

The Schramm-Loewner evolution (SLE) is a one-parameter family of random growth processes that has been successfully used to analyze a number of models from two-dimensional statistical mechanics. Currently there is interest in trying to formalize our understanding of conformal field theory using SLE. Smirnov recently showed that the scaling limit of interfaces of the 2d critical Ising model can be described by SLE(3). The primary goal of this talk is to explain how a certain non-local observable of the 2d critical Ising model studied by Arguin and Saint-Aubin can be rigorously described using multiple SLE(3) and Smirnov's result. As an extension of this result, we explain how to compute the probability that a Brownian excursion and an SLE(k) curve, 0 < k < 4, do not intersect.
• Wednesday, April 29 at 3:00 in room 2-151: Ron Peled (NYU)

Phase Transitions in Gravitational Allocation

Given a Poisson point process of unit masses (“stars”) in dimension d >= 3, Newtonian gravity partitions space into domains of attraction (cells) of equal volume. The allocation is translation equivariant - the shape of cells do not depend on absolute position in space. We investigate the quantitative geometry of the allocation's cells. Our first result shows that a.s. all cells are bounded and that their diameters have exponential tails. We continue and investigate large deviations for the cells. We find that the probability that mass exp(−R^t) in a cell travels distance R decays like exp(−R^(f_d(t))) and we identify the functions f_d exactly. These functions are piecewise linear and the discontinuities of f'_d represent phase transitions. We observe two distinct behaviors: In dimension 3, large deviations are due to a “distant attracting galaxy” which attracts the mass from afar. In dimensions d >= 5, large deviations are due to a “wormhole”. A thin tube along which the star density increases monotonically and which pulls the mass through it. In dimension 4 we ﬁnd a double phase transition with a transition between low- dimensional behavior (attracting galaxy) and high-dimensional behavior (wormhole) at t = 4/3. As consequences, we determine the tail behavior of the distance from a star to a uniform point in its cell, and prove a sharp lower bound for the tail probability of the cell's diameter, matching our earlier upper bound.

This is joint work with Sourav Chatterjee, Yuval Peres and Dan Romik.
• Tuesday, May 5 at 4:30 in room 2-146: Ionel Popescu (Georgia Tech)

Functional Inequalities in One Dimensional Free Probability

Combining random matrices and classical functional inequalities as Talagrand's, Log-Sobolev, Brunn-Minkowski and Poincare, one can get (and sometimes even prove) the analogues of the functional inequalities in one dimensional free probability. What we will show is a new approach to proving these inequalities which does not involve any random matrices.