  We discuss relations between the amenability of a graph and spectral
properties of a random walk driven by a dynamical system. In order to include
graphs which are not locally compact, we introduce the concept of amenability
of weighted graphs, which generalises the usual notion as the new definition is
shown to be equivalent to Foelner's condition. As a first result, we obtain the
following generalisation of Kesten's amenability criterion to graphs and
non-independent increments: If the random walk is driven by a full-branched
Gibbs-Markov map, the graph is amenable with respect to the weight induced by
the random walk if and only if the spectral radius of the associated Markov
operator is equal to one. By employing inducing schemes, one then obtains
criteria for amenability through Markov maps with less regularity. We conclude
the paper with the following applications to Schreier graphs. If the random
walk is driven by an uniformly expanding map with non-Markovian increments,
then, under certain conditions, the Schreier graph is amenable if the
probability of a return in time n does not decay exponentially in n.
Furthermore, in the context of geometrically finite Kleinian groups, one
obtains a version of Brooks's amenability criterion for not necessarily normal
subgroups.
