Density-dependent stochastic resetting: a large deviations framework for achieving target distributions over networks
Francesco Coghi, Kristian Stølevik Olsen · 2024
Read Density-dependent stochastic resetting: a large deviations framework for achieving target distributions over networks by Francesco Coghi, Kristian Stølevik Olsen (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-10016.txt.
Introduction
Francesco Coghi and Kristian Stølevik Olsen built a framework in 2024 for steering crowds of random walkers on a network toward chosen patterns. Their tool is resetting: now and then a walker is sent back to a set spot, and here the rate of resetting depends on how crowded the local area is.
Crowd based resetting makes walkers affect each other even though they never interact directly. The framework covers both the path over time and the long run pattern. It can pick resetting rules that make a uniform spread, or other rare patterns, as likely as possible. The work uses large deviation theory, which prices how unlikely a given crowd pattern is.
Catalog record
| CREATOR | Francesco Coghi, Kristian Stølevik Olsen |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 67 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-10016
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Density-dependent stochastic resetting: a large deviations framework for achieving target distributions over networks Francesco Coghi, Kristian Stølevik Olsen Abstract We develop a framework for designing density-dependent stochastic resetting protocols to regulate distributions of random walkers on networks. Resetting mechanisms that depend on local densities induce correlations in otherwise non-interacting walkers. Our framework allows for the study of both transient trajectories and stationary properties and identifies resetting protocols that maximise the likelihood of homogeneous and, more generally, rare configurations of random walkers. Preprint: APS/123-QED I Introduction Networks arise across numerous scientific disciplines, ranging from social contact networks to transportation and resource distribution systems [ 1 , 2 , 3 , 4 ] . When explored through random walks [ 5 , 6 , 7 , 8 ] , these networks naturally reach steady states reflecting their heterogeneous structure—highly connected nodes may attract higher populations, leading to uneven distributions. In many practical scenarios, however, achieving a homogeneous distribution of resources across a network is desirable [ 9 , 8 , 10 , 11 ] . For example, in managing utility bicycles in a city, it is crucial to prevent overcrowding at specific locations and ensure their availability at other sites. A warehouse acting as a central stock point could facilitate redistribution by repeatedly resetting utility bicycles from clustered locations to the warehouse, and therefore favour a more balanced configuration across the network. Such strategies are particularly relevant when nodes have finite carrying capacities, where breaches could result in inefficiencies or detrimental effects. Here, we develop a novel framework to design stochastic resetting protocols that maximise the likelihood of achieving specific configurations, such as homogeneous distributions, despite underlying network heterogeneity. Our resetting mechanism is density-dependent, where the fraction of a population reset from a node depends on its local population. This introduces complex correlations among an otherwise non-interacting population of random walkers. Unlike traditional uses of resetting, which interrupts and re-starts stochastic trajectories [ 12 , 13 , 14 ] , our density-dependent approach leverages resetting to counteract certain network-induced dynamics and promote specific global configurations. To illustrate this, we study a resetting protocol where the resetting probability at a node scales as a power-law function of the node’s population density (see Fig. 1 ). On heterogeneous networks, we find optimal power-law exponents, \beta , that maximise the likelihood of achieving homogeneous configurations. Whether this optimal resetting scheme makes homogeneous states typical or just more likely to achieve depends on the network structure. Our framework is inspired by rare-event sampling techniques, such as genealogy algorithms [ 15 , 16 ] and cloning algorithms [ 17 , 18 , 19 , 20 ] , and leverages these methods to sample interesting rare events of the distribution of walkers over graphs. Additionally, our approach extends these techniques by incorporating the resetting mechanism, which potentially introduces an entirely new layer of control. The framework developed here allows for the study of both transient trajectories and long-time stationary properties of node occupation measures on graphs, addressing both dynamical pathways of the system and long-term averaged configurations that are especially relevant in practical applications where full control of the system is not possible. The paper is organised as follows: in Section II , we introduce the model of density-dependent resetting dynamics and describe both typical and stationary dynamics. Section III focuses on studying fluctuations of the resetting scheme to identify protocols that maximise the likelihood of specific atypical states, such as homogenous state occupancies. Finally, in Section IV , we apply the framework to illustrate how it achieves homogeneous distributions of walkers on a fully connected graph and a heterogeneous graph with non-uniform vertex connectivity. We conclude the paper with a summary and open questions in Section V . Figure 1: Schematics of the density-dependent resetting protocol. In a), how the probability of resetting p(\xi_{\ell}/\mathcal{N})^{\beta} from a node with population \xi_{\ell} changes at varying \beta . In b), a cartoon showing the desired effect of the density-dependent reset scheme at homogenising the walkers population over a graph. II Model of density-dependent reset dynamics II.1 Model We consider an ensemble of \mathcal{N} discrete-time random walks \left(X_{\ell}\right)^{(k)}_{0\leq\ell\leq n} , where k\in[1,\mathcal{N}] , exploring an undirected, unweighted graph G=(V,E) in n time steps. Here, V denotes a set of N vertices, while E represents the set of edges. At each discrete time step \ell , the state X_{\ell} takes a value in the vertex set V . All random walks in the ensemble adhere to the same transition dynamics defined by a transition matrix \Pi=\left\{\pi_{i,j}\right\}_{i,j\in V} . Specifically, the entry \pi_{i,j} represents the probability of transitioning from vertex i to vertex j at time \ell , given that the random walk was at vertex i at time \ell-1 . We further impose that a random walk can move from vertex i to vertex j only if i and j are directly connected in the graph G . This connectivity constraint is encoded using the adjacency matrix A=\left\{a_{i,j}\right\}_{i,j\in V} , where a_{i,j}=1 if (i,j)\in E , and a_{i,j}=0 otherwise. All \mathcal{N} random walks are initialised at time \ell=0 on a designated vertex s , referred to as the source node. In our motivating example, this source node functions similarly to a warehouse. At each time step, every random walk independently moves to an adjacent vertex according to the transition probabilities defined by the matrix \Pi . After each step, but before the subsequent time step begins, a fraction of the random walks occupying each vertex is reset to the source node. Previously, the effect of resetting on random walks on networks has been studied in the context of steady-states and first-passage times [ 21 , 22 ] , or resetting rules that depend on the network topology [ 23 , 24 , 25 , 26 ] . The resetting protocol we consider follows a power-law dependence on the number of walkers present at each occupied vertex. Let \eta_{\ell+1}(i) denote the number of random walks at vertex i at time \ell+1 . The update rule for \eta_{\ell+1}(i) is given by: \eta_{\ell+1}(i)=\xi_{\ell+1}(i)-p\left(\frac{\xi_{\ell+1}(i)}{\mathcal{N}}\right)^{\beta}\xi_{\ell+1}(i)+\delta_{i,s}\sum_{j\in V}p\left(\frac{\xi_{N,\ell+1}(j)}{\mathcal{N}}\right)^{\beta}\xi_{\ell+1}(j)\,, (1) where \xi_{\ell+1}(i)=\sum_{j\in\partial(i)}\eta_{\ell}(j)\pi_{j,i}\,, (2) represents the number of walkers that have moved from a neighbouring node of i to i in the time step \ell\rightarrow\ell+1 , viz. the occupation on node i before resetting takes place. The second term on the r.h.s. of ( 1 ) accounts for the number of walkers removed from vertex i due to the resetting process. These walkers are subsequently placed back at the source node i=s , as represented by the third and final term on the right-hand side of ( 1 ). The fraction of walkers at vertex i that is reset to the source node is given by p\left(\frac{\xi_{\ell+1}(i)}{\mathcal{N}}\right)^{\beta}\,, (3) where p\in[0,1] controls the resetting probability, and \beta\geq 0 modulates the non-linearity of the reset mechanism. This resetting rule introduces correlations into the dynamics of the random walks, as the probability of resetting depends on the local density of walkers at each vertex. To better understand the resetting mechanism, let us first examine the special case where \beta=0 . In this scenario, the fraction of walkers removed from vertex i at each time step remains constant at p , regardless of the number