Schedule

• February 3

  Vincent Vargas (Paris-Dauphine)

  Gaussian multiplicative chaos revisited

  Abstract: 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.

• February 10

  Joel H. Spencer (NYU)

  Exciting Neurons

  Abstract: 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.)

• 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 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
  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.

• March 3

  Dan Stroock (MIT)

  The Fundamental Solution to the Wright-Fisher Equation

  Abstract: 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.

• March 10

  Oren Louidor (NYU)

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

  Abstract: 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.

• 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, 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)

• March 31

  Tai Melcher (University of Virginia)

  Heat kernel analysis for semi-infinite 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 Cameron-Martin type quasi-invariance 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 "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.

• April 14

  Assaf Naor (NYU)

  Towards a calculus for non-linear 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, 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.

• April 16

  Thursday at 4:30 in room 2-131

  Sourav Chatterjee (Berkeley)

  Chaos, Concentration and Multiple Valleys

  Abstract: Disordered systems are an important class of models in statistical mechanics, having the defining characteristic that the energy landscape is a fixed realization of a random field. Examples include various models of glasses and polymers. They also arise in other subjects, like fitness 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 confirms long-standing physics intuition about connections between chaos, anomalous fluctuations 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 first rigorous proof of chaos in any nontrivial disordered system. Applications to other models like spin glasses, fitness models, and general Gaussian fields will also be discussed

• April 17

  Friday at 3:00 in room 2-136

  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 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.

• 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 4-265

  Alice Guionnet (ENS-Lyon)

  Free Brownian motion and applications

  Abstract: 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.

  ---

  Tuesday at 4:30 in room 2-146

  Michael Kozdron (U. Regina)

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

  Abstract: 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.

• April 29

  Wednesday at 3:00 in room 2-151

  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 find 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.

• May 5

  Tuesday at 4:30 in room 2-146

  Ionel Popescu (Georgia Tech)

  Functional Inequalities in One Dimensional Free Probability

  Abstract: 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.

• May 21

  Thursday at 4:30 in room 2-146

  Ori Gurel-Gurevich (Microsoft Research)

  Choice-memory tradeoff in allocations

  Abstract: Consider the classical balls-and-bins 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.