A long-time tail for random walk in random scenery

Consider a simple random walk on ^d whose sites are colored black or white independently with probabilityq, resp. 1–q. Walk and coloring are independent. Letn_k be the number of steps by the walk between itskth and (k+1) th visits to a black site (i.e., the length of itskth white run), and let_k =E(n_k)–q^–1. Our main result is a proof that (*) lim_k k^d/2_k = (1 –q)q^{d/2 – 2}(d/2)^d/2. Since it is known thatq^{– 1}_k =E(n₁n_{k + 1} B) –E(n₁ B)E(n_{k + 1} B), withB the event that the origin is black, (*) exhibits a long-time tail in the run length autocorrelation function. Numerical calculations of_k (1k100) ind=1, 2, and 3 show that there is an oscillatory behavior of_k for smallk. This damps exponentially fast, following which the power law sets in fairly rapidly. We prove that if the coloring is not independent, but is convex in the sense of FKG, then the decay of_k cannot be faster than (*).