7
$\begingroup$

I'm looking for a reference for the following claim.

Let $W(n)$ be a centered random walk on $\mathbb Z^d$ with $W(0)=0$. Suppose that $W(n)$ has a finite second moment.

Let $n\ge 1 $ and $k \in \mathbb Z ^d$ such that $||k||_2 \le \sqrt{n}$ and $\mathbb P ( W(n)=k)>0$. I want to show that in this case $\mathbb P (W(n)=k)\ge c n^{-\frac{d}{2}}$ for some positive $c$ that is independent of $n$ and $k$.

I found references that give the asymptotic behavior of $\mathbb P (W(n)=k)$ under the assumption that $W(n)$ is irreducible or aperiodic but I didn't find a reference for the general case above.

$\endgroup$
5
  • $\begingroup$ If the walk is not irreducible, then the lower bound you ask for cannot be true : if one cannot reach $k$ from $e$, then, $P(W(n)=k)=0$. If the walk is irreducible, then this is standard, as you probably know. $\endgroup$
    – M. Dus
    Jan 24, 2021 at 11:30
  • 1
    $\begingroup$ This is exactly why I assumed that $\mathbb P (W(n)=k)>0$ $\endgroup$
    – Dor
    Jan 24, 2021 at 11:33
  • 1
    $\begingroup$ Are you assuming a finite second moment? Otherwise this lower bound is false even for irreducible centered walks in one dimension. $\endgroup$ Jan 25, 2021 at 1:12
  • $\begingroup$ Yes, you are right. I added the finite second moment assumption. Thank you $\endgroup$
    – Dor
    Jan 25, 2021 at 6:11
  • 1
    $\begingroup$ Have you looked in Petrov's book ? (Sums of ....) . He states a number of local limit theorems with bounds on the remainder. I think I have done this in 1-d using his results, You can get a non asymptotic result, but maybe not all n. $\endgroup$
    – mike
    Jan 25, 2021 at 7:48

1 Answer 1

5
$\begingroup$

$\newcommand\R{\mathbb R}\newcommand\Z{\mathbb Z}\newcommand\De\Delta$This follows almost immediately from the multidimensional local limit theorem (MLLT) proved by Meĭzler, D. G.; Parasyuk, O. S.; Rvačeva, E. L. in the paper "On a many dimensional local limit theorem of the theory of probability." (Russian) Ukrain. Mat. Žurnal 1, (1949). no. 1, 9--20.

The sufficiency part of their result can be stated as follows.

Let $Y_1,Y_2,\dots$ be iid random vectors with values in $\Z^d$. Let $S$ denote the support set of (the distribution of) $Y_1$. Suppose that the lattice generated by the set $S-S$ is the entire set $\Z^d$. Let $a$ and $C$ denote, respectively, the mean and the covariance matrix of (the distribution of) $Y_1$. (Note that the condition on $S$ implies that the matrix $C$ is invertible.) Let $Z_n:=Y_1+\dots+Y_n$. Then \begin{equation} P(Z_n=z)=\frac1{(2\pi n)^{d/2}\sqrt\De}\,\Big[\exp\Big\{-\frac12\,Q\Big(\frac{z-na}{\sqrt n}\Big)\Big\}+o(1)\Big] \tag{1} \end{equation} uniformly over all $z\in\Z^d$, where $\De$ is the determinant of $C$ and $Q$ is the quadratic form with the matrix $C^{-1}$.

The paper by Meĭzler et al is in Russian; however, I think it is not hard to read it using Google Translate, say. Unfortunately, there is a mistake in the statement of the result in that paper, where $C$ is defined, not as the covariance matrix $EY_1Y_1^T-EY_1\,EY_1^T$ of $Y_1$, but as $EY_1Y_1^T$ (as usual, we identify $\Z^p$ with the set $\Z^{p\times1}$ of all $p\times 1$ column matrices with integral entries). However, the proof actually seems to be a correct proof of the correct version of the result -- see e.g. formula (10) in that paper.


Let now $X_1,X_2,\dots$ be the iid jumps of your random walk, so that $W_n:=W(n)=X_1+\dots+X_n$. Let $L$ be the minimal lattice in $\Z^d$ such that the support of the distribution of $X_1$ is contained in $c+L$ for some $c\in\Z^d$. For this minimal lattice $L$, take indeed any $c\in\Z^d$ such that the support of the distribution of $X_1$ is contained in $c+L$. Let $(b_1,\dots,b_r)$ be any basis of the lattice $L$ (where necessarily $1\le r\le d$), so that $L=\Z b_1+\dots+\Z b_r$. For each natural $j$, let $Y_j$ the $r\times 1$ column matrix of the coordinates of the random vector $X_1-c$ with respect to the basis $(b_1,\dots,b_r)$ of $L$, so that $$Y_j=M(X_j-c)$$ for some matrix $M$. Moreover, all values of $Y_j$ are in $\Z^r$. Furthermore, the lattice generated by the set $S-S$ is the entire set $\Z^r$, where $S$ still denotes the support set of (the distribution of) $Y_1$. Note also that $a=EY_j=EM(X_j-c)=-Mc$, since $EX_j=0$.

It follows by (1) that uniformly in $k=nc+l\in nc+L$ with $\|k\|_2\le\sqrt n$ \begin{align*} P(W_n=k)&=P(W_n=Ml) \\ &=\frac1{(2\pi n)^{r/2}\sqrt\De}\,\big[\exp\big\{-\frac1{2n}\,Q(Ml+nMc)\big\}+o(1)\big] \\ &=\frac1{(2\pi n)^{r/2}\sqrt\De}\,\big[\exp\big\{-\frac1{2n}\,Q(Mk)\big\}+o(1)\big] \\ &\ge\frac K{n^{r/2}} \end{align*} for some positive real constant $K$ independent of $n,k$. On the other hand, $P(W_n=k)>0$ only if $k\in nc+L$. Thus, \begin{align*} P(W_n=k)\ge\frac K{n^{r/2}}\ge\frac K{n^{d/2}} \end{align*} for all $k\in\Z^d$ such that $P(W_n=k)>0$, as desired.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.