Probability

The probability community has obtained fruitful results about the connectivity of random graphs in the last 50 years. Random topology is an emerging field that studies higher-order connectivity of random simplicial complexes, which are higher-order generalizations of graphs. Many classical…

Given a discrete-time non-lattice supercritical branching random walk (or branching Brownian motion) in $\mathbb{R}^d$, we investigate its first passage time to a shifted unit ball of a distance $x$ from the origin, conditioned upon survival. We provide precise asymptotics up to $O(1)$ (…

Motivated by modeling time-dependent processes on networks like social interactions and infection spread, we consider a version of the classical Erdős–Rényi random graph G(n,p) where each edge has a distinct random timestamp, and connectivity is constrained to sequences of edges with increasing…

Spin models on graphs are a source of many interesting questions in statistical physics, algorithms, and combinatorics. The Ising model is a classical example: first introduced as a model of magnetization, it can combinatorially be described as a weighted probability distribution on two-vertex…

Last passage percolation (LPP) is a model of random geometry where the main observable is a directed path evolving in a random environment. When the environment distribution has light tails and a fast decay of correlation, the random fluctuations of LPP are predicted to be explained by the…

Fundamentals of statistical mechanics explain that systems in thermal equilibrium spend a greater fraction of their time in states with apparent order because these states have lower energy. This explanation is remarkable, and powerful, because energy is a "local" property of states. While non-…

Strongly correlated particle systems, such as Coulomb gases and zeros of Gaussian polynomials, have been shown in recent years to display a wide range of behavior vis-a-vis their spatial laws. In particular, their local distributions under spatial conditioning are often characterized by…

The Burnside process is a general Markov chain for sampling unlabeled objects. Two examples of the Burnside process give new algorithms for uniformly sampling contingency tables and integer partitions. Both these algorithms have "lumped" versions. These lumped processes are also Markov chains,…

The stochastic block model (SBM), a random graph generalizing the Erdős–Rényi model, has long served as a framework for community detection. For SBMs with $n$ vertices and a fixed number of communities $q$, Decelle et al. (2011) predicted that efficient recovery is possible above the Kesten–…

The stochastic block model is a canonical model of communities in random graphs. Given a sparse stochastic block model, the two standard inference tasks are:

1. Weak recovery: Can we estimate the communities with non-trivial overlap with the true communities?
2. Detection/hypothesis…