  We introduce two natural notions of cogrowth for finitely generated
semigroups --- one local and one global --- and study their relationship with
amenability and random walks. We establish the minimal and maximal possible
values for cogrowth rates, and show that non-monogenic free semigroups are
exactly characterised by minimal global cogrowth. We consider the relationship
with cogrowth for groups and with amenability of semigroups. We also study the
relationship with random walks on finitely generated semigroups, and in
particular the spectral radius of the associated Markov operators (when
defined) on $\ell_2$-spaces. We show that either of maximal global cogrowth or
the weak F{\o}lner condition suffices for its spectral radius to be at least
$1$, since left amenability implies the weak F{\o}lner condition, this
represents a generalisation to semigroups of one implication of Kesten's
Theorem for groups. By combining with known results about amenability, we are
able to establish a number of new sufficient conditions for (left or right)
amenability in broad classes of semigroups. In particular, maximal local
cogrowth left implies amenability in any left reversible semigroup, while
maximal global cogrowth (which is a much weaker property) suffices for left
amenability in an extremely broad class of semigroups encompassing all inverse
semigroups, left reversible left cancellative semigroups and left reversible
regular semigroups.
