I am a probabilist mainly interested in models featuring a hierarchical structure. A prime example is the branching random walk/branching Brownian motion and branching processes in general, but I have also worked on random planar maps, Gaussian multiplicative chaos, interval fragmentations, random trees, first passage percolation and random walk in a random environment on a tree.

I have had the pleasure of working together with the following wonderful people: Louigi Addario-Berry, Itai Benjamini, Jean Bérard, Julien Berestycki, Pierre Boutaud, Linxiao Chen, Nicolas Curien, Robert Görke, Olivier Hénard, Michel Pain, Elliot Paquette, Rémi Rhodes, Andrea Schumm, Jason Schweinsberg, Christian Staudt, Vincent Vargas, Dorothea Wagner, Ofer Zeitouni.

Slides of selected talks

Papers/Preprints

Note: list might be incomplete. Please check on the arXiv for a complete list.

with Julien Berestycki and Jason Schweinsberg
in preparation

We consider one-dimensional branching Brownian motion in which particles are absorbed at the origin. We assume that when a particle branches, the offspring distribution is supercritical, but the particles are given a critical drift towards the origin so that the process eventually goes extinct with probability one. We establish precise asymptotics for the probability that the process survives for a large time $t$, improving upon a result of Kesten (1978) and Berestycki, Berestycki, and Schweinsberg (2014). We also prove a Yaglom-type limit theorem for the behavior of the process conditioned to survive for an unusually long time, which also improves upon results of Kesten (1978). An important tool in the proofs of these results is the convergence of branching Brownian motion with absorption to a continuous state branching process.

with Pierre Boutaud
arXiv:1902.05330, submitted, 2019 Download: Preprint

We introduce a set of tools which simplify and streamline the proofs of limit theorems concerning near-critical particles in branching random walks under optimal assumptions. We exemplify our method by giving another proof of the Seneta-Heyde norming for the critical additive martingale, initially due to Aïdékon and Shi. The method involves in particular the replacement of (truncated) second moments by truncated first moments, and the replacement of ballot-type theorems for random walks by estimates coming from an explicit expression for the potential kernel of random walks killed below the origin. Of independent interest might be a short, self-contained proof of this expression, as well as a criterion for convergence in probability of non-negative random variables in terms of conditional Laplace transforms.

with Louigi Addario-Berry
arXiv:1810.05129, submitted Download: Preprint

We prove an algorithmic hardness result for finding low-energy states in the so-called continuous random energy model (CREM), introduced by Bovier and Kurkova in 2004 as an extension of Derrida's generalized random energy model. The CREM is a model of a random energy landscape $(X_v)_{v \in \{0,1\}^N}$ on the discrete hypercube with built-in hierarchical structure, and can be regarded as a toy model for strongly correlated random energy landscapes such as the family of $p$-spin models including the Sherrington–Kirkpatrick model. The CREM is parameterized by an increasing function $A:[0,1]\to [0,1]$, which encodes the correlations between states. We exhibit an algorithmic hardness threshold $x_*$, which is explicit in terms of $A$. More precisely, we obtain two results: First, we show that a renormalization procedure combined with a greedy search yields for any $\varepsilon > 0$ a linear-time algorithm which finds states $v \in \{0,1\}^N$ with $X_v \ge (x_*-\varepsilon ) N$. Second, we show that the value $x_*$ is essentially best-possible: for any $\varepsilon > 0$, any algorithm which finds states $v$ with $X_v \ge (x_*+\varepsilon )N$ requires exponentially many queries in expectation and with high probability. We further discuss what insights this study yields for understanding algorithmic hardness thresholds for random instances of combinatorial optimization problems.

with Michel Pain
arXiv:1806.05152, to appear in Annals of Probability Download: Preprint

Let $(Z_t)_{t\geq 0}$ denote the derivative martingale of branching Brownian motion, i.e.\@ the derivative with respect to the inverse temperature of the normalized partition function at critical temperature. A well-known result by Lalley and Sellke [Ann. Probab., 15(3):1052--1061, 1987] says that this martingale converges almost surely to a limit $Z_\infty $, positive on the event of survival. In this paper, our concern is the fluctuations of the derivative martingale around its limit. A corollary of our results is the following convergence, confirming and strengthening a conjecture by Mueller and Munier [Phys. Rev. E, 90:042143, 2014]: \[ \sqrt {t} \left ( Z_\infty - Z_t + \frac {\log t}{\sqrt {2\pi t}} Z_\infty \right ) \xrightarrow [t\to \infty ]{} S_{Z_\infty }, \quad \text {in law}, \] where $S$ is a spectrally positive 1-stable Lévy process independent of $Z_\infty $. In a first part of the paper, a relatively short proof of (a slightly stronger form of) this convergence is given based on the functional equation satisfied by the characteristic function of $Z_\infty $ together with tail asymptotics of this random variable. We then set up more elaborate arguments which yield a more thorough understanding of the trajectories of the particles contributing to the fluctuations. In this way, we can upgrade our convergence result to functional convergence. This approach also sets the ground for a follow-up paper, where we study the fluctuations of more general functionals including the renormalized critical additive martingale. All proofs in this paper are given under the hypothesis $\mathbb E[L(\log L)^3] < \infty $, where the random variable $L$ follows the offspring distribution of the branching Brownian motion. We believe this hypothesis to be optimal.

with Linxiao Chen and Nicolas Curien
arXiv:1702.06916, submitted Download: Preprint

We study the branching tree of the perimeters of the nested loops in critical $O(n)$ model for $n \in (0,2)$ on random quadrangulations. We prove that after renormalization it converges towards an explicit continuous multiplicative cascade whose offspring distribution $(x_i)_{i \ge 1}$ is related to the jumps of a spectrally positive α-stable Lévy process with $\alpha = \frac {3}{2} \pm \frac {1}{\pi } \arccos (n/2)$ and for which we have the surprisingly simple and explicit transform $$ \mathbb E\left [\sum _{i \ge 1} (x_i)^\theta \right ] = \frac {\sin (\pi (2-\alpha ))}{\sin (\pi (\theta - \alpha ))} \quad \mbox {for }\theta \in (\alpha , \alpha +1).$$ An important ingredient in the proof is a new formula of independent interest on first moments of additive functionals of the jumps of a left-continuous random walk stopped at a hitting time. We also identify the scaling limit of the volume of the critical $O(n)$-decorated quadrangulation using the Malthusian martingale associated to the continuous multiplicative cascade.

Bernoulli 24, 297–315, 2018 Download: Journal · Preprint

A λ-invariant measure of a sub-Markov chain is a left eigenvector of its transition matrix of eigenvalue λ. In this article, we give an explicit integral representation of the λ-invariant measures of subcritical Bienaymé–Galton–Watson processes killed upon extinction, i.e. upon hitting the origin. In particular, this characterizes all quasi-stationary distributions of these processes. Our formula extends the Kesten–Spitzer formula for the (1-)invariant measures of such a process and can be interpreted as the identification of its minimal λ-Martin entrance boundary for all λ. In the particular case of quasi-stationary distributions, we also present an equivalent characterization in terms of semi-stable subordinators. Unlike Kesten and Spitzer's arguments, our proofs are elementary and do not rely on Martin boundary theory.

ALEA, Lat. Am. J. Probab. Math. Stat. 13, 545–561, 2016 Download: Journal · Preprint

We consider random walks indexed by arbitrary finite random or deterministic trees. We derive a simple sufficient criterion which ensures that the maximal displacement of the tree-indexed random walk is determined by a single large jump. This criterion is given in terms of four quantities: the tail and the expectation of the random walk steps, the height of the tree and the number of its vertices. The results are applied to critical Galton–Watson trees with offspring distributions in the domain of attraction of a stable law.

with Rémi Rhodes, Vincent Vargas and Ofer Zeitouni
Ann. Inst. H. Poincaré Probab. Statist. 52, 1281–1320, 2016 Download: Journal · Preprint

We initiate in this paper the study of analytic properties of the Liouville heat kernel. In particular, we establish regularity estimates on the heat kernel and derive non trivial lower and upper bounds.

with Olivier Hénard
Journal de l'Ecole Polytechnique 3, 365–400, 2016 Download: Journal · Preprint

We study random trees which are invariant in law under the operation of contracting each edge independently with probability $p\in (0,1)$. We show that all such trees can be constructed through Poissonian sampling from a certain class of random measured $\mathbb R$-trees satisfying a natural scale invariance property. This has connections to exchangeable partially ordered sets, real-valued self-similar increasing processes and quasi-stationary distributions of Galton–Watson processes.

with Elliot Paquette
Israel Journal of Mathematics 212, 337–384, 2016 Download: Journal · Preprint

We consider a random interval splitting process, in which the splitting rule depends on the empirical distribution of interval lengths. We show that this empirical distribution converges to a limit almost surely as the number of intervals goes to infinity. We give a characterization of this limit as a solution of an ODE and use this to derive precise tail estimates. The convergence is established by showing that the size-biased empirical distribution evolves in the limit according to a certain deterministic evolution equation. Although this equation involves a non-local, non-linear operator, it can be studied thanks to a carefully chosen norm with respect to which this operator is contractive. In finite-dimensional settings, convergence results like this usually go under the name of stochastic approximation and can be approached by a general method of Kushner and Clark. An important technical contribution of this article is the extension of this method to an infinite-dimensional setting.

with Itai Benjamini
in Geometric Aspects of Functional Analysis, Israel Seminar (GAFA) 2011-2013, Lecture Notes in Mathematics, Vol. 2116, 47–51, Bo'az Klartag, Emanuel Milman (eds.), Springer, 2014 Download: Journal · Preprint

We consider first passage percolation (FPP) on $\mathbb {T}_{d}\times G$, where $\mathbb {T}_d$ is the $d$-regular tree ($d\ge 3$) and $G$ is a graph containing an infinite ray $0,1,2,…$. It is shown that for a fixed vertex $v$ in the tree, the fluctuation of the distance in the FPP metric between the points $(v,0)$ and $(v,n)$ is of the order of at most $\log n$. We conjecture that the real fluctuations are of order $1$ and explain why.

with Ofer Zeitouni
Annales de l'Institut Henri Poincaré, Probabilités et Statistiques 52, 1144–1160, 2016 Download: Journal · Preprint

We consider the distribution of the maximum $M_T$ of branching Brownian motion with time-inhomogeneous variance of the form $\sigma ^2(t/T)$, where $\sigma (\cdot )$ is a strictly decreasing function. This corresponds to the study of the time-inhomogeneous Fisher–Kolmogorov-Petrovskii-Piskunov (F-KPP) equation $ F_t(x,t)=\sigma ^2(1-t/T)F_{xx} (x,t)/2+ g(F(x,t))$, for appropriate nonlinearities $g(\cdot )$. Fang and Zeitouni (2012) showed that $M_T-v_\sigma T$ is negative of order $T^{1/3}$, where $v_\sigma =\int _0^1 \sigma (s)ds$. In this paper, we show the existence of a function $m'_T$, such that $M_T-m'_T$ converges in law, as $T\rightarrow \infty $. Furthermore, $m'_T=v_\sigma T - w_\sigma T^{1/3} - \sigma (1)\log T + O(1)$ with $w_\sigma = 2^{-1/3}\alpha _1 \int _0^1 \sigma (s)^{1/3} |\sigma '(s)|^{2/3}\,ds$. Here, $-\alpha _1=-2.33811...$ is the largest zero of the Airy function $\operatorname {Ai}$. The proof uses a mixture of probabilistic and analytic arguments.

Probability Theory and Related Fields 166, 1061–1173, 2016 Download: Journal · Preprint

We consider branching Brownian motion on the real line with the following selection mechanism: Every time the number of particles exceeds a (large) given number $N$, only the $N$ right-most particles are kept and the others killed. After rescaling time by $\log ^3N$, we show that the properly recentred position of the $\lfloor \alpha N\rfloor $-th particle from the left, $\alpha \in (0,1)$, converges in law to an explicitly given spectrally positive Lévy process. This behaviour has been predicted to hold for a large class of models falling into the universality class of the FKPP equation with weak multiplicative noise [Brunet et al., Phys. Rev. E 73(5), 056126 (2006)] and is proven here for the first time for such a model.

with Ofer Zeitouni
Ann. Appl. Probab. 24, 2070–2090, 2014 Download: Journal · Preprint

Consider a $d$-ary rooted tree ($d\geq 3$) where each edge $e$ is assigned an i.i.d. (bounded) random variable $X(e)$ of negative mean. Assign to each vertex $v$ the sum $S(v)$ of $X(e)$ over all edges connecting $v$ to the root, and assume that the maximum $S_n^*$ of $S(v)$ over all vertices $v$ at distance $n$ from the root tends to infinity (necessarily, linearly) as $n$ tends to infinity. We analyze the Metropolis algorithm on the tree and show that under these assumptions there always exists a temperature $1/\beta $ of the algorithm so that it achieves a linear (positive) growth rate in linear time. This confirms a conjecture of Aldous (Algorithmica, 22(4):388-412, 1998). The proof is obtained by establishing an Einstein relation for the Metropolis algorithm on the tree.

with Jean Bérard
Electronic Journal of Probability 19, no. 22, 1–17, 2014 Download: Journal · Preprint

We consider a system of $N$ particles on the real line that evolves through iteration of the following steps: 1) every particle splits into two, 2) each particle jumps according to a prescribed displacement distribution supported on the positive reals and 3) only the $N$ right-most particles are retained, the others being removed from the system. This system has been introduced in the physics literature as an example of a microscopic stochastic model describing the propagation of a front. Its behavior for large $N$ is now well understood – both from a physical and mathematical viewpoint – in the case where the displacement distribution admits exponential moments. Here, we consider the case of displacements with regularly varying tails, where the relevant space and time scales are markedly different. We characterize the behavior of the system for two distinct asymptotic regimes. First, we prove convergence in law of the rescaled positions of the particles on a time scale of order $\log N$ and give a construction of the limit based on the records of a space-time Poisson point process. Second, we determine the appropriate scaling when we let first the time horizon, then $N$ go to infinity.

Electronic Communications in Probability 18, no. 5, 1–9, 2013 Download: Journal · Preprint

We call a point process $Z$ on $\mathbb R$ exp-1-stable if for every $\alpha ,\beta \in \mathbb R$ with $e^\alpha +e^\beta =1$, $Z$ is equal in law to $T_\alpha Z+T_\beta Z'$, where $Z'$ is an independent copy of $Z$ and $T_x$ is the translation by $x$. Such processes appear in the study of the extremal particles of branching Brownian motion and branching random walk and several authors have proven in that setting the existence of a point process $D$ on $\mathbb R$ such that $Z$ is equal in law to $\sum _{i=1}^\infty T_{\xi _i} D_i$, where $(\xi _i)_{i\ge 1}$ are the atoms of a Poisson process of intensity $e^{-x}\,dx$ on $\mathbb R$ and $(D_i)_{i\ge 1}$ are independent copies of $D$ and independent of $(\xi _i)_{i\ge 1}$. In this note, we show how this decomposition follows from the classic LePage decomposition of a (union)-stable point process. Moreover, we give a short proof of it in the general case of random measures on $\mathbb R$.

Annales de l'Institut Henri Poincaré Probabilités et Statistiques 49, 428–455, 2013 Download: Journal · Preprint

We study supercritical branching Brownian motion on the real line starting at the origin and with constant drift $c$. At the point $x > 0$, we add an absorbing barrier, i.e. individuals touching the barrier are instantly killed without producing offspring. It is known that there is a critical drift $c_0$, such that this process becomes extinct almost surely if and only if $c \ge c_0$. In this case, if $Z_x$ denotes the number of individuals absorbed at the barrier, we give an asymptotic for $P(Z_x=n)$ as $n$ goes to infinity. If $c=c_0$ and the reproduction is deterministic, this improves upon results of L. Addario-Berry and N. Broutin [1] and E. A\"ıdékon [2] on a conjecture by David Aldous about the total progeny of a branching random walk. The main technique used in the proofs is analysis of the generating function of $Z_x$ near its singular point $1$, based on classical results on some complex differential equations.

with Robert Görke, Andrea Schumm, Christian Staudt and Dorothea Wagner
J. Exp. Algorithmics 18, 1.5:1.1--1.5:1.29, 2013 Download: Journal

Maximizing the quality index modularity has become one of the primary methods for identifying the clustering structure within a graph. Since many contemporary networks are not static but evolve over time, traditional static approaches can be inappropriate for specific tasks. In this work, we pioneer the NP-hard problem of online dynamic modularity maximization. We develop scalable dynamizations of the currently fastest and the most widespread static heuristics and engineer a heuristic dynamization of an optimal static algorithm. Our algorithms efficiently maintain a modularity-based clustering of a graph for which dynamic changes arrive as a stream. For our quickest heuristic we prove a tight bound on its number of operations. In an experimental evaluation on both a real-world dynamic network and on dynamic clustered random graphs, we show that the dynamic maintenance of a clustering of a changing graph yields higher modularity than recomputation, guarantees much smoother clustering dynamics, and requires much lower runtimes. We conclude with giving sound recommendations for the choice of an algorithm.

with Robert Görke, Christian Staudt and Dorothea Wagner
in Experimental Algorithms, Lecture Notes in Computer Science 6049, 436–448, Paola Festa (ed.), Springer Berlin / Heidelberg, 2010 Download: Journal

Maximizing the quality index modularity has become one of the primary methods for identifying the clustering structure within a graph. As contemporary networks are not static but evolve over time, traditional static approaches can be inappropriate for specific tasks. In this work we pioneer the NP-hard problem of online dynamic modularity maximization. We develop scalable dynamizations of the currently fastest and the most widespread static heuristics and engineer a heuristic dynamization of an optimal static algorithm. Our algorithms efficiently maintain a modularity-based clustering of a graph for which dynamic changes arrive as a stream. For our quickest heuristic we prove a tight bound on its number of operations. In an experimental evaluation on both a real-world dynamic network and on dynamic clustered random graphs, we show that the dynamic maintenance of a clustering of a changing graph yields higher modularity than recomputation, guarantees much smoother clustering dynamics and requires much lower runtimes. We conclude with giving recommendations for the choice of an algorithm.

Note: this list is automatically generated from a .bib file by a Python script. Feel free to use and modify it as you please.

Theses

Unpublished notes