  The usual random walk on a group (homogeneous both in time and in space) is
determined by a probability measure on the group. In a random walk with random
transition probabilities this single measure is replaced with a stationary
sequence of measures, so that the resulting (random) Markov chains are still
space homogeneous, but no longer time homogeneous. We study various notions of
measure theoretical boundaries associated with this model and establish an
analogue of the Poisson formula for (random) bounded harmonic functions. Under
natural conditions on transition probabilities we identify these boundaries for
several classes of groups with hyperbolic properties and prove the boundary
triviality (i.e., the absence of non-constant random bounded harmonic
functions) for groups of subexponential growth, in particular, for nilpotent
groups.
