Random walk with momentum

Question

Consider an integer random walk starting at 0 with the following conditions:

• The first step is plus or minus 1, with equal probability.

• Every future step is: 60% likely to be in the same direction as the previous step, 40% likely to be in the opposite direction

What sort of distribution does this yield?

I know that a non-momentum random walk yields a normal distribution. Does the momentum just change the variance, or change the nature of the distribution entirely?

I'm looking for a generic answer, so by 60% and 40% above, I really mean p and 1-p

Answer 1

To jump to the conclusion immediately, the "momentum" does not change the fact that the normal distribution is an asymptotic approximation of the distribution of the random walk, but the variance changes from $4np(1-p)$ to $np/(1-p)$. This can be derived by relatively elementary considerations in this special case. It is not awfully difficult to generalize the arguments below to a CLT for finite state space Markov chains, say, but the biggest problem is actually the computation of the variance. For the particular problem it can be computed, and hopefully the arguments below can convince the reader that it is the correct variance.

Using the insight that Cardinal provides in a comment, the random walk is given as $$S_n = \sum_{k=1}^n X_k$$ where $X_k \in \{-1, 1\}$ and the $X_k$'s form a Markov chain with transition probability matrix $$ \left(\begin{array}{cc} p & 1-p \\ 1-p & p \end{array}\right). $$ For asymptotic considerations when $n \to \infty$ the initial distribution of $X_1$ plays no role, so lets fix $X_1 = 1$ for the sake of the following argument, and assume also that $0 < p < 1$. A slick technique is to decompose the Markov chain into independent cycles. Let $\sigma_1$ denote the first time, after time 1, that the Markov chain returns to 1. That is, if $X_2 = 1$ then $\sigma_1 = 2$, and if $X_2 = X_3 = -1$ and $X_4 = 1$ then $\sigma_1 = 4$. In general, let $\sigma_i$ denote the $i$'th return time to 1 and let $\tau_i = \sigma_i - \sigma_{i-1}$ denote the inter-return times (with $\sigma_0 = 1$). With these definitions, we have

• With $U_i = \sum_{k = \sigma_{i-1}+1}^{\sigma_i} X_k$ then $$S_{\sigma_n} = X_1 + \sum_{i=1}^n U_i.$$
• Since $X_k$ takes the value $-1$ for $k = \sigma_{i-1}+1, \ldots, \sigma_{i}-1$ and $X_{\sigma_i} = 1$ it holds that $$U_i = 2 - \tau_i.$$
• The inter-return times, $\tau_i$, for a Markov chain are i.i.d. (formally due to the strong Markov property) and in this case with mean $E(\tau_i) = 2$ and variance $V(\tau_i) = 2\frac{p}{1-p}$. It is indicated how to compute the mean and variance below.
• The ordinary CLT for i.i.d. variables yields that $$S_{\sigma_n} \overset{\text{asymp}}{\sim} N\left(0, \frac{2np}{1-p}\right).$$
• The final thing to note, which requires a small leap of faith, because I leave out the details, is that $\sigma_n = 1 + \sum_{i=1}^n \tau_i \sim 2n$, which yields that $$S_{n} \overset{\text{asymp}}{\sim} N\left(0, \frac{np}{1-p}\right).$$

To compute the moments of $\tau_1$ one may note that $P(\tau_1 = 1) = p$ and for $m \geq 2$, $P(\tau_1 = m) = (1-p)^2p^{m-2}$. Then techniques similar to those used when computing moments for the geometric distribution may be applied. Alternatively, if $X$ is geometric with success probability $1-p$ and $Z = 1(\tau_1 = 1)$ then $1 + X(1-Z)$ has the same distribution as $\tau_1$, and it is easy to compute the mean and variance for this latter representation.

Answer 2

Van Belle's 'Rule of Thumb' 8.7 (from the second edition of his book) includes an approximation for the standard error of the mean when innovations have autocorrelation $\rho$. Translating this using $\rho = 2p - 1$ gives $$\mbox{True standard error of }\bar{x} \approx \sqrt{\frac{p}{1-p}}\frac{s}{\sqrt{n}},$$ where $n \bar{x}$ is the position of the random walk after $n$ steps, and $s$ is the sample standard deviation (which will be, asymptotically in $n$, $\sqrt{1 - \bar{x}^2}$. The upshot is that I expect, as a rough approximation, that the standard deviation of $n \bar{x}$ should be around $\sqrt{n p/(1-p)}$.

edit: I had the wrong autocorrelation (or rather $p$ should have been interpreted differently); is now consistent (I hope!)