Deviations of a random walk in a random scenery with stretched exponential tails

Let be a d-dimensional random walk in random scenery, i.e., with a random walk in and an i.i.d. scenery, independent of the walk. We assume that the random variables Yz have a stretched exponential tail. In particular, they do not possess exponential moments. We identify the speed and the rate of the logarithmic decay of for all sequences satisfying a certain lower bound. This complements results of Gantert et al. [Annealed deviations of random walk in random scenery, preprint, 2005], where it was assumed that Yz has exponential moments of all orders. In contrast to the situation (Gantert et al., 2005), the event {Zn>ntn} is not realized by a homogeneous behavior of the walk's local times and the scenery, but by many visits of the walker to a particular site and a large value of the scenery at that site. This reflects a well-known extreme behavior typical for random variables having no exponential moments.