Exact and approximate mean first passage times on trees and other necklace structures: a local equilibrium approach

Yanik-Pascal Förster; Luca Gamberi Gamberi; Evan Tzanis; Pierpaolo Vivo; Alessia Annibale

doi:10.1088/1751-8121/ac4ece

Exact and approximate mean first passage times on trees and other necklace structures: a local equilibrium approach

Yanik-Pascal Förster, Luca Gamberi Gamberi, Evan Tzanis, Pierpaolo Vivo^*, Alessia Annibale

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

4 Citations (Scopus)

46 Downloads (Pure)

Abstract

In this work we propose a novel method to calculate mean first-passage times (MFPTs) for random walks on graphs, based on a dimensionality reduction technique for Markov state models, known as local-equilibrium (LE). We show that for a broad class of graphs, which includes trees, LE coarse-graining preserves the MFPTs between certain nodes, upon making a suitable choice of the coarse-grained states (or clusters). We prove that this relation is exact for graphs that can be coarse-grained into a one-dimensional lattice where each cluster connects to the lattice only through a single node of the original graph. A side result of the proof generalises the well-known essential edge lemma (EEL), which is valid for reversible random walks, to irreversible walkers. Such a generalised EEL leads to explicit formulae for the MFPTs between certain nodes in this class of graphs. For graphs that do not fall in this class, the generalised EEL provides useful approximations if the graph allows a one-dimensional coarse-grained representation and the clusters are sparsely interconnected. We first demonstrate our method for the simple random walk on the c-ary tree, then we consider other graph structures and more general random walks, including irreversible random walks.

Original language	English
Article number	115001
Number of pages	33
Journal	Journal of Physics A
Volume	55
Issue number	11
DOIs	https://doi.org/10.1088/1751-8121/ac4ece
Publication status	Published - 18 Mar 2022

Keywords

mean first passage time, networks, random walks

Access to Document

10.1088/1751-8121/ac4eceLicence: CC BY

mfpts_necklace
I grant arXiv.org a perpetual, non-exclusive license to distribute this article. I certify that I have the right to grant this license. I understand that submissions cannot be completely removed once accepted. I understand that arXiv.org reserves the right to reclassify or reject any submission.
Accepted author manuscript, 2.94 MBLicence: Other

Cite this

@article{421bafc639704c3d8466a72a8f7415eb,

title = "Exact and approximate mean first passage times on trees and other necklace structures: a local equilibrium approach",

abstract = "In this work we propose a novel method to calculate mean first-passage times (MFPTs) for random walks on graphs, based on a dimensionality reduction technique for Markov state models, known as local-equilibrium (LE). We show that for a broad class of graphs, which includes trees, LE coarse-graining preserves the MFPTs between certain nodes, upon making a suitable choice of the coarse-grained states (or clusters). We prove that this relation is exact for graphs that can be coarse-grained into a one-dimensional lattice where each cluster connects to the lattice only through a single node of the original graph. A side result of the proof generalises the well-known essential edge lemma (EEL), which is valid for reversible random walks, to irreversible walkers. Such a generalised EEL leads to explicit formulae for the MFPTs between certain nodes in this class of graphs. For graphs that do not fall in this class, the generalised EEL provides useful approximations if the graph allows a one-dimensional coarse-grained representation and the clusters are sparsely interconnected. We first demonstrate our method for the simple random walk on the c-ary tree, then we consider other graph structures and more general random walks, including irreversible random walks.",

keywords = "mean first passage time, networks, random walks",

author = "Yanik-Pascal F{\"o}rster and Gamberi, {Luca Gamberi} and Evan Tzanis and Pierpaolo Vivo and Alessia Annibale",

note = "Funding Information: PV and ET acknowledge support from UKRI Future Leaders Fellowship scheme [No. MR/S03174X/1]. Y-PF is supported by the EPSRC Centre for Doctoral Training in Cross-disciplinary Approaches to Non-Equilibrium Systems (CANES EP/L015854/1). Publisher Copyright: {\textcopyright} 2022 The Author(s). Published by IOP Publishing Ltd.",

year = "2022",

month = mar,

day = "18",

doi = "10.1088/1751-8121/ac4ece",

language = "English",

volume = "55",

journal = "Journal of Physics A",

number = "11",

}

TY - JOUR

T1 - Exact and approximate mean first passage times on trees and other necklace structures: a local equilibrium approach

AU - Förster, Yanik-Pascal

AU - Gamberi, Luca Gamberi

AU - Tzanis, Evan

AU - Vivo, Pierpaolo

AU - Annibale, Alessia

N1 - Funding Information: PV and ET acknowledge support from UKRI Future Leaders Fellowship scheme [No. MR/S03174X/1]. Y-PF is supported by the EPSRC Centre for Doctoral Training in Cross-disciplinary Approaches to Non-Equilibrium Systems (CANES EP/L015854/1). Publisher Copyright: © 2022 The Author(s). Published by IOP Publishing Ltd.

PY - 2022/3/18

Y1 - 2022/3/18

N2 - In this work we propose a novel method to calculate mean first-passage times (MFPTs) for random walks on graphs, based on a dimensionality reduction technique for Markov state models, known as local-equilibrium (LE). We show that for a broad class of graphs, which includes trees, LE coarse-graining preserves the MFPTs between certain nodes, upon making a suitable choice of the coarse-grained states (or clusters). We prove that this relation is exact for graphs that can be coarse-grained into a one-dimensional lattice where each cluster connects to the lattice only through a single node of the original graph. A side result of the proof generalises the well-known essential edge lemma (EEL), which is valid for reversible random walks, to irreversible walkers. Such a generalised EEL leads to explicit formulae for the MFPTs between certain nodes in this class of graphs. For graphs that do not fall in this class, the generalised EEL provides useful approximations if the graph allows a one-dimensional coarse-grained representation and the clusters are sparsely interconnected. We first demonstrate our method for the simple random walk on the c-ary tree, then we consider other graph structures and more general random walks, including irreversible random walks.

AB - In this work we propose a novel method to calculate mean first-passage times (MFPTs) for random walks on graphs, based on a dimensionality reduction technique for Markov state models, known as local-equilibrium (LE). We show that for a broad class of graphs, which includes trees, LE coarse-graining preserves the MFPTs between certain nodes, upon making a suitable choice of the coarse-grained states (or clusters). We prove that this relation is exact for graphs that can be coarse-grained into a one-dimensional lattice where each cluster connects to the lattice only through a single node of the original graph. A side result of the proof generalises the well-known essential edge lemma (EEL), which is valid for reversible random walks, to irreversible walkers. Such a generalised EEL leads to explicit formulae for the MFPTs between certain nodes in this class of graphs. For graphs that do not fall in this class, the generalised EEL provides useful approximations if the graph allows a one-dimensional coarse-grained representation and the clusters are sparsely interconnected. We first demonstrate our method for the simple random walk on the c-ary tree, then we consider other graph structures and more general random walks, including irreversible random walks.

KW - mean first passage time, networks, random walks

UR - http://www.scopus.com/inward/record.url?scp=85125843995&partnerID=8YFLogxK

U2 - 10.1088/1751-8121/ac4ece

DO - 10.1088/1751-8121/ac4ece

M3 - Article

VL - 55

JO - Journal of Physics A

JF - Journal of Physics A

IS - 11

M1 - 115001

ER -

Exact and approximate mean first passage times on trees and other necklace structures: a local equilibrium approach

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this