Random spanning trees of Cayley graphs and an associated compactification of semigroups

A sequential construction of a random spanning tree for the Cayley graph of a finitely generated, countably infinite subsemigroup V of a group G is co nsidered. At stage n, the spanning tree T is approximated by a finite tree T-n rooted at the identity. The approximation Tn+1 is obtained by connectin g edges to the points of V that are not already vertices of T-n but can be obtained from vertices of T-n via multiplication by a random walk step taki ng values in the generating set of V. This construction leads to a compacti fication of the semigroup V in which a sequence of elements of V that is no t eventually constant is convergent if the random geodesic through the span ning tree T that joins the identity to the n(th) element of the sequence co nverges in distribution as n --> infinity. The compactification is identifi ed in a number of examples. Also, it is shown that if h(T-n) and #(T-n) den ote, respectively, the height and size of the approximating tree T-n, then there are constants 0 < c(h) less than or equal to 1 and 0 less than or equ al to c(#) less than or equal to log2 such that lim(n-->infinity) n(-1) h(T -n) = c(h) and lim(n-->infinity) n(-1) log#(T-n) = c(#) almost surely.