8 ALESSANDRO FIGA-TALAMANCA AND TIM STEGER

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

algebra

ll{G).

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 —

^i)~l

are algebraic

functions of the entries of /x, since (7 — /i)

_ 1

=

j~1(6e

— /i/7)

- 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

£l(G).

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 } .