The longest increasing subsequence (LIS) of a uniformly random permutation is a well studied problem. Vershik-Kerov and Logan-Shepp first showed that asymptotically the typical length of the LIS is 2sqrt(n). This line of research culminated in the work of Baik-Deift-Johansson who related this length to the GUE Tracy-Widom distribution. We study the length of the LIS of random permutations drawn from the Mallows measure, introduced by Mallows in connection with ranking problems in statistics. We prove limit theorems for the LIS for different regimes of the parameter of the distribution. I will also describe some recent results on the longest common subsequence of independent Mallows permutations. Relevant background for the talk will be introduced as needed. Based on work with Ron Peled, Riddhi Basu and Ke Jin.

Abstract: One of the most dynamic areas of probability theory is the study of the behaviour of discrete optimization problems on random inputs. My talk will focus on the probabilistic analysis of one of the first and foundational combinatorial optimization problems: the minimum spanning tree problem. The structure of a random minimum spanning tree (MST) of a graph G turns out to be intimately linked to the behaviour of critical and near-critical percolation on G. I will describe this connection and some of my results, alone and with coauthors, on the structure, scaling limits, and volume growth of random MSTs. It turns out that, on high-dimensional graphs, random minimum spanning trees are expected to be three-dimensional when viewed intrinsically, and six-dimensional when viewed as embedded objects.

The partner model is an SIS epidemic in a population with random formation and dissolution of partnerships, and disease transmission only occurs within partnerships. Foxall, Edwards, and van den Driessche found the critical value and studied the subcritical and supercritical regimes. Recently Foxall has shown that (if there are enough initial infecteds) then the critical model survives for time \(O(N^{1/2})\). Here we improve that result by proving the convergence of \(i_N(t)=I(tN^{1/2})/N^{1/2}\) to a limiting diffusion. We do this by showing that in the first O(1), this four dimensional process collapses to two dimensions: the number of SI and II partnerships are constant multiples of the the number of infected singles \(I_t\). The other variable \(Y_t\), the total number of singles, behaves like an Ornstein-Uhlenbeck process on a time scale O(1) and averages out of the limit theorem for \(i_N(t)\). This is joint work with Anirban Basak and Eric Foxall.

I will present a few recent results on random planar metrics of two-dimensional discrete Gaussian free fields, including Liouville first passage percolation, the chemical distance for level-set percolation and the electric effective resistance on an associated random network. Besides depicting a fascinating picture for 2D GFF, these metric aspects are closely related to various models of planar random walks.

I will discuss an ensemble sampling scheme based on a decomposition of the target average of interest into subproblems that are each individually easier to solve and can be solved in parallel. The most basic version of the scheme computes averages with respect to a given density and is a generalization of the Umbrella Sampling method for the calculation of free energies. For equilibrium versions of the scheme we have developed error bounds that reveal that the existing understanding of umbrella sampling is incomplete and potentially misleading. We demonstrate that the improvement from umbrella sampling over direct simulation can be dramatic in certain regimes. Our bounds are motivated by new perturbation bounds for Markov Chains that we recently established and that are substantially more detailed than existing perturbation bounds for Markov chains. I will also briefly outline a ``trajectory stratification’’ technique that extends the basic umbrella sampling philosophy to the calculation of dynamic averages with respect a given Markov process. The scheme is capable of computing very general dynamic averages and offers a natural way to parallelize in both time and space.

The inviscid Burgers' equation has the remarkable property that its dynamics preserve the class of spectrally negative L\'{e}vy initial data, as observed by Carraro and Duchon (statistical solutions) and Bertoin (entropy solutions). Further, the evolution of the L\'{e}vy measure admits a mean-field description, given by the Smoluchowski coagulation equation with additive kernel. In this talk we discuss ongoing efforts to generalize this result to scalar conservation laws, a special case where this is done, and a connection with integrable systems. Includes work with F. Rezakhanlou.

We review the Mean Field Game (MFG) paradigm introduced independently by Caines-Huang-Malhame and Lasry Lyons ten years ago, and we illustrate the relevance for applications with a couple of examples (bird flocking and room exit). We then review the probabilistic approach based on Forward-Backward Stochastic Differential Equations (FBSDEs), and we derive the Master Equation from a version of the chain rule (Ito's formula) for functions over flows of probability measures. Finally, we give a new form to the extension of MFGs to the case of major and minor players and, at least in the finite state space case, we describe an application to virus contagion (e.g. cyber security).

Given a continuous time Markov Chain \( q(x,y)\) on a finite set S, the associated noisy voter model is the continuous time Markov chain on \(\{0,1\}^S\) which evolves by (i) for each two sites x and y in S, the state at site x changes to the value of the state at site y at rate \( q(x,y) \) and (ii) each site rerandomizes its state at rate 1. We show that if there is a uniform bound on the rates \(q(x,y)\) and the corresponding stationary distributions are ``almost'' uniform, then the mixing time has a sharp cutoff at time \(\log |S|/2\) with a window of order 1. Lubetzky and Sly proved cutoff with a window of order 1 for the stochastic Ising model on toroids: we obtain the special case of their result for the cycle as a consequence of our result.

It is a well known fact that velocity grandients in a flow change the dispersion of a passive tracer. One clear manifestation of this phenomenon is that in systems with homogenization type diffusive long time/large scale behavior, the effective diffusivity often differs greatly from the molecular one. An important aspect of these well known result is that they are only valid on timescales much longer than the inverse diffusivity. We are interested in what happens on shorter timescales (subhomogenization regimes) in a family of two-dimensional incompressible periodic flows that consists only of pockets of recirculations essentially acting as traps and infinite flowlines separating these where significant transport is possible. Our approach is to follow the random motion of a tracer particle and show that under certain scaling it resembles time-changed Brownian motions. This shows that while the trajectories are still diffusive, the variance grows differently than linear.

In 1979, G. Parisi predicted a variational formula for the thermodynamic limit of the free energy in the Sherrington-Kirkpatrick model and described the role played by its minimizer, called the Parisi measure. This remarkable formula was proven by Talagrand in 2006. In this talk I will explain a new representation of the Parisi functional that finally connects the temperature parameter and the Parisi measure as dual parameters. Based on joint-works with Wei-Kuo Chen.

We will show that the solutions to a large family of stochastic PDEs that behave as the linear heat equation develop large-scale space-time peaks on infinitely-many different scales. We formalize this assertion by appealing to the Barlow-Taylor theory of macroscopic fractals. We will also present some earlier work on fixed-time results for comparison purposes. This talk is based on a paper and a work in progress with Kunwoo Kim (Technion) and Yimin Xiao (Michigan State University).

We consider a model of infection spread on the complete graph on N vertices. Edges are dynamic, modelling the formation and breakup of non-permanent monogamous partnerships, and the infection can spread only along active edges. We identify a basic reproduction number \(R_0\) such that the infection dies off in \(O(\log N)\) time when \(R_0\)<1, and survives for at least \(e^{cN}\) time when \(R_0\)>1 and a positive fraction of vertices are initially infectious. We also identify a unique endemic state that exists when \(R_0\)>1, and show it is metastable. When \(R_0\)=1, with considerably more effort we can show the infection survives on the order of \(N^{1/2}\) amount of time.

Importance sampling is an accelerated Monte Carlo algorithm that can reduce variance when estimating small probabilities. The design of the algorithm involves the choice of a change of measure, and based on this choice the performance can range from substantially better than standard Monte Carlo to substantially worse. One approach to choosing a change of measure involves embedding the problem of interest in a sequence of processes that satisfies a large deviations principle, and then basing the change of measure on subsolutions to the Hamilton-Jacobi-Bellman equation associated the large deviations rate function. This approach has the benefit of guaranteeing a certain level of asymptotic performance based on the subsolution, but different embeddings can lead to different rate functions, subsolutions, and consequently different algorithms. I will contrast the strengths and weaknesses of two different embeddings, one using a scaling commonly referred to as the standard large deviations scaling and the other using a scaling referred to as moderate deviations.

We study a random walk on the integers Z which evolves in a dynamic environment determined by its own trajectory. Sites flip back and forth between two modes, p and q. R consecutive right jumps from a site in the q-mode are required to switch it to the p-mode, and L consecutive left jumps from a site in the p-mode are required to switch it to the q-mode. From a site in the p-mode the walk jumps right with probability p and left with probability (1-p), while from a site in the q-mode these probabilities are q and (1-q). We prove a sharp cutoff for right/left transience of the random walk in terms of an explicit function of the parameters $\alpha = \alpha(p,q,R,L)$. For $\alpha > 1/2$ the walk is transient to $+\infty$ for any initial environment, whereas for $\alpha < 1/2$ the walk is transient to $-\infty$ for any initial environment. In the critical case, $\alpha = 1/2$, the situation is more complicated and the behavior of the walk depends on the initial environment. We are able to give a characterization of transience/recurrence in many instances, including when either R=1 or L=1 and when R=L=2. In the noncritical case, we also show that the walk has positive speed, and in some situations are able to give an explicit formula for this speed. This is joint work with my former post-doc, Nick Travers, now at Indiana University.

Consider a standard branching Brownian motion whose particles have varying mass. At time t, if a total mass m of particles have distance less than one from a fixed particle x, then the mass of particle x decays at rate m. The total mass increases via branching events: on branching, a particle of mass m creates two identical mass-m particles. One may define the front of this system as the point beyond which there is a total mass less than one (or beyond which the expected mass is less than one). This model possesses much less independence than standard BBM. Nonetheless, it is possible to prove that (in a rather weak sense) the front is at distance ~ c t^{1/3} behind the typical BBM front.

In this talk I will review the basic ideas of the regularity structure theory developed by Martin Hairer, as well as its applications to stochastic PDE problems. I will then discuss my joint work with Hairer on the sine-Gordon equation and central limit theorems for stochastic PDEs.

Jigsaw percolation is a nonlocal process that iteratively merges elements of a partition of the vertices in a deterministic puzzle graph according to the connectivity properties of a random collaboration graph. We assume the collaboration graph is an Erdos-Renyi graph with edge probability p, and investigate the probability that the puzzle graph is solved, that is, that the process eventually produces the partition {V}. In some generality, for puzzle graphs with N vertices of degrees about D, this probability is close to 1 or 0 depending on whether pD(log N) is large or small. We give more detailed results for the one dimensional cycle and two dimensional torus puzzle graphs, where in many instances we can prove sharp phase transitions.

We study evolutionary games on the torus with N points in dimensions \(d\ge 3\) with matrices of the form \(\bar G = {\bf 1} + w G\), where 1 is a matrix that consists of all 1's, and w is small. We show that there are three weak selection regimes (i) \(w \gg N^{-2/d}\), (ii) \(N^{-2/d} \gg w \gg N^{-1}\), and (iii) there is a mutation rate \(\mu\) so that \(\mu \gg N^{-1}\) and \(\mu \gg w\) where in the last case we have introduced a mutation rate \(\mu\) to make it nontrivial. In the first and second regimes the rescaled process converges to a PDE and an ODE respectively. In the third, which is the classical weak selection regime of population genetics, we give a new derivation of Tarnita's formula which describes how the equilibrium frequencies are shifted away from uniform due to the spatial structure.

I will present a tutorial on the mathematical models utilized in molecular biology. I will begin with an introduction to the usual stochastic and deterministic models, and then introduce terminology and results from chemical reaction network theory. I will end by presenting the “deficiency zero” theorem in both the deterministic and stochastic settings.

We consider random polynomials whose coefficients are independent and uniform on {-1,1}. We will show that the probability that such a polynomial of degree n has a double root is o(n^{-2}) when n+1 is not divisible by 4 and is of the order n^{-2} otherwise. We will also discuss extensions to random polynomials with more general coefficient distributions. This is joint work with Ron Peled and Ofer Zeitouni.

The sandpile group of a finite graph is an abelian group that is defined using the graph Laplacian. I will describe a natural random walk on this group. The main questions are: what is the mixing time of the sandpile random walk, and how is it affected by the geometry of the underlying graph? These questions can sometimes be answered even if the actual group is unknown. I will present an explicit characterization of the eigenvalues and eigenfunctions of the sandpile walk, and demonstrate an inverse relationship between the spectral gaps of the sandpile walk and the simple random walk on the underlying graph. This is joint work with Lionel Levine and John Pike.

Recently, quantitative stochastic homogenization of operators in divergence form has witnessed important progress. Our goal is to go beyond the error bound to analyze statistical fluctuations around the homogenized limit. We prove a pointwise two-scale expansion and a large scale central limit theorem for the solution. The approach is probabilistic. The main ingredients include the Kipnis-Varadhan method applied to symmetric diffusion in random environment, a quantitative martingale central limit theorem, the Helffer-Sjostrand covariance representation and Stein's method. This is joint work with Jean-Christophe Mourrat.

We will describe and analyze some models of the spread of information on Twitter. The competition between memes fro the limited resource of user attention leads to critical branching processes, and resulting heavy tailed distributions for meme popularity.

In '53, GI Taylor estimated the effective dispersion rate of a solute diffusing in the presence of a laminar flow in a pipe. It turns out that the length scales involved in typical pipes are too short for Taylor's result to apply. The goal of my talk will be to establish a preliminary estimate for the effective dispersion rate in a model problem at time scales much shorter than those required in Taylor's result. Precisely, I will study a diffusive tracer in the presence of a fast cellular flow. The main result (joint with A. Novikov) shows that the variance at intermediate time scales is of order $\sqrt{t}$. This was conjectured by W. Young, and is consistent with an anomalous diffusive behaviour.

Self-exciting point processes are simple point processes that have been widely used in neuroscience, sociology, finance and many other fields. In many contexts, self-exciting point processes can model the complex systems in the real world better than the standard Poisson processes. We will discuss the Hawkes process, the most studied self-exciting point process in the literature. We will talk about the limit theorems and asymptotics in different regimes. Extensions to Hawkes processes and other self-exciting point processes will also be discussed.

In the first part of the talk I will address certain repulsion behavior of roots of random polynomials and of eigenvalues of random matrices. In the second part, some applications of this phenomenon will be presented.

Over the last few years a wide array of random graph models have been postulated to understand properties of empirically observed networks. Most of these models come with a parameter t (usually related to edge density) and a (model dependent) critical time t_c which specifies when a giant component emerges. There is evidence to support that for a wide class of models, under moment conditions, the nature of this emergence is universal and looks like the classical Erdos-Renyi random graph, in the sense of the critical scaling window and (a) the sizes of the components in this window (all maximal component sizes scaling like n^{2/3}) and (b) the structure of components (rescaled by n^{-1/3}) converge to random fractals related to the continuum random tree. Till date, (a) has been proven for a number of models using different techniques while (b) has been proven for only two models, the classical \erdos random graph and the rank-1 inhomogeneous random graph. The aim of this paper is to develop a general program for proving such results. The program requires three main ingredients: (i) in the critical scaling window, components merge approximately like the multiplicative coalescent (ii) scaling exponents of susceptibility functions in the barely subcritical regime are the same as the Erdos-Renyi random graph and (iii) macroscopic averaging of expected distances between random points in the same component in the barely subcritical regime. We show that these apply to a number of fundamental random graph models including the configuration model, inhomogeneous random graphs modulated via a finite kernel and bounded size rules. Thus these models all belong to the domain of attraction of the classical Erdos-Renyi random graph. As a by product we also get the first known results for component sizes at criticality for a general class of inhomogeneous random graphs. This is joint work with Xuan Wang, Sanchayan Sen and Nicolas Broutin.

I will introduce and discuss a canonical notion of Brownian motion in the random geometry of Liouville quantum gravity, called Liouville Brownian motion. I will explain the construction and discuss some of its basic properties, for instance related to its heat kernel and to the time spent in the thick points of the Gaussian Free Field. Time permitting I will also discuss a derivation of the KPZ formula based on the Liouville heat kernel (joint work with C. Garban. R. Rhodes and V. Vargas).

The Ising-Kac model is a variant of the ferromagnetic Ising model in which each spin variable interacts with all spins in a neighbourhood of radius $\ga^{-1}$ for $\ga \ll1$ around its base point. We study the Glauber dynamics for this model on a discrete two-dimensional torus $\Z^2/ (2N+1)\Z^2$, for a system size $N \gg \ga^{-1}$ and for an inverse temperature close to the critical value of the mean field model. We show that the suitably rescaled coarse-grained spin field converges in distribution to the solution of a non-linear stochastic partial differential equation. This equation is the dynamic version of the $\Phi^4_2$ quantum field theory, which is formally given by a reaction diffusion equation driven by an additive space-time white noise. It is well-known that in two spatial dimensions, such equations are distribution valued and a \textit{Wick renormalisation} has to be performed in order to define the non-linear term. Formally, this renormalisation corresponds to adding an infinite mass term to the equation. We show that this need for renormalisation for the limiting equation is reflected in the discrete system by a shift of the critical temperature away from its mean field value. This is a joint work with J.C. Mourrat (Lyon).

How does intrinsic noise from stochastic ion channels affect spontaneous activity in a single neuron? The size of a neuron affects how many ion channels in the membrane facilitate the generation of action potentials. Fewer ion channels causes an increase in the number of spontaneous action potentials. The density of neural tissue is therefore fundamentally limited by spontaneous activity. Evolutionary pressure tends to favor neural tissue with higher density for a variety of reasons, but the increase in spontaneous activity limits how dense it can become and still remain functional. I will talk about how large deviation theory can be used to quantify the relationship between ion channels (type and number) and spontaneous activity.