18
$\begingroup$

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

Improve this question
$\endgroup$
4
  • $\begingroup$ Actually, @Dilip, you need a Markov chain with states indexed by ordered pairs $(i,i+1)$ and $(i,i-1)$, $i\in\mathbb{Z}$. The transitions are $(i,i+1)\to(i+1,i+1)$ and $(i,i-1)\to(i-1,i)$ with probability $p$ and $(i,i+1)\to(i+1,i)$ and $(i,i-1)\to(i-1,i-2)$ with probability $1-p$. $\endgroup$ – whuber♦ Oct 25 '11 at 16:39
  • $\begingroup$ Note that the step sizes form a Markov chain on $\{-1,+1\}$ and you happen(?!) to have started it at a stationary distribution. $\endgroup$ – cardinal Oct 25 '11 at 16:46
  • $\begingroup$ Are you wanting a limiting (marginal) distribution for $S_n = \sum_{i=1}^n X_n$ where the $X_n \in \{-1,+1\}$ are the steps of the walk? $\endgroup$ – cardinal Oct 25 '11 at 16:47
  • $\begingroup$ Another approach might be to look at alternating sums of geometric random variables, then apply some martingale theory. The problem is you would have to define some kind of stopping time, which might be tricky. $\endgroup$ – shabbychef Nov 8 '11 at 6:50
7
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ +1 nice. I would only have written assymptotic distribution for $1/\sqrt{n}S_n$, to show clearly that CLT applies in the usual way. But that is only the matter of taste. $\endgroup$ – mpiktas Oct 26 '11 at 6:36
1
$\begingroup$

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!)

Improve this answer
$\endgroup$
2
  • $\begingroup$ Interesting. I'm not sure that yields anything very sensible for the $p=0$ subcase; though, that could be due to pathologies associated with that case. $\endgroup$ – cardinal Oct 25 '11 at 21:34
  • $\begingroup$ @cardinal good catch, the autocorrelation should be $\rho = 2p - 1,$ not $1 - 2p$. correcting it... $\endgroup$ – shabbychef Oct 25 '11 at 22:26

Your Answer

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