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)$ occuring 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.

  • $\begingroup$ 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. $\endgroup$ – Anthony Quas Jul 17 '15 at 8:23
  • $\begingroup$ 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. $\endgroup$ – Titus 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.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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