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.
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.
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.
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.
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 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
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).
Tuesday, April 28
at 3:00 in room 4-265:
Alice Guionnet (ENS-Lyon)
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.
Tuesday, April 28 at 4:30 in room 2-146: Michael Kozdron (U.
Regina)
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 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.
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.
Thursday, May 21 at 4:30 in room 2-146: Ori
Gurel-Gurevich (Microsoft Research)
Choice-memory tradeoff in allocations
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.