Pratima Hebbar, Probability Seminar on October 21, 2021

David Aldous, Probability Seminar Sept 30, 2021 TITLE: Can one prove existence of an infectiousness threshold (for a pandemic) in very general models of disease spread? ABSTRACT: Intuitively, in any kind of disease transmission model with an infectiousness parameter, there should exist a critical value of the parameter separating a very likely from a very unlikely resulting pandemic. But even formulating a general conjecture is challenging. In the most simplistic model (SI) of transmission, one can prove this for an essentially arbitrary large weighted contact network. The proof for SI depends on a simple lemma concerning hitting times for increasing set-valued Markov processes. Can one extend to SIR or SIS models over similarly general networks, where the lemma is no longer applicable?

I will talk about some models coming from Physics and Queueing Theory that give rise to singular reflected processes in their diffusion limit. Such diffusions are characterized by non-elliptic generators (which are not even hypoelliptic) in the interior, and ergodicity arises from non-trivial interactions between the diffusion, drift and reflection. I will introduce a regenerative process approach which identifies renewal times in diffusion paths and analyzes excursions between successive renewal times. This provides a detailed description of the stationary distribution even when closed form expressions are unavailable. Based on joint works with Chris Burdzy, Brendan Brown, Mauricio Duarte and Debankur Mukherjee.

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.

Branching Brownian motion is a classical process in probability theory belonging to the class of “Log-correlated random fields”. We study the structure of extreme level sets of this process, namely the sets of particles whose height is within a fixed distance from the order of the global maximum. It is well known that such particles congregate at large times in clusters of order-one genealogical diameter around local maxima which form a Cox process in the limit. We add to these results by finding the asymptotic size of extreme level sets and the typical height and shape of those clusters which carry such level sets. We also find the right tail decay of the distribution of the distance between the two highest particles. These results confirm two conjectures of Brunet and Derrida.(joint work with A. Cortines, O Louidor)

Data lying in a high dimensional ambient space are commonly thought to have a much lower intrinsic dimension. In particular, the data may be concentrated near a lower-dimensional subspace or manifold. There is an immense literature focused on approximating the unknown subspace and the unknown density, and exploiting such approximations in clustering, data compression, and building of predictive models. Most of the literature relies on approximating subspaces and densities using a locally linear, and potentially multiscale, dictionary with Gaussian kernels. In this talk, we propose a simple and general alternative, which instead uses pieces of spheres, or spherelets, to locally approximate the unknown subspace. I will also introduce a curved kernel called the Fisher–Gaussian (FG) kernel which outperforms multivariate Gaussians in many cases. Theory is developed showing that spherelets can produce lower covering numbers and mean square errors for many manifolds, as well as the posterior consistency of the Dirichlet process mixture of the FG kernels. Time permitting, I will also talk about an ongoing project about stochastic differential geometry.

In r-neighbor bootstrap percolation, the vertices of Z^d are initially occupied independently with probability p and empty otherwise. Occupied vertices remain occupied forever, and empty vertices iteratively become occupied when they have at least r occupied neighbors. It is a classic result of van Enter (r=d=2) and Schonmann (d>2 and r between 2 and d) that every vertex in Z^d eventually becomes occupied for any initial density p>0. In the polluted bootstrap percolation model, vertices of Z^d are initially closed with probability q, occupied with probability p and empty otherwise. The r-neighbor bootstrap rule is the same, but now closed vertices act as obstacles, and remain closed forever. This model was introduced 20 years ago by Gravner and McDonald, who studied the case d=r=2 and proved a phase transition exists for this model as p and q tend to 0. We prove a similar phase transition occurs when d=r=3, and we identify the polynomial scaling between p and q at which this transition occurs for the modified bootstrap percolation model. For one direction, our proof relies on duality methods in Lipschitz percolation to find a blocking structure that prevents occupation of the origin. The other direction follows from a rescaling argument, and the recent results of Holroyd and Gravner for d>r=2. This is joint work with Holroyd and Gravner.

The talk will contain a review of several recent results on the analytic continuation of the random analytic functions. We will start from the classical theorem on the random Taylor series (going to Borel’ s school), but the main subject will be the random zeta – function (which was introduced implicitly by Cramer) and its generalizations. We will show that “true primes are not truly random “, since zeta – functions for the random “pseudo-primes” (in the spirit of Cramer) have no analytic continuation through the critical line Re (z) = 1/2.

Viewed forwards in time, a population reproducing according to some random mechanism can be thought of as a branching process. What if it is viewed backwards? We can take a sample of individuals from the current generation and trace their genealogy backwards, and for instance find their most recent common ancestor; this is known as a coalescent process. If we know a population's random mating process, but have no actual data as to what the phylogenetic tree looks like, how do we derive the distribution of the time until its most recent common ancestor? I will discuss a variant on the classical Wright-Fisher reproductive model and deduce some parameter thresholds for emergence of different qualitative features of the tree. An isomorphic problem may also be useful in computer science for bounding the running time of certain random sampling algorithms.

Consider a connected network and suppose each edge in the network has a random positive edge weight. Understanding the structure and weight of the shortest path between nodes in the network is one of the most fundamental problems studied in modern probability theory and goes under the name first passage percolation. It arises as a fundamental building block in many interacting particle system models such as the spread of epidemics on networks. To a large extent such problems have been only studied in the context of the n-dimensional lattice. In the modern context these problems take on an additional significance with the minimal weight measuring the cost of sending information while the number of edges on the optimal path (hopcount) representing the actual time for messages to get between vertices in the network. Given general models of random graphs with random edge costs, can one develop techniques to analyze asymptotics of functionals of interest which are robust to the model formulation? The aim of this talk is to describe a heuristic based on continuous time branching processes which gives very easily, a wide array of asymptotic results for random network models in terms of the Malthusian rate of growth and the stable age distribution of associated branching process. These techniques allow us to solve not only first passage percolation problems rigorously but also understand functionals such as the degree distribution of shortest path trees, congestion across edges as well as asymptotics for “betweeness centrality” a concept of crucial interest in social networks, in terms of Cox processes and extreme value distributions. These techniques also allow one to exactly solve models of “weak disorder” in the context of the stochastic mean field model of distance, a model of great interest in probabilistic combinatorial optimization.

In this talk I will go over two examples of one-dimensional interacting particle systems: Aldous' up-the-river problem, and a modified Diffusion Limited Growth. I will explain how these systems connect to certain PDE problems with boundaries. For the up-the-river problem this connection helps to solve Aldous’ conjecture regarding an optimal strategy. For the modified DLA, this connection helps to characterize the scaling exponent and scaling limit of the boundary at the critical density. This talk is based on joint work with Amir Dembo and Wenpin Tang.

We investigate an example of noise-induced stabilization in the plane that was also considered in (Gawedzki, Herzog, Wehr 2010) and (Birrell,Herzog, Wehr 2011). We show that despite the deterministic system not being globally stable, the addition of additive noise in the vertical direction leads to a unique invariant probability measure to which the system converges at a uniform, exponential rate. These facts are established primarily through the construction of a Lyapunov function which we generate as the solution to a sequence of Poisson equations. Unlike a number of other works, however, our Lyapunov function is constructed in a systematic way, and we present a meta-algorithm we hope will be applicable to other problems. We conclude by proving positivity properties of the transition density by using Malliavin calculus via some unusually explicit calculations. arXiv:1111.175v1 [math.PR]

The multi-population replicator dynamics (RD) can be considered a dynamic approach to the study of multi-player games, where it was shown to be related to Cross-learning, as well as of systems of co-evolving populations. However, not all of its equilibria are Nash equilibria (NE) of the underlying game, and neither convergence to an NE nor convergence in general are guaranteed. Although interior equilibria are guaranteed to be NE, no interior equilibrium can be asymptotically stable in the multi-population RD, resulting, e.g., in cyclic orbits around a single interior NE. We report on our investigation of a new notion of equilibria of RD, called mutation limits, which is based on the inclusion of a naturally arising, simple form of mutation, but is invariant under the specific choice of mutation parameters. We prove the existence of such mutation limits for a large range of games, and consider an interesting subclass, that of attracting mutation limits. Attracting mutation limits are approximated by asymptotically stable equilibria of the (mutation-)perturbed RD, and hence, offer an approximate dynamic solution of the underlying game, especially if the original dynamic has no asymptotically stable equilibria. Therefore, the presence of mutation will indeed stabilise the system in certain cases and make attracting mutation limits near-attainable. Furthermore, the relevance of attracting mutation limits as a game theoretic equilibrium concept is emphasised by the relation of (mutation-)perturbed RD to the Q-learning algorithm in the context of multi-agent reinforcement learning. However, in contrast to the guaranteed existence of mutation limits, attracting mutation limits do not exist in all games, raising the question of their characterization.

The classical result of Bramson gives a precise logarithmic correction to the speed of front propagation in one dimensional branching random walks and Brownian motions. I will discuss several variants of this model where the slowdown term is not classical.

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

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.

I will discuss a series of results concerning the effect of the derivative operator on the locations of the zeros of a random analytic function. Two models are considered. In the first, the zeros are chosen IID from some measure on the complex plane. In the second, the zeros are chosen to be a Poisson point process on the real line. Repeated differentiation results in a nearly deterministic zero set.

Random Polymers are modeled as a one dimensional random walk (S_n), with excursion length distribution P(S_1 = n) = \phi(n)/n^\alpha, \alpha > 1 and \phi(n) a slowly varying function. The polymer gets a random reward whenever it visits or crosses an interface. The random rewards are realised as a sequence of i.i.d. variables (\omega_n). Depending on the relation between the mean value of the disorder \omega_n and the temperature, the polymer might prefer to stick to the interface (pinnings) or undergo a long excursion away from it (depinning). In this talk we will review some aspects of random polymer models. We will also discuss in more detail the pinning-depinning transition of the `Pinning' model and prove its annealed and quenched critical points are distinct. This is joint work with Ken Alexander.

Consider a Galton-Watson tree. Pick two individuals at random by simple random sampling from the nth generation and trace heir lines of descent back in time till they meet. Call that generation X_n. In this talk we will discuss the probability distribution of X_n and its limits for the four cases m <1, m=1, m greater than 1 but finite, and m infinite, where m is the mean offspring size.

We consider the ferromagnetic Ising model on a sequence of graphs $G_n$ converging locally weakly to a rooted random tree. Generalizing [Montanari, Mossel, and Sly (2012)], under an appropriate “continuity" property, we show that the Ising measures on these graphs converge locally weakly to a measure, which is obtained by first picking a random tree, and then the symmetric mixture of Ising measures with + and - boundary conditions on that tree. Under the extra assumptions that $G_n$ are edge-expanders, we show that the local weak limit of the Ising measures conditioned on positive magnetization, is the Ising measure with + boundary condition on the limiting tree. The “continuity" property holds except possibly for countably many choices of $\beta$, which for limiting trees of minimum degree at least three, are all within certain explicitly specified compact interval. We further show the edge-expander property for (most of) the configuration model graphs corresponding to limiting (multi-type) Galton Watson trees. This talk is based on a joint work with Amir Dembo.

Markov chain methods for Monte Carlo simulation of complex physical or statistical models often require significant tuning. Recent theoretical progress has renewed interest in "adaptive" Markov chain algorithms which learn from their sample history. However, these algorithms produce non-Markovian, time-inhomogeneous, irreversible stochastic processes, making rigorous analysis challenging. We show that lower bounds on the mixing times of these processes can be obtained using familiar ideas of hitting times and conductance from the theory of reversible Markov chains. The bounds obtained are sufficient to demonstrate slow mixing of several recently proposed algorithms including adaptive Metropolis kernels and the equi-energy sampler on some multimodal target distributions. These results provide the first non-trivial bounds on the mixing times of adaptive MCMC samplers, and suggest a way of classifying adaptive schemes that leads to new hybrid algorithms. Many open problems remain.

We consider particle systems that are perturbations of the voter model and show that when space and time are rescaled the system converges to a solution of a reaction diffusion equation in dimensions $d \ge 3$. Combining this result with properties of the PDE and a block construction, we give general, and often asymptotically sharp, conditions for the existence of non-trivial stationary distributions, and for extinction of one type. As applications, we describe the phase diagrams of three systems when the parameters are close to the voter model: (i) a stochastic spatial Lotka-Volterra model of Neuhauser and Pacala, (ii) a model of the evolution of cooperation of Ohtsuki, Hauert, Lieberman, and Nowak, and (iii) a continuous time version of the non-linear voter model of Molofsky, Durrett, Dushoff, Griffeath, and Levin. The first two applications confirm conjectures of Cox and Perkins and Ohtsuki et al.

The now ubiquitous Tracy-Widom laws were first discovered in the context of the Gaussian Orthogonal, Unitary, and Symplectic Ensembles (G{O/U/S}E) of random matrix theory. The latter may be viewed as logarithmic gases with quadratic (Gaussian) potential at three special inverses temperatures (beta=1,2,4). A few years back, Jose Ramirez, Balint Virag, and I showed that that one obtains generalizations of the Tracy-Widom laws at all inverse temperatures (beta>0), though still for quadratic potentials. I'll explain how similar ideas (and considerably more labor) extends the result to general potential, general temperature log-gases. This is joint work with Manjunath Krishnapur and Balint Virag.

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.

In this talk we study the rate of growth of the expectation of the number of holes (the rank of the first homology group) in a polyomino with uniform and percolation distributions. We prove the existence of linear bounds for the expected number of holes of a polyomino with respect to both the uniform and percolation distributions. Furthermore, we exhibit particular constants for the upper and lower bounds in the uniform distribution case. This results can be extend, using the same techniques, to other polyforms and higher dimensions.

In this talk we consider this question for a family of random walks on the square lattice. When the randomness is turned to the maximum, we have the symmetric random walk, which is known to scale to a planar Brownian motion. When the randomness is turned to zero, we have the rotor walk, for which its scaling limit is an open problem. This talk is about random walks that lie in between these two extreme cases and for which we can prove their scaling limit. This is a joint work with Lila Greco, Lionel Levine, and Boyao Li.

This is a joint work with B.Driver. The groups in question are modeled on an abstract Wiener space. Then a group Brownian motion is defined, and its properties are studied in connection with the geometry of this group. The main results include quasi-invariance of the heat kernel measure, log Sobolev inequality (following a bound on the Ricci curvature), and the Taylor isomorphism to the corresponding Fock space. The latter is a version of the Ito-Wiener expansion in the non-commutative setting.

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.

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.

The graph Laplacian has been of interest in statistics, machine learning, and theoretical computer science in areas from manifold learning to analysis of Markov chains. A common uses of the graph Laplacian has been in spectral clustering and dimension reduction. A theoretical motivation for why spectral clustering works is the Cheeger inequality which relates the eigenvalues of the graph Laplacian to how disconnected the graph is, Betti zero for topology. We ask how the Cheeger inequality extends to higher-order Laplacians, operators on simplicial complexes, and what clustering means for these higher-order operators. This is joint work with John Steenbergen Related to the graph Laplacian is the idea of random walks on graphs. We will define a random walk on simplicial complexes with a stationary distribution that is related to the k-dimensional Laplacian. The stationary distribution reveals (co)homology of the geometry of the random walk. We apply this random walk to the problem of semi-supervised learning, given some labeled observations and many unlabeled observations how does one propagate the labels.