Random Walks on Discrete Groups: Boundary and Entropy

The paper is devoted to a study of the exit boundary of random walks on discrete groups and related topics. We give an entropic criterion for triviality of the boundary and prove an analogue of Shannon's theorem for entropy, obtain a boundary triviality criterion in terms of the limit behavior of convolutions and prove a conjecture of Furstenberg about existence of a nondegenerate measure with trivial boundary on any amenable group. We directly connect Kesten's and Folner's amenability criteria by consideration of the spectral measure of the Markov transition operator. Finally we give various examples, some of which disprove some old conjectures.