\magnification=1200
\input amssym.def
\long\def\ppp #1. #2\par{\medbreak
\noindent{ #1.\enspace}{\sl#2}\par
\ifdim\lastskip<\medskipamount \removelastskip\penalty55\medskip\fi}
\baselineskip=18pt
\def \rank {\hbox {rank} }
\def \supp {\hbox {supp} }
\def \nl {\par}
\newcount\pno
\pno=0
\newcount\sno
\sno=1
\font\Bbb=msbm10
%\input /za/hebisch/my.mor
\def \Cal { \Bbb }
\long\def \p #1 #2 {\advpnr {\edef \pnrp {\hbox{ \pnr } }
\global \let #1=\pnrp } \ppp {\pnr. {\bf Lemma}}. {#2} \par}
\def \t #1 #2 {\advpnr {\edef \pnrp {\hbox{ \pnr } } \global \let #1=\pnrp }
\ppp {\pnr . {\bf Theorem}}. {#2} \par}
\def \nr #1 {\advpnr { \edef \pnrp {\hbox{ \pnr } }
\global \let #1=\pnrp
} \pnr}
\def \advpnr {\global\advance\pno by 1}
\def \pnr {(\the \sno.\the \pno)}
%*****************************
\newcount\refno
\refno=1
\def \rf #1 #2 {\setbox3=\box2
\global\edef #1{\the \refno}
\setbox2=\vbox{\unvbox3
\vskip 0pt plus2pt
\hbox { \hbox to 2em{[\the \refno \global\advance\refno by1]\hfil}
\vtop {\advance\hsize by-5em \noindent
\strut #2 \hfil \strut } } } }
\global \def \diam {\mathop{\hbox{ diam } }}
\def \supp {\mathop{\hbox{ supp }} }
\edef \int {\int\limits}
\long\def\nic#1{}
\rf {\A} {G. Alexopoulos, Fonctions harmoniques born\'{e}es sur les groupes
r\'{e}solubles. C. R. Acad. Sci. Paris, t. 305, s\'{e}rie I, 1987, p.777-779.}
\rf {\DV} {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.}
\rf {\Hht} {W. Hebisch, On the heat kernel, {\it Math. Z. } 210 (1992), 593-605.}
\rf {\HSf} {W. Hebisch, L. Saloff-Coste, Gaussian estimates for Markov chains
and random walks on groups, {\it Annals of Prob}. 21 (1993), 673--709. }
%\rf {\Vl} { N. Th. Varopoulos, Small time Gaussian estimates
%for the heat kernel: part2, J. Funct.
%Anal. 83, 3--41 (1990).}
\rf {\PS} {Ch. Pittet, L. Saloff-Coste, Amenable groups. isoperimetric profiles
and random walks, preprint.}
\rf {\Vda} { N. Th. Varopoulos, Diffusion on Lie groups (I),
Can. J. Math. 46 (1994), 438-448.}
\rf {\Vdb} { N. Th. Varopoulos, Diffusion on Lie groups (II),
Can. J. Math. 46 (1994), 1073-1093.}
\rf {\Vh} { N. Th. Varopoulos, The heat kernel on Lie groups,
Rev. Math. Ib. 12(1996), 141-186. }
{\bf On random walks on discrete solvable groups}
by Waldemar Hebisch
{\bf 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 [\A], [\Hht], [\HSf], [\Vda], [\Vdb], [\Vh]
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.
{\bf Note} Our results seem to be a particular case of results
from [\PS]. While [\PS] covers more topics and the technical
details are different the idea for getting both lower and upper
bound is the same. Morover, in [\PS] it is pointed out that one may
modify the example to get finitely presented solvable groups with
''fast'' decay of $p_n(e)$.
{\bf Results}
Let $G_d$ be the semidirect product of ${\Bbb Z}^{d}$ and ${\Bbb
Z}^{{\Bbb Z}^d}$ and
$p_n$ be the simple random walk on $G_d$.
We will call the ${\Bbb Z}^d$ part $H$. Then an element of $G$ is a pair
$(h,f)$ with $h\in 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$
%such functions
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_1h_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\ne h$. Of course $A_h$ is isomorphic to ${\Bbb Z}$.
Note that $T(h)^{-1}A_e=A_h$. We choose $(\delta_k,0)$, $k=1,\dots,d$ and
$(0,\delta_0)$ as generators of $G_d$. Then, the probability distribution
$p_1$ is given by
$$p_1((\pm\delta_k,0))=p_1((0,\pm\delta_0))={1\over 2(d+1)}.$$
As usual, $p_n$ is the $n$-th convolution power of $p_1$.
\t {\a} { For every $d$ there exist $C$ and $c>0$ such that
for all $n$
$$
c\exp(-Cn^{d/(d+2)}\log n)\leq p_{2n}(e)\leq C\exp(-cn^{d/(d+2)}).$$
There exist $G$ and $p_1$ such that for every $\epsilon>0$
$p_{n}(e)$ decays faster then $\exp(-n^{1-\epsilon})$.}
\t {\b} { 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}) \leq
\sup_{g\in G}P(\prod_{j=1}^{n}(Y_jZ_j)=g)\leq \exp(-cn^{d/d+2}).$$}
P. Note that $Y_jZ_j=(Y_j,Z_j)$ and
$$
\prod_{j=1}^{n}(Y_j,Z_j)=
(\prod_{j=1}^{n}Y_j,\prod_{j=1}^{n}T^{-1}(\prod_{l=j+1}^{n}Y_j)Z_j)$$
$$
\sup_{g\in G}P(\prod_{j=1}^{n}(Y_jZ_j)=g)\leq
\sup_{f\in F}P(\prod_{j=1}^{n}T^{-1}(\prod_{l=j+1}^{n}Y_l)Z_j=f).$$
Since $F$ is commutative
$$
\prod_{j=1}^{n}T^{-1}(\prod_{l=j+1}^{n}Y_l)Z_j=
\prod_{h\in H}T^{-1}(h)\prod_{h=\prod_{l=j+1}^{n}Y_l}Z_j\leqno (1)$$
Since $T^{-1}(h)Z_j$ takes values in $A_h$, the first product above
is simply a cartesian produkt (of independent variables). Morover,
%$Z_j$ have the same distribution so
on each axis we may apply to $Z_j$ the central limit theorem, so
$$
P(\prod_{j=1}^{n}T^{-1}(\prod_{l=j+1}^{n}Y_l)Z_j=f)=
E(\prod_{h\in H}P(\prod_{j=1}^{n_h}Z_j=f(h)))$$
$$
\leq E( \prod_{h\in H} (1+cn_h)^{-1/2})
\leq E(\exp(-\tilde c|\{h\in H : n_h>0\}|))$$
where $n_h$ is the number of $j$ such that $h=\prod_{l=j+1}^{n}Y_l$. By
[\DV]
$$
E(\exp(-\tilde c|\{h\in H : n_h>0\}|)) \leq \exp(-c n^{d/(d+2)}).$$
Similarly
$$
P(\prod_{j=1}^{n}(Y_j,Z_j)\in H)=P(\prod_{j=1}^{n}T^{-1}(\prod_{l=j+1}^{n}Y_l)Z_j=0)\geq
E( \prod_{h\in H} (1+cn_h)^{-1/2})$$
$$
\geq E( \exp(-c_0\log(2+n)|\{h\in H : n_h>0\}|))$$
$$
\geq E( \exp(-c_0|\{h\in H : n_h>0\}|))^{\log(2+n)}$$
$$
\geq c\exp(-c_1 n^{d/(d+2)})^{\log(2+n)}$$
where the last inequality follows from [\DV]. Next, since $Y$ is symmetric
$E(Y)=0$ and $E(|\prod_{j=1}^{n}Y_j|^2)\leq Cn$. Put
$$\phi(x)=c\exp(-c_1 x^{d/(d+2)})^{\log(2+x)}$$ nad let $r$ be the
smallest such that $Cnr^{-2}\leq 1/2\phi(n)$.
Then $r\leq {C_3\over \phi(n)}$ and
$$P(|\prod_{j=1}^{n}Y_j|>r)\leq 1/2\phi(n)$$
so with probability at least $1/2\phi(n)$ the product $\prod_{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_4r^{d}$ elements, so the maximal probability is at least
$$1/2\phi(n)/(C_4r^{d})\geq C_5\phi(n)^{d+1}$$
which differs from $\phi$ only because of constants.
P. of \a :
Let $X$ be a random variable with distributon $p_1$ and let
$Y$ nad $Z$ be (independent) random variables such that
$$P(Z=(0,\pm\delta_0))=1/2
\qquad P(Y=(\pm\delta_k,0)=1/2d\quad k=1,\dots,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 $\prod_{i=1}^nX_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 $\omega$ such that $P(\omega(i)=0)=d/(d+1)$ and
$P(\omega(i)=1)=1/(d+1)$. We have $X_i=Y_i$ iff $\omega(i)=0$
(and $X_i=Z_i$ iff $\omega(i)=1$).
Let $A=\{\omega(1)=0\}$ and $B=\{\omega(1)=1\}$.
Let $m_i$ and $l_i$ be defined inductively: $m_0=l_0=1$, $m_{i+1}=
\min\{k:k>m_i,\omega(k-1)=0,\omega(k)=1\}$, $l_{i+1}=
\min\{k:k>l_i,\omega(k-1)=1,\omega(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_1n]}>n)<\exp(-c_1n)$. On $A$ put
$\tilde Y_i=\prod_{k=l_{i-1}}^{m_i-1}Y_k$ and
$\tilde Z_i=\prod_{k=m_i}^{l_i-1}Z_k$, on $B$ put
$\tilde Y_i=\prod_{k=l_i}^{m_i-1}Y_k$ and
$\tilde Z_i=\prod_{k=m_i}^{l_{i+1}-1}$. Let $A_n=A\cap\{l_{[c_1n]}\leq n\}$.
Then, on $A_n$
$$
\prod_{i=1}^{n}X_i=\prod_{i=1}^{[c_1n]}(\tilde Y_i\tilde Z_i)
\prod_{i=l_{[c_1n]}}^{n}X_i.$$
Let us note that $\tilde Y_i$ and $\tilde Z_i$ are independent, and
$\tilde Y_i$ have common distribution with values in $H$ and
that $\tilde Z_i$ have common distribution with values in $A_e$ and that
$P(\tilde Z_1=0)>0$. Next
$$\sup_{g\in G} P((\prod_{i=1}^{n}X_i=g)\cap A)\leq
P(l_{[c_1n]}>n)+\sup_{g\in G}
P(\prod_{i=1}^{[c_1n]}(\tilde Y_i\tilde Z_i)=g)$$
%$$\leq \sum_{i=0}^{n}\exp(-cj^{d/(d+2)})P(j_n=i|A) \leq
%P(j_n=c_1n)+\exp(-c_2n^{d/(d+2)})
$$\leq \exp(-c_3n)+\exp(-c_2n^{d/(d+2)})$$
where the estimate for the second term follows from \b.
Estimate on $B$ is similar, thus giving the upper estimate.
To get the lower bound, we first note, that as in \b, it is enough to estimate
$$P(\prod_{j=1}^{n}X_j\in H).$$
Morover, we may add to
$p_1$ atom in $0$. Indeed, if $q=ap+(1-p)\delta_0$ then
$$
q^n=\sum c_{n,k}p^k$$ where $c_{n,k}$ are binomial coefficients.
%By the central limit theorem
There exists $b>0$ such that for large $n$
$$\sum_{2k1/4.$$
Since $p^{2k}(0)$ decreases and $p^{2k+1}(0)=0$
$$
q^{n}(0)\leq \sum_{k\geq bn}c_{n,2k}p^{2k}(0)+\exp(-bn)\leq$$
$$
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
$$
\tilde p_1(x)={2d+2\over 2d+3}p_1+{1\over 2d+3}\delta_{(0,0)}$$
Then $P(Z=(0,\pm\delta_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 \b. Since $\prod_{i=1}^{n}X_i$
and $\omega$ seem to be dependent, we consider conditional
distribution and then take expectation in $\omega$.
%So, we
%would like to have
%$$
%P((\prod_{i=1}^{n}X_i=(0,0))\cap A | \omega) \geq
%P((\prod_{i=1}^{l_{n+1}-1}X_i=(0,0))\cap A | \omega) $$
%but we can get only
%$$
%P((\prod_{i=1}^{n}X_i\in H)\cap A | \omega) \geq
%P((\prod_{i=1}^{l_{n+1}-1}X_i\in H)\cap A | \omega).$$
As in the proof of \b, we note that the second (in $F$)
coordinate of $\prod X_i$ has a (conditional in $\omega$ and $Y_j$, $j=1,\dots$)
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\geq 0$. Hence $q^{\star k}(0)$ is
decreasing in $k$. Consequently
$$
P((\prod_{i=1}^{n}X_i\in H)\cap A | \omega,Y_1,Y_2,\dots) \geq
P((\prod_{i=1}^{l_{n+1}-1}X_i\in H)\cap A | \omega,Y_1,Y_2,\dots).$$
%Integrating, we get ineqality for unconditional pob
Next, with the notation as in the proof of upper bound
$$
P((\prod_{i=1}^{n}X_i\in H)\cap A ) \geq
P((\prod_{i=1}^{l_{n+1}-1}X_i\in H)\cap A ) =
P((\prod_{i=1}^{n}(\tilde Y_i\tilde Z_i)\in H)\cap A )$$
and we end the proof applying \b.
To get the last claim of \a 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 ${\Bbb Z}^d$, for any $d$, so in the final estimate
we can take $d$ as large as we wish.
{\bf References}
\vskip 0.3cm
\unvbox 2
\end