Given a random walk on a lattice $$L$$ (not necessarily centered - we allow $$E[X_i] \neq 0$$ for the i.i.d. increments $$X_i$$), let $$p_t(x)$$ denote the probability measure of state $$x \in L$$ after $$t$$ time increments. I am interested in the time evolution of the maximum difference of neighboring states' measures:

$$\max_{x \in L, ~ x \sim y} |p_t(x) - p_t(y)|.$$

Here $$x \sim y$$ indicates sites $$x$$ and $$y$$ are adjacent, or that $$P_x(y) = P$$ (a walker started at $$x$$ transitions to $$y$$ in a single step$$) > 0$$.

I've explored various texts and online notes, but they don't seem to cover questions of the pointwise nature of these distributions; typically a distribution's weak limit is found via CLT or saddle-point approximation and it's left at that.

As a first effort, it's straightforward to look at the simple random walk on $$\mathbb{Z}$$ (where the increments are $$+1$$ or $$-1$$ with equal probability) and use Stirling's approximation to confirm that

$$\max_{k \in \mathbb{Z}} |p_t(k+1) - p_t(k)| \approx C/t$$

for some constant $$C$$ (the $$\approx$$ indicating omission of lower order terms). One also finds that this occurs around $$\lfloor k\rfloor = \sqrt{t}$$, just as one would expect considering the limiting Gaussian distribution, $$\Phi(x) = (2\pi)^{-1/2} e^{-x^2/2}$$, which has $$\sup_x \Phi'(x)$$ occurring around $$x = 1$$.

Any help in attacking the problem in higher dimensions and with non-simple probability transitions would be appreciated, though I suspect a thorough answer exists in the literature. Pointers to the relevant resources are welcome (even preferred!).

This is a migrant copy of the following MSE post.

• Aren't there parity issues with your problem? I would think that for the standard lattice, the difference between neighbouring probabilities is the same as the maximum of the two. Jul 17 '15 at 8:23
• That's a fair point. My interest would be in the largest mass difference between two even or odd integers in that case. Ideally the problem would be solved in a lazy setting, where a walker always has a chance to stay at his current position. Jul 17 '15 at 16:37

The estimate you seek is a consequence of a strong local CLT, valid for aperiodic walks (at least on $Z^d$). See for example chapter 2 in Lawler-Limic. (Theorem 2.1.1 should be enough.)