Current Series

[View Past Series]

Wed Sep 16

Probability Seminar

4:00pm - Via Zoom
Tail bounds for the averaged empirical distribution on a geodesic in first-passage percolation
Wai-Kit Lam, UMN

Consider $\mathbb{Z}^d$ with nearest-neighbor edges. In first-passage percolation, we place i.i.d. nonnegative weights $(t_e)$ on the edges, and study the induced graph metric $T(x,y)$. A geodesic is a minimizing path for this metric. In a joint work with M. Damron, C. Janjigian and X. Shen, we study the empirical distribution on a geodesic $\gamma$ from $0$ to $x$: $\nu^x(B) := (number of edges e in \gamma with t_e \in B) / (number of edges e in \gamma)$. We establish bounds for the averaged empirical distribution $E \nu^x(B)$, particularly showing that if the law of $t_e$ has finite moments of any order strictly larger than 1, then roughly speaking the limiting averaged empirical distribution has all moments.

Wed Sep 23

Probability Seminar

9:00am - Via Zoom
Forest fire processes and near-critical percolation with heavy-tailed impurities
Pierre Nolin, City University of Hong Kong

We discuss models of forest fires (or epidemics): on a given planar lattice, all vertices are initially vacant, and then become occupied at rate 1. If an occupied vertex is hit by lightning, which occurs at a (typically very small) rate, all the vertices connected to it "burn" instantaneously, i.e. they become vacant. We want to analyze the behavior of such processes near and beyond the critical time (the time after which, in the absence of fires, infinite connected components would emerge).

We are led to introduce a percolation model where regions ("impurities") are removed from the lattice, in an independent fashion. These impurities are not only microscopic, but also allowed to be mesoscopic. We are interested in whether the connectivity properties of percolation remain of the same order as without impurities, for values of the percolation parameter close to the critical value. This generalizes a celebrated result by Kesten for near-critical percolation (that can be viewed as critical percolation with single-site impurities).

This talk is based on a joint work with Rob van den Berg (CWI and VU, Amsterdam).

Wed Sep 30

Probability Seminar

4:00pm - Via Zoom
Empirical measures, geodesic lengths, and a variational formula in first-passage percolation
Erik Bates, University of Wisconsin–Madison

We consider the standard first-passage percolation model on Z^d, in which each edge is assigned an i.i.d. nonnegative weight, and the passage time between any two points is the smallest total weight of a nearest-neighbor path between them.  Our primary interest is in the empirical measures of edge-weights observed along geodesics from 0 to ne_1.  For various dense families of edge-weight distributions, we prove that these measures converge weakly to a deterministic limit as n tends to infinity.  The key tool is a new variational formula for the time constant.  In this talk, I will derive this formula and discuss its implications for the convergence of both empirical measures and lengths of geodesics.

Wed Oct 07

Probability Seminar

4:00pm - Via Zoom
The r-to-p norm of non-negative random matrices
Souvik Dhara, MIT

For an n\times n matrix A_n, the r\to p operator norm is defined as \|A_n\|_{r\to p}:= \sup_{x \in R^n:\|x\|_r\leq 1 } \|A_n\|_p for r, p\geq 1. For different choices of r and p, this norm corresponds to key quantities that arise in diverse applications including matrix condition number estimation, clustering of data, and finding oblivious routing schemes in transportation networks. This talk considers r\to p norms of symmetric random matrices with nonnegative entries, including adjacency matrices of  Erdos-Renyi random graphs, matrices with positive sub-Gaussian entries, and certain sparse matrices. For 1< p\leq r< \infty, the asymptotic normality,  as n\to\infty, of the appropriately centered and scaled norm \|A_n\|_{r\to p} is established. Furthermore,  a sharp \ell_\infty-approximation for the unique maximizing vector in the definition of \|A_n\|_{r\to p} is obtained, which may be of independent interest. In fact, the vector approximation result is shown to hold for a broad class of deterministic sequence of matrices having certain asymptotic expansion properties. The results obtained can be viewed as a  generalization of the seminal results of F\"{u}redi and  Koml\'{o}s (1981) on asymptotic normality of the largest singular value of a class of symmetric random matrices, which corresponds to the special case r=p=2 considered here. In the general case with 1< p\leq r < \infty, the spectral methods are no longer applicable, which requires a new approach, involving a refined convergence analysis of a nonlinear power method and establishing a perturbation bound on the maximizing vector.

 This is based on a joint work with Debankur Mukherjee (Georgia Tech) and Kavita Ramanan (Brown University).