The Dirichlet problem at infinity for random walks on graphs with a strong isoperimetric inequality

Summary We study the spatial behaviour of random walks on infinite graphs which are not necessarily invariant under some transitive group action and whose transition probabilities may have infinite range. We assume that the underlying graphG satisfies a strong isoperimetric inequality and that the transition operatorP is strongly reversible, uniformly irreducible and satisfies a uniform first moment condition. We prove that under these hypotheses the random walk converges almost surely to a random end ofG and that the Dirichlet problem forP-harmonic functions is solvable with respect to the end compactification If in addition the graph as a metric space is hyperbolic in the sense of Gromov, then the same conclusions also hold for the hyperbolic compactification in the place of the end compactification. The main tool is the exponential decay of the transition probabilities implied by the strong isoperimetric inequality. Finally, it is shown how the same technique can be applied to Brownian motion to obtain analogous results for Riemannian manifolds satisfying Cheeger's isoperimetric inequality. In particular, in this general context new (and simpler) proofs of well known results on the Dirichlet problem for negatively curved manifolds are obtained.The first author was partially supported by Consiglio Nazionale delle Ricerche, GNAFA Current address: Department of Mathematics, University of Edinburgh, Edinburgh EH9 3JZ, Scotland