Spring 2009
Tuesday 4:30  5:30 pm
Room 2146
Schedule

February 3
Vincent Vargas (ParisDauphine)
Gaussian multiplicative chaos revisited
Abstract: Kahane introduced the theory of Gaussian multiplicative chaos in 1985 to give a rigorous meaning to the KolmogorovObukhov (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.

February 10
Joel H. Spencer (NYU)
Exciting Neurons
Abstract: Imagine a large number $n$ of neurons. Each has activity level $0$ to $k1$, 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 ErdosRenyi 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 ErdosRenyi phase transition. (Joint work with Fabian Kuhn (MIT) et. al.)

February 17
Tobias Friedrich (ICSI Berkeley)
Deterministic random walks and their application to rumor spreading
Abstract: 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.

February 24
Robin Pemantle (U. Penn.)
Some analytic problems arising from random tilings
Abstract: Random tiling ensembles, such as dimer packings or the socalled 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 fiveminute explanation of how one can "read off" the limit behavior from the generating function, giving as examples
 The Arctic Circle Theorem for dimer tilings of the Aztec
 The Octic Circle Theorem for diabolo tilings of the diamond;
 Some strange and beautiful limit shapes for twodimensional quantum random walk.
In the last third of the talk, I will discuss some technical aspects of the analysis of these problems.

March 3
Dan Stroock (MIT)
The Fundamental Solution to the WrightFisher Equation
Abstract: The WrightFisher 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.

March 10
Oren Louidor (NYU)
Mixing time analysis of the Glauber dynamics for the qstates Potts model on the complete graph
Abstract: We consider the qcolors Potts model on the ncomplete 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.

March 17
Sebastien Roch (Microsoft Research)
A Probabilistic Analysis of Clustering Algorithms for Phylogenetic Inference
Abstract: Among the many techniques used by biologists to reconstruct the Tree of Life from molecular sequences, socalled distancematrix 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, distancematrix methods can be surprisingly accurate.
This is joint work with Yuval Peres.

March 24
No seminar (spring break)

March 31
Tai Melcher (University of Virginia)
Heat kernel analysis for semiinfinite Lie groups
Abstract: 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 CameronMartin type quasiinvariance theorem and a logarithmic Sobolev inequality, as well as some potential applications.

April 7
Jim Propp (U. Mass. Lowell)
Rotor walks and Markov chains
Abstract: For any locally finite Markov chain one can construct deterministic "rotorrouter" analogues. Such an analogue typically has many of the same properties as the random process it mimics but is more sharply concentrated around its averagecase behavior. I will discuss the general theory of derandomization of Markov chains via rotorrouters, 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 rotorrouter 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.

April 14
Assaf Naor (NYU)
Towards a calculus for nonlinear spectral gaps.
Abstract: 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, nonEuclidean, geometries: a standard procedure which is used a lot in embedding theory, most strikingly as a method to prove nonembeddability 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 nonlinear spectral gaps under graph operations such as powering and zigzag 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.

April 16
Thursday at 4:30 in room 2131
Sourav Chatterjee (Berkeley)
Chaos, Concentration and Multiple Valleys
Abstract: 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 longstanding 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

April 17
Friday at 3:00 in room 2136
Gideon Amir (Toronto)
The speed process of the Totally Asymmetric Exclusion Process(TASEP)
Abstract: 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 multitype TASEP, and prove that the joint distribution of the speeds is stationary with respect to the multitype 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 multitype 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 workinprogress with Omer Angel and Benedek Valko from the University of Toronto.

April 21
Yuval Peres (Microsoft Research)
Embedding groups in Hilbert space and rate of escape of random walks.
Abstract: 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).

April 28
Tuesday at 3:00 in room 4265
Alice Guionnet (ENSLyon)
Free Brownian motion and applications
Abstract: Free Brownian motion is an operatorvalued 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.
Tuesday at 4:30 in room 2146
Michael Kozdron (U. Regina)
Using multiple SLE to explain a certain observable in the 2d Ising model
Abstract: The SchrammLoewner evolution (SLE) is a oneparameter family of random growth processes that has been successfully used to analyze a number of models from twodimensional 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 nonlocal observable of the 2d critical Ising model studied by Arguin and SaintAubin 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.

April 29
Wednesday at 3:00 in room 2151
Ron Peled (NYU)
Phase Transitions in Gravitational Allocation
Abstract: 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 highdimensional 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.

May 5
Tuesday at 4:30 in room 2146
Ionel Popescu (Georgia Tech)
Functional Inequalities in One Dimensional Free Probability
Abstract: Combining random matrices and classical functional inequalities as Talagrand's, LogSobolev, BrunnMinkowski 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.

May 21
Thursday at 4:30 in room 2146
Ori GurelGurevich (Microsoft Research)
Choicememory tradeoff in allocations
Abstract: Consider the classical ballsandbins setup: n balls are thrown independently and uniformly into n bins. The most loaded bin then has log n/log log n balls with high probability. What happens when instead of throwing balls completely by random, there is an allocation algorithm which is given k uniformly and independently selected bins to choose from for the location of each ball? A well known result of Azar, Broder, Karlin & Upfal states that one can then achieve a maximal load of log_k log n, simply by putting each ball in the less loaded of the k optional bins. In order to implement this simple algorithm, one needs to keep track of the status of the entire array of n bins, which requires about n bits of memory.
The problem of what can be achieved with less memory was raised by Itai Benjamini. The main result in this talk is that, generally speaking, there is a tradeoff between the number of choices, k, and the memory, m. That is, when km>>n one can achieve a constant maximal load, while for km<<n the maximal load quickly reaches the same order of magnitude as in the completely random setting.
A key ingredient in the proofs of the lower bounds is a large deviation inequality, which relates the sum of a sequence of bounded dependent random variables with the sum of their conditional expectations. This inequality may prove useful in other combinatorial or algorithmic problems.
Joint work with Noga Alon and Eyal Lubetzky.
Fall 2008 Organizers
 Lionel Levine
 Scott Sheffield
 Dan Stroock