DYOGENE/ERC NEMO Seminar series

Usually held on Monday, the DYOGENE/ERC NEMO Seminar Series invites researchers to present their work on stochastic processes, random graphs and point processes.

Future talks can be found on the following calendar.

Most talks were recorded and are available on Canal U :

Here is the list of the talks from 2021 till now.

  • 3/07/2023, Eyal Castiel, Georgia Tech. Parallel server systems in extended heavy traffic. Abstract: The standard setting for studying parallel server systems (PSS) at the diffusion scale is based on the heavy traffic condition (HTC), which assumes that the underlying static allocation linear program (LP) is critical and has a unique solution. This solution determines the graph of basic activities, which identifies the set of activities (i.e., class-server pairs) that are operational. In this talk we explore the extended HTC, where the LP is merely assumed to be critical. Because multiple solutions are allowed, multiple sets of operational activities, referred to as modes, are available. Formally, the scaling limit for the control problem associated with the model is given by a so called workload control problem (WCP) in which a cost associated with a diffusion process is to be minimized by dynamically switching between these modes.
  • 26/06/2023, Thomas Budzinski, ENS de Lyon. The Maximal Agreement Subtree problem for random trees. Abstract : Consider two binary trees whose leaves are labelled from 1 to n. What is the size of the largest set of labels such that the genealogy between these labels is the same in both trees? If the trees are picked uniformly at random in an independent way, a crude argument shows that this size grows at most like the square root of n. We show that this is not optimal. Perhaps surprisingly, this problem is linked to the study of the optimal Hölder regularity of homeomorphisms between two independent Brownian trees. Based on joint work with Delphin Sénizergues
  • 19/06/2023, Ali Khezeli, Inria Paris. An Improved Lower Bound on the Largest Common Subtree of Random Leaf-Labeled Binary Trees. Abstract: It is known that the size of the largest common subtree (i.e., the maximum agreement subtree) of two independent random binary trees with n given labeled leaves is of order between n^(0.366) and n^(1/2). We improve the lower bound to order n^(0.4464) by constructing a common subtree recursively and by proving a lower bound for its asymptotic growth. The construction is a modification of an algorithm proposed by D. Aldous by splitting the tree at the centroid and by proceeding recursively.
  • 2/06/2023, Venkat Anantharam, EECS Department, University of California, Berkeley. Reversible Markov decision processes. Abstract: A Markov decision process is called reversible if for every stationary Markov control strategy the resulting Markov chain is reversible. In view of their relevance in applications such as Markov Chain Monte Carlo algorithms, such reversible Markov decision process seem to be of interest to study in their own right. We characterize all discrete time reversible Markov decision processes with finite state and action spaces, generalizing earlier work of Cogill and Peng. We discuss how the policy iteration algorithm to find an optimal stationary Markov control strategy is considerably simplified for reversible Markov decision processes. The potential to apply powerful tools from the study of reversible Markov chains, such as the Poisson gas of Markovian loops and the Gaussian free field, will also be discussed.
  • 30/05/2023, Adam Timar, University of Iceland; Alfred Renyi Institute of Mathematics. The question of connectedness in the Free Uniform Spanning Forest. Abstract: The uniform measure on the set of all spanning trees of a finite graph is a classical object in probability. In an infinite graph, one can take an exhaustion by finite subgraphs, with some boundary conditions, and take the limit measure. The Free Uniform Spanning Forest (FUSF) is one of the natural limits, but it is less understood than the wired version, the WUSF. If we take a finitely generated group, then several properties of WUSF and FUSF have been known to be independent of the chosen Cayley graph of the group: the average degree in WUSF and in FUSF; the number of ends in the components of the WUSF and of the FUSF; the number of trees in the WUSF. Lyons and Peres asked if this latter should also be the case for the FUSF. In a joint work with Gábor Pete we give two different Cayley graphs of the same group such that the FUSF is connected in one of them and it has infinitely many trees in the other. Furthermore, since our example is a virtually free group, we obtained a counterexample to the general expectation, that such “tree-like” graphs would have connected FUSF. Several open questions are inspired by the results. We also present some preliminary results and conjectures on phase transition phenomena that happen if we put conductances on the edges of the underlying graph.
  • 22/05/2023, Elizabeth O’Reilly, California Institute of Technology. Optimal Convex and Nonconvex Regularizers for a Data Source. Abstract: Regularization is a widespread technique used in statistical estimation problems that helps to capture low dimensional structure in the data and improve signal recovery. For computational and geometric reasons, many regularizers are induced by certain classes of convex bodies, such as polyhedral regularizers in dictionary learning. We propose a generalization of this approach by formulating an optimization problem over the space of star bodies to learn the best regularizer for a given dataset. Through a connection with a dual mixed volume inequality for star bodies, we provide a characterization of the population risk minimizers of this problem and establish strong consistency of the empirical risk minimizers. Based on joint work with Oscar Leong, Yong Sheng Soh, and Venkat Chandrasekaran.
  • 17/04/2023, Lewis Bowen, University of Texas at Austin. Finitary random interlacements and the Gaboriau-Lyons problem. Abstract: The von Neumann-Day problem asks whether every non-amenable group contains a non-abelian free group. It was answered in the negative by Ol’shanskii in the 1980s. The measurable version (formulated by Gaboriau-Lyons) asks whether every non-amenable measured equivalence relation contains a non-amenable treeable subequivalence relation. This paper obtains a positive answer in the case of arbitrary Bernoulli shifts over a non-amenable group, extending work of Gaboriau-Lyons. The proof uses an approximation to the random interlacement process by random multistep of geometrically-killed random walk paths. There are two applications: (1) the Gaboriau-Lyons problem for actions with positive Rokhlin entropy admits a positive solution, (2) for any non-amenable group, all Bernoulli shifts factor onto each other.
  • 03/04/2023, Giovanni Luca Torrisi, CNR-IAC, Roma, Italy. Normal approximation of means of the Dirichlet-Ferguson measure. Abstract: The Dirichlet-Ferguson measure is a cornerstone in Bayesian nonparametrics and the study of the distributional properties of expectations with respect to (w.r.t.) such a measure is a line of research initiated in the seventies and still very active. We provide explicit upper bounds for (i) the Wasserstein distance between the law of a random mean w.r.t. the Dirichlet-Ferguson measure and the standard Gaussian distribution (ii) the d_2 and the convex distances between the law of a random vector, whose components are random means w.r.t. the Dirichlet-Ferguson measure, and a multivariate Gaussian distribution. As application of the general bounds, we study the normal approximation of linear transformations of random vectors distributed according to the Dirichlet law. Based on a joint work with Ian Flint, University of Melbourne.
  • 28/03/2023, Takis Konstantopoulos, University of Liverpool. Max growth systems and their perfect simulation. Abstract: We discuss how these models arise from random directed graphs and talk about perfect simulation.
  • 27/03/2023, David McDonald, University of Ottawa. Rare events in a polling system: Rays & Spirals. Abstract: It’s a situation everyone dreads. A road is down to one lane for repairs. Traffic is let through one way until the backlog clears and then traffic is let through the other way to clear that backlog and so on. When stuck in a very long queue it is inevitable to wonder how did I get into this mess?We study a polling model with a server having exponential service time with mean 1/μ alternating between two queues, emptying one queue before switching to the other. Customers arrive at queue one according to a Poisson process with rate λ1 and at queue two with rate λ2. We discuss how we get at a rare event with a large number of customers in the system. In fact this can happen in two different ways depending on the parameters. In one case one queue simply explodes and runs away without emptying. We call this the ray case. In the other spiral case the queues are successively emptied but in a losing battle as the system zigzags to the rare event. This dichotomy extends to the steady state distribution and leads to quite different asymptotic behavior in the two cases.
  • 20/03/2023, Leo Dort, ENS Lyon. Dynamical Erdös-Rényi Random Graph. A Local Convergence Point of View. Abstract: Local weak convergence of graphs, introduced by Itaï Benjamini and Oded Schramm in 2001, tries to understand the intern geometry of a typical vertex in large graphs and is a great tool to study asymptotic properties of these large graphs. In this presentation, we will discuss about notions of local weak convergence for dynamical graphs, that are graphs in which edges are allowed to appear and disappear in function of time. Motivating by questions of modeling spread of infection in population, we will introduce a notion of local convergence which takes into account the local geometry in space and in time of dynamical neighborhood of a typical vertex. We will focus on the example of dynamical percolation on the complete graph, for which the local limit is an evolving “tree” which can “growth” and “segmented”. This talk is based on a joint work with Emmanuel Jacob.
  • 13/03/2023, D.Yogeshwaran, Indian Statistical Institute, Bangalore. Poisson process approximation under stabilization and Palm coupling. Abstract: We present some Poisson process approximation results for stabilizing functionals of Poisson (or Binomial) processes that arise in stochastic geometry. Our bounds are derived for the Kantorovich-Rubinstein distance between a point process and an appropriate Poisson point process. We will discuss application to largest k-nearest neighbour distances. This is based on a joint project with Omer Bobrowski (Technion) and Matthias Schulte (Hamburg Institute of Technology) [see arXiv:2104.13261].
  • 6/03/2023, Philippe Robert, Inria Paris. A Palm Space Approach to Non-Linear Hawkes Processes. Abstract: A Hawkes process on the real line is a point process whose intensity function at time t is a functional of its past activity before time t. It is defined by its activation and memory functions. By using the classical correspondence between a stationary point process and its Palm measure, for stationary Hawkes point processes we establish a characterization of the Palm measure in terms of an invariant distribution of a Markovian kernel. We prove that if the activation function is continuous and its growth rate is at most linear with a rate below some constant, then there exists a stationary Hawkes point process. The classical Lipschitz condition of the literature for an unbounded activation function is therefore relaxed. Our proofs rely on a combination of coupling methods, monotonicity properties of linear Hawkes processes and classical results on Palm distributions. An investigation of the Hawkes process starting from the null measure, the empty state, plays also an important role. The classical linear case of Hawkes and Oakes is revisited at this occasion. Limit results for some explosive Hawkes point processes, i.e. when there does not exist a stationary version, are also obtained. Joint work with Gaëtan Vignoud (INRIA and Dioxycle).
  • 27/02/2023, Ke Feng, Inria Paris. Spatial network calculus and performance guarantees in wireless networks. Abstract: In this talk, we introduce spatial regulation properties for stationary spatial point processes and develops the first steps of a calculus for this regulation, which can be seen as an extension to space of the classical network calculus. Specifically, two classes of regulations are defined: one includes ball regulation and shot-noise regulation, which are shown equivalent; the other one includes void regulation. These regulations are defined both in the strong and weak sense: the former requires the regulations to hold everywhere in space, whereas the latter is built upon Palm calculus and only requires the regulations to hold as observed by a jointly stationary point process. Based on spatial network calculus, we derive performance guarantees in various wirless network models satisfying the regulation properties. We give universal bounds on the SINR for all links, which lead to link service curves based on information-theoretic achievability. They are combined with classical network calculus to provide end-to-end latency guarantees for all packets in wireless queuing networks. Such guarantees do not exist in networks that are not spatially regulated, e.g., Poisson-type networks.
  • 13/02/2023, Pascal Moyal, IECL – Université de Lorraine. Two approaches of maximal matchings on large random graphs. Abstract: We address the problem of designing simple online matching algorithms on large random graphs. We propose two approaches: first, we show how to couple the construction of the Configuration Model for a prescribed degree distribution with the construction of the matching itself, to derive the large graph limit of the matching coverage for various local matching algorithms (in the sense that they only depend of the degrees of the nodes). Second, we address the case of large stochastic block models. We show how the problem then reduces to the stability study of a related stochastic matching model, and provide conditions under which a perfect matching can be obtained infinitely often as the size of the graph goes large. (joint works with H.B.A. Diallo Aoudi/Vincent Robin and M. Jonckheere/N. Soprano Loto).
  • 20/01/2023, Christine Fricker, Inria Paris. Mean-field analysis for closed stochastic networks of finite capacity nodes with reservation. Abstract: The work is motivated by car-sharing systems like Autolib’ in Paris (2011-2017) where, for charging, electric cars are parked in small capacity nodes. We consider a simple model for this system as a set of M/M/1/K queues where customers (cars) move between nodes. To prevent users to look for a parking space at the end of the trip in a saturated area, users can reserve the destination space at the beginning of the trip, or even before the trip. We present both cases. The performance of the system is measured by the probability that a node has no cars or no parking space available. The main issue is the impact of the reservation. The study is based on mean-field analysis. Some aspects are presented in the talk. It is a joint work with C. Bourdais and H. Mohamed.
  • 16/01/2023, Ayoub Belhadji, Ockham, LIP, ENS de Lyon. Kernel approximations using determinantal point processes. Abstract: We study approximation problems in reproducing kernel Hilbert spaces (RKHS) using random nodes. More precisely, we focus on kernel quadrature and kernel interpolation for smooth functions living in an RKHS using nodes that follow the distribution of a determinantal point process (DPP) tailored to the RKHS. We prove fast convergence rates that depend on the eigenvalues of the RKHS kernel. This unified analysis gives new insights on the rates of the quadratures and interpolations based on DPPs, especially for high dimensional numerical integration problems.
  • 09/01/2023, Raphaël Lachièze-Rey, Université Paris Cité. Percolation of random fields excursions. Abstract: We consider homogeneous real random functions defined on the Euclidean space. We are in particular interested in the percolation properties of their excursion sets in dimension 2, defined as the (random) sets obtained after thresholding the field at some fixed value which is the parameter. We will present some results obtained for 1- centred Gaussian random fields and 2- for shot-noise fields, which can be seen as the Poisson counterparts of Gaussian fields. It turns out that under mild assumptions, as in many parametric models, there is a critical value that separates percolation from non-percolation, and we furthermore observe a sharp phase transition around this value. For symmetric auto-dual models, and in particular for Gaussian excursions, the critical value is trivially 0. For non-symmetric shot-noise excursions, we estimate the critical value at high intensity by approximating the shot-noise field by a Gaussian field through a strong invariance principle.
  • 05/12/2022, Nicholas Gast, Inria. The bias of fluid approximation: Poisson equation, averaging methods and two-timescale processes. Abstract: Fluid approximation often provide a good tool to study a stochastic process. In this talk, I will review tools that are used to compute the error made when using fluid approximations. I will introduce the notion of generators and how to compare them. This will lead us to talk about Poisson equation and Stein’s method. Finally, I will apply this to two-timescale processes and show how to use this to guarantee the accuracy of time-averaging methods.
  • 28/11/2022, Milad Barzegar, Sharif University of Technology. On the dependence structure of negatively dependent measures. Abstract: A major breakthrough in the theory of negatively dependent – i.e., repulsive – probability measures was the introduction of “strongly Rayleigh measures” by Borcea, Brändén and Liggett in 2009. These measures constitute a very well-behaved and rich class of probability measures, so much so that they are considered the “main” class of negatively dependent measures. An interesting feature of negatively dependent measures is their complex dependence structure. This is essentially due to intrinsic constraints in their dependence structure. In this talk, I will present two strong manifestations of this phenomenon in the class of strongly Rayleigh measures: (i) tail triviality, which is equivalent to asymptotic independence of distant parts of the stochastic process, and (ii) paving property, which, roughly speaking, says that it is possible to partition a set of strongly Rayleigh random variables into a small number of subsets such that the random variables in each subset are “almost independent”. This talk is based on joint works with Kasra Alishahi and Mohammadsadegh Zamani.
  • 14/11/2022, Payam Delgosha, University of Illinois. A Notion of Entropy for Sparse Marked Graphs and its Applications in Graphical Data Compression. Abstract: Many modern data sources arising from social networks, biological data, etc. are best viewed as being represented by combinatorial structures such as graphs, rather than time series. The local weak limit theory for sparse graphs, also known as the objective method, provides a framework which enables one to make sense of a stationary stochastic process for sparse graphs. The theory of time series is the engine driving an enormous range of applications in areas such as control theory, communications, information theory and signal processing. It is to be expected that a theory of stationary stochastic processes for combinatorial structures, in particular graphs, would eventually have a similarly wide-ranging impact. Employing the above framework, we introduce a notion of entropy for probability distributions on rooted graphs. This is a generalization of the notion of entropy introduced by Bordenave and Caputo to graphs which carry marks on their vertices and edges. The above notion of entropy can be considered as a natural counterpart for the Shannon entropy rate in the world of graphical data. We illustrate this by introducing a universal compression scheme for marked graphical data. We also discuss a low complexity universal compression algorithm for marked graphical data. Furthermore, we will discuss an extension of this approach to a more general sparsity regime that also takes into account heavy-tailed sparse graphs in which the number of edges in the graph scales super linearly with the number of vertices. In order to do this, we employ the sparse graphon framework as well as an appropriate notion of entropy for this framework. Using this, we introduce a universal lossless compression method which is simultaneously applicable to both sparsity regimes, namely the local weak convergence regime and the sparse graphon regime.
  • 07/11/2022, Michel Davydov, Inria Paris. Propagation of chaos and Poisson Hypothesis for replica mean-field models of intensity-based neural networks. Abstract: Neural computations arising from myriads of interactions between spiking neurons can be modeled as network dynamics with punctuate interactions. However, most relevant dynamics do not allow for computational tractability. To circumvent this difficulty, the Poisson Hypothesis regime replaces interaction times between neurons by Poisson processes. We prove that the Poisson Hypothesis holds at the limit of an infinite number of replicas in the replica-mean-field model, which consists of randomly interacting copies of the network of interest. The proof is obtained through a novel application of the Chen-Stein method to the case of a random sum of Bernoulli random variables and a fixed point approach to prove a law of large numbers for exchangeable random variables.
  • 24/10/2022, Francois Baccelli, Inria Paris and ENS. Migration-Contagion Processes. Abstract: Consider the following migration process based on a closed network of N queues with K_N customers. Each station is a ./M/infty queue with service (or migration) rate mu. Upon departure, a customer is routed independently and uniformly at random to another station. In addition to migration, these customers are subject to an SIS (Susceptible, Infected, Susceptible) dynamics. That is, customers are in one of two states: I for infected, or S for susceptible. Customers can only swap their state either from I to S or from S to I in stations. More precisely, at any station, each susceptible customer becomes infected with the instantaneous rate alpha.Y if there are Y infected customers in the station, whereas each infected customer recovers and becomes susceptible with rate beta. We let N tend to infinity and assume that \lim_{N\to infty} K_N/N= eta := lambda/mu, where \eta is a positive constant representing the customer density. The main problem of interest is about the set of parameters of such a system for which there exists a stationary regime where the epidemic survives in the limiting system. The latter limit will be referred to as the thermodynamic limit. We establish several structural properties (monotonicity and convexity) of the system, which allow us to give the structure of the phase transition diagram of this thermodynamic limit w.r.t. \eta. The analysis of this SIS model reduces to that of a wave-type PDE for which we found no explicit solution. This plain SIS model is one among several companion stochastic processes that exhibit both migration and contagion. Two of them are discussed in the present paper as they provide variants to the plain SIS model as well as some bounds. These two variants are the SIS-DOCS (Departure On Change of State) and the SIS-AIR (Averaged Infection Rate), which both admit closed form solutions. The SIS-AIR system is a classical mean-field model where the infection mechanism based on the actual population of infected customers is replaced by a mechanism based on some empirical average of the number of infected customers in all stations. The latter admits a product-form solution. SIS-DOCS features accelerated migration in that each change of SIS state implies an immediate departure. This model leads to another wave-type PDE that admits a closed form solution. In this text, the main focus is on the closed systems and their limits. The open systems consisting of a single station with Poisson input are instrumental in the analysis of the thermodynamic limits and are also of independent interest. Joint work with S. Foss and S. Shneer.


  • 13/10/2022, Anita winter, University of Duisburg-Essen. The space of algebraic measure trees and Aldous chain on cladograms in the diffusion limit. Abstract: In this talk we consider a Markov chain in the space of cladograms with a fixed number of leaves introduced and investigated by Aldous in 2000. We show that this Markov chain on a suitable time scale converges to a diffusion on continuum trees as the number of leaves goes to infinity. For that we give with algebraic measure trees a combinatorial notion of continuum trees. We equip the space of algebraic measure trees with the Gromov-weak convergence with respect to the distance arising from the distribution of branch points. (this is joint work with Wolfgang Löhr and Leonid Mytnik)
  • 10/10/2022, Bharath Roy Choudhury, Inria Paris. Genealogy of records of a class of random walks. Abstract: Consider the trajectory $w(i)$ of a random walk with i.i.d. increments taking their values in the set of integers larger than -2 and with mean 0. For each time $i$, draw an edge from $(i,w(i))$ to $(j,w(j))$, where $j$ is the smallest time larger than $i$ such that $w(j) \ge w(i)$. This defines the record random graph of the random walk. We show that this random graph is an infinite one-ended unimodular random tree, and more precisely a unimodular Eternal Galton-Watson Tree. We analyze the distribution of the random walk seen from the $n$-th record location of $(0,w(0))$ and the limiting value of this distribution as $n$ tends to infinity. We show that the latter can be described in terms of the Kesten Tree associated with this Galton-Watson Tree. We also establish various invariance properties of the trajectory of the random walk based on invariance properties of the Eternal Galton-Watson Tree.
  • 04/07/2022, Charles Bordenave, Institut de Mathématiques de Marseille. Sofic entropy of processes on infinite random trees. Abstract. This is a joint work with Agnes Backhausz et Balasz Szegedy. We define a natural notion of micro-state entropy associated to a random process on a unimodular random tree. This entropy is closely related to Bowen’s sofic entropy in dynamical systems. It allows to compute the asymptotic free energy of factor models on random graphs and it gives a variational framework to solve many combinatorial optimization problems on random graphs. We give a formula for this entropy for a large class of processes. I will also give a conjecture for a general formula of this sofic entropy.
  • 27/06/2022, Eliza O’Reilly, California Institute of Technology. Random Tessellation Forests. Abstract: Random forests are a popular class of algorithms used for regression and classification. The original algorithm introduced by Breiman in 2001 and many of its variants are ensembles of randomized decision trees built from axis-aligned partitions of the feature space. One such variant, called Mondrian random forests, were proposed to handle the online setting and are the first class of random forests for which minimax rates were obtained in arbitrary dimension. However, the restriction to axis-aligned splits fails to capture dependencies between features, and oblique splits have shown improved empirical performance for many tasks. By viewing the Mondrian as a special case of the stable under iterated (STIT) process in stochastic geometry, we resolve some open questions about the generalization of split directions. In particular, we utilize the theory of stationary random tessellations to show that STIT random forests achieve minimax rates for Lipschitz and C^2 functions. This work opens many new questions at the intersection of stochastic geometry and machine learning. Based on joint work with Ngoc Tran.
  • 20/06/2022, Matteo D’Achille, Université Paris-Est – Créteil Val-de-Marne. Back and forth between the beta distribution and edge stochastic domination in ERAPs. Abstract: I will survey recent and less recent results on the phase diagram of Euclidean Random Assignment Problems (ERAPs), which are discrete versions of the Monge-Kantorovich problem. In particular, I will try to illustrate how the geometry inherent in these models, which are random distance models on the complete bipartite graph beyond the mean field approximation, can be exploited to obtain detailed information on the expected ground state energy in one dimension, or to compare the ground state energies of different models in general dimension. Based mainly on current works in progress with Andrea Sportiello (LIPN, Paris-Nord University) and Yuqi Liu (LAMA, Paris-Est University).
  • .13/06/2022, Pierre Calka, University of Rouen. Fluctuations of random convex interfaces. Abstract. We consider the convex hull of a point set constituted with independent and uniformly distributed points in a smooth convex body K of R^d. We show that the rescaled maximal radial fluctuation as well as maximal facet area follow asymptotically a Gumbel extreme value distribution as the size of the input goes to infinity. These results rely in particular on the study of a so-called typical facet of the random polytope. In particular, the rates of convergence are similar to those observed for a large variety of random interfaces in probability theory (random cluster models, oriented random walks…). This is joint work with J. E. Yukich.
  • 08/06/2022, Subhro Ghosh, National University of Singapore. The unreasonable effectiveness of determinantal processes. Abstract : In 1960, Wigner published an article famously titled “The Unreasonable Effectiveness of Mathematics in the Natural Sciences†. In this talk we will, in a small way, follow the spirit of Wigner’s coinage, and explore the unreasonable effectiveness of determinantal processes (a.k.a. DPPs) far beyond their context of origin. DPPs originated in quantum and statistical physics, but have emerged in recent years to be a powerful toolbox for many fundamental learning problems. In this talk, we aim to explore the breadth and depth of these applications. On one hand, we will explore a class of Gaussian DPPs and the novel stochastic geometry of their parameter modulation, and their applications to the study of directionality in data and dimension reduction. At the other end, we will consider the fundamental paradigm of stochastic gradient descent, where we leverage connections with orthogonal polynomials to design a minibatch sampling technique based on data-sensitive DPPs ; with provable guarantees for a faster convergence exponent compared to traditional sampling. Based on the following works. [1] Gaussian determinantal processes: A new model for directionality in data, with P. Rigollet, Proceedings of the National Academy of Sciences, vol. 117, no. 24 (2020), pp. 13207–13213 (PNAS Direct Submission). [2] Determinantal point processes based on orthogonal polynomials for sampling minibatches in SGD, with R. Bardenet and M. Lin Advances in Neural Information Processing Systems 34 (Spotlight at NeurIPS 2021).
  • 23/05/2022, Sergey Foss, Heriot-Watt University. Structural properties of a conditioned random walk on the integer lattice with local constraints. Abstract: We consider a random walk on a one/multidimensional integer lattice with random bounds on local times, conditioned on the event that it hits a high level before its death. We introduce an auxiliary “core” process that has a regenerative structure and plays a key role in our analysis. We obtain representations for the distribution of the random walk in terms of the similar distribution of the “core” process. Based on that, we prove limiting theorems by letting the high level to tend to infinity. In particular, we generalise results for a simple symmetric one-dimensional random walk obtained earlier in the paper by Benjamini and Berestycki (2010). The talk is based on a joint work with Alexander Sakhanenko.
  • 16/05/2022, Herman Thorisson, University of Iceland. Forward and backward limits. Abstract: We start by considering irreducible aperiodic positive recurrent Markov chains, and the proof of the main limit theorem by the classical coupling argument, — which is well known. It is less known, however, that basically the same argument yields the main limit theorem in the null recurrent case. We then note that the classical coupling can also be applied to time-inhomogeneous Markov chains but does not give convergence to a limit, — or, rather, not without a change of perspective.
  • 02/05/2022, Seva Schneer, Heriot-Watt University. Discrete-time TASEP with holdback. Abstract: We study the following interacting particle system. There are $\rho n$ particles, $\rho < 1$, moving clockwise (“right”), in discrete time, on $n$ sites arranged in a circle. Each site may contain at most one particle. At each time, a particle may move to the right-neighbour site according to the following rules. If its right-neighbour site is occupied by another particle, the particle does not move. If the particle has unoccupied sites (“holes”) as neighbours on both sides, it moves right with probability 1. If the particle has a hole as the right-neighbour and an occupied site as the left-neighbour, it moves right with probability $0 < p < 1$. (We refer to the latter rule as a “holdback” property.) From the point of view of holes moving counter-clockwise, this is a zero-range process. The main question we address is: what is the system steady-state flux (or throughput) when $n$ is large, as a function of density $ρ$? The most interesting range of densities is $0 \le \rho \le 1/2$. We define the system typical flux as the limit, in $n$ going to infinity, of the steady-state flux in a system subject to additional random perturbations, when the perturbation rate vanishes. Our main results show that: (a) the typical flux is different from the formal flux, defined as the limit, in $n$ going to infinity, of the steady-state flux in the system without perturbations, and (b) there is a phase transition at density $h=p/(1+p)$. If $\rho < h$, the typical flux is equal to $\rho$, which coincides with the formal flux. If $\rho > h, a condensation phenomenon occurs, namely the formation and persistence of large particle clusters; in particular, the typical flux in this case is $p(1-\rho) < h < \rho$, which differs from the formal flux when $h < \rho < 1/2$. This is joint work with Sasha Stolyar (UIUC).
  • 25/04/2022, Eva Löcherbach, Université Paris 1. Perfect simulation of interacting point processes with infinite interaction range. Abstract : I will present a (partly) new method for perfectly sampling from the stationary regime of point processes having an infinite number of interacting components. This method is based on what is called Kalikow decomposition of the stochastic intensity of the process, together with an exploration of the spatial-temporal past of the process called Clan-of-Ancestors method. Such decompositions have been introduced in the framework of discrete time processes with long memory and/or g-measures, by Kalikow in 1990. I will explain how this method can be generalized to the framework of point processes in continuous time and which are the limitations of this approach. Finally I will discuss several examples, in particular Hawkes processes with an infinite number of components, having a strict refractory period. My talk is based on joint work with Patricia Reynaud-Bouret and Tien Cuong Phi (Nice).
  • 11/04/2022, David Aldous, University of Berkeley. Open problems within three topics in spatial networks: scale-invariance, the nearest unvisited vertex walk, and a toy model of 4X games. Abstract: (1) Some of my old work involved an axiomatization of the SIRSN class of networks, whose primatives are routes between almost all pairs of points in the plane. Many open problems within this framework have not been studied. (2) The “nearest unvisited vertex” (NUV) walk is a deterministic walk on a network with real edge-lengths, classically studied in the worst-case algorithm setting. The setting of random networks was not previously studied. Order-of-magnitude results are not difficult, but more refined analysis seems a challenging open problem. (3) 4X games (exemplified by Stellaris) are complex strategy games played by millions of young people. Here is a huge over-simplification of the initial stages of such games. Players starting from different vertices of a realization of a large random network can move a marker and grow an empire consisting of their visited vertices, while not allowed to enter any opponent’s empire. In this over-simplified game, the goal is to acquire the largest empire. The NUV walk is one simple strategy: how does this compare with other strategies?
  • 14/03/2022, Jean-François Le Gall, Université Paris-Saclay. Brownian motion indexed by the Brownian tree. Abstract: The Brownian tree, also called Aldous’ CRT, is the universal scaling limit of large discrete random trees. Brownian motion indexed by the Brownian tree is obtained by assigning a real « label » to each point of the Brownian tree, in such a way that labels evolve like linear Brownian motion when moving along a segment of the tree. This model appears in the asymptotics of several random combinatorial objects, such as planar graphs or embedded trees. We will explain how one can develop an excursion theory for Brownian motion indexed by the Brownian tree and, if time permits, how this excursion theory applies to the Markovian properties of local times in this model.
  • 07/03/2022, Alexandre Gaudillière, CNRS. Spectral properties and applications of Kirchhoff’s forests. Abstract: Random spanning forests, which are efficiently sampled by Wilson’s algorithm, enjoy both abelian and integrability properties, expressed through Diaconis and Fulton’s representation and Kirchhoff’s theorem, respectively. We will present these properties together with a number of applications ranging from selecting well distributed nodes in a given network to performing spectral estimation for its associated Laplacian. This is based on a joint work with Pierre-Olivier Amblard, Luca Avena, Simon Barthelmé, Fabienne Castell, Clothilde Mélot, Matteo Quattropani and Nicolas Tremblay.
  • 21/02/2022, Takis Konstantopoulos, University of Liverpool. Longest and heaviest paths in random directed graphs. Abstract:I will give an overview of research in the area of random directed graphs with possibly random edge weights. We are interested in longest paths between two vertices (or heaviest paths if there are weights). Typically, the longest path satisfies a law of large numbers and a central limit theorem (which gives a non-normal distribution in the limit if the vertex set is not one-dimensional). The constant in the law of large numbers as a function of the graph parameters and weight distributions cannot be computed explicitly except, perhaps, in very simple cases. A lot of work has been done in obtaining bounds and in studying its behaviour. For example, is it a smooth function of the connectivity parameter p? These kinds of graphs appear in several areas: in computer science, in statistical physics, in performance evaluation of computer systems and in mathematical ecology. They originated in a paper by Barak and Erdos but have also been studied independently, in connection with the applications above. The questions asked are related to the so-called last passage percolation problems because we can interpret “longest” in a time sense (what’s the worst case road that will take us from a point to another point?). As such, it is not surprising that in some cases, the limiting behaviour is related to limits of large random matrices. However, the complete picture is not understood and so open problems will also be presented.
  • 14/02/2022, Umberto de Ambroggio, University of Bath. The probability of unusually large components in critical random graphs via ballot theorems. Abstract: We consider the classical Erdős-Rényi random graph as well as percolation on a random regular graph and provide matching upper and lower bounds for the probability of observing unusually large maximal components in these models when considered near criticality. We sketch the proof for the upper bounds, which is based on a ballot-type estimate (that could be of independent interest) for the probability that a random walk stays positive for n steps and finishes at some level j. We also present a simple, yet general result which yields polynomial upper bounds for the probability of observing large components in several models of random graphs when considered at criticality.
  • 07/02/2022, Samuel Mellick, ENS de Lyon. The cost of point processes. Abstract: Every invariant point process on a topological group has a numerical invariant associated to it, its cost. It has a simple and entirely probabilistic definition, and connections with many other invariants of interest to ergodic theorists. But results beyond the case of countable discrete groups remain scarce. If every aperiodic point process on a group has the same cost then it is said to have “fixed price”. In this talk I will describe joint work with Miklós Abért where we prove the first novel cases of nondiscrete groups with fixed price. No sophisticated knowledge of group theory or ergodic theory will be assumed
  • 1/01/2022, Nicolas Curien, Université Paris-Saclay. On the nearest neighbor tree. Abstract: Let points X_1,X_2, … be i.d.d. uniform over [0,1]^d. When a new point X_n arrives, it connects to the nearest point in X1,…,X_{n-1}. This forms a sequence of trees (T_n). If your are given the sequence of unlabeled tree (T_n), can you recover information about the underlying space, in particular the dimension d? If initially, two points are placed, called seeds and colored in red and blue, we color the points according to the color of its parent. We shall also look at the interfaces between the blue points and the red points answering a few conjectures of Aldous. Based on ongoing joint works with Jerome Casse and Alice Contat And with Anne-Laure Badesvant, Guillaume Blanc and Arvind Singh.
  • 24/01/2022, Senya Shlosman, Centre de Physique Theorique; Skoltech Center of Advanced Studies.The geometry of random contours and its impact on the correlations. Abstract: I will talk about the models of statistical physics which can be expressed as collections of random contours (such as the Ising model). Their geometric properties, such as entropic repulsion, are responsible for some interesting behavior of the underlying models. All this has to do with the correlation decay, the Gibbs measures, and the g-measures, which notions will be reminded of. Based on paper with A. van Enter, The Schonmann projection: how Gibbsian is it?https://arxiv.org/abs/2102.10622
  • 7/01/2022, Céline Comte, Eindhoven University of Technology. Stochastic Dynamic Matching in Graphs. Abstract: In this presentation, we will consider a stochastic dynamic matching model, in which items of different classes arrive according to independent Poisson processes, and compatibilities between items are described by an undirected graph on their classes. We will first focus on a specific matching policy called first-come-first-matched. Our main contribution is the observation that, under this policy, the matching model is equivalent to an order-independent (loss) queue, a model that has recently gained momentum in the queueing-theory literature. Using this equivalence, we will formulate simpler proofs for several existing results and derive closed-form expressions for performance metrics like the matching rate along an edge and the waiting probability of a class. In a second time, we will use results from graph theory and linear algebra to characterize the set of achievable matching rate vectors under any matching policy. The first part of this presentation is based on the paper “Stochastic non-bipartite matching models and order-independent loss queues” published in the journal Stochastic Models, Taylor & Francis (2022). The second part of this presentation is based on the recent preprint “Stochastic dynamic matching: a mixed graph-theory and linear-algebra approach” published in collaboration with Fabien Mathieu (LINCS) and Ana Busic (Inria and PSL University).
  • 06/12/2021, Mendes Oulamara, IHES. Rotational invariance of planar percolation. Abstract: We prove the asymptotic rotational invariance of the critical FK-percolation model on the square lattice with any cluster-weight between 1 and 4. These models are expected to exhibit conformally invariant scaling limits that depend on the cluster weight, thus covering a continuum of universality classes. The rotation invariance of the scaling limit is a strong indication of the wider conformal invariance, and may indeed serve as a stepping stone to the latter. Based on joint work with Hugo Duminil-Copin, Karol Kajetan Kozlowski, Dmitry Krachun and Ioan Manolescu.
  • 29/11/2021, Jean François Delmas, Ecole des Ponts ParisTech. Asymptotic for the cumulative distribution function of the degrees and homomorphism densities for random graphs sampled from a graphon. Abstract: We shall first recall the limits of large dense random networks, also called graphon, as well as the construction of (random) graphs sampled from graphon. It is known that homomorphism densities for the sampled graphs converge a.s. to those of the graphon (LLN). We shall give results on the corresponding fluctuation (CLT). We also provide the asymptotics for the fluctuation of the cumulative distribution function (CDF) for the degrees.
  • 22/11/2021, Tom Hutchcroft, California Institute of Technology. Supercritical percolation on finite transitive graphs. Abstract: In Bernoulli bond percolation, each edge of some graph are chosen to be either deleted or retained independently at random with retention probability p. For many large finite graphs, there is a phase transition such that if p is sufficiently large then there exists a giant cluster whose volume is proportional to that of the graph with high probability. We prove that in this phase the giant cluster must be unique with high probability: this was previously known only for tori and expander graphs via methods specific to those cases. Joint work with Philip Easo.
  • 08/11/2021, Adam Timar, University of Iceland and Renyi Institute, Budapest. Poisson factor matchings and allocations of optimal tail. Abstract: Consider two independent Poisson point processes of unit intensity in $\R^d$. Find a perfect matching between them that makes the distance between pairs decay as fast as possible (in the proper sense). We are interested in factor matching rules, meaning that every point can determine its pair using local information and using the same method. Some of the earlier matching schemes, such as the stable matching, are known to be far from optimal. The question of optimal tail for a matching was open until now, even though the analogous question for an allocation rule was solved. We will talk about this optimal allocation rule (joint work with Roland Marko) and a very recent development that has led to finding an optimal matching.
  • 25/10/2021, Ali Khezeli, Inria Paris. Stationary and Point-Stationary Circle Packings. Abstract: In the recent years, circle packing has been used in the study of unimodular planar graphs. I. Benjamini and A. Timar (2019) studied stationary circle packings, where the latter is a random circle packing of the plane such that its distribution is invariant under translations. They proposed the problem whether every unimodular planar graph can be represented by a stationary circle packing or not, and proved it only for CP-hyperbolic graphs. In this talk, first, a simple counterexample to this problem will be presented. Then, a natural weakening of the problem will be discussed: Can every unimodular planar graph be represented by a point-stationary circle packing? It is explained why this problem is natural and that it is related to the large-scale properties of the graph; e.g., the existence of a mean for the radii of the circles in the circle packing. Finally, two counterexamples will be presented with two different proof techniques: Using indistinguishability of level sets in an Eternal Galton-Watson tree and approximation by finite graphs (https://arxiv.org/abs/1912.12862).
  • 18/10/2021, Mendes Oulamara, IHES. From Free Energy Estimates to Large Scale Geometric Fluctuations of a Discrete Random Surface Model. Abstract : The six-vertex model, first introduced to model ice, has deep connections with many planar statistical physics models (the Ising model, dimers, percolation, loop O(n) models…). Its height function representation is a random function h:ZxZ -> Z such that the height of two neighbouring points differ by 1 or -1. It can hence be seen as a random discrete surface. Now, assume that one sets this function to be zero on the boundary of some planar domain D, how does the height fluctuate inside the domain? Is it typically flat or rough (i.e. it has unbounded variance)? In this joint work with Hugo Duminil-Copin, Alex Karrila and Ioan Manolescu, we show that estimates on the free energy of the model (that is, global information at the level of the partition function) can be translated into probabilistic statements on the geometry of the height function, and we deduce roughness in some range of parameters. (arxiv.org/abs/2012.13750)
  • 11/10/2021, Hermann Thorisson, University of Iceland. Embeddings into Brownian motion. Abstract: We outline a method of embedding patterns into the path of a two-sided Brownian motion. The patterns can for instance be a given distribution (the Skorokhod embedding), a particular type of excursion, or the Brownian bridge. The method is unbiased which means that conditionally on the pattern the one-sided processes developing backward and forward from the pattern are independent Brownian motions. The method relies on finding appropriate local times for the pattern. We expect the method to work also for embedding patterns in planar and spatial Brownian motion.

Comments are closed.