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 条
  • [41] Expected hitting times for random walks on quadrilateral graphs and their applications
    Huang, Jing
    Li, Shuchao
    LINEAR & MULTILINEAR ALGEBRA, 2018, 66 (12): : 2389 - 2408
  • [42] Convergence of mixing times for sequences of random walks on finite graphs
    Croydon, D. A.
    Hambly, B. M.
    Kumagai, T.
    ELECTRONIC JOURNAL OF PROBABILITY, 2012, 17 : 1 - 32
  • [43] Expected hitting times for random walks on weak products of graphs
    González-Arévalo, B
    Palacios, JL
    STATISTICS & PROBABILITY LETTERS, 1999, 43 (01) : 33 - 39
  • [44] Spanning trees from the commute times of random walks on graphs
    Qiu, Huaijun
    Hancock, Edwin R.
    IMAGE ANALYSIS AND RECOGNITION, PT 2, 2006, 4142 : 375 - 385
  • [45] Analytical results for the distribution of cover times of random walks on random regular graphs
    Tishby, Ido
    Biham, Ofer
    Katzav, Eytan
    JOURNAL OF PHYSICS A-MATHEMATICAL AND THEORETICAL, 2022, 55 (01)
  • [46] First passage time distribution in random walks with absorbing boundaries
    Nagar, A
    Pradhan, P
    PHYSICA A-STATISTICAL MECHANICS AND ITS APPLICATIONS, 2003, 320 : 141 - 148
  • [47] Random walks with shrinking steps: First-passage characteristics
    Rador, T
    Taneri, S
    PHYSICAL REVIEW E, 2006, 73 (03):
  • [48] Random walks on complex networks with first-passage resetting
    Huang, Feng
    Chen, Hanshuang
    PHYSICAL REVIEW E, 2021, 103 (06)
  • [49] Random Walks on Random Graphs
    Cooper, Colin
    Frieze, Alan
    NANO-NET, 2009, 3 : 95 - +
  • [50] Exact expressions of mean first-passage times and splitting probabilities for random walks in bounded rectangular domains
    Condamin, S.
    Benichou, O.
    JOURNAL OF CHEMICAL PHYSICS, 2006, 124 (20):
12345