Spring 2018

  • Feb 20 @ Penn: Cheyne Homberger (Maryland)

    Permuted Packings and Permutation Breadth

    The breadth of a permutation p is the minimum value of |i - j| + |p(i) - p(j)|, taken over all relevant i and j. Breadth has important consequences to permutation pattern containment, and connections to plane tiling. In this talk we explore the breadth of random permutations using both probabilistic techniques and combinatorial geometry. In particular, we present the expected breadth of a random permutation, the proportion of permutations with a fixed breadth, and a constructive proof for maximizing unique large patterns in permutations. This talk is based on work with both David Bevan and Bridget Tenner and with Simon Blackburn and Pete Winkler.

  • Feb 13 @ Penn: Ewain Gwynne (MIT)

    A mating-of-trees approach for graph distances and random walk on random planar maps

    I will discuss a general strategy for proving estimates for a certain class of random planar maps, namely, those which can be encoded by a two-dimensional walk with i.i.d. increments via a ``mating-of-trees" type bijection. This class includes the uniform infinite planar triangulation (UIPT) and the infinite-volume limits of random planar maps sampled with probability proportional to the number of spanning trees, bipolar orientations, or Schnyder woods they admit.Using this strategy, we obtain non-trivial estimates for graph distances in certain natural non-uniform random planar maps. We also prove that random walk on the UIPT typically travels graph distance $n^{1/4 + o_n(1)}$ in $n$ units of time and that the spectral dimension of a class of random planar maps (including the UIPT) is a.s. equal to 2---i.e., the return probability to the starting point after $n$ steps is $n^{-1+o(1)}$.Our approach proceeds by way of a strong coupling of the encoding walk for the map with a correlated two-dimensional Brownian motion (Zaitsev, 1998), which allows us to compare our given map with the so-called mated-CRT map constructed from this correlated two-dimensional Brownian. The mated-CRT map is closely related to SLE-decorated Liouville quantum gravity due to results of Duplantier, Miller, and Sheffield (2014). So, we can analyze the mated-CRT map using continuum theory and then transfer to other random planar maps via strong coupling. We expect that this approach will have further applications in the future.Based on various joint works with Nina Holden, Tom Hutchcroft, Jason Miller, and Xin Sun.

  • Jan 30 @ Penn: David Burstein (Swarthmore)

    Tools for constructing graphs with fixed degree sequences

    Constructing graphs that resemble their empirically observed counterparts is integral for simulating dynamical processes that occur on networks. Since many real-world networks exhibit degree heterogeneity, we consider some challenges in randomly constructing graphs with a given bi-degree sequence in an unbiased way. In particular, we propose a novel method for the asymptotic enumeration of directed graphs that realize a bi-degree sequence, d, with maximum degree d_max = O(S^{1/2 - tau}) for an arbitrarily small positive number tau, where S is the number of edges; the previous best results allow for d_max = o(S^{1/3} ). Our approach is based on two key steps, graph partitioning and degree preserving switches. The former allows us to relate enumeration results to sequences that are easy to handle, while the latter facilitates expansions based on numbers of shared neighbors of pairs of nodes. We will then discuss the implications of our work in context to other methods, such as Markov Chain Monte Carlo, for generating graphs with a prescribed degree sequence. Joint work with Jonathan Rubin.

  • Jan 16 @ Penn: Jeffrey Kuan (Columbia)

    Algebraic constructions of Markov duality functions

    Markov duality in spin chains and exclusion processes has found a wide variety of applications throughout probability theory. We review the duality of the asymmetric simple exclusion process (ASEP) and its underlying algebraic symmetry. We then explain how the algebraic structure leads to a wide generalization of models with duality, such as higher spin exclusion processes, zero range processes, stochastic vertex models, and their multi-species analogues.

  • Fall 2017

  • Dec 5 @ Penn: Konstantinos Karatapanis (Penn)

    One dimensional system arising in stochastic gradient descent

    We consider SDEs of the form dX_t = |X_t|^k/t^gamma dt+1/t^gamma dB_t, for a fixed k in [1,infty). We find the values of gamma in (1/2,1] such that X_t will not converge to the origin with probability 1. Furthermore, we can show that for the rest of the permissible values the process will converge to the origin with some positive probability. The previous results extend for processes that satisfy dX_t = f(X_t)/t^gamma dt+1/t^gamma dB_t, when f(x) is comparable to |x|^k in a neighborhood of the origin. As it is expected, similar results are true for discrete processes satisfying X_{n+1} - X_n =f(X_n)/n^gamma+Y_{n+1}/n^gamma. Here, Y_{n+1} are martingale differences that are almost surely bounded and satisfy E(Y_{n+1}^2| F_n )>delta>0.

  • Nov 14 @ Penn: Miklos Racz (Princeton)

    How fragile are information cascades?

    It is well known that sequential decision making may lead to information cascades. If the individuals are choosing between a right and a wrong state, and the initial actions are wrong, then the whole cascade will be wrong. We show that if agents occasionally disregard the actions of others and base their action only on their private information, then wrong cascades can be avoided. Moreover, we obtain the optimal asymptotic rate at which the error probability at time t can go to zero. This is joint work with Yuval Peres, Allan Sly, and Izabella Stuhl.

  • Nov 7 @ Temple: Indrajit Jana (Temple)

    Spectrum of Random Band Matrices

    We consider the limiting spectral distribution of matrices of the form $\frac{1}{2b_{n}+1} (R + X)(R + X)^{*}$, where $X$ is an $n\times n$ band matrix of bandwidth $b_{n}$ and $R$ is a non random band matrix of bandwidth $b_{n}$. We show that the Stieltjes transform of ESD of such matrices converges to the Stieltjes transform of a non-random measure. And the limiting Stieltjes transform satisfies an integral equation. For $R=0$, the integral equation yields the Stieltjes transform of the Marchenko-Pastur law.

  • Oct 24 @ Penn: Lisa Hartung (NYU)

    Extreme Level Sets of Branching Brownian Motion

    We study the structure of extreme level sets of a standard one dimensional branching Brownian motion, 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)

  • Oct 17 @ Temple: Atilla Yilmaz (NYU)

    Homogenization of a class of 1-D nonconvex viscous Hamilton-Jacobi equations with random potential

    There are general homogenization results in all dimensions for (inviscid and viscous) Hamilton-Jacobi equations with random Hamiltonians that are convex in the gradient variable. Removing the convexity assumption has proved to be challenging. There was no progress in this direction until two years ago when the 1-D inviscid case was settled positively and several classes of (mostly inviscid) examples for which homogenization holds were constructed as well as a 2-D inviscid counterexample. Methods that were used in the inviscid case are not applicable to the viscous case due to the presence of the diffusion term. In this talk, I will present a new class of 1-D viscous Hamilton-Jacobi equations with nonconvex Hamiltonians for which homogenization holds. Due to the special form of the Hamiltonians, the solutions of these PDEs with linear initial data have representations involving exponential expectations of controlled Brownian motion in random potential. The effective Hamiltonian is the asymptotic rate of growth of these exponential expectations as time goes to infinity and is explicit in terms of the tilted free energy of (uncontrolled) Brownian motion in random potential. The proof relies on (i) analyzing the large deviation behavior of the controlled Brownian particle which assumes the role of one of the players in an emergent two-player game, (ii) identifying asymptotically optimal control policies and (iii) constructing correctors which lead to exponential martingales. Based on recent joint work with Elena Kosygina and Ofer Zeitouni.

  • Oct 10 @ Penn: Sourav Chatterjee (Stanford)

    Rigidity of the 3D hierarchical Coulomb gas

    The mathematical analysis of Coulomb gases, especially in dimensions higher than one, has been the focus of much recent activity. For the 3D Coulomb, there is a famous prediction of Jancovici, Lebowitz and Manificat that if N is the number of particles falling in a given region, then N has fluctuations of order cube-root of E(N). I will talk about the recent proof of this conjecture for a closely related model, known as the 3D hierarchical Coulomb gas. I will also try to explain, through some toy examples, why such unusually small fluctuations may be expected to appear in interacting gases.

  • Oct 3 @ Penn: Stephen Melczer (Penn)

    Lattice Path Enumeration, Multivariate Singularity Analysis, and Probability Theory

    The problem of enumerating lattice paths with a fixed set of allowable steps and restricted endpoint has a long history dating back at least to the 19th century. For several reasons, much research on this topic over the last decade has focused on two dimensional lattice walks restricted to the first quadrant, whose allowable steps are "small" (that is, each step has coordinates +/- 1, or 0). In this talk we relax some of these conditions and discuss recent work on walks in higher dimensions, with non-small steps, or with weighted steps. Particular attention will be given to the asymptotic enumeration of such walks using representations of the generating functions as diagonals of rational functions, through the theory of analytic combinatorics in several variables. Several techniques from computational and experimental mathematics will be highlighted, and open conjectures of a probabilistic nature will be discussed.

  • Sep 26 @ Penn: Evita Nestoridi (Princeton)

    Cutoff for random to random

    Random to random is a card shuffling model that was created to study strong stationary times. Although the mixing time of random to random has been known to be of order n log n since 2002, cutoff had been an open question for many years, and a strong stationary time giving the correct order for the mixing time is still not known. In joint work with Megan Bernstein, we use the eigenvalues of the random to random card shuffling to prove a sharp upper bound for the total variation mixing time. Combined with the lower bound due to Subag, we prove that this walk exhibits cutoff at (3 /4) n log n, answering a conjecture of Diaconis.

  • Sep 19 @ Penn: Marcus Michelen (Penn)

    Invasion Percolation on Galton-Watson Trees

    Given an infinite rooted tree, how might one sample, nearly uniformly, from the set of paths from the root to infinity? A number of methods have been studied including homesick random walks, or determining the growth rate of the number of self-avoiding paths. Another approach is to use percolation. The model of invasion percolation almost surely induces a measure on such paths in Galton-Watson trees, and we prove that this measure is absolutely continuous with respect to the limit uniform measure; other properties of invasion percolation are proved as well. This work in progress is joint with Robin Pemantle and Josh Rosenberg.

  • Sep 12 @ Temple: Nicholas Crawford (Technion)

    Stability of Phases and Interacting Particle Systems

    In this talk, I will discuss recent work with W. de Roeck on the following natural question: Given an interacting particle system are the stationary measures of the dynamics stable to small (extensive) perturbations? In general, there is no reason to believe this is so and one must restrict the class of models under consideration in one way or another. As such, I will focus in this talk on the simplest setting for which one might hope to have a rigorous result: attractive Markov dynamics (without conservation laws) relaxing at an exponential rate to its unique stationary measure in infinite volume. In this case we answer the question affirmatively. As a consequence we show that ferromagnetic Ising Glauber dynamics is stable to small, non-equilibrium perturbations in the entire uniqueness phase of the inverse temperature/external field plane. It is worth highlighting that this application requires new results on the (exponential) rate of relaxation for Glauber dynamics defined with non-zero external field.

  • Sep 5 @ Penn: Allan Sly (Princeton)

    Large Deviations for First Passage Percolation

    We establish a large deviation rate function for the upper tail of first passage percolation answering a question of Kesten who established the lower tail in 1986. Moreover, conditional on the large deviation event, we show that the minimal cost path is delocalized, that is it moves linearly far from the straight line path. Joint work with Riddhipratim Basu (Stanford/ICTS) and Shirshendu Ganguly (UC Berkeley)

  • Spring 2017

  • May 2 @ Penn: Milan Bradonjic (Rutgers)

    Percolation in Weighted Random Connection Model

    When modeling the spread of infectious diseases, it is important to incorporate risk behavior of individuals in a considered population. Not only risk behavior, but also the network structure created by the relationships among these individuals as well as the dynamical rules that convey the spread of the disease are the key elements in predicting and better understanding the spread. We propose the weighted random connection model, where each individual of the population is characterized by two parameters: its position and risk behavior. A goal is to model the effect that the probability of transmissions among individuals increases in the individual risk factors, and decays in their Euclidean distance. Moreover, the model incorporates a combined risk behavior function for every pair of the individuals, through which the spread can be directly modeled or controlled. The main results are conditions for the almost sure existence of an infinite cluster in the weighted random connection model. We use results on the random connection model and site percolation in Z^2.

  • Apr 25 @ Temple: Chris Sinclair (U. Oregon)

    An introduction to p-adic electrostatics

    We consider the distribution of N p-adic particles with interaction energy proportional to the log of the p-adic distance between two particles. When the particles are constrained to the ring of integers of a local field, the distribution of particles is proportional to a power of the p-adic absolute value of the Vandermonde determinant. This leads to a first question: What is the normalization constant necessary to make this a probability measure? This sounds like a triviality, but this normalization constant as a function of extrinsic variables (like number of particles, or temperature) holds much information about the statistics of the particles. Viewed another way, this normalization constant is a p-adic analog of the now famous Selberg integral. While a closed form for this seems out of reach, I will derive a remarkable identity that may hold the key to unlocking more nuanced information about p-adic electrostatics. Along the way we’ll find an identity for the generating function of probabilities that a degree N polynomial with p-adic integer coefficients split completely. Joint work with Jeff Vaaler.

  • Apr 11 @ Penn: Patrick Devlin (Rutgers)

    Biased random permutations are predictable (proof of an entropy conjecture of Leighton and Moitra)

    Suppose F is a random (not necessarily uniform) permutation of {1, 2, ... , n} such that |Prob(F(i) < F(j)) -1/2| > epsilon for all i,j. We show that under this assumption, the entropy of F is at most (1-delta)log(n!), for some fixed delta depending only on epsilon [proving a conjecture of Leighton and Moitra]. In other words, if (for every distinct i,j) our random permutation either noticeably prefers F(i) < F(j) or prefers F(i) > F(j), then the distribution inherently carries significantly less uncertainty (or information) than the uniform distribution. Our proof relies on a version of the regularity lemma, a combinatorial bookkeeping gadget, and a few basic probabilistic ideas. The talk should be accessible for any background, and we will gently recall any relevant notions (e.g., entropy) as needed. Those unhappy with the talk are welcome to form an unruly mob to depose the speaker, and pitchforks and torches will be available for purchase. This is from a recent paper joint with Huseyin Acan and Jeff Kahn.

  • Apr 4 @ Penn: Tobias Johnson (NYU)

    Galton-Watson fixed points, tree automata, and interpretations

    Consider a set of trees such that a tree belongs to the set if and only if at least two of its root child subtrees do. One example is the set of trees that contain an infinite binary tree starting at the root. Another example is the empty set. Are there any other sets satisfying this property other than trivial modifications of these? I'll demonstrate that the answer is no, in the sense that any other such set of trees differs from one of these by a negligible set under a Galton-Watson measure on trees, resolving an open question of Joel Spencer's. This follows from a theorem that allows us to answer questions of this sort in general. All of this is part of a bigger project to understand the logic of Galton-Watson trees, which I'll tell you more about. Joint work with Moumanti Podder and Fiona Skerman.

  • Mar 28 @ Temple: Arnab Sen (Minnesota)

    Majority dynamics on the infinite 3-regular tree

    The majority dynamics on the infinite 3-regular tree can be described as follows. Each vertex of the tree has an i.i.d. Poisson clock attached to it, and when the clock of a vertex rings, the vertex looks at the spins of its three neighbors and flips its spin, if necessary, to come into agreement with majority of its neighbors. The initial spins of the vertices are taken to be i.i.d. Bernoulli random variables with parameter p. In this talk, we will discuss a couple of new results regarding this model. In particular, we will show that the limiting proportion of ‘plus’ spins in the tree is continuous with respect to the initial bias p. A key tool in our argument is the mass transport principle. The talk is based on an ongoing work with M. Damron.

  • Mar 21 @ Temple: Paul Bourgade (Courant)

    Local extrema of random matrices and the Riemann zeta function

    Fyodorov, Hiary & Keating have conjectured that the maximum of the characteristic polynomial of random unitary matrices behaves like extremes of log-correlated Gaussian fields. This allowed them to conjecture the typical size of local maxima of the Riemann zeta function along the critical axis. I will first explain the origins of this conjecture, and then outline the proof for the leading order of the maximum, for unitary matrices and the zeta function. This talk is based on a joint works with Arguin, Belius, Radziwill and Soundararajan.

  • Feb 28 @ Temple: James Melbourne (Delaware)

    Bounds on the maximum of the density for certain linear images of independent random variables

    We will present a generalization of a theorem of Rogozin that identifies uniform distributions as extremizers of a class of inequalities, and show how the result can reduce specific random variables questions to geometric ones. In particular, by extending "cube slicing" results of K. Ball, we achieve a unification and sharpening of recent bounds on densities achieved as projections of product measures due to Rudelson and Vershynin, and the bounds on sums of independent random variable due to Bobkov and Chistyakov. Time permitting we will also discuss connections with generalizations of the entropy power inequality.

  • Feb 21 @ Penn: Shirshendu Ganguly (Berkeley)

    Large deviation and counting problems in sparse settings

    The upper tail problem in the Erd ?os-R Ženyi random graph G ~ Gn,p, where every edge is included independently with probability p, is to estimate the probability that the number of copies of a graph H in G exceeds its expectation by a factor 1 + d. The arithmetic analog considers the count of arithmetic progressions in a random subset of Z/nZ, where every element is included independently with probability p. In this talk, I will describe some recent results regarding the solution of the upper tail problem in the sparse setting i.e. where p decays to zero, as n grows to infinity. The solution relies on non-linear large deviation principles developed by Chatterjee and Dembo and more recently by Eldan and solutions to various extremal problems in additive combinatorics.

  • Feb 14 @ Temple: Mihai Nica (NYU)

    Intermediate disorder limits for multi-layer random polymers

    The intermediate disorder regime is a scaling limit for disordered systems where the inverse temperature is critically scaled to zero as the size of the system grows to infinity. For a random polymer given by a single random walk, Alberts, Khanin and Quastel proved that under intermediate disorder scaling the polymer partition function converges to the solution to the stochastic heat equation with multiplicative white noise. In this talk, I consider polymers made up of multiple non-intersecting walkers and consider the same type of limit. The limiting object now is the multi-layer extension of the stochastic heat equation introduced by O'Connell and Warren. This result proves a conjecture about the KPZ line ensemble. Part of this talk is based on joint work with I. Corwin.

  • Feb 07 @ Temple: Fabrice Baudoin (U. Conn)

    Stochastic areas and Hopf fibrations

    We define and study stochastic areas processes associated with Brownian motions on the complex symmetric spaces ℂℙn and ℂℍn. The characteristic functions of those processes are computed and limit theorems are obtained. For ℂℙn the geometry of the Hopf fibration plays a central role, whereas for ℂℍn it is the anti-de Sitter fibration. This is joint work with Jing Wang (UIUC)

  • Jan 31 @ Penn: Nina Holden (MIT)

    How round are the complementary components of planar Brownian motion?

    Consider a Brownian motion W in the complex plane started from 0 and run for time 1. Let A(1), A(2),... denote the bounded connected components of C-W([0,1]). Let R(i) (resp.\ r(i)) denote the out-radius (resp.\ in-radius) of A(i) for i \in N. Our main result is that E[\sum_i R(i)^2|\log R(i)|^\theta ]<\infty for any \theta <1. We also prove that \sum_i r(i)^2|\log r(i)|=\infty almost surely. These results have the interpretation that most of the components A(i) have a rather regular or round shape. Based on joint work with Serban Nacu, Yuval Peres, and Thomas S. Salisbury.

  • Jan 24 @ Penn: Charles Burnette(Drexel University)

    Abelian Squares and Their Progenies

    A polynomial P ∈ C[z1, . . . , zd] is strongly Dd-stable if P has no zeroes in the closed unit polydisc D d . For such a polynomial define its spectral density function as SP (z) = P(z)P(1/z) −1 . An abelian square is a finite string of the form ww0 where w0 is a rearrangement of w. We examine a polynomial-valued operator whose spectral density function’s Fourier coefficients are all generating functions for combinatorial classes of con- strained finite strings over an alphabet of d characters. These classes generalize the notion of an abelian square, and their associated generating functions are the Fourier coefficients of one, and essentially only one, L2 (T d)-valued oper- ator. Integral representations and asymptotic behavior of the coefficients of these generating functions and a combinatorial meaning to Parseval’s equation are given as consequences.

  • Fall 2016

  • Dec 06 @ Penn: Hao Shen (Columbia)

    Some new scaling limit results on ASEP and Glauber dynamics of spin models

    We discuss two scaling limit results for discrete models converging to stochastic PDEs. The first is the asymmetric simple exclusion process in contact with sources and sinks at boundaries, called Open ASEP. We prove that under weakly asymmetric scaling the height function converges to the KPZ equation with Neumann boundary conditions. The second is the Glauber dynamics of the Blume-Capel model (a generalization of Ising model), in two dimensions with Kac potential. We prove that the averaged spin field converges to the stochastic quantization equations. A common challenge in the proofs is how to identify the limiting process as the solution to the SPDE, and we will discuss how to overcome the difficulties in the two cases. (Based on joint works with Ivan Corwin and Hendrik Weber)

  • Nov 29 @ Temple: Jack Hanson (CUNY)

    Arm events in invasion percolation

    Invasion percolation is a "self-organized critical" distribution on random subgraphs of Z^2, believed to exhibit much of the same behavior as critical percolation models. Self-organization means that this happens spontaneously without tuning some parameter to a critical value. In two dimensions, some aspects of the invasion graph are known to correspond to those in critical models, and some differences are known. We will discuss new results on the probabilities of various "arm events" -- events that connections from the origin to a large distance n are either present or "closed" in the invasion graph. We show that some of these events have probabilities obeying power laws with the same power as in the critical model, while all others differ from the critical model's by a power of n.

  • Nov 15 @ Penn: Elliot Paquette (Ohio State)

    The law of fractional logarithm in the GUE minor process

    Consider an infinite array of standard complex normal variables which are independent up to Hermitian symmetry. The eigenvalues of the upper-left NxN submatrices, form what is called the GUE minor process. This largest-eigenvalue process is a canonical example of the Airy process which is connected to many other growth processes. We show that if one lets N vary over all natural numbers, then the sequence of largest eigenvalues satisfies a 'law of fractional logarithm,' in analogy with the classical law of iterated logarithm for simple random walk. This GUE minor process is determinantal, and our proof relies on this. However, we reduce the problem to correlation and decorrelation estimates that must be made about the largest eigenvalues of pairs of GUE matrices, which we hope is useful for other similar problems.

  • Nov 08 @ Penn: Sébastien Bubeck (Microsoft)

    Local max-cut in smoothed polynomial time

    The local max-cut problem asks to find a partition of the vertices in a weighted graph such that the cut weight cannot be improved by moving a single vertex (that is the partition is locally optimal). This comes up naturally, for example, in computing Nash equilibrium for the party affiliation game. It is well-known that the natural local search algorithm for this problem might take exponential time to reach a locally optimal solution. We show that adding a little bit of noise to the weights tames this exponential into a polynomial. In particular we show that local max-cut is in smoothed polynomial time (this improves the recent quasi-polynomial result of Etscheid and Roglin). Joint work with Omer Angel, Yuval Peres, and Fan Wei.

  • Nov 01 @ Penn: Henry Towsner (Penn)

    Markov Chains of Exchangeable Structures

    The Aldous--Hoover Theorem characterizes arrays of random variables which are exchangeable - that is, the distribution is invariant under permutations of the indices of the array. We consider the extension to exchangeable Markov chains. In order to give a satisfactory classification, we need an extension of the Adous--Hoover Theorem to "relatively exchangeable" arrays, which are only invariant under some permutations. Different families of permutations lead to different characterization theorems, with the crucial distinction coming from a model theoretic characterization of the way finite arrays can be amalgamated.

  • Oct 25 @ Penn: Alexey Bufetov (MIT)

    Asymptotics of stochastic particle systems via Schur generating functions

    We will discuss a new approach to the analysis of the global behavior of stochastic discrete particle systems. This approach links the asymptotics of these systems with properties of certain observables related to the Schur symmetric functions. As applications of this method, we prove the Law of Large Numbers and the Central Limit Theorem for various models of random lozenge and domino tilings, non-intersecting random walks, and decompositions of tensor products of representations of unitary groups. Based on joint works with V. Gorin and A. Knizel.

  • Oct 18 @ Penn: Sanchayan Sen (Eindhoven)

    Random discrete structures: Scaling limits and universality

    One major conjecture in probabilistic combinatorics, formulated by statistical physicists using non-rigorous arguments and enormous simulations in the early 2000s, is as follows: for a wide array of random graph models on n vertices and degree exponent \tau>3, typical distance both within maximal components in the critical regime as well as on the minimal spanning tree on the giant component in the supercritical regime scale like n^{\frac{\tau\wedge 4 -3}{\tau\wedge 4 -1}}. In other words, the degree exponent determines the universality class the random graph belongs to. More generally, recent research has provided strong evidence to believe that several objects constructed on a wide class of random discrete structures including (a) components under critical percolation, (b) the vacant set left by a random walk, and (c) the minimal spanning tree, viewed as metric measure spaces converge, after scaling the graph distance, to some random fractals, and these limiting objects are universal under some general assumptions. We report on recent progress in proving these conjectures. Based on joint work with Shankar Bhamidi, Nicolas Broutin, Remco van der Hofstad, and Xuan Wang.

  • Oct 11 @ Penn: Louigi Addario-Berry (McGill)

    The front location for branching Brownian motion with decay of mass

    I will describe joint work with Sarah Penington (Oxford). 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, and martingales are hard to come by. 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. At a high level, our argument for this may be described as a proof by contradiction combined with fine estimates on the probability Brownian motion stays in a narrow tube of varying width.

  • Oct 04 @ Temple: Ramon van Handel (Princeton)

    Chaining, interpolation, and convexity

    A significant achievement of modern probability theory is the development of sharp connections between the boundedness of random processes and the geometry of the underlying index set. In particular, the generic chaining method of Talagrand provides in principle a sharp understanding of the suprema of Gaussian processes. The multiscale geometric structure that arises in this method is however notoriously difficult to control in any given situation. In this talk, I will exhibit a surprisingly simple but very general geometric construction, inspired by real interpolation of Banach spaces, that is readily amenable to explicit computations and that explains the behavior of Gaussian processes in various interesting situations where classical entropy methods are known to fail.

  • Sep 27 @ Penn: Amanda Lohss (Drexel)

    Corners in Tree-Like Tableaux.

    Tree–like tableaux are combinatorial objects which exhibit a natural tree structure and are connected to the partially asymmetric simple exclusion process (PASEP). There was a conjecture made on the total number of corners in tree–like tableaux and the total number of corners in symmetric tree–like tableaux. We have proven both conjectures based on a bijection with permutation tableaux and type–B permutation tableaux. In addition, we have shown that the number of diagonal boxes in symmetric tree–like tableaux is asymptotically normal and that the number of occupied corners in a random tree–like tableau is asymptotically Poisson. This extends earlier results of Aval, Boussicault, Nadeau, and Laborde Zubieta, respectively.

  • Sep 20 @ Temple: Wei Wu (NYU)

    Loop erased random walk, uniform spanning tree and bi-Laplacian Gaussian field in the critical dimension.

    Critical lattice models are believed to converge to a free field in the scaling limit, at or above their critical dimension. This has been (partially) established for Ising and $\Phi^4$ models for $d \geq 4$. We describe a simple spin model from uniform spanning forests in $\mathbb{Z}^d$ whose critical dimension is 4 and prove that the scaling limit is the bi-Laplacian Gaussian field for $d\ge 4$. At dimension 4, there is a logarithmic correction for the spin-spin correlation and the bi-Laplacian Gaussian field is a log correlated field. The proof also improves the known mean field picture of LERW in $d=4$, by showing that the renormalized escape probability (and arm events) of 4D LERW converge to some "continuum escaping probability". Based on joint works with Greg Lawler and Xin Sun.

  • Sep 13 @ Penn: Yuri Kifer (Hebrew University)

    An Introduction to Limit Theorems for Nonconventional Sums

    I'll survey some of the series results on limit theorems for nonconventional sums of the form \[ \sum_{n=1}^NF(X_n,X_{2n},...,X_{\ell n}) \] and more general ones, where $\{ X_n\}$ is a sequence of random variables with sufficiently weak dependence.

  • Sep 06 @ Penn: Jian Ding (Chicago)

    Random planar metrics of Gaussian free fields

    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.

  • Spring 2016

  • May 05 @ Penn: Oren Louidor (Technion)

    Aging in a logarithmically correlated potential

    We consider a continuous time random walk on the box of side length N in Z^2, whose transition rates are governed by the discrete Gaussian free field h on the box with zero boundary conditions, acting as potential: At inverse temperature \beta, when at site x the walk waits an exponential time with mean \exp(\beta h_x) and then jumps to one of its neighbors chosen uniformly at random. This process can be used to model a diffusive particle in a random potential with logarithmic correlations or alternatively as Glauber dynamics for a spin-glass system with logarithmically correlated energy levels. We show that at any sub-critical temperature and at pre-equilibrium time scales, the walk exhibits aging. More precisely, for any \theta > 0 and suitable sequence of times (t_N), the probability that the walk at time t_N(1+\theta) is within O(1) of where it was at time t_N tends to a non-trivial constant as N \to \infty, whose value can be expressed in terms of the distribution function of the generalized arcsine law. This puts this process in the same aging universality class as many other spin-glass models, e.g. the random energy model. Joint work with Aser Cortines-Peixoto and Adela Svejda.

  • Apr 26 @ Penn: Josh Rosenberg (Penn)

    The frog model with drift on R

    This paper considers the following scenario. There is a Poisson process on R with intensity f where 0 \le f(x) \le infty for x \ge 0 and f(x)=0 for x \le 0. The "points" of the process represent sleeping frogs. In addition, there is one active frog initially located at the origin. At time t=0 this frog begins performing Brownian motion with leftward drift C (i.e. its motion is a random process of the form B_t-Ct). Any time an active frog arrives at a point where a sleeping frog is residing, the sleeping frog becomes active and begins performing Brownian motion with leftward drift C, that is independent of the motion of all of the other active frogs. This paper establishes sharp conditions on the intensity function f that determine whether the model is transient (meaning the probability that infinitely many frogs return to the origin is 0), or non-transient (meaning this probability is greater than 0).

  • Apr 19 @ Penn: Dan Jerison (Cornell)

    Markov chain convergence via regeneration

    How long does it take for a reversible Markov chain to converge to its stationary distribution? This talk discusses how to get explicit upper bounds on the time to stationarity by identifying a regenerative structure of the chain. I will demonstrate the flexibility of this approach by applying it in two very different cases: Markov chain Monte Carlo estimation on general state spaces, and finite birth and death chains. In the first case, an unusual perspective on the popular ``drift and minorization'' method leads to a simple bound that improves on existing convergence results. In the second case, a hidden connection between reversibility and monotonicity recovers sharp upper bounds on the cutoff window.

  • Apr 12 @ Penn: Zsolt Pajor-Gyulai (Courant)

    Stochastic approach to anomalous diffusion in two dimensional, incompressible, periodic, cellular flows

    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 molecular 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 a time-changed Brownian motions. This shows that while the trajectories are still diffusive, the variance grows differently than linear.

  • Apr 05 @ Penn: Boris Hanin (MIT)

    Nodal Sets of Random Eigenfunctions of the Harmonic Oscillator

    Random eigenfunctions of energy E for the isotropic harmonic oscillator in R^d have a U(d) symmetry and are in some ways analogous to random spherical harmonics of fixed degree on S^d, whose nodal sets have been the subject of many recent studies. However, there is a fundamentally new aspect to this ensemble, namely the existence of allowed and forbidden regions. In the allowed region, the Hermite functions behave like spherical harmonics, while in the forbidden region, Hermite functions are exponentially decaying and it is unclear to what extent they oscillate and have zeros.
    The purpose of this talk is to present several results about the expected volume of the zero set of a random Hermite function in both the allowed and forbidden regions as well as in a shrinking tube around the caustic. The results are based on an explicit formula for the scaling limit around the caustic of the fixed energy spectral projector for the isotropic harmonic oscillator. This is joint work with Steve Zelditch and Peng Zhou.

  • Mar 29 @ Penn: John Pike (Cornell)

    Random walks on abelian sandpiles

    Given a simple connected graph $G=(V,E)$, the abelian sandpile Markov chain evolves by adding chips to random vertices and then stabilizing according to certain toppling rules. The recurrent states form an abelian group $\Gamma$, the sandpile group of $G$. I will discuss joint work with Dan Jerison and Lionel Levine in which we characterize the eigenvalues and eigenfunctions of the chain restricted to $\Gamma$ in terms of ``multiplicative harmonic functions'' on $V$. We show that the moduli of the eigenvalues are determined up to a constant factor by the lengths of vectors in an appropriate dual Laplacian lattice and use this observation to bound the mixing time of the sandpile chain in terms of the number of vertices and maximum vertex degree of $G$. We also derive a surprising inverse relationship between the spectral gap of the sandpile chain and that of simple random walk on $G$.

  • Mar 22 @ Temple: Christian Benes (CUNY)

    The scaling limit of the loop-erased random walk Green's function

    We show that the probability that a planar loop-erased random walk passes through a given edge in the interior of a lattice approximation of a simply connected domain converges, as the lattice spacing goes to zero, to a multiple of the SLE(2) Green's function. This is joint work with Greg Lawler and Fredrik Viklund.

  • Mar 15 @ Temple: Philippe Sosoe (Harvard)

    The chemical distance in critical percolation

    The chemical distance is the graph distance inside percolation clusters. In the supercritical phase, this distance is known to be linear with exponential probability, enabling a detailed study of processes like random walks on the infinite cluster. By contrast, at the critical point, the distance is known to be longer than Euclidean by some (unknown) power. I will discuss this and some bounds on distance, as well as a result comparing the chemical distance to the size of the lowest crossing. Joint work with Jack Hanson and Michael Damron.

  • Mar 01 @ Penn: Sumit Mukherjee (Columbia)

    Mean field Ising models

    In this talk we consider the asymptotics of the log partition function of an Ising model on a sequence of finite but growing graphs/matrices. We give a sufficient condition for the mean field prediction to the log partition function to be asymptotically tight, which in particular covers all regular graphs with degree going to infinity. We show via several examples that our condition is "almost necessary" as well. As application of our result, we derive the asymptotics of the log partition function for approximately regular graphs, and bi-regular bi-partite graphs. We also re-derive asymptotics of the log partition function for a sequence of graphs convering in cut metric. This is joint work with Anirban Basak from Duke University.

  • Feb 16 @ Temple: Yuri Bakhtin (Courant)

    Burgers equation with random forcing

    I will talk about the ergodic theory of randomly forced Burgers equation (a basic nonlinear evolution PDE related to fluid dynamics and growth models) in the noncompact setting. The basic objects are one-sided infinite minimizers of random action (in the inviscid case) and polymer measures on one-sided infinite trajectories (in the positive viscosity case). Joint work with Eric Cator, Kostya Khanin, Liying Li.

  • Feb 09 @ Penn: Nayantara Bhatnagar (Delaware)

    Limit Theorems for Monotone Subsequences in Mallows Permutations

    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 and LDS of random permutations drawn from the Mallows measure, introduced by Mallows in connection with ranking problems in statistics. Under this measure, the probability of a permutation p in S_n is proportional to q^Inv(p) where q is a real parameter and Inv(p) is the number of inversions in p. We determine the typical order of magnitude of the LIS and LDS, large deviation bounds for these lengths and a law of large numbers for the LIS for various regimes of the parameter q. In the regime that q is constant, we make use of the regenerative structure of the permutation to prove a Gaussian CLT for the LIS. This is based on joint work with Ron Peled and with Riddhi Basu.

  • Feb 02 @ Penn: Erik Slivken (UC Davis)

    Bootstrap Percolation on the Hamming Torus

    Bootstrap percolation on a graph is a simple to describe yet hard to analyze process on a graph. It begins with some initial configuration (open or closed) on the vertices. At each subsequent step a vertex may change from closed to open if enough of its neighbors are already open. For a random initial configuration where each vertex is open independently with probability p, how does the probability that eventually every vertex will be open change as p varies? The large neighborhood size of the Hamming torus leads to a distinctly different flavor than previous results on the grid and hypercube. We will focus on Hamming tori with high dimension, giving a detailed description of the long term behavior of the process.

  • Jan 26 @ Penn: Vadim Gorin (MIT)

    Largest eigenvalues in random matrix beta-ensembles: structures of the limit

    Despite numerous articles devoted to its study, the universal scaling limit for the largest eigenvalues in general beta log-gases remains a mysterious object. I will present two new approaches to such edge scaling limits. The outcomes include a novel scaling limit for the differences between largest eigenvalues in submatrices and a Feynman-Kac type formula for the semigroup spanned by the Stochastic Airy Operator. (based on joint work with M.Shkolnikov)

  • Fall 2015

  • Dec 01 @ Penn: Sivak Mkrtchyan (Rochester)

    The entropy of Schur-Weyl measures

    We will study local and global statistical properties of Young diagrams with respect to a Plancherel-type family of measures called Schur-Weyl measures and use the results to answer a question from asymptotic representation theory. More precisely, we will solve a variational problem to prove a limit-shape result for random Young diagrams with respect to the Schur-Weyl measures and apply the results to obtain logarithmic, order-sharp bounds for the dimensions of certain representations of finite symmetric groups.

  • Nov 17 @ Penn: Partha Dey (UIUC)

    Longest increasing path within the critical strip

    Consider a Poisson Point Process of intensity one in the two-dimensional square of side length $n$. In Baik-Deift-Johansson (1999), it was shown that the length of a longest increasing path (an increasing path that contains the most number of points) when properly centered and scaled converges to the Tracy-Widom distribution. Later Johansson (2000) showed that all maximal paths lie within the strip of width $n^{2/3+o(1)}$ around the diagonal with high probability. We consider the length $L(n,w)$ of longest increasing paths restricted to lie within a strip of width $w$ around the diagonal and show that when properly centered and scaled it converges to a Gaussian distribution whenever $w \ll n^{2/3}$. We also obtain tight bounds on the expectation and variance of $L(n,w)$ which involves application of BK inequality and approximation of the optimal restricted path by locally optimal unrestricted path. Based on joint work with Matthew Joseph and Ron Peled.

  • Nov 10 @ Penn: Charles Bordenave (Toulouse)

    A new proof of Friedman’s second eigenvalue Theorem and its extensions

    It was conjectured by Alon and proved by Friedman that a random d-regular graph has nearly the largest possible spectral gap, more precisely, the largest absolute value of the non-trivial eigenvalues of its adjacency matrix is at most 2 √ ( d − 1) + o(1) with probability tending to one as the size of the graph tends to infinity. We will discuss a new method to prove this statement and give some extensions to random lifts and related models.

  • Nov 03 @ Penn: Christian Gromoll (UVA)

    Fluid limits and queueing policies

    There are many different queueing policies discussed in the literature. They tend to be defined in model-specific ways that differ in format from one policy to another, each format suitable for the task at hand (e.g. steady-state derivation, scaling-limit theorem, or proof of some other property). The ad hoc nature of the policy definition often limits the scope of potentially quite general arguments. Moreover, because policies are defined variously, it's difficult to approach classification questions for which the answer presumably spans many policies. In this talk I'll propose a definition of a general queueing policy and discuss exactly what I mean by "general". The setup makes it possible to frame questions about queues in terms of an arbitrary policy and, potentially, to classify policies according to the answer. In this vein, I'll discuss a few results and some ongoing work on proving fluid limit theorems for general policies.

  • Oct 27 @ Penn: Doug Rizzolo (U Delaware)

    Random pattern-avoiding permutations

    Abstract: In this talk we will discuss recent results on the structure of random pattern-avoiding permutations. We will focus a surprising connection between random permutations avoiding a fixed pattern of length three and Brownian excursion. For example, this connection lets us describe the shape of the graph of a random 231-avoiding permutation of {1,...,n} as n tends to infinity as well as the asymptotic distribution of fixed points in terms of Brownian excursion. Time permitting, we will discuss work in progress on permutations avoiding longer patterns. This talk is based on joint work with Christopher Hoffman and Erik Slivken.

  • Oct 20 @ Penn: Tai Melcher (UVA)

    Smooth measures in infinite dimensions

    A collection of vector fields on a manifold satisfies H\"{o}rmander's condition if any two points can be connected by a path whose tangent vectors lie in the given collection. It is well known that a diffusion which is allowed to travel only in these directions is smooth, in the sense that its transition probability measure is absolutely continuous with respect to the volume measure and has a strictly positive smooth density. Smoothness results of this kind in infinite dimensions are typically not known, the first obstruction being the lack of an infinite-dimensional volume measure. We will discuss some smoothness results for diffusions in a particular class of infinite-dimensional spaces. This is based on joint work with Fabrice Baudoin, Daniel Dobbs, Bruce Driver, Nate Eldredge, and Masha Gordina.

  • Oct 06 @ Penn: Leonid Petrov (UVA)

    Bethe Ansatz and interacting particle systems

    I will describe recent advances in bringing a circle of ideas and techniques around Bethe ansatz and Yang–Baxter relation under the probabilistic roof, which provides new examples of stochastic interacting particle systems, and techniques to solve them. In particular, I plan to discuss a new particle dynamics in continuous inhomogeneous medium with features resembling traffic models, as well as queuing systems. This system has phase transitions (discontinuities in the limit shape) and Tracy-Widom fluctuations (even at the point of the phase transition).

  • Sep 29 @ Temple: David Belius (Courant)

    Branching in log-correlated random fields

    This talk will discuss how log-correlated random fields show up in diverse settings, including the study of cover times and random matrix theory. This is explained by the presence of an underlying approximate branching structure in each of the models. I will describe the most basic model of the log-correlated class, namely Branching Random Walk (BRW), where the branching structure is explicit, and explain how to adapt ideas developed in the context of BRW to models where the branching structure is not immediately obvious.

  • Sep 24 @ Penn: Steven Heilman (UCLA)

    Strong Contraction and Influences in Tail Spaces

    We study contraction under a Markov semi-group and influence bounds for functions all of whose low level Fourier coefficients vanish. This study is motivated by the explicit construction of 3-regular expander graphs of Mendel and Naor, though our results have no direct implication for the construction of expander graphs. In the positive direction we prove an L_{p} Poincar\'{e} inequality and moment decay estimates for mean 0 functions and for all 1 \less p \less \infty, proving the degree one case of a conjecture of Mendel and Naor as well as the general degree case of the conjecture when restricted to Boolean functions. In the negative direction, we answer negatively two questions of Hatami and Kalai concerning extensions of the Kahn-Kalai-Linial and Harper Theorems to tail spaces. For example, we construct a function $f\colon\{-1,1\}^{n}\to\{-1,1\}$ whose Fourier coefficients vanish up to level $c \log n$, with all influences bounded by $C \log n/n$ for some constants $0\lessc,C\less \infty$. That is, the Kahn-Kalai-Linial Theorem cannot be improved, even if we assume that the first $c\log n$ Fourier coefficients of the function vanish. This implies there is a phase transition in the largest guaranteed influence of functions $f\colon\{-1,1\}^{n}\to\{-1,1\}$, which occurs when the first $g(n)\log n$ Fourier coefficients vanish and $g(n)\to\infty$ as $n\to\infty$ or $g(n)$ is bounded as $n\to\infty$.. joint with Elchanan Mossel and Krzysztof Oleszkiewicz

  • Sep 15 @ Penn: Toby Johnson (USC)

    The frog model on trees

    Imagine that every vertex of a graph contains a sleeping frog. At time 0, the frog at some designated vertex wakes up and begins a simple random walk. When it lands on a vertex, the sleeping frog there wakes up and begins its own simple random walk, which in turn wakes up any sleeping frogs it lands on, and so on. This process is called the frog model. I'll (mostly) answer a question posed by Serguei Popov in 2003: On an infinite d-ary tree, is the frog model recurrent or transient? That is, is each vertex visited infinitely or finitely often by frogs? The answer is that it depends on d: there's a phase transition between recurrence and transience as d grows. Furthermore, if the system starts with Poi(m) sleeping frogs on each vertex independently, for any d there's a phase transition as m grows. This is joint work with Christopher Hoffman and Matthew Junge.

  • Sep 08 @ Penn: Matt Junge (U. Washington)

    Splitting hairs (with choice)

    Sequentially place n balls into n bins. For each ball, two bins are sampled uniformly and the ball is placed in the emptier of the two. Computer scientists like that this does a much better job of evenly distributing the balls than the "choiceless" version where one places each ball uniformly. Consider the continuous version: Form a random sequence in the unit interval by having the nth term be whichever of two uniformly placed points falls in the larger gap between the previous n-1 points. We confirm the intuition that this sequence is a.s. equidistributed, resolving a conjecture from Itai Benjamini, Pascal Maillard and Elliot Paquette. The history goes back a century to Weyl and more recently to Kakutani.