  We consider random walks on the set of all words over a finite alphabet such
that in each step only the last two letters of the current word may be modified
and only one letter may be adjoined or deleted. We assume that the transition
probabilities depend only on the last two letters of the current word.
Furthermore, we consider also the special case of random walks on free products
by amalgamation of finite groups which arise in a natural way from random walks
on the single factors. The aim of this paper is to compute several equivalent
formulas for the rate of escape with respect to natural length functions for
these random walks using different techniques.
