SCIENTIFIC PROGRAMS AND ACTIVITIES

Toronto Probability Seminar 2009-10
held at the Fields Institute

Organizers
Bálint Virág , Benedek Valkó
University of Toronto, Mathematics and Statistics

For questions, scheduling, or to be added to the mailing list, contact the organizers at:
probsem-at-math-dot-toronto-dot-edu

and

Joseph Najnudel (Univerisity of Zurich)
Permutations, virtual permutations, and a related flow of operators

Mark Holmes (University of Auckland)
A combinatorial result with applications to random walks

Excited random walks (or random walks in cookie environments) are random walk models in which the probability of departing to the right from a site depends on the number of visits to that site (equivalently how many cookies have been eaten at that site) up to the present time. Work of Zerner, Basdevant and Singh, and others, has demonstrated various different types of behaviour possible with a bounded number of biased cookies at each site

We'll discuss a deterministic combinatorial result that compares two integer sequences l(n) and r(n) defined in terms of collections L and R of arrows satisfying a natural monotonicity relation. Applying this when the arrows are random, the sequences produce non-monotone couplings of self-interacting random walks (such as excited random walks in one dimension). This allows us to extend known results about such models.

*SPECIAL SUMMER SEMINAR*

Tom Salisbury (York)
Random walks in degenerate random environments

At each vertex of the planar square lattice, independently lay down pairs of arrows, heading either North and East (with probability p), or South and West (with probability 1-p). Then do a simple random walk according to the available arrows. This is one of a number of related RWRE models we'll consider. An example of the results obtained is that for p close to 1/2 there is an infinite cluster of points that communicate with each other, while for p close to 0 or 1 all such clusters are finite. This is joint work with Mark Holmes (Auckland).

Blint Virg(Toronto)
Random matrix eigenvalues and Gaussian analytic functions

There are two natural ways of producing repelling random point-clouds on the complex plane: either by taking the eigenvalues of some random matrix or by considering the zeros of a random (Gaussian) analytic function. I will explain some old and new connections between the two worlds.

Domokos Szasz (Budapest University of Technology)
TBA

Neal Madras (York University)
Entangled Clusters in Percolation

In bond percolation on the simple cubic lattice, each bond is independently "open" with probability p. Suppose we view each open bond as a solid but flexible bar, with all bars that share an endpoint being joined at that point. Then it is possible for two disjoint connected components to be topologically entangled. Is it possible for all connected components to be finite, and yet for an infinite number of them to form a single entangled cluster? G. Grimmett and A. Holroyd showed that this happens (almost
surely) for some values of p, but not when p is very close to 0. They then asked whether the number of entangled clusters (modulo translation) with exactly N edges is bounded exponentially in N. We prove that the answer is yes. Among our corollaries we obtain:
(1) an improved lower bound on the critical value for this "entanglement percolation", and
(2) exponential decay of the tail probabilities for the size of the entangled cluster containing the origin, when p is small.This is joint work with Mahshid Atapour.

Domokos Szsz (Toronto and Budapest University of Technology)
Billiard Models and Energy Transfer

Recent progress in the theory of hyperbolic billiards has enhanced the interest towards billiard models since they are the most promising for the derivation of laws of statistical physics from newtonian dynamics. Parallel to this progress, energy transfer models (in particular, the study of diffusion and of Fourier's law of heat conduction) have recently
come to the center of interest. In this talk I will present two determinstic models with energy transfer and will treat a stochastic version of one of them in detail.

Paul Bourgade (Paris VI and Courant Institute)
Mesoscopic Fluctuations of Zeta Zeros

For large unitary matrices, the number of eigenvalues in distinct shrinking intervals satisfies a central limit theorem, whose covariance structure is related to some branching processes. In this talk we present these random matrix results, following works of Diaconis, Evans and Wieand, and show the strict analogue for the zeros of L-functions.

In this lecture we will discuss a phase transition in the Liouville property for automaton groups.

We will start by discussing the Liouville property , which says that the only bounded harmonic functions on a graph are constant, and connect it to amenability of groups. We will then describe automaton groups - which have played an important role in providing (counter-)examples to many problems in group theory, (e.g. groups with intemediate growth) and their Schreier graphs represent classical fractals such as the Sierpinski gasket and Julia sets of finite polynomials such as the Basilica set.

Our main result shows that there is a phase transition in the Liouville property of automaton groups with respect to a certain classification - the degree of activity growth - that will be described. We conclude that all automaton groups with up to linear activity are amenable. The proof has many probablistic elements such as random walks on the Schreier graphs and electrical networks.

This talk is based on joint work with O. Angel and B. Virag

Jinho Baik (University of Michigan)
Maximal Crossings and Nestings of a Random Perfect Matching

A perfect matching on 2n is an n disjoint pairing of 2n numbers. Given a matching, one can consider crossings and nestings. For example, the number of perfect matchings with no crossings equals the Catalan number, and so is the number of matchings with no nestings. Recently, Chen, Deng, Du, Stanley and Yan studied various properties of the maximal crossings and maximal nestings of a matching. Especially they are shown to be symmetric random variables if we consider uniformly random matchings.

It was also deduced, by making connections to various existing works, that the maximal crossings and the maximal nestings are asymptotically distributed as the GOE Tracy-Widom distribution from random matrix theory. In this talk, we will show that they are asymptotically independent. We use the determinantal formula obtained by the above authors. Connections to an integrable differential equation, the Ablowitz-Ladik equation, will also be discussed.

Joint work with Robert Jenkins.

Wiener-Hopf factorization and related fluctuation identities allow us to study various functionals of a Levy process, such as extrema, first/last passage time, overshoot and undershoot, etc. Due to many applications of Levy processes in Mathematical Finance there is a lot of interest in studying processes for which one can compute distributions of these functionals analytically. Unfortunately the list of such examples is very short: it contains processes with one-sided jumps, subclass of stable processes, processes with hyperexponential jumps. In this talk we will discuss several recent results on Wiener-Hopf factorization for processes having meromorphic characteristic exponent. This class is a natural generalization of processes having rational transform; it shares many key properties related to the analytical structure of Wiener-Hopf factorization, but at the same time it is a much larger class which allows for more flexible modeling of jumps.

It is an open problem to determine the number of infinite-volume ground states in the Edwards-Anderson (nearest neighbor) spin glass model on Z^d for d \geq 2 (with, say mean zero Gaussian couplings). This is a limiting case of the problem of determining the number of extremal Gibbs states at low temperature. In both cases, there are competing conjectures for d \geq 3, but no complete results even for d=2. I report on new results which go some way toward proving that (with zero external field, so that ground states come in pairs, related by a global spin flip) there is only a
single ground state pair (GSP). Our result is weaker in two ways: First, it applies not to the full plane Z^2, but to a half-plane. Second, rather than showing that a.s. (with respect to the quenched random coupling realization J) there is a single GSP, we show that there is a natural joint distribution on J and GSP's such that for a.e. J, the conditional distribution on GSP's given J is supported on only a single GSP. The methods used are a combination of percolation-like geometric arguments with translation invariance (in one of the two coordinate directions of the half-plane) and uses as a main tool the ``excitation metastate'' which is a probability measure on GSP's and on how they change as one or more individual couplings vary.

Joint work with Louis-Pierre Arguin, Michael Damron, and Dan Stein.

It is classical that the $L_2$ mixing time of Brownian motion on a nice domain in Euclidean space with reflectance on its boundary, is inversely proportional to the spectral gap of the Neumann Laplacian on that domain.

For convex domains, we provide a new characterization of the spectral gap, by showing that Cheeger's isoperimetric inequality, the spectral gap of the Neumann Laplacian, exponential concentration of Lipschitz functions, and any arbitrarily slow (but fixed) tail-decay of these functions, are all quantitatively equivalent (to within universal constants, independent of the dimension). This extends previous results of Maz'ya, Cheeger, Gromov--Milman, Buser and Ledoux. As an application, we conclude a sharp quantitative stability result for the spectral gap on convex domains under convex perturbations which preserve volume (up to constants) and under maps which are ``on-average'' Lipschitz. This also leads to the following characterization of the square root of the $L_2$ mixing time of Brownian motion on convex domains: it is equivalent (up to constants) to the expectation (with respect to the uniform measure on the domain) of the distance from the ``worst'' Borel set having measure 1/2. In addition, we easily recover (and extend) many previously known lower bounds on the spectral gap of convex domains, due to Payne--Weinberger, Li-Yau, Kannan--Lovasz--Simonovits, Bobkov and Sodin.

The proof involves estimates on the diffusion semi-group following Bakry--Ledoux and a result from Riemannian Geometry on the concavity of the isoperimetric profile. Our results extend to the more general setting of Riemannian manifolds with density which satisfy the $CD(0,\infty)$ curvature-dimension condition of Bakry-Emery, and to more general isoperimetric, functional and concentration inequalities.

Random symmetric matrices with entries that vanish outside a band around the diagonal, but otherwise have independent identically distributed matrix elements, were introduced in the physics literature as an effective model of a "localization/delocalization" transition seen in disordered materials. In this talk, it will be shown that such matrices satisfy a localization condition which guarantees that eigenvectors have strong overlap with only $W^\mu$ standard basis vectors where $W$ is the band width and $\mu$ is an positive exponent. This statement is vacuous if
$W^\mu> N$, the size of the matrix, but if $W^\m << N$ as $N$ tends to infinity, then a typical eigenvector is essentially supported on a vanishing fraction of standard basis vectors. For a Gaussian band ensemble, with matrix elements given by i.i.d. centered Gaussians within a band of width $W$, the estimate $\mu ~ ln 8$ holds. The role of this band matrix model in physics and some open problems and conjectures will also be discussed.

The real Ginibre random matrix (the nxn matrix with all entries iid standard normals) is perhaps the most natural non-Hermitian matrix ensemble one could ask for. Its spectrum however does not enjoy the determinantal nature possessed by its complex analog, making the determination of various spectral limit laws more difficult. We show that, as expected from the complex case, the spectral radius has a classical Gumbel distribution limit. More interesting (maybe) we prove a limit law for the largest real eigenvalue, described in terms of a Fredholm determinant whose kernel (sadly) lacks some of the important structure (in particular, integrability) that one is accustomed to in random matrix theory.

Joint work with Christopher Sinclair.

Simple trends in high-dimensional data sets are modeled by spiked real Gaussian sample covariance matrices. In the large-size limit, the behaviour of the top eigenvalue exhibits a phase transition as a function of the strength of then trend. Using a stochastic operator limit approach, we show that the top eigenvalue has an asymptotic distribution near the phase transition and give several characterizations of the limit laws; one of these involves only a linear boundary value problem. In the well-studied complex case, our PDE description reproduces known explicit formulas and yields a simple new derivation of the Painleve formula for the Tracy-Widom distribution.

This is joint work with Balint Virag.

Robert Masson (UBC)
Random walks on the two dimensional uniform spanning tree

We study random walks on the uniform spanning tree (UST) on Z^2. We obtain estimates for the transition probabilities of the random walk, the distance of the walk from its starting point after n steps, and exit times of both Euclidean balls and balls in the intrinsic graph metric. In particular, we prove that the spectral dimension of the uniform spanning tree on Z^2 is 16/13 almost surely.

In order to prove these results, we use the work of Barlow, Jarai, Kumagai, Misumi and Slade on random walks on random graphs which implies that it suffices to establish volume and effective resistance bounds for the UST. Using Wilson's algorithm, we show that this reduces to obtaining estimates on the number of steps of loop-erased random walks (LERW) in subsets of Z^2. If we let M_n be the number of steps of a LERW from the origin to the circle of radius n, then Kenyon showed that E[M_n] is logarithmically asymptotic to n^{5/4}. In addition to this fact, we need
to show that with high probability, M_n is close to its mean. In fact, we will obtain exponential moment bounds for M_n which implies that the tails of M_n decay exponentially.

Joint work with Martin Barlow.

We consider a polymer with configuration modeled by the trajectory of a Markov chain, interacting with a potential of form u+V_n when it visits a particular state 0 at time n, with V_n representing i.i.d. quenched disorder. There is a critical value of u above which the polymer is pinned by the potential. The main question of interest is, how does this depinning transition differ from the one in the annealed model, where the interaction is effectively homogeneous in n? The most important element is the distribution of the return time to 0 for the underlying Markov chain, and one would like to characterize those return-time distributions which do and do not result in different critical exponents, or critical points, for the quenched vs. annealed model. This problem is much better understood than it was 5 years ago, though many questions remain open. We will give an overview of some recent results.

Let T be the return time to the origin of a simple random walk on a recurrent graph. We show that T is heavy tailed and non-concentrated. More precisely, we have

i) P(T>t) > c/sqrt(t)
ii) P(T=t|T>=t) < C log(t)/t

Inequality i) is attained on Z, and we construct an example demonstrating the sharpness of ii). We use this example to answer negatively a question of Peres and Krishnapur about recurrent graphs with the finite collision property (that is, two independent SRW on them collide only finitely many times, almost surely).

Joint work with Asaf Nachmias.

We will give an overview of the recent results regarding random matrices exhibiting local (microscopic) Poisson eigenvalue statistics. It is known that the Poisson statistics holds for certain classes of random Hermitian matrices, random unitary matrices, random operators on rooted tree graphs and it is conjectured that it also holds for random non-Hermitian Anderson models. We discuss in detail the case of the random CMV matrices, which are the unitary analog of the one-dimensional random Schrodinger operator.

In the talk I will present a family of new, unsolved problems and some partial solutions. The common theme is local (Benjamini-Schramm) convergence of sequences of finite graphs of bounded degree. We will use some notions of asymptotic group theory, ergodic theory and topology.

Antonio Auffinger (Courant)
Directed Polymers in a Random Environment with Heavy Tails

We study the model of Directed Polymers in Random Environment in 1+1 dimensions, where the environment is i.i.d. with a site distribution having a polynomial tail with power -\alpha, where \alpha \in (0,2). After proper scaling of temperature 1/\beta, we show strong localization of the polymer to an optimal region in the environment where energy and entropy are best balanced. We prove that this region has a weak limit under linear scaling and identify the limiting distribution as an (\alpha, \beta) indexed family of measures on Lipschitz curves lying inside the 45 degree rotated square with unit diagonal. In particular, this shows order of n for the transversal fluctuations of the polymer. If (and only if) \alpha is small enough, we find that there exists a random critical temperature above which the effect of the environment is not macroscopically noticeable.

Joint work with Oren Louidor.

The Wick formula reduces the computation of Gaussian integrals over a real or complex vector space to a combinatorial rule plus knowledge of a scalar matrix (which probabilists call the covariance matrix and physicists call the propagator). Interesting applications of the Wick formula often deal with Gaussian integrals over the space of Hermitian matrices, and the associated combinatorics is that of maps on surfaces. Now suppose that one wants to compute integrals over a compact group of matrices, such as the unitary group. There is an analogue of the Wick formula available in this setting - now the "propagator" is the Gram matrix associated to a certain projection. The resulting combinatorics is that of symmetric polynomials evaluated at Jucys-Murphy elements, and this connection allows one to obtain interesting asymptotics, recursive structure, character expansion, and other features of unitary matrix integrals.

For probabilists, a Gaussian spin glass is essentially a Gaussian process on {-1,+1}^N whose variance is N. An important example is the Sherrington-Kirkpatrick model whose covariance is a function of the Hamming distance on {-1,+1}^N. In this talk, I will give an overview of some of the conjectures coming from physics about the behavior of the extrema in the limit of large N, as well as the recent progress on these conjectures in probability. I will focus especially on the ultrametricity conjecture, which is a bold statement about the Gibbs measure of these processes and their extremal statistics in general.

The Doob h-transform: theory and examples
Alex Bloemendal, University of Toronto
I will discuss what it means to condition a Markov process on its exit state, and use the resulting theory to consider various examples of conditioned random walk and Brownian motion.

Doob's h-transform: a few more examples
Alex Bloemendal, University of Toronto

Brownian motion conditioned never to exit a domain and the ground state of the Dirichlet Laplacian; Weyl chambers, the Vandermonde, and Dyson's Brownian motion; Polya's urn.