2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – user31373 Jun 25 '12 at 14:05
  • $\begingroup$ 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) $\endgroup$ – FD. Jun 25 '12 at 14:26
  • $\begingroup$ 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. $\endgroup$ – mike Jun 25 '12 at 15:28
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – FD. Jun 25 '12 at 15:53

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.