A Chung–Lu random graph is an inhomogeneous Erdős–Rényi random graph in which vertices are assigned average degrees, and pairs of vertices are connected by an edge with a probability that is... Show moreA Chung–Lu random graph is an inhomogeneous Erdős–Rényi random graph in which vertices are assigned average degrees, and pairs of vertices are connected by an edge with a probability that is proportional to the product of their average degrees, independently for different edges. We derive a central limit theorem for the principal eigenvalue and the components of the principal eigenvector of the adjacency matrix of a Chung–Lu random graph. Our derivation requires certain assumptions on the average degrees that guarantee connectivity, sparsity and bounded inhomogeneity of the graph. Show less
We consider a spatial version of the classical Moran model with seed-banks where the constituentpopulations have finite sizes. Individuals live in colonies labelled by Zd , d ≥ 1, playing the... Show moreWe consider a spatial version of the classical Moran model with seed-banks where the constituentpopulations have finite sizes. Individuals live in colonies labelled by Zd , d ≥ 1, playing the roleof a geographic space, carry one of two types, ♥ or ♠, and change type via resampling as longas they are active. Each colony contains a seed-bank into which individuals can enter to becomedormant, suspending their resampling until they exit the seed-bank and become active again. Individualsresample not only from their own colony, but also from other colonies according to a symmetric randomwalk transition kernel. The latter is referred to as migration. The sizes of the active and the dormantpopulations depend on the colony and remain constant throughout the evolution.It was shown in den Hollander and Nandan (2021) that the spatial system is well-defined, admitsa family of equilibria parametrised by the initial density of type ♥, and exhibits a dichotomybetween clustering (mono-type equilibrium) and coexistence (multi-type equilibrium). This dichotomyis determined by a clustering criterion that is given in terms of the dual of the system, which consistsof a system of interacting coalescing random walks. In this paper we provide an alternative clusteringcriterion, given in terms of an auxiliary dual that is simpler than the original dual, and identify a rangeof parameters for which the criterion is met, which we refer to as the clustering regime. It turns out thatif the sizes of the active populations are non-clumping (i.e., do not take arbitrarily large values in finiteregions of the geographic space) and the relative strengths of the seed-banks (i.e., the ratio of the sizesof the dormant and the active population in each colony) are bounded uniformly over the geographicspace, then clustering prevails if and only if the symmetrised migration kernel is recurrent.The spatial system is hard to analyse because of the interaction in the original dual and theinhomogeneity of the colony sizes. By comparing the auxiliary dual with a non-interacting two-particlesystem, we are able to control the correlations that are caused by the interactions. The work in denHollander and Nandan (2021) and the present paper is part of a broader attempt to include dormancyinto interacting particle systems. Show less
In this paper, which is a culmination of our previous research efforts, we provide a general framework for studying mixing profiles of non-backtracking random walks on dynamic random graphs... Show moreIn this paper, which is a culmination of our previous research efforts, we provide a general framework for studying mixing profiles of non-backtracking random walks on dynamic random graphs generated according to the configuration model. The quantity of interest is the scaling of the mixing time of the random walk as the number of vertices of the random graph tends to infinity. Subject to mild general conditions, we link two mixing times: one for a static version of the random graph, the other for a class of dynamic versions of the random graph in which the edges are randomly rewired but the degrees are preserved. With the help of coupling arguments we show that the link is provided by the probability that the random walk has not yet stepped along a previously rewired edge.To demonstrate the utility of our framework, we rederive our earlier results on mixing profiles for global edge rewiring under weaker assumptions, and extend these results to an entire class of rewiring dynamics parametrised by the range of the rewiring relative to the position of the random walk. Along the way we establish that all the graph dynamics in this class exhibit the trichotomy we found earlier, namely, no cut-off, one-sided cut-off or two-sided cut-off.For interpolations between global edge rewiring, the only Markovian graph dynamics considered here, and local edge rewiring (i.e., only those edges that are incident to the random walk can be rewired), we show that the trichotomy splits further into a hexachotomy, namely, three different mixing profiles with no cut-off, two with one-sided cutoff, and one with two-sided cut-off. Proofs are built on a new and flexible coupling scheme, in combination with sharp estimates on the degrees encountered by the random walk in the static and the dynamic version of the random graph. Some of these estimates require sharp control on possible short-cuts in the graph between the edges that are traversed by the random walk. Show less
Chakrabarty, A.; Hazra, R.S.; Hollander, W.T.F. den; Sfragara, M. 2021
We consider an inhomogeneous Erdos-Renyi random graph G(N) with vertex set [N] = {1, . . . , N} for which the pair of vertices i, j is an element of [N], i not equal j, is connected by an edge with... Show moreWe consider an inhomogeneous Erdos-Renyi random graph G(N) with vertex set [N] = {1, . . . , N} for which the pair of vertices i, j is an element of [N], i not equal j, is connected by an edge with probability r (i/N + j/N), independently of other pairs of vertices. Here, r : [0, 1](2) -> (0, 1) is a symmetric function that plays the role of a reference graphon. Let lambda(N) be the maximal eigenvalue of the adjacency matrix of G(N). It is known that lambda(N)/N satisfies a large deviation principle as N -> infinity. The associated rate function psi(r) is given by a variational formula that involves the rate function I-r of a large deviation principle on graphon space. We analyse this variational formula in order to identify the properties of psi(r) , specially when the reference graphon is of rank 1. Show less
We consider a system of interacting Moran models with seed-banks. Individuals live in colonies and are subject to resampling and migration as long as they are active. Each colony has a seed-bank... Show moreWe consider a system of interacting Moran models with seed-banks. Individuals live in colonies and are subject to resampling and migration as long as they are active. Each colony has a seed-bank into which individuals can retreat to become dormant, suspending their resampling and migration until they become active again. The colonies are labelled by Z(d), d >= 1, playing the role of a geographic space. The sizes of the active and the dormant population are finite and depend on the location of the colony. Migration is driven by a random walk transition kernel. Our goal is to study the equilibrium behaviour of the system as a function of the underlying model parameters. In the present paper, under a mild condition on the sizes of the active populations, the system is well defined and has a dual. The dual consists of a system of interacting coalescing random walks in an inhomogeneous environment that switch between an active state and a dormant state. We analyse the dichotomy of coexistence (= multitype equilibria) versus clustering (= mono-type equilibria) and show that clustering occurs if and only if two random walks in the dual starting from arbitrary states eventually coalesce with probability one. The presence of the seed-bank enhances genetic diversity. In the dual this is reflected by the presence of time lapses during which the random walks are dormant and do not move. Show less
Dionigi, P.; Garlaschelli, D.; Hollander, W.T.F. den; Mandjes, M. 2021
For random systems subject to a constraint, the microcanonical ensemble requires the constraint to be met by every realisation ('hard constraint'), while the canonical ensemble requires the... Show moreFor random systems subject to a constraint, the microcanonical ensemble requires the constraint to be met by every realisation ('hard constraint'), while the canonical ensemble requires the constraint to be met only on average ('soft constraint'). It is known that for random graphs subject to topological constraints breaking of ensemble equivalence may occur when the size of the graph tends to infinity, signalled by a non-vanishing specific relative entropy of the two ensembles. We investigate to what extent breaking of ensemble equivalence is manifested through the largest eigenvalue of the adjacency matrix of the graph. We consider two examples of constraints in the dense regime: (1) fix the degrees of the vertices (= the degree sequence); (2) fix the sum of the degrees of the vertices (= twice the number of edges). Example (1) imposes an extensive number of local constraints and is known to lead to breaking of ensemble equivalence. Example (2) imposes a single global constraint and is known to lead to ensemble equivalence. Our working hypothesis is that breaking of ensemble equivalence corresponds to a non-vanishing difference of the expected values of the largest eigenvalue under the two ensembles. We verify that, in the limit as the size of the graph tends to infinity, the difference between the expected values of the largest eigenvalue in the two ensembles does not vanish for (1) and vanishes for (2). A key tool in our analysis is a transfer method that uses relative entropy to determine whether probabilistic estimates can be carried over from the canonical ensemble to the microcanonical ensemble, and illustrates how breaking of ensemble equivalence may prevent this from being possible. Show less
Avena, L.; Chino, Y.; Costa, C. de; Hollander, W.T.F. den 2019
In previous work by Avena and den Hollander [3], a model of a random walk in a dynamic random environment was proposed where the random environment is resampled from a given law along a given... Show moreIn previous work by Avena and den Hollander [3], a model of a random walk in a dynamic random environment was proposed where the random environment is resampled from a given law along a given sequence of times. In the regime where the increments of the resampling times diverge, which is referred to as the cooling regime, a weak law of large numbers and certain fluctuation properties were derived under the annealed measure, in dimension one. In the present paper we show that a strong law of large numbers and a quenched large deviation principle hold as well. In the cooling regime, the random walk can be represented as a sum of independent variables, distributed as the increments of a random walk in a static random environment over diverging periods of time. Our proofs require suitable multi-layer decompositions of sums of random variables controlled by moment bounds and concentration estimates. Along the way we derive two results of independent interest, namely, concentration inequalities for the random walk in the static random environment and an ergodic theorem that deals with limits of sums of triangular arrays representing the structure of the cooling regime. We close by discussing our present understanding of homogenisation effects as a function of the cooling scheme, and by hinting at what can be done in higher dimensions. We argue that, while the cooling scheme does not affect the speed in the strong law of large numbers nor the rate function in the large deviation principle, it does affect the fluctuation properties. Show less
Hollander, W.T.F. den; Majumdar, S.N.; Meylahn, J.M.; Touchette, T. 2019
We study the distribution of additive functionals of reset Brownian motion, a variation of normal Brownian motion in which the path is interrupted at a given rate and placed back to a given reset... Show moreWe study the distribution of additive functionals of reset Brownian motion, a variation of normal Brownian motion in which the path is interrupted at a given rate and placed back to a given reset position. Our goal is two-fold: (1) for general functionals, we derive a large deviation principle in the presence of resetting and identify the large deviation rate function in terms of a variational formula involving large deviation rate functions without resetting. (2) For three examples of functionals (positive occupation time, area and absolute area), we investigate the effect of resetting by computing distributions and moments, using a formula that links the generating function with resetting to the generating function without resetting. Show less
Synchronization of neurons forming a network with a hierarchical structure is essential for the brain to be able to function optimally. In this paper we study synchronization of phase oscillators... Show moreSynchronization of neurons forming a network with a hierarchical structure is essential for the brain to be able to function optimally. In this paper we study synchronization of phase oscillators on the most basic example of such a network, namely, the hierarchical lattice. Each site of the lattice carries an oscillator that is subject to noise. Pairs of oscillators interact with each other at a strength that depends on their hierarchical distance, modulated by a sequence of interaction parameters. We look at block averages of the oscillators on successive hierarchical scales, which we think of as block communities. In the limit as the number of oscillators per community tends to infinity, referred to as the hierarchical mean-field limit, we find a separation of time scales, i.e., each block community behaves like a single oscillator evolving on its own time scale. We argue that the evolution of the block communities is given by a renormalized mean-field noisy Kuramoto equation, with a synchronization level that depends on the hierarchical scale of the block community. We find three universality classes for the synchronization levels on successive hierarchical scales, characterized in terms of the sequence of interaction parameters. What makes our model specifically challenging is the non-linearity of the interaction between the oscillators. The main results of our paper therefore come in three parts: (I) a conjecture about the nature of the renormalisation transformation connecting successive hierarchical scales; (II) a truncation approximation that leads to a simplified renormalization transformation; (III) a rigorous analysis of the simplified renormalization transformation. We provide compelling arguments in support of (I) and (II), but a full verification remains an open problem. Show less
The mixing time of a random walk, with or without backtracking, on a random graph generated according to the configuration model on n n vertices, is known to be of order logn logn . In this paper,... Show moreThe mixing time of a random walk, with or without backtracking, on a random graph generated according to the configuration model on n n vertices, is known to be of order logn logn . In this paper, we investigate what happens when the random graph becomes dynamic, namely, at each unit of time a fraction α n αn of the edges is randomly rewired. Under mild conditions on the degree sequence, guaranteeing that the graph is locally tree-like, we show that for every ε∈(0,1) ε∈(0,1) the ε ε -mixing time of random walk without backtracking grows like 2log(1/ε)/log(1/(1−α n )) − − − − − − − − − − − − − − − − − − − − − √ 2log(1/ε)/log(1/(1−αn)) as n→∞ n→∞ , provided that lim n→∞ α n (logn) 2 =∞ limn→∞αn(logn)2=∞ . The latter condition corresponds to a regime of fast enough graph dynamics. Our proof is based on a randomised stopping time argument, in combination with coupling techniques and combinatorial estimates. The stopping time of interest is the first time that the walk moves along an edge that was rewired before, which turns out to be close to a strong stationary time. Show less
Berger, Q.; Hollander, W.T.F. den; Poisat, J. 2018
This paper considers an undirected polymer chain on , , with i.i.d. random charges attached to its constituent monomers. Each self-intersection of the polymer chain contributes an energy to the... Show moreThis paper considers an undirected polymer chain on , , with i.i.d. random charges attached to its constituent monomers. Each self-intersection of the polymer chain contributes an energy to the interaction Hamiltonian that is equal to the product of the charges of the two monomers that meet. The joint probability distribution for the polymer chain and the charges is given by the Gibbs distribution associated with the interaction Hamiltonian. The object of interest is the annealed free energy per monomer in the limit as the length n of the polymer chain tends to infinity.We show that there is a critical curve in the parameter plane spanned by the charge bias and the inverse temperature separating an extended phase from a collapsed phase. We derive the scaling of the critical curve for small and for large charge bias and the scaling of the annealed free energy for small inverse temperature. We argue that in the collapsed phase the polymer chain is subdiffusive, namely, on scale it moves like a Brownian motion conditioned to stay inside a ball with a deterministic radius and a randomly shifted center. We further expect that in the extended phase the polymer chain scales like a weakly self-avoiding walk.The scaling of the critical curve for small charge bias and the scaling of the annealed free energy for small inverse temperature are both anomalous. Proofs are based on a detailed analysis for simple random walk of the downward large deviations of the self-intersection local time and the upward large deviations of the range. Part of our scaling results are rough. We formulate conjectures under which they can be sharpened. The existence of the free energy remains an open problem, which we are able to settle in a subset of the collapsed phase for a subclass of charge distributions. Show less
Berg, M. van den; Bolthausen, E.; Hollander, W.T.F. den 2018