Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. 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

Let's consider a random walk on a fixed lattice with step size 1 in 1 dimensions. In variation to the broadly discussed basic case, with a probability p the next step will be in the opposite direction of the previous step. The direction of the first step is also chosen randomly with same probability p.

In my opinion the result should be identical to an unbiased random walk regardless of p, however experiments in Excel seem to suggest that there is a difference (path looks more jagged; but this could be an artifact of the PRNG used). If there really is a difference I would like to know how to calculate the expected distance from origin after n steps and passing times.

Edit: I had a bug in my formula, now p is changing the look of the graph. With p = 0.5 you have an unbiased random walk, with p = 1 it is completely predictable. Thus my question about traveled distance and passing times / passing probabilities has some eligibility.

share|cite|improve this question
You should not expect the result to be identical. If $p=10^{-10}$, the expected distance from the center after $100$ steps is very close to $100$. For the unbiased walk it's around $10$. An interesting question, I'll think some more. – user31373 Jun 25 '12 at 14:05
Greatly appreciated. Thanks for your example, I think until now we have 3 easy cases: p = 0: straight line, p = 0.5 unbiased random walk, p = 1: alternating sequence (0/1) or (-1/0) – FD. Jun 25 '12 at 14:26
i think you are just alternating geometric r.v.s. Having picked a direction you do a geometric(1-p) number of steps in that direction, then the same in the opposite. – mike Jun 25 '12 at 15:28
up vote 2 down vote accepted

The paper Un principe d'invariance pour une classe de marches $p$-corrélées sur $\mathbb Z^d$ (in French) by Alexis Bienvenüe studies a $d$-dimensional model which contains yours (called $1$-dimensional Gillis' random walk) as a special case. (Beware that the integer $p$ in the title of the paper is not your parameter $p$.) Thus, one knows that the random walk is recurrent for every $p\ne0$ (your $p$) and that the position $X_n$ at time $n$ is such that $\frac{X_n}{\sqrt{n\sigma^2}}$ converges in distribution to a standard normal random variable, with $\sigma^2=\frac{1-p}p$.

share|cite|improve this answer
Thanks for the link! Let's do a simple example just to verify: p=0.9, n=1000 gives an expected distance of approx. 10.54, right? – FD. Jun 25 '12 at 15:53

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.