MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I would like to know what the asymptotic limiting behavior is for the following random walk on $\mathbb Z^d$. By Donsker's invariance principle, I suspect that its behavior is diffusive, i.e., the distribution of its path converge to $d$-dimensional Brownian motion, but I am not certain.

The state space for the walker is the discrete unit tangent bundle $X = \mathbb Z^d \times U^d$, where $U^d = \{ \pm e_1, \cdots, \pm e_d \}$. The walker is a Markov chain, so we need only specify its transition probabilities.

Here's the basic idea. From position $x = (q,u)$, the walker samples an independent geometric random variable, moves that distance in direction $u$, then chooses a new orthogonal direction uniformly and independently.

Let me make this a little more precise, since there's a free parameter here tuning the step-length distribution, and I want to know how the limiting behavior depends on this parameter.

Fix some $p \in (0,1]$, representing the inverse-mean of the step-length distribution. Given that its position is $x = (q,u)$, the walker samples a geometric random variable $S \in \{1, 2, 3, \cdots\}$ with parameter $p$, then moves to position $x + Su$. Then, the walker samples a new direction uniformly and independently from the set $u^\perp := U^d - \{ u, -u \}$.

  • Is the scaling limit for this random walker equal to a $d$-dimensional Brownian motion? How does one make this scaling limit precise?

  • If so, how does the diffusion constant depend on the parameter $p$ and the dimension $d$?

share|cite|improve this question
silly remark: the case d=2 leads to usual Brownian scaling by considering the chain at even times (this is a usual random walk on Z^2). – Alekk Mar 6 '13 at 9:06
Nice remark, actually! Maybe a wise choice of random times also leads to an iid sequence in higher dimension as well (that's what I meant by "done by hand") ? – Vincent Beffara Mar 6 '13 at 11:31

Maybe this can be done by hand, but if not, it is a consequence of more general central limit theorems for additive functionals of Markov chains, i.e. for expressions of the form $$S_n = \frac 1 {\sqrt n}\sum_{k=1}^n [f(X_k)-\pi(f)]$$ where $(X_n)$ is an ergodic Markov chain with invariant measure $\pi$. Here the chain is the sequence of jumps, and he function is the identity. Possible reference: G. Jones, "On the Markov chain central limit theorem", Probability Surveys 1 (2004), 299-320 (link).

About estimating the diffusion parameter, the increments of your walk are orthogonal in distribution, so you can compute the expected square norm of $S_n$ directly by expanding the sum...

share|cite|improve this answer

For $n$ large, each direction is chosen $n/d + O(n^{-1/2})$ so that each coordinate evolves approximately (after usual $\epsilon^{1/2}$-in-space-$\epsilon$-in-time scaling) as a Brownian motion and the coordinate are approximately independent. In other words $W_t^{(\epsilon)} = \sqrt{\epsilon} \ Q_{\epsilon^{-1}t}$ behaves as a standard Brownian motion with infinitesimal variance $\sigma^2(p) \ dt$, with $\sigma^2(p)=(1-p)p^{-2}$ the variance of a $p$-geometric random variable, looked at time $t/d$. This is the same as saying that $W_t^{(\epsilon)}$ behaves as a standard Brownian motion with infinitesimal variance $d^{-1} \ \sigma^2(p) \ dt$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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