Asymptotic entropy of the ranges of random walks on discrete groups

Inspired by Benjamini et al.(2010) and Windisch(2010),we consider the entropy of the random walk ranges Rnformed by the first n steps of a random walk S on a discrete group.In this setting,we show the existence of hR:=limn→∞H(Rn)/n called the asymptotic entropy of the ranges.A sample version of the above statement in the sense of Shannon(1948) is also proved.This answers a question raised by Windisch(2010).We also present a systematic characterization of the vanishing asymptotic entropy of the ranges.Particularly,we show that hR=0 if and only if the random walk either is recurrent or escapes to negative infinity without left jump.By introducing the weighted digraphs Γnformed by the underlying random walk,we can characterize the recurrence property of S as the vanishing property of the quantity limn→∞H(Γn)/n,which is an analogue of hR.