Note that if x G G, then d(x, e) (with respect to the Cayley graph) is equal
to the length of x as a reduced word in the generators. In general we have
d(x, y) =
where | | denotes the length of a reduced word.
We introduce here some notation associated with G. We shall be interested
in the function spaces
0(G) = {/: G - C; ||/||p = ( £ |/(x)|") ' oo}. .
The group G acts on these spaces according to (x f)(y) =
and this
representation is called the {left) regular representation. When
this representation is unitary. If 6X G
is given by
then x / = 6X* f. Sometimes we write 6xy with the same meaning as Sx(y).
is a convolution algebra with 6e as the identity. All the above
applies to any discrete group.
A random walk on G is defined by giving an infinite matrix R = (R(y, x))y,xeG
with nonnegative coefficients, satisfying ^ZyR(y^x) = 1. The random walk is
called symmetric if R(x, y) = R(y, x) for all x and y.
The number R(y, x) represents the probability of taking a step from x to y.
The matrix R = (R(y,x)) is called the transition matrix of the random walk.
Observe that the conditions R(y, x) 0 and ]Ty R(y, x) = 1 imply that we can
define the powers of R as infinite matrices
^2tRn~1(y,t)R(t,x). Induction shows that
]"(*,, x) =
J ^ J T * - 1
(»,*)*(*,*) =
y y t
The number Rn(y, x) represents the probability of going from x to y in n steps.
The conditions R(y, x) 0 and ^ R(y, x) 1 imply that the matrix R
defines a bounded linear operator on ^{G); (Rf)(y) = ^2X R{y'»x)
We say that the random walk R is G-invariant if R{ty,tx) = R(y,x) for all
x,y,t G G. A G-invariant random walk may also be invariant for other isometries
of the tree. An important special case is that of a random walk which is invariant
with respect to any isometry. In the latter case R(y, x) will depend only on ^he
distance between x and y. Such a random walk is called isotropic.
From now on we consider only G-invariant random walks. Define a probability
measure \i on G by \±{x) R(x,e). Since R is G-invariant, R(y,x) =
and Rf(y) = ^2X
= (/ fi)(y). Moreover if
denotes the n-th
convolution power of /x, then the coefficients of Rn are jin{x~ly). A G-invariant
Previous Page Next Page