The seminar covers a wide range of topics in pure and applied probability and in mathematical physics.
Unless otherwise noted, the talks take place on **Fridays, 11am-12noon**, in room **WWH 512**. See directions to the Courant Institute.

Thomas Leblé helps organizing, in behalf of the Probability/Mathematical physics group.
To be kept informed, you can subscribe to the Probability Seminar Mailing list.

Old webpage.

Critical percolation is fairly well-understood on Z^d for d > 11. Exact values of many critical exponents are rigorously known: for instance, the “one-arm” probability that the origin is connected by an open path to distance r scales as r^{-2}. However, most existing methods rely heavily on the symmetries of the lattice, so they do not extend to fractional spaces. We will discuss progress on these questions in the high-dimensional upper half-space (and within cubes), including the result that the half-space one-arm probability scales as r^{-3}.

Neural networks have experienced a renaissance in recent years, finding success in tasks from machine vision (e.g. self-driving cars) to natural language processing (e.g. Alexa or Siri) and reinforcement learning (e.g. AlphaGo). A mathematical theory of how and why they work is only in the very starting stages.

The purpose of this talk is to address an important numerical stability issue for neural networks, known as the exploding and vanishing gradient problem. I will explain what this problem is and how it turns precisely into a problem of studying products of many matrices in the regime where both the sizes and the number of matrices tend to infinity together. I will present some joint work with Mihai Nica on the behavior of matrices in this regime.

The hierarchical Laplacian was initially introduced in the works of N. Bogolubov and his school (V. Vladimirov, I. Volovich, E. Zelinov) as an essential object in the $p$–adic analysis. Similar ideas were developed by F. Dyson in his famous paper on the phase transitions in $1D$ Ising model with the long range potentials.

We define Dyson–Vladimirov hierarchical Laplacian $\Delta$ as the non-local operator in $L^2 (\mathbb{R}, dx)$ associated the Dyson metric on $\mathbb{R}$. Such Laplacian has many features of the classical fractals (renorm group etc.).

The talk will present the elements of the spectral theory of the hierarchical Hamiltonian $H = -\Delta + V(x)$. The theory includes the standard results (on the essential self – adjointness, negative spectrum etc.) for the deterministic operators and the results in the spirit of the Anderson localization for the class of the random Schrödinger operators.

(Joint work with Alexey Kulik and Michael Scheutzow)

We will present new coupling techniques for analyzing ergodicity of
nonlinear stochastic PDEs with additive forcing. These methods
complement the Hairer-Mattingly approach (2006, 2011). In the first
part of the talk, we demonstrate how a generalized coupling approach
can be used to study ergodicity for a broad class of nonlinear SPDEs,
including 2D stochastic Navier-Stokes equations. This extends the
results of [N. Glatt-Holtz, J. Mattingly, G. Richards, 2017]. The
second part of the talk is devoted to SPDEs that satisfy comparison
principle (e.g., stochastic reaction-diffusion equation). Using a new
version of the coupling method, we establish exponential ergodicity of
such SPDEs in the hypoelliptic setting and show how the corresponding
Hairer-Mattingly results can be refined.

O. Butkovsky, A. Kulik, M. Scheutzow (2018). Generalized couplings
and ergodic rates for SPDEs and other Markov models. arXiv:1806.00395;
to appear in "The Annals of Applied Probability".

The Ricci flow on a surface is an intrinsic evolution of the metric converging to a constant curvature metric within the conformal class. It can be seen as an (infinite-dimensional) gradient flow. We introduce a natural 'Langevinization' of that flow, thus constructing an SPDE with invariant measure expressed in terms of Liouville Conformal Field Theory.

Joint work with Hao Shen (Wisconsin).

We consider a continuous time random walk on the rooted binary tree of depth $n$ with all transition rates equal to one and study its cover time, namely the time until all vertices of the tree have been visited. We prove that, normalized by $2^{n+1} n$ and then centered by $(\log 2) n - \log n$, the cover time admits a weak limit as the depth of the tree tends to infinity. The limiting distribution is identified as that of a Gumbel random variable with rate one, shifted randomly by the logarithm of the sum of the limits of the derivative martingales associated with two negatively correlated discrete Gaussian free fields on the infinite version of the tree. The existence of the limit and its overall form were conjectured in the literature. Our approach is quite different from those taken in earlier works on this subject and relies in great part on a comparison with the extremal landscape of the discrete Gaussian free field on the tree. Joint work with Aser Cortines and Santiago Saglietti.

The random-cluster model is a dependent percolation model where the weight of a configuration is proportional to q to the power of the number of connected components. It is highly related to the ferromagnetic q-Potts model, where every vertex is assigned one of q colors, and monochromatic neighbors are encouraged. Through non-rigorous means, Baxter showed that the phase transition is first-order whenever $q > 4$ - i.e. there are multiple Gibbs measures at criticality. We provide a rigorous proof of this claim. Like Baxter, our proof uses the correspondence between the above models and the six-vertex model, which we analyze using the Bethe ansatz and transfer matrix techniques. We also prove Baxter's formula for the correlation length of the models at criticality. This is joint work with Hugo Duminil-Copin, Maxime Gangebin, Ioan Manolescu, and Vincent Tassion.

Consider the problem of recovering $v \in \mathbb S^{N-1}$ from an i.i.d. Gaussian $k$-tensor spiked by the rank-one tensor $v^{\otimes k}$. The likelihood function for this is an example of a complex high-dimensional landscape. It is information-theoretically possible to detect the spike at order 1 signal-to-noise ratios, but if $k>2$ it is expected that the signal-to-noise ratio needs to diverge in $N$ to efficiently recover $v$. We seek to understand the mechanisms for, and obstructions to, such planted signal recovery in high dimensions, via locally optimizing algorithms.
We study recovery thresholds for a family of ``vanilla" algorithms known as Langevin dynamics, on general
landscapes consisting of a planted non-linear signal function perturbed by isotropic Gaussian noise.
We propose a mechanism for success/failure of recovery via such algorithms in terms of the curvature of the planted signal.

Joint work with G. Ben Arous and A. Jagannath.

Consider a perturbed lattice ${v+Y_v}$ obtained by adding IID d-dimensional Gaussian variables ${Y_v}$ to the lattice points in $Z^d$. Suppose that one point, say $Y_0$, is removed from this perturbed lattice; is it possible for an observer, who sees just the remaining points, to detect that a point is missing? In one and two dimensions, the answer is positive: the two point processes (before and after $Y_0$ is removed) can be distinguished using smooth statistics, analogously to work of Sodin and Tsirelson (2004) on zeros of Gaussian analytic functions. (cf. Holroyd and Soo (2011)). The situation in higher dimensions is more delicate; our solution depends on a game-theoretic idea, in one direction, and on the unpredictable paths constructed by Benjamini, Pemantle and the speaker (1998), in the other.(Joint work with Allan Sly).

The Liouville Brownian motion is Brownian motion in 2D, time changed by the exponential of the Gaussian free field along its trajectory. In recent work with Jian Ding and Fuxi Zhang, we established the existence of scaling exponent for the (logarithmic) short time asymptotics of the heat kernel, and linked the exponent to the scaling exponent of the graph distance for Liouville quantum gravity., which we also proved exists. I will describe this and some related developments.

What can one say about a graph from multiple (short) random walk trajectories on it? In this talk we consider algorithms that only "see" walk trajectories and the degrees along the way.

We will show that the number of vertices, edges and mixing time can be all estimated with a number of RW steps that is sublinear in the size of the graph and in its mixing or relaxation time. Our bounds on the number of RW steps are optimal up to constant or polylog factors. We also argue that such algorithms cannot "know when to stop", and discuss additional conditions that circumvent this limitation. To prove our results, we rely on bounds for random walk intersections by Peres, Sauerwald, Sousi and Stauffer.

Joint with Anna Ben-Hamou (Sorbonne) and Yuval Peres (MSR).

Consider an $n \times n$ matrix with i.i.d.~Bernoulli($p$) entries.
It is well known that for $p= \Omega(1)$, i.e.~$p$ is bounded below by some positive constant,
the matrix is invertible with high probability. If $p \ll \frac{\log n}{n}$ then the matrix contains
zero rows and columns with high probability and hence it is singular with high probability.
In this talk, we will discuss the sharp transition of the invertibility of this matrix at $p =\frac{\log n}{n}$.
This phenomenon extends to the adjacency matrices of directed and undirected Erd\H{o}s-R\'{e}nyi graphs, and random bipartite graph.

Joint work with Mark Rudelson.

The characteristic polynomial of the Gaussian beta--ensemble can be represented,
via its tridiagonal model, as an entry in a product of independent random two--by--two matrices.
For a point z in the complex plane, at which the transfer matrix is to be evaluated, this product
of transfer matrices splits into three independent factors, each of which can be understood as a different dynamical
system in the complex plane. Conjecturally, we show that the characteristic polynomial is always represented as
product of at most three terms, an exponential of a Gaussian field, the stochastic Airy function, and a
diffusion similar to the stochastic sine equation.

We explain the origins of this decomposition, and we show partial progress in establishing part of it.

Joint work with Diane Holcomb and Gaultier Lambert.

I will report on recent work with Louigi Addario-Berry on algorithmic hardness for finding low-energy states in the continuous random energy model of Bovier and Kurkova. This model can be regarded as a toy model for strongly correlated random energy landscapes such as the Sherrington--Kirkpatrick model. We exhibit a precise and explicit hardness threshold: finding states of energy above the threshold can be done in linear time, while below the threshold this takes exponential time for any algorithm with high probability. I further discuss what insights this yields for understanding algorithmic hardness thresholds for random instances of combinatorial optimization problems.

Consider a list of n particles labelled in increasing order. A sorting network is a way of sorting this list into decreasing order by swapping adjacent particles, using as few swaps as possible.
Simulations of large-n uniform random sorting networks reveal a
surprising and beautiful global structure involving sinusoidal particle trajectories, a semicircle law, and a theorem of Archimedes.

Based on these simulations, Angel, Holroyd, Romik, and Virag made a series of conjectures about the limiting behaviour of sorting networks. In this talk, I will discuss how to use the local structure of random sorting networks to prove these conjectures.

We study the Kardar-Parisi-Zhang equation in dimension $d\geq 3$ with space-time white noise which is smoothed in space. There is a natural disorder parameter attached to this equation which measures the intensity of the noise. We show that when the disorder is small, the approximating solution converges to a well-defined limit (with the limit depending on both the disorder and the mollification procedure), while the re-scaled fluctuations converge to a Gaussian limit as predicted by the Edwards-Wilkionson regime. We also study the associated stochastic heat equation with multiplicative noise, which carries a natural Gaussian mutiplicative noise (GMC) on the Wiener space. When the disorder is large, we also show that the total mass of the GMC converges to zero, while the endpoint distribution of a Brownian path under the (renormlaized) GMC measure is purely atomic. Based on joint works with, A. Shamov & O. Zeitouni, F. Comets & C. Cosco as well Y. Broeker.

What is the fate of a random-walk forager that depletes its environment as it wanders? Whenever the forager lands on a food-containing site, all the food is consumed and the forager becomes fully sated. However, when the forager lands on an empty site, it moves one time unit closer to starvation. If the forager wanders S steps without encountering food, it starves to death. We show that the lifetime of this starving random walk forager scales linearly with S in one dimension by solving an underlying non-Markovian first-passage problem. In greater than two dimensions, we present evidence that the lifetime grows quasi-exponentially in S.

We also investigate the role of greed, in which the forager preferentially moves towards food when faced with a choice of hopping to food or to an empty site in its local neighborhood. Paradoxically, the forager lifetime can have a non-monotonic dependence on greed, with different senses to the non-monotonicity in one and in two dimensions. In one dimension, the forager lifetime exhibits a huge peak when greed is negative, while in two dimensions the maximum lifetime occurs for positive, but not perfect, greed.

Finally, we briefly discuss the role of frugality and myopia on foraging dynamics. Frugality means that the forager does not eat until it is nutritionally depleted beyond a specified level. Myopia means that the forager sometime does not "see" food at its current site and leaves the food undisturbed.