On random walks on discrete solvable groups

by Waldemar Hebisch

Introduction

This paper is concerned with the decay of p_{n}(e) for symmetric random walk on discrete solvable group G of exponential growth. Previous results in [1], [3], [4], [6], [7], [8] shows that on Lie groups one has polynomial decay or decay of type exp(−n^{1/3}) and that this remains true for polycyclic groups. Morover there is rather general estimate from above of the similar type. So one may conjecture that such a type of decay is correct for all solvable groups of exponential growth. We are going to show that in fact on discrete solvable groups much faster decay is possible. One may also notice that our groups have no finite presentation. As only groups with finite presentations can occur in geometric problems it would be nice to handle those, however we leave this problem open.

Note Our results seem to be a particular case of results from [5]. While [5] covers more topics and the technical details are different the idea for getting both lower and upper bound is the same. Morover, in [5] it is pointed out that one may modify the example to get finitely presented solvable groups with ”fast” decay of p_{n}(e).

Results

Let G_{d} be the semidirect product of Z^{d} and Z^{Z^{d}} and p_{n} be the simple random walk on G_{d}. We will call the Z^{d} part H. Then an element of G is a pair (h, f) with h ∈ H and f beeing integer valued function on H taking only finitely many values different from 0. In the sequel we will denote by F the set of all such f. H acts on F by translations (we define translations by the formula (T (h)f)(x) = f(xh)). Multiplication on G is given by the formula

(h_{1}, f_{1})(h_{2}, f_{2}) = (h_{1}h_{2}, T (h_{2}^{−1})f_{1} + f_{2}).

Let A_{h} be a subgroup of G consisting of pairs (0, f) with f(x) = 0 for x ≠ h. Of course A_{h} is isomorphic to Z. Note that T (h)^{−1}A_{e} = A_{h}. We choose (δ_{k}, 0), k = 1, …, d and (0, δ_{0}) as generators of G_{d}. Then, the probability distribution p_{1} is given by

p_{1}((±δ_{k}, 0)) = p_{1}((0, ±δ_{0})) = \frac{1}{2(d + 1)}.

As usual, p_{n} is the n-th convolution power of p_{1}.

(1.1). Theorem. For every d there exist C and c > 0 such that for all n

c exp(−Cn^{d/(d+2)} log n) ≤ p_{2n}(e) ≤ C exp(−cn^{d/(d+2)}).

There exist G and p_{1} such that for every ϵ > 0 p_{n}(e) decays faster then exp(−n^{1−ϵ}).

(1.2). Theorem. Let Z and Y be random variables with values in A_{e} and H respectively. Assume that Z and Y are symmetric, have finite second moment, P (Z = 0) > 0, and that the values of Z (Y resp.) generate A_{e} (H resp.). Let Z_{j} and Y_{j} be independent random variables, Z_{j} have the same distribution as Z and Y_{j} have the same distribution as Y. Then there is c > 0 such that

c exp(−c^{−1} log(n)n^{d/d+2}) ≤ sup_{g∈G} P (∏_{j=1}^{n}(Y_{j}Z_{j}) = g) ≤ exp(−cn^{d/d+2}).

P. Note that Y_{j}Z_{j} = (Y_{j}, Z_{j}) and

∏_{j=1}^{n}(Y_{j}, Z_{j}) = (∏_{j=1}^{n} Y_{j}, ∏_{j=1}^{n} T^{−1}( ∏_{l=j+1}^{n} Y_{j})Z_{j})

sup_{g∈G} P (∏_{j=1}^{n}(Y_{j}Z_{j}) = g) ≤ sup_{f∈F} P (∏_{j=1}^{n} T^{−1}( ∏_{l=j+1}^{n} Y_{l})Z_{j} = f).

Since F is commutative

(1)  ∏_{j=1}^{n} T^{−1}( ∏_{l=j+1}^{n} Y_{l})Z_{j} = ∏_{h∈H} T^{−1}(h) ∏ ; h=∏_{l=j+1}^{n} Y_{l} Z_{j}

Since T^{−1}(h)Z_{j} takes values in A_{h}, the first product above is simply a cartesian produkt (of independent variables). Morover, on each axis we may apply to Z_{j} the central limit theorem, so

P (∏_{j=1}^{n} T^{−1}( ∏_{l=j+1}^{n} Y_{l})Z_{j} = f) = E( ∏_{h∈H} P (∏_{j=1}^{n_{h}} Z_{j} = f(h)))

≤ E( ∏_{h∈H}(1 + cn_{h})^{−1/2}) ≤ E(exp(−c̃|{h ∈ H : n_{h} > 0}|))

where n_{h} is the number of j such that h = ∏_{l=j+1}^{n} Y_{l}. By [2]

E(exp(−c̃|{h ∈ H : n_{h} > 0}|)) ≤ exp(−cn^{d/(d+2)}).

Similarly

P (∏_{j=1}^{n}(Y_{j}, Z_{j}) ∈ H) = P (∏_{j=1}^{n} T^{−1}( ∏_{l=j+1}^{n} Y_{l})Z_{j} = 0) ≥ E( ∏_{h∈H}(1 + cn_{h})^{−1/2})

≥ E(exp(−c_{0} log(2 + n)|{h ∈ H : n_{h} > 0}|))
≥ E(exp(−c_{0}|{h ∈ H : n_{h} > 0}|))^{log(2+n)}
≥ c exp(−c_{1}n^{d/(d+2)})^{log(2+n)}

where the last inequality follows from [2]. Next, since Y is symmetric E(Y) = 0 and E(| ∏_{j=1}^{n} Y_{j}|^{2}) ≤ Cn. Put

ϕ(x) = c exp(−c_{1}x^{d/(d+2)})^{log(2+x)}

nad let r be the smallest such that Cnr^{−2} ≤ 1/2ϕ(n). Then r ≤ \frac{C_{3}}{ϕ(n)} and

P (| ∏_{j=1}^{n} Y_{j}| > r) ≤ 1/2ϕ(n)

so with probability at least 1/2ϕ(n) the product ∏_{j=1}^{n}(Y_{j}, Z_{j}) takes a value in the ball centered at 0 and of radius r in H. This ball has C_{4}r^{d} elements, so the maximal probability is at least

1/2ϕ(n)/(C_{4}r^{d}) ≥ C_{5}ϕ(n)^{d+1}

which differs from ϕ only because of constants.

P. of (1.1) : Let X be a random variable with distributon p_{1} and let Y nad Z be (independent) random variables such that

P (Z = (0, ±δ_{0})) = 1/2 P (Y = (±δ_{k}, 0) = 1/2d k = 1, …, d.

We consider X as a mixture of random variables Y and Z, that is X equals Y with probability d/(d + 1), otherwise X equals Z. Next, let X_{i} (or Y_{i} or Z_{i}) be independent random variables with the same distribution as X (resp. Y or Z). Consequently, we treat ∏_{i=1}^{n} X_{i} as a product of Y_{i} and Z_{i} (with random choice between Y_{i} and Z_{i}). We group Y -s and Z-s into series. More precisely, consider sequence of independent (also from Y -s and Z-s) random variables ω such that P (ω(i) = 0) = d/(d + 1) and P (ω(i) = 1) = 1/(d + 1). We have X_{i} = Y_{i} iff ω(i) = 0 (and X_{i} = Z_{i} iff ω(i) = 1). Let A = {ω(1) = 0} and B = {ω(1) = 1}. Let m_{i} and l_{i} be defined inductively: m_{0} = l_{0} = 1, m_{i+1} = min{k : k > m_{i}, ω(k −1) = 0, ω(k) = 1}, l_{i+1} = min{k : k > l_{i}, ω(k −1) = 1, ω(k) = 0}. The differences m_{i} − m_{i−1} are independent, and except for i = 1 have a common distribution (which is convolution of two geometric distrbutions). There exists c_{1} > 0 such that P (l_{[c_{1}n]} > n) < exp(−c_{1}n). On A put Ỹ_{i} = ∏_{k=l_{i−1}}^{m_{i}−1} Y_{k} and Z̃_{i} = ∏_{k=m_{i}}^{l_{i}−1} Z_{k}, on B put Ỹ_{i} = ∏_{k=l_{i}}^{m_{i}−1} Y_{k} and Z̃_{i} = ∏_{k=m_{i}}^{l_{i+1}−1}. Let A_{n} = A ∩ {l_{[c_{1}n]} ≤ n}. Then, on A_{n}

∏_{i=1}^{n} X_{i} = ∏_{i=1}^{[c_{1}n]}(Ỹ_{i}Z̃_{i}) ∏_{i=l_{[c_{1}n]}}^{n} X_{i}.

Let us note that Ỹ_{i} and Z̃_{i} are independent, and Ỹ_{i} have common distribution with values in H and that Z̃_{i} have common distribution with values in A_{e} and that P (Z̃_{1} = 0) > 0. Next

sup_{g∈G} P ((∏_{i=1}^{n} X_{i} = g) ∩ A) ≤ P (l_{[c_{1}n]} > n) + sup_{g∈G} P ( ∏_{i=1}^{[c_{1}n]}(Ỹ_{i}Z̃_{i}) = g)

≤ exp(−c_{3}n) + exp(−c_{2}n^{d/(d+2)})

where the estimate for the second term follows from (1.2) . Estimate on B is similar, thus giving the upper estimate.

To get the lower bound, we first note, that as in (1.2) , it is enough to estimate

P (∏_{j=1}^{n} X_{j} ∈ H).

Morover, we may add to p_{1} atom in 0. Indeed, if q = ap + (1 − p)δ_{0} then

q^{n} = ∑ c_{n,k}p^{k}

where c_{n,k} are binomial coefficients. There exists b > 0 such that for large n

∑_{2k<bn} c_{n,k}r ≤ exp(−bn)

Since p^{2k}(0) decreases and p^{2k+1}(0) = 0

q^{n}(0) ≤ ∑_{k≥bn} c_{n,2k}p^{2k}(0) + exp(−bn) ≤

p^{2[bn]}(0) + exp(−bn)

so any subexponential lower bound for q^{n}(0) will give corresponding lower bound for p^{n}(0).

We put

p̃_{1}(x) = \frac{2d + 2}{2d + 3}p_{1} + \frac{1}{2d + 3}δ_{(0,0)}

Then P (Z = (0, ±δ_{0})) = P (Z = (0, 0)) = 1/3.

Next, we restrict our attention to A. We are going to lenghten the product to get fixed number of series, and then to apply (1.2) . Since ∏_{i=1}^{n} X_{i} and ω seem to be dependent, we consider conditional distribution and then take expectation in ω. As in the proof of (1.2) , we note that the second (in F) coordinate of ∏ X_{i} has a (conditional in ω and Y_{j}, j = 1, …) distribution which is a cartesian product of one dimensional distributions. Each of those one dimensional distributions is a convolution power of distribution of Z. Since the distribution q of Z is unimodal (thanks to the added atom at 0), its convolution powers have maximum at 0 for any k ≥ 0. Hence q^{⋆k}(0) is decreasing in k. Consequently

P ((∏_{i=1}^{n} X_{i} ∈ H) ∩ A|ω, Y_{1}, Y_{2}, …) ≥ P (( ∏_{i=1}^{l_{n+1}−1} X_{i} ∈ H) ∩ A|ω, Y_{1}, Y_{2}, …).

Next, with the notation as in the proof of upper bound

P ((∏_{i=1}^{n} X_{i} ∈ H) ∩ A) ≥ P (( ∏_{i=1}^{l_{n+1}−1} X_{i} ∈ H) ∩ A) = P ((∏_{i=1}^{n}(Ỹ_{i}Z̃_{i}) ∈ H) ∩ A)

and we end the proof applying (1.2) .

To get the last claim of (1.1) we consider H = G_{1}. One easily checks that the number of sites visited by the random walk on G_{1} is larger then th corresponding number on Z^{d}, for any d, so in the final estimate we can take d as large as we wish.

References

[1] G. Alexopoulos, Fonctions harmoniques bornées sur les groupes résolubles. C. R. Acad. Sci. Paris, t. 305, série I, 1987, p.777-779.

[2] M. D. Donsker, S. R. S. Varadhan, On the number of distinct sites visited by a random walk, Comm. Pure Appl. Math 32 (1979), 721–747.

[3] W. Hebisch, On the heat kernel, Math. Z. 210 (1992), 593-605.

[4] W. Hebisch, L. Saloff-Coste, Gaussian estimates for Markov chains and random walks on groups, Annals of Prob. 21 (1993), 673–709.

[5] Ch. Pittet, L. Saloff-Coste, Amenable groups. isoperimetric profiles and random walks, preprint.

[6] N. Th. Varopoulos, Diffusion on Lie groups (I), Can. J. Math. 46 (1994), 438-448.

[7] N. Th. Varopoulos, Diffusion on Lie groups (II), Can. J. Math. 46 (1994), 1073-1093.

[8] N. Th. Varopoulos, The heat kernel on Lie groups, Rev. Math. Ib. 12(1996), 141-186.