# Random walk uniformly hitting a compact set

Suppose $G$ is a locally compact compactly generated group. Let $\mu$ be a probability measure that is:

1. Adapted to $G$, i.e. there is no proper subgroup $H$ such that $\mu(H)=1$.

2. Symmetric, i.e. $\mu(A)=\mu(A^{-1})$.

3. compactly supported, and $1_G$ is in the support.

4. $\mu<<\lambda$, where $\lambda$ is Haar.

Let $K$ be a compact set with $\lambda(K)>0$. Let $\mu^{*n}$ be the $n$-fold convolution $\mu*...*\mu$.

Do there exist $c>0$ and $n>0$ such that $\frac{d\mu^{*n}}{d\lambda}\geq c>0$ on $K$?

In other words, do a $\mu$ random walk, when hitting $K$, after many steps, hits it (in a sense) uniformly?

In the special case of a finitely generated group, you can easily find a counter-example. So, without any other assumption, the answer is no.

Take $G=\mathbb{Z}$ and $\mu=\frac{1}{2}(\delta_{-1}+\delta_1)$. These satisfy your assumptions. Now, take $K=\{0,1\}$. For every $n$, either $\mu^{*n}$ is supported on even numbers or on odd numbers, so either $\mu^{*n}(1)=0$ or $\mu^{*n}(0)=0$.

EDIT: Now that you added aperiodicity, for finitely generated groups, the answer is yes if yo replace adaptedness by irreducibility. More precisely, you only have to assume that there is $n_0\geq 0$ such that $\mu^{*n_0}(e)>0$ and that the symmetric support of $\mu$ generates $G$. Indeed, let $K$ be a compact (i.e. finite set). For every $x\in K$, there exists $n_x$ such that $\mu^{*n_x}(x)>0$ and using aperiodicity, for $n\geq n_x+n_0$, $\mu^{*n}(x)>0$. Since $K$ is finite, you can take $n=\max (n_x+n_0,x\in K)$, so that for every $x\in K$, $\mu^{*n}(x)>0$.

The exact same proof works in the general case if the following holds: for every $x\in G$, there exists an open neighborhood $U_x$ of $x$, some positive $c_x$ and $n_x\geq 0$ such that $\frac{d\mu^{*n_x}}{d\lambda}\geq c_x>0$ on $U_x$.

• Absolutely right. A simple random walk on $\mathbb{Z}$ would satisfy the above. However, periodicity is in a sense non-natural, so let me please in retrospect also add to the assumptions that $1_G$ is in the support of $\mu$. Sorry for being inaccurate about the details. Thanks! – Melafefon Chamutz Feb 14 '18 at 4:54
• Sure, on finitely generated groups, I agree. The more intricate case is the non-discrete one. There are two things that I don't understand in your answer: (1) Why would such $n_x$ and $c_x$ exist? note that even if $x\in supp(\mu^{n_x})$, this doesn't imply $\frac{d\mu^{n_x}}{d\lambda}(x)>c_x\geq 0$. (2) Even if $\frac{d\mu^{n_x}}{d\lambda}(x)>c_x\geq 0$, how do you go from that to $K$? – Melafefon Chamutz Feb 14 '18 at 18:23
• No I know, I'm just saying that with this stronger irreducibility condition, you have the result. Now, for your question (2): assume that you have (1) and let $K$ be compact. For every $x$ in $K$, you have $U_x$, $c_x$ and $n_x$, which gives you an open cover of $K$. Take a finite sub-cover and take the minimum of the $c_x$ and the maximum of the $n_x$ for this sub-cover and you get the result on $K$. – M. Dus Feb 14 '18 at 19:01
• Suppose $n$ is the maximal index and $c$ is the minimal lower bound, and take some $x$ with which you obtained the finite cover. Why would $\frac{d\mu^{*n}}{d\lambda}(x)\geq c>0$? sure, you have it for $n_x$, but why do you have it for $n$? (assuming $n\neq n_x$) – Melafefon Chamutz Feb 14 '18 at 19:10
• Well, more precisely, using the same property for $x=1$, you get $n_1$ such that $\frac{d\mu^{*n_1}}{d\lambda}\geq c_1>0$, Then, by induction, you get, for $n\geq n_x+n_1$, $\frac{d\mu^{*n}}{d\lambda}\geq (c_1\lambda(U_x))^{n-n_x-n_1+1}c_x$ on $U_x$. This proves that for large $n$, every $\frac{d\mu^{*n}}{d\lambda}\geq c$ on every $U_x$, which is enough to conclude. – M. Dus Feb 14 '18 at 19:35

The answer is positive under the assumptions boldfaced below, which hold at least when $G$ is a complete connected Riemannian manifold (see the Remark at the end of this answer), so that the case of $G=\mathbb R^d$ is of course included. On the other hand, the simple counterexample given by M. Dus shows that without a connectedness condition the desired conclusion will fail to hold in general.

Since the measure $\mu$ is nonzero, the set $E:=\{x\in G\colon f(x)>t\}$ is of nonzero $\lambda$-measure for some real $t>0$, where $f:=\frac{d\mu}{d\lambda}$. Also, $E=E^{-1}$, since $\mu$ is symmetric. Hence, \begin{equation*} f^{*2}(x)=\int f(y^{-1}x)f(y)dy\ge t\int_E f(y^{-1}x)\,dy\ge t^2|E\cap(xE^{-1})|=t^2|E\cap(xE)|, \end{equation*} where $dy:=\lambda(dy)$, and $|\cdot|:=\lambda(\cdot)$. By the regularity of the measure $\lambda$, \begin{equation*} |C_E|>\tfrac12\,|C| \end{equation*} for some compact set $C$, where $C_E:=C\cap E$. Assuming that $G$ has a countable basis of neighborhoods of $1_G$, it follows, by continuity, that \begin{equation*} |(xC)_E\cap C_E|>\tfrac12\,|C| \tag{1} \end{equation*} for all $x\in B$, where $B$ is some (without loss of generality, symmetric) neighborhood of $1_G$. So, $$f^{*2}(x)\ge t^2|(xE)\cap E|\ge t^2|(xC)_E\cap C_E|>\tfrac{t^2}2\,|C|=:c_1>0 \tag{2}$$ for all $x\in B$.

Suppose next that for some symmetric neighborhood $\hat B$ of $1_G$ such that $\hat B\subseteq B$ and all natural $n\ge2$ we have \begin{equation*} a_n:=\inf_{x\in \hat B^n}\,|(xB)\cap \hat B^{n-1}|>0. \tag{3} \end{equation*} (If e.g. $G=\mathbb R^d$, $B$ is the ball centered at $0$ of "radius" $r>0$ with respect to (say) the $\ell_\infty^d$ norm, and $\hat B=\frac12\,B$, then $a_n=r^d$.) Define recursively $c_n:=c_{n-1}c_1 a_n$ for $n\ge2$, with $c_1$ as above.

It follows by induction that \begin{equation*} f^{*2n}\ge c_n>0 \end{equation*} on $\hat B^n$. Indeed, for $n=1$ this follows by (2) and the condition $\hat B\subseteq B$. For $n\ge2$ and any $x\in \hat B^n$, by induction and (2), \begin{multline*} f^{*2n}(x)=\int f^{*2}(y^{-1}x)f^{*2(n-1)}(y)dy\ge c_{n-1}\int_{\hat B^{n-1}} f^{*2}(y^{-1}x)dy \\ \ge c_{n-1}\int_{(xB)\cap \hat B^{n-1}} f^{*2}(y^{-1}x)dy \ge c_{n-1}c_1 a_n=c_n>0. \end{multline*} (For the penultimate inequality in the above display, we used the fact that for any $y\in xB$ we have $y^{-1}x\in B^{-1}=B$ and hence, by (2), $f^{*2}(y^{-1}x)\ge c_1$.) Thus, the desired result follows if we finally assume that for any compact $K$ and any (or, equivalently, any symmetric) neighborhood $U$ of $1_G$ there is a natural $n$ such that $$U^n\supseteq K. \tag{4}$$

Remark. Conditions (1), (3), and (4), used above, will hold when $G$ is metrizable with a metric $d$ satisfying the following "linear" connectedness condition: $$\forall x,y\in G\ \forall t\in[0,1]\ \exists z\in G\quad d(x,z)=(1-t)d(x,y)\quad \& \quad d(z,y)=td(x,y). \tag{5}$$ In particular, condition (5) holds when $G$ is a complete connected Riemannian manifold; see e.g. wiki/Hopf--Rinow theorem and wiki/Riemannian_manifold.

Let us now verify that (5) implies (1), (3), and (4). This is obvious concerning (1), since $G$ is now a metric space and therefore has a countable basis of neighborhoods of $1_G$. Also, (5) implies $$B_r^n=B_{nr} \tag{6}$$ for all natural $n$ and all real $r>0$, where $B_r:=\{x\in G\colon d(x,1_G)\le r\}$, the $d$-ball of radius $r$ centered at $1_G$.

Take now any real $r>0$ and any compact $K$. Then $K\subseteq FB_r$ for some finite $F\subseteq G$. By (6), for each $x\in F$ there is some natural $n_x$ such that $x\in B_r^{n_x}$ and hence $xB_r\subseteq B_r^{n_x+1}$. So, $K\subseteq FB_r\subseteq B_r^n$ for $n:=1+\max_{x\in F}n_x$, which verifies (4).

It remains to verify (3). Without loss of generality, there we have $B=B_r$ for some real $r>0$. Take any natural $n\ge2$, then any $a\in(1/n,1)$, and let $\hat B:=B_{ar}$. It is enough to show that $$a_n\ge|B_b|>0, \tag{7}$$ where $b:=\frac r2\,(1-a)>0$. First here, if $|B_b|=0$ then $|K|=0$ for any compact $K$, which would contradict the condition that $G$ is compactly generated. So, we have the second inequality in (7). To verify the first inequality there, take any $x\in\hat B^n=B_{nar}$, so that $d(x,1_G)=nar_1$ for some $r_1\in[0,r]$. Let \begin{equation*} s:=nar_1-\tfrac{r_1}2\,(1+a)=(n-1)ar_1-\tfrac{r_1}2\,(1-a)\in[0,(n-1)ar_1]. \end{equation*} By (5), there is some $z\in G$ such that \begin{equation*} d(z,1_G)=s,\quad d(x,z)=nar_1-s=\tfrac{r_1}2\,(1+a). \end{equation*} For any $y\in zB_b$, we have $d(y,z)\le b$ and hence \begin{equation*} d(y,x)\le d(y,z)+d(z,x)\le b+\tfrac{r_1}2\,(1+a)\le b+\tfrac r2\,(1+a)=r, \end{equation*} \begin{equation*} d(y,1_G)\le d(y,z)+d(z,1_G)\le b+s\le b+(n-1)ar-\tfrac r2\,(1-a)=(n-1)ar, \end{equation*} so that $y\in (xB_r)\cap B_{(n-1)ar}=(xB)\cap \hat B^{n-1}$. So, $zB_b\subseteq(xB)\cap \hat B^{n-1}$, whence $|(xB)\cap \hat B^{n-1}|\ge|B_b|$, for all $x\in\hat B^n$, which implies the first inequality in (7).

Thus, all the conditions (1), (3), and (4) are verified.

• That's a nice construction, but can you provide details on why is $\displaystyle \int_{(x+B)\cap \frac{n-1}{2}B}g(x-y)dy\geq c_1a_n$ ? Maybe I'm missing something but it does not seem to follow from the above estimates (that hold for $x\in B$). – M. Dus Feb 14 '18 at 4:58
• @M.Dus : I have added a detail explaining this inequality. – Iosif Pinelis Feb 14 '18 at 16:20
• Nice! however, this heavily depends on the geometry of $\mathbb{R}^d$. I'm thinking how to choose $B$ in the general locally compact case. – Melafefon Chamutz Feb 14 '18 at 18:34
• @iPe : Why do you think this heavily depends on the geometry? I have now replaced the former ball $C$ by an appropriate compact set, which always exists. In the comment now appended at the end of my answer, it is explained that all we need are conditions (1), (3), (4), and it is also explained that for $B$ we can take a small enough symmetric neighborhood $B$ of $1_G$. Can you give a good example of a continuous locally compact group where some of the conditions (1), (3), (4) fail(s) to hold? – Iosif Pinelis Feb 14 '18 at 20:38
• I have now rewritten the answer in general terms, for locally compact groups under apparently broad conditions. – Iosif Pinelis Feb 15 '18 at 1:43