Discrete Green's functions and random walks on graphs

被引：21

作者：

Xu, Hao ^{[1
]}

Yau, Shing-Tung ^{[1
]}

机构：

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

来源：

JOURNAL OF COMBINATORIAL THEORY SERIES A | 2013年 / 120卷 / 02期

关键词：

Discrete Green's functions; Random walks; Graphs; Hitting times; HITTING TIMES;

D O I：

10.1016/j.jcta.2012.10.002

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We prove an explicit formula of Chung-Yau's Discrete Green's functions as well as hitting times of random walks on graphs. The formula is expressed in terms of two natural counting invariants of graphs. Uniform derivations of Green's functions and hitting times for trees and other special graphs are given. (C) 2012 Elsevier Inc. All rights reserved.

引用

页码：483 / 499

页数：17

共 10 条

[1]

[Anonymous], 1997, CBMS REG C SER MATH

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

Chen, HY ;

Zhang, FJ .

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

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

Chung, F ;

Yau, ST .

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

[4]

Chung F, 2010, BOLYAI SOC MATH STUD, V20, P43

[5] COLLISIONS AMONG RANDOM-WALKS ON A GRAPH [J].

COPPERSMITH, D ;

TETALI, P ;

WINKLER, P .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 1993, 6 (03) :363-374

[6]

LOVASZ L, 1993, COMBINATORICS P ERDO, V2, P353

[7] On hitting times of random walks on trees [J].

Palacios, Jose Luis .

STATISTICS & PROBABILITY LETTERS, 2009, 79 (02) :234-236

[8]

Tetali P., 1991, Proceedings of the Tenth Annual ACM Symposium on Principles of Distributed Computing, P273, DOI 10.1145/112600.112623

[9]

Tetali P, 1994, COMB PROBAB COMPUT, V3, P421

[10]

Tetali P., 1991, J. Theor. Probab., V4, P101, DOI [DOI 10.1007/BF01046996, 10.1007/BF01046996]

← 1 →