A Hitting Time Formula for the Discrete Green's Function

作者：Beveridge Andrew^*

来源：Combinatorics Probability & Computing, 2016, 25(3): 362-379.

DOI：10.1017/S0963548315000152

The discrete Green's without boundary) G is a pseudo-inverse of the combinatorial Laplace operator of a graph G = (V, E). We reveal the intimate connection between Green's function and the theory of exact stopping rules for random walks on graphs. We give an elementary formula for Green's function in terms of state-to-state hitting times of the underlying graph. Namely, G(i, j) = pi(j)(H(pi, j) - H(i, j)), where pi(i) is the stationary distribution at vertex i, H(i, j) is the expected hitting time for a random walk starting from vertex i to first reach vertex j, and H(pi, j) = Sigma(k is an element of V) pi H-k(k,j). This formula also holds for the digraph Laplace operator.
The most important characteristics of a stopping rule are its exit frequencies, which are the expected number of exits of a given vertex before the rule halts the walk. We show that Green's function is, in fact, a matrix of exit frequencies plus a rank one matrix. In the undirected case, we derive spectral formulas for Green's function and for some mixing measures arising from stopping rules. Finally, we further explore the exit frequency matrix point of view, and discuss a natural generalization of Green's function for any distribution tau defined on the vertex set of the graph.

• 出版日期2016-5