Encounter times of random walkers with simultaneous resetting on networks
Pith reviewed 2026-05-09 23:11 UTC · model grok-4.3
The pith
Simultaneous resetting lets multiple random walkers on a network meet faster, with exact formulas from the transition-matrix spectrum.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
For the collective Markov process of multiple random walkers undergoing simultaneous resetting on a finite network, the mean first-encounter time admits an exact expression built from the eigenvalues and eigenvectors of the transition matrices of the reset-free dynamics. A general criterion on finite networks determines the resetting probabilities that reduce this mean time relative to the no-reset case and yield an optimal value.
What carries the argument
Spectral decomposition of the single-walker transition matrix, which supplies the closed-form mean first-encounter time once simultaneous resetting is imposed on the whole collection.
If this is right
- The mean first-encounter time can be evaluated from the spectrum without running trajectories.
- Nonzero resetting shortens encounter times only for targets that are close to the walkers' initial positions.
- Simultaneous resetting outperforms independent resetting on regular networks.
- On heterogeneous networks the advantage reverses and independent resetting can be faster.
Where Pith is reading between the lines
- The same spectral criterion could be applied to design collective search protocols on transportation or communication graphs.
- A hybrid scheme that sometimes resets walkers together and sometimes independently might combine the benefits observed in the two cases.
- The formulas remain valid for any diagonalizable transition matrix, including those arising from directed or weighted networks.
Load-bearing premise
The underlying process without resetting must be a Markov chain on a finite network whose transition matrix is diagonalizable.
What would settle it
Simulate two walkers on a four-node cycle with resetting probability 0.2, compute the empirical average time until they occupy the same node, and check whether it equals the value obtained from the eigenvalue sum.
Figures
read the original abstract
In this work, we study the dynamics of multiple random walkers on networks subject to a simultaneous resetting protocol, whereby all walkers are synchronously returned to their respective initial nodes. For this collective Markovian process, we derive exact analytical expressions for the mean first-encounter time, defined as the average time required for all walkers to meet for the first time at a given node. These results are formulated in terms of the eigenvalues and eigenvectors of the transition matrices governing the dynamics without resetting, providing a clear spectral interpretation of the impact of resetting on encounter processes. We further establish a general criterion for finite networks that determines when the introduction of a nonzero resetting probability reduces the mean first-encounter time and leads to an optimal resetting strategy. The theoretical predictions are illustrated through numerical results on regular and heterogeneous networks, for encounters involving two or more walkers, and for combinations of local and nonlocal dynamics. Our findings demonstrate that simultaneous resetting can significantly reduce encounter times for specific target nodes and initial conditions, while becoming ineffective for highly exploratory dynamics or distant targets. A comparison with independent resetting shows that simultaneous resetting is more efficient in homogeneous networks, whereas independent resetting can outperform it in heterogeneous structures, thereby revealing a trade-off between synchronization and exploration. The framework provides a unified approach to collective search and encounter problems on networks with resetting.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript examines multiple random walkers on finite networks undergoing simultaneous resetting to their initial positions. It derives exact closed-form expressions for the mean first-encounter time (MFET) to a target node in terms of the eigenvalues and eigenvectors of the individual walkers' transition matrices (without resetting), obtained via spectral decomposition of the joint Markov chain. A general criterion is given for when a nonzero resetting probability r reduces the MFET relative to the r=0 case and yields an optimal r. The results are illustrated numerically for two or more walkers on regular and heterogeneous networks, comparing simultaneous versus independent resetting and local versus nonlocal dynamics.
Significance. The spectral approach yields parameter-free analytical predictions for MFET under simultaneous resetting and identifies network-dependent trade-offs with independent resetting. The exact expressions and the optimality criterion constitute a unified framework for collective search problems; the numerical verification on both regular and heterogeneous graphs strengthens the claims. These tools are likely to be useful for analyzing resetting-enhanced encounter processes on networks.
minor comments (3)
- [§2] §2 (or wherever the joint transition matrix is introduced): the tensor-product construction of the unperturbed joint chain and the rank-one update for simultaneous resetting should be written explicitly, including the precise form of the resetting operator, to make the subsequent resolvent derivation fully self-contained.
- [§4] The optimality criterion (presumably in §4) is stated for finite networks; a short remark on whether the same spectral argument extends immediately to infinite or continuous-state limits would clarify the scope.
- [Numerical results section] Figure captions for the numerical panels should state the number of independent realizations used to estimate the MFET and whether the plotted points are averages or single-run values.
Simulated Author's Rebuttal
We thank the referee for their positive and accurate summary of our manuscript, as well as for recognizing the significance of the spectral approach and the optimality criterion for resetting. The recommendation for minor revision is noted. No specific major comments were raised in the report.
Circularity Check
No significant circularity
full rationale
The derivation relies on standard spectral decomposition of the joint Markov chain (tensor product of individual transition matrices) for the unperturbed dynamics, followed by a rank-one update for simultaneous resetting to obtain the mean first-encounter time via the fundamental matrix or resolvent in the same eigenbasis. These steps are self-contained applications of linear algebra to finite-state Markov chains with the stated diagonalizability assumption; no parameter is fitted to data and then renamed as a prediction, no self-citation supplies a load-bearing uniqueness theorem or ansatz, and the optimality criterion follows directly from comparing the resulting closed-form expressions. The numerical illustrations on example networks serve only as verification, not as inputs to the analytic results.
Axiom & Free-Parameter Ledger
free parameters (1)
- resetting probability r
axioms (2)
- domain assumption Dynamics without resetting obey a time-homogeneous Markov chain on a finite network
- domain assumption The transition matrix is diagonalizable
Reference graph
Works this paper leans on
-
[1]
accounts for the collective hops governed by the transition probabilities ˆW, while the second term rep- resents the resetting process to ⃗ r. Alternatively, the dy- namics under resetting can be described by the transition probability matrix ˆΠ (⃗ r;γ), defined as ˆΠ (⃗ r;γ) ≡ (1 − γ) ˆW +γ ˆΘ (⃗ r). (4) Here, ˆΘ (⃗ r) describes resetting to the nodes ⃗ r...
-
[2]
can be written in the more compact form P(⃗i, ⃗j,γ ;t + 1) = ∑ ⃗l∈V S P(⃗i, ⃗l,γ ;t) ˆΠ (⃗ r;γ)⃗l→ ⃗j . (6) B. Mean first encounter times The matrix ˆΠ (⃗ r;γ) fully characterizes the collective dynamics with resetting, ensuring that all walkers can visit every node of the network as long as the resetting probability satisfies 0 ≤ γ < 1. The matrix Π (⃗ r;γ...
-
[3]
has a direct analogy with the dynamics of a single walker [ 62]. This similarity al- lows for an analytical treatment of the problem of S non- interacting random walkers, particularly for calculating the mean number of steps required to first reach a given configuration. To this end, we begin by introducing a compact notation for the eigenvalues and eigenve...
-
[4]
we have, P(⃗i, ⃗j,γ ;t) = ⟨⃗i|ˆΠ (⃗ r;γ)t|⃗j⟩ = ∑ ⃗l∈V S ⟨⃗i|ˆΠ (⃗ r;γ)t|ψ ⃗l⟩⟨ ¯ψ ⃗l|⃗j⟩ = ∑ ⃗l∈V S ζt ⃗l ⟨⃗i ⏐ ⏐ψ ⃗l ⟩ ⟨ ¯ψ ⃗l ⏐ ⏐⃗j⟩. (13) 4 The stationary distribution is then given by P ∞ ⃗j (⃗i,γ ) ≡ lim T →∞ 1 T T∑ t=0 P(⃗i, ⃗j,γ ;t) = ∑ ⃗l∈V S δζ⃗l, 1 ⟨⃗i ⏐ ⏐ψ ⃗l ⟩ ⟨ ¯ψ ⃗l ⏐ ⏐⃗j⟩, (14) where only the largest eigenvalue ζ = 1 contributes in the lon...
-
[5]
We assume that each individual transition matrix W(s) is diagonalizable
in a more explicit way, involving the resetting probabilityγ. We assume that each individual transition matrix W(s) is diagonalizable. Under this assumption, we introduce the lth eigenvector of the walker s W(s)|φ (s) l ⟩ =λ (s) l |φ (s) l ⟩, s = 1, 2,...,S, (19) where {λ (s) l }N l=1 denote the eigenvalues of the transition matrix W(s), with the correspo...
-
[6]
( 1) for synchronous random walkers, the eigenvalues of ˆW are obtained as λ⃗l ≡ S∏ s=1 λ (s) ls
and ( 19), ˆW|φ⃗l⟩ =λ⃗l|φ⃗l⟩, (21) where, using the definition in Eq. ( 1) for synchronous random walkers, the eigenvalues of ˆW are obtained as λ⃗l ≡ S∏ s=1 λ (s) ls . (22) In addition, since the eigenvalues of W(s) satisfy |λ (s) ls | ≤ 1, it follows that |ζ⃗l| ≤ 1 for all ⃗l ∈ V S. To proceed further, we also need the set of left eigenvectors. For the i...
-
[7]
for the MFET ⟨T (⃗i, ⃗j,γ )⟩ of random walkers starting from the nodes⃗i and reaching simultaneously the target node ⃗j = (j,j,...,j ) for the first time, while being subject to stochastic resetting to the nodes ⃗ r, we obtain for ⃗i ̸=⃗j ⟨T (⃗i, ⃗j,γ )⟩ = 1 P ∞ ⃗j (⃗ r,γ) ∑ ⃗l∈I ⟨⃗j|φ⃗l⟩⟨ ¯φ⃗l |⃗j⟩ − ⟨⃗i|φ⃗l⟩⟨ ¯φ⃗l |⃗j⟩ 1 − (1 − γ)λ⃗l (29) valid for 0 < γ...
-
[8]
(36) Using the definition of z(⃗i, ⃗j,γ ) introduced in Eq
becomes z2(⃗i, ⃗j, 0)> 1 + 1 ⟨T (⃗i, ⃗j, 0)⟩ , ⃗i ̸=⃗j. (36) Using the definition of z(⃗i, ⃗j,γ ) introduced in Eq. ( 33), let us define Λ ≡ ⟨T 2(⃗i, ⃗j, 0)⟩ − ⟨T (⃗i, ⃗j, 0)⟩ 2 ⟨T (⃗i, ⃗j, 0)⟩ 2 − 1 ⟨T (⃗i, ⃗j, 0)⟩ − 1. (37) As a consequence of Eq. ( 36), the value taken by Λ in Eq. ( 37) for a given system determines whether the in- troduction of resettin...
-
[9]
from the spectral properties of ˆW is exposed in Appendix A. III. RESULTS In this section, we present numerical results illustrating the impact of simultaneous resetting on the mean first- encounter time of multiple random walkers. We focus on representative network topologies and initial conditions to elucidate the role of the resetting probability and th...
-
[10]
Figure 2(a) shows the network topology together with the initial nodes of the random walkers fixed to i1 = 1 and i2 = 5. In Fig. 2(b) we present ⟨T (i1,i 2;j,γ )⟩ as a function of γ, obtained by numerically evaluating Eq. ( 29) for j = 1, 2,...,N . The different nodes j in Fig. 2(a) [and their corre- sponding curves on Fig. 2(b)] are color-coded accord- ing...
-
[11]
as a function of j, which encapsu- lates the combined effect of the walkers’ initial positions and the encounter node. The relevance of Λ( i1,i 2;j) lies in the fact that, based on information on the dynamics without resetting only, it allows us to anticipate whether the introduction of resetting can reduce the encounter times. As shown by the inset, Λ( i1...
-
[12]
Further details on L´ evy flights and fractional transport on networks can be found in Refs
define a L´ evy flight, characterized by long-range hops in rings with wi→ j (α ) ∼ d− (1+2α ) ij for dij ≫ 1, where dij denotes the length of the short- est path between nodes i and j. Further details on L´ evy flights and fractional transport on networks can be found in Refs. [ 71–73]. Figure 5 illustrates the effect of combining two random- walk strategies...
-
[13]
M. R. Evans and S. N. Majumdar, Phys. Rev. Lett. 106, 160601 (2011)
work page 2011
-
[14]
M. R. Evans and S. N. Majumdar, J. Phys. A: Math. Theor. 44, 435001 (2011)
work page 2011
- [15]
-
[16]
M. R. Evans, S. N. Majumdar, and G. Schehr, J. Phys. A: Math. Theor. 53, 193001 (2020)
work page 2020
-
[17]
A. Pal, A. Kundu, and M. R. Evans, J. Phys. A: Math. Theor. 49, 225001 (2016)
work page 2016
- [18]
-
[19]
U. Bhat, C. D. Bacco, and S. Redner, J. Stat. Mech.: Theory Exp 2016, 083401 (2016)
work page 2016
- [20]
- [21]
- [22]
-
[23]
P. Juli´ an-Salgado, L. Dagdug, and D. Boyer, Phys. Rev. E 109, 024134 (2024)
work page 2024
-
[24]
S. N. Majumdar, S. Sabhapandit, and G. Schehr, Phys. Rev. E 91, 052131 (2015)
work page 2015
- [25]
-
[26]
S. Ray, D. Mondal, and S. Reuveni, J. Phys. A: Math. Theor. 52, 255002 (2019)
work page 2019
-
[27]
L. Kusmierz, S. N. Majumdar, S. Sabhapandit, and G. Sche hr, Phys. Rev. Lett. 113, 220602 (2014)
work page 2014
-
[28]
/suppress L. Ku´ smierz and E. Gudowska-Nowak,Phys. Rev. E 92, 052127 (2015)
work page 2015
-
[29]
/suppress L. Ku´ smierz and E. Gudowska-Nowak,Phys. Rev. E 99, 052116 (2019)
work page 2019
-
[30]
A. Mas´ o-Puigdellosas, D. Campos, and V. M´ endez, Phys. Rev. E 99, 012141 (2019)
work page 2019
-
[31]
M. E. J. Newman, Networks: An Introduction (Oxford University Press, Oxford, 2010)
work page 2010
-
[32]
Barab´ asi,Network Science (Cambridge University Press, Cambridge, 2016)
A.-L. Barab´ asi,Network Science (Cambridge University Press, Cambridge, 2016)
work page 2016
- [33]
-
[34]
Van Mieghem, Graph Spectra for Complex Networks (Cambridge University Press, New York, 2011)
P. Van Mieghem, Graph Spectra for Complex Networks (Cambridge University Press, New York, 2011)
work page 2011
-
[35]
B. D. Hughes, Random Walks and Random Environments: Vol. 1: Random Walks (Oxford University Press, New York, 1995)
work page 1995
-
[36]
Lov´ asz, in Combinatorics, Paul Erd˝ os is Eighty, Vol
L. Lov´ asz, in Combinatorics, Paul Erd˝ os is Eighty, Vol. 2, edited by D. Mikl´ os, V. T. S´ os, and T. Sz˝ onyi (J´ anos Bolyai Mathematical Society, Budapest, 1996) pp. 353–398
work page 1996
- [37]
-
[38]
J. D. Noh and H. Rieger, Phys. Rev. Lett. 92, 118701 (2004)
work page 2004
-
[39]
V. Tejedor, O. B´ enichou, and R. Voituriez, Phys. Rev. E 80, 065104(R) (2009)
work page 2009
- [40]
-
[41]
K. Avrachenkov, R. van der Hofstad, and M. Sokol, in Algorithms and Models for the Web Graph , edited by A. Bonato, F. C. Graham, and P. Pra/suppress lat (Springer, Cham, 2014) pp. 23–33
work page 2014
-
[42]
K. Avrachenkov, A. Piunovskiy, and Y. Zhang, Methodol. Comput. Appl. Probab. 20, 1173 (2018)
work page 2018
-
[43]
D. C. Rose, H. Touchette, I. Lesanovsky, and J. P. Garrah an, Phys. Rev. E 98, 022129 (2018)
work page 2018
-
[44]
A. P. Riascos, D. Boyer, P. Herringer, and J. L. Mateos, Phys. Rev. E 101, 062147 (2020)
work page 2020
- [45]
- [46]
-
[47]
O. L. Bonomo and A. Pal, Phys. Rev. E 103, 052129 (2021)
work page 2021
-
[48]
F. H. Gonz´ alez, A. P. Riascos, and D. Boyer, Phys. Rev. E 103, 062126 (2021)
work page 2021
- [49]
-
[50]
A. P. Riascos, D. Boyer, and J. L. Mateos, J. Phys. A: Math. Theor. 55, 274002 (2022)
work page 2022
-
[51]
T. M. Michelitsch, G. D’Onofrio, F. Polito, and A. P. Ria scos, Chaos 35, 013119 (2025)
work page 2025
-
[52]
T. Weng, J. Zhang, M. Small, and P. Hui, Phys. Rev. E 95, 052103 (2017)
work page 2017
-
[53]
A. P. Riascos and J. L. Mateos, PLOS ONE 12, e0184532 (2017)
work page 2017
-
[54]
R. Mastrandrea, J. Fournet, and A. Barrat, PLOS ONE 10, e0136497 (2015)
work page 2015
-
[55]
R. Pastor-Satorras and A. Vespignani, Phys. Rev. Lett. 86, 3200 (2001)
work page 2001
-
[56]
L. D. Valdez, L. A. Braunstein, and S. Havlin, Phys. Rev. E 101, 032309 (2020)
work page 2020
-
[57]
M. Bestehorn, A. P. Riascos, T. M. Michelitsch, and B. A. Collet, Contin. Mech. Thermodyn. 33, 1207 (2021)
work page 2021
-
[58]
T. Granger, T. M. Michelitsch, M. Bestehorn, A. P. Riasc os, and B. A. Collet, Entropy 26, 362 (2024)
work page 2024
-
[59]
L. Giuggioli, S. P´ erez-Becker, and D. P. Sanders, Phys. Rev. Lett. 110, 058103 (2013)
work page 2013
-
[60]
M. E. Craft, Philos. Trans. R. Soc. Lond., B, Biol. Sci. 370, 20140107 (2015)
work page 2015
-
[61]
V. Kishore, M. S. Santhanam, and R. E. Amritkar, Phys. Rev. Lett. 106, 188701 (2011)
work page 2011
-
[62]
L. Dai, M. Dai, Y. Huang, Y. Li, J. Shen, H. Chi, and W. Su, Physica A 541, 123352 (2020) . 19
work page 2020
-
[63]
T. Weng, J. Zhang, M. Small, B. Harandizadeh, and P. Hui, Phys. Rev. E 97, 032320 (2018)
work page 2018
-
[64]
D. P. Sanders, Phys. Rev. E 80, 036119 (2009)
work page 2009
-
[65]
A. P. Riascos and D. P. Sanders, Phys. Rev. E 103, 042312 (2021)
work page 2021
-
[66]
T. Weng, J. Zhang, M. Small, and P. Hui, EPL 119, 48006 (2017)
work page 2017
-
[67]
T. Weng, J. Zhang, M. Small, H. Yang, and P. Hui, Chaos 28, 083109 (2018)
work page 2018
-
[68]
D. Rubio-G´ omez, A. P. Riascos, and J. L. Mateos, J. Phys. A: Math. Theor. 58, 325003 (2025)
work page 2025
- [69]
- [70]
- [71]
- [72]
- [73]
-
[74]
A. P. Riascos and J. L. Mateos, J. Complex Netw. 9, cnab032 (2021)
work page 2021
- [75]
- [76]
-
[77]
A. Pal, S. Kostinski, and S. Reuveni, J. Phys. A: Math. Theor. 55, 021001 (2022)
work page 2022
-
[78]
Random resetting i n search problems,
A. Pal, V. Stojkoski, and T. Sandev, “Random resetting i n search problems,” in Target Search Problems , edited by D. Grebenkov, R. Metzler, and G. Oshanin (Springer Nature Sw itzerland, Cham, 2024) pp. 323–355
work page 2024
- [79]
- [80]
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.