Tuesdays, 2:00 PM - 3:00 PM , 939 Evans

The convergence of Galton-Watson trees to a continuous object called the Brownian random tree (or Aldous continuum random tree) can be formalized in multiple ways. We first review the method of encoding trees via random walks and height functions, as discussed by Sourav in a previous session. A different method uses objects called real trees to discuss convergence of the trees directly, without reference to auxiliary encodings. We discuss this formalism and give a feeling for how it works.

Reference: "Random Trees and Applications" by Le Gall, found here.

Splitting trees model a population where individuals have i.i.d. lifetimes and give birth to independent copies of themselves at constant rate along their life. We will see how this random population can be encoded by nice Lévy processes excursions, and how the genealogy of the extant individuals at a fixed time t can be simply encoded by a Poisson process on R² - a coalescent point process. We will then be able to give a classical representation of Yule trees in terms of Poisson point processes.

Reference: "The countour of splitting trees is a Lévy process" by Lambert, found here.

Totally Asymmetric Simple Exclusion Process (TASEP) on the integers is one of the classical exactly solvable models in the KPZ universality class. We study the "slow bond" model, where TASEP on $\Z$ is imputed with a slow bond at the origin. The slow bond increases the particle density immediately to its left and decreases the particle density immediately to its right. Whether or not this effect is detectable in the macroscopic current started from the step initial condition has attracted much interest over the years and this question was settled recently (Basu, Sidoravicius, Sly (2014)) by showing that the current is reduced even for arbitrarily small strength of the defect. Following non-rigorous physics arguments (Janowsky, Lebowitz (1992, 1994)) and some unpublished works by Bramson, a conjectural description of properties of invariant measures of TASEP with a slow bond at the origin was provided in Liggett's 1999 book. We establish Liggett's conjectures and in particular show that TASEP with a slow bond at the origin, started from step initial condition, converges in law to an invariant measure that is asymptotically close to product measures with different densities far away from the origin towards left and right. Our proof exploits the correspondence between TASEP and last passage percolation on $\Z^2$.

Reference: "Invariant Measures for TASEP with a Slow Bond", Basu, Sarkar, and Sly, found here.

We introduce the idea of cut metric on a graph then relate it to the second eigenvalue of the normalized graph Laplacian. The inequality that gives this relationship is known as Cheeger's inequality. This has proven highly relevant to work in expander graphs, random walk on graphs and other areas of probability.

A non-backtracking walk on a graph is a directed path such that no edge is the inverse of its preceding edge. We explain how to study some properties of these by looking at largest eigenvalue of an associated non-backtracking matrix, then present some applications to community detection.

Reference: "Non-backtracking spectrum of random graphs: community detection and non-regular Ramanujan graphs", Bordenave, Lelarge, and Massoulie, found here

We review the "appetizer" of chapter 0 describing covering of convex sets via the probabilistic method. We then discuss basic cases of concentration inequalities for independent random variables. In particular we introduce the classes of sub-Gaussian and sub-exponential random variables and some basic concentration results about them.

Reference: High Dimensional Probability by Roman Vershynin.

General methods for getting lower bounds on random variables are hard to come by. We present Chaterjee's very recent paper that describes a general method of getting lower bounds via coupling arguments.

Chatterjee's paper can be found here.

We will go over the first part of Chapter 5 of HDP, "Concentration without Independence." We will discuss concentration of Lipschitz functions on the sphere and extend the ideas to other natural metric spaces. As an application we will derive the Johnson-Lindenstrauss Lemma. .

We first explain the tensorization property of variance (also known as the Efron-Stein inequality) and demonstrate its use via an easy corollary, the bounded differences inequality. Next, we present a more general perspective for variance-type bounds. The key idea is an equivalence between so-called Poincaré inequalities, exponentially fast convergence of Markov Processes, and bounds on certain energy functionals known as Dirichlet forms.

This talk is drawn from Chapter 2 of Ramon van Handel's notes on Probability in High Dimension, found here.