random walk is symmetric if and only if the measure \i is symmetric, that is, if
and only if fi(x) = //(x - 1 ).
We say that the random walk defined by the matrix R is a nearest neighbor
random walk if R(y, x) = 0, whenever d(x, y) ^ 1. In particular, according to our
definition, R(x, x) 0 for a nearest neighbor random walk. If R is G-invariant
and nearest neighbor, then fi is supported on the generators {ai,--- , a
g +
i } .
Since a^ = e, fi necessarily satisfies /i(x) = /x(x_1). Therefore a G-invariant
nearest neighbor random walk is necessarily symmetric. The resolvent or Green
function, (7 it!)-1, of the operator R is of great interest. For large 7, (7 R)~x
is right convolution with (7 —/x)_1, where (7 —/x)_1 is defined in the convolution
The resolvent can be computed explicitly for a nearest neighbor
random walk. However, it is worthwhile to consider first the calculation of the
resolvent in the more general case where \i is finitely supported; i.e., when the
random walk takes steps of bounded length. In Sections 4 and 5 we shall show
that under these hypotheses (7 /i)~1(x) is an algebraic function of 7.
If the support of \i is fixed as some particular finite subset of G, then the
entries of (7 /i)
_ 1
are in fact algebraic functions (jointly) of 7 and the entries
of /1. For our purposes, algebraicity with respect to 7 is the main point. One
may as well read the proof as a proof that the entries of (6e
are algebraic
functions of the entries of /x, since (7 /i)
_ 1
- 1
We mention here that the isotropic nearest neighbor random walk is called
the simple random walk. The resolvent (7 fi)~l(x) for the simple random
walk is a constant multiple of q~z\x\ where z is a complex number satisfying
7 (QZ + Ql~z)/(q+l)- The theory of representations of finitely generated free
groups described in [FT-Pil] depends strongly on this formula for the resolvent.
2. The Method of Paths
For the time being assume only that R = (R(y, x))y,xeG is an arbitrary matrix
defining a bounded linear operator on
This assumption is clearly satisfied
if R(y,x) = n(x~ly) where fi is a probability measure on G. The method of
paths gives a useful formula for the resolvent of the matrix R. We start with a
few definitions.
(2.1) Definition. Let x,y e G and let B be any subset of G. An n-path
from x to y is any sequence of n -f 1 elements of G, (xn, ,#o) £ G
n + 1
, such
that XQ = x and xn = y. We say that the path (xni , #o) stops at B if Xj £ B,
for 0 j n and xn G B. We denote by 7rn(y, x; B) the set of n-paths from x
to y which stop at B. That is,
7rn(y,x;B) = {(xn,--- ,x0) e G
n + 1
; x0 = x, xn = y,
Xj £ B, for 0 j n, xn G B } .
Previous Page Next Page