An Explicit Formula of Hitting Times for Random Walks on Graphs

被引：0

作者：

Xu, Hao ^{[1
,2
]}

Yau, Shing-Tung ^{[3
]}

机构：

[1] Zhejiang Univ, Ctr Math Sci, Hangzhou 310027, Zhejiang, Peoples R China

[2] Univ Pittsburgh, Dept Math, Pittsburgh, PA 15260 USA

[3] Harvard Univ, Dept Math, Cambridge, MA 02138 USA

来源：

PURE AND APPLIED MATHEMATICS QUARTERLY | 2014年 / 10卷 / 03期

关键词：

Random walk; hitting time; spanning tree; DISCRETE GREENS-FUNCTIONS; CONNECTED GRAPH;

D O I：

暂无

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We prove an explicit formula of hitting times in terms of enumerations of spanning trees for random walks on general connected graphs. We apply the formula to improve Lawler's bound of hitting times for general graphs and derive closed formulas of hitting times for some special graphs.

引用

页码：567 / 581

页数：15

共 16 条

[1]

Aleliunas Romas., 1979, Proceedings of the 20th Symposium on Foundations of Computer Science (FOCS), P218, DOI [10.1109/SFCS.1979.34, DOI 10.1109/SFCS.1979.34]

[2]

[Anonymous], 1990, Random Structures and Algorithms, DOI 10.1002/rsa.3240010303

[3]

Chandra A. K., 1989, Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing, P574, DOI 10.1145/73007.73062

[4]

Chang X., PREPRINT

[5] The expected hitting times for graphs with cutpoints [J].

Chen, HY ;

Zhang, FJ .

STATISTICS & PROBABILITY LETTERS, 2004, 66 (01) :9-17

[6] Discrete Green's functions [J].

Chung, F ;

Yau, ST .

JOURNAL OF COMBINATORIAL THEORY SERIES A, 2000, 91 (1-2) :191-214

[7]

Chung Fan R. K., 2011, ADV LECT MATH ALM, V17

[8] A SPANNING TREE METHOD FOR BOUNDING HITTING TIMES OF RANDOM WALKS ON GRAPHS [J].

Cogill, Randy ;

Peng, Cheng .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 2010, 24 (03) :808-820

[9]

Feige U., 1996, Computational Complexity, V6, P341, DOI 10.1007/BF01270386

[10]

Georgakopoulos A., ARXIV13023212

← 1 2 →