Cutpoint decoupling and first passage times for random walks on graphs

被引：12
|
作者：
Kirkland, SJ [1 ]
Neumann, M
机构：
[1] Univ Regina, Dept Math & Stat, Regina, SK S4S 0A2, Canada
[2] Univ Connecticut, Dept Math, Storrs, CT 06269 USA
来源：
SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS | 1999年 / 20卷 / 04期
关键词：
Markov chains; first passage times; random walks; cutpoint graphs;
D O I：
10.1137/S0895479897318800
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
One approach to the computations for Markov chains, due to Meyer, is to break a problem down into corresponding computations for several related chains involving a smaller number of states. In this spirit, we focus on the mean first passage matrix associated with a random walk on a connected graph, and consider the problem of transforming the computation of that matrix into smaller tasks. We show that this is possible when there is a cutpoint in the graph and provide an explicit formula for the mean first passage matrix when this is the case.
引用
收藏
页码：860 / 870
页数：11
相关论文
共 50 条
  • [31] First-passage exponents of multiple random walks
    Ben-Naim, E.
    Krapivsky, P. L.
    JOURNAL OF PHYSICS A-MATHEMATICAL AND THEORETICAL, 2010, 43 (49)
  • [32] First-passage properties of bursty random walks
    Volovik, D.
    Redner, S.
    JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT, 2010,
  • [33] Linking the mixing times of random walks on static and dynamic random graphs
    Avena, Luca
    Guldas, Hakan
    van Der Hofstad, Remco
    den Hollander, Frank
    Nagy, Oliver
    STOCHASTIC PROCESSES AND THEIR APPLICATIONS, 2022, 153 : 145 - 182
  • [34] First Passage Time for Random Walks in Heterogeneous Networks
    Hwang, S.
    Lee, D. -S.
    Kahng, B.
    PHYSICAL REVIEW LETTERS, 2012, 109 (08)
  • [35] Convergence of blanket times for sequences of random walks on critical random graphs
    Andriopoulos, George
    COMBINATORICS PROBABILITY AND COMPUTING, 2023, 32 (03) : 478 - 515
  • [36] First passage and first hitting times of Levy flights and Levy walks
    Palyulin, Vladimir V.
    Blackburn, George
    Lomholt, Michael A.
    Watkins, Nicholas W.
    Metzler, Ralf
    Klages, Rainer
    Chechkin, Aleksei V.
    NEW JOURNAL OF PHYSICS, 2019, 21 (10):
  • [37] Everlasting impact of initial perturbations on first-passage times of non-Markovian random walks
    Levernier, N.
    Mendes, T., V
    Benichou, O.
    Voituriez, R.
    Guerin, T.
    NATURE COMMUNICATIONS, 2022, 13 (01)
  • [38] Everlasting impact of initial perturbations on first-passage times of non-Markovian random walks
    N. Levernier
    T. V. Mendes
    O. Bénichou
    R. Voituriez
    T. Guérin
    Nature Communications, 13
  • [39] FIRST PASSAGE PERCOLATION ON INHOMOGENEOUS RANDOM GRAPHS
    Kolossvary, Istvan
    Komjathy, Julia
    ADVANCES IN APPLIED PROBABILITY, 2015, 47 (02) : 589 - 610
  • [40] Hitting Times of Random Walks on Edge Corona Product Graphs
    Zhu, Mingzhe
    Xu, Wanyue
    Li, Wei
    Zhang, Zhongzhi
    Kan, Haibin
    COMPUTER JOURNAL, 2024, 67 (02): : 485 - 497
12345