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

I am wondering if there are some studies about the number of reverses of direction to return to the starting point in random walk (either symmetric or non-symmetric), for example, its distribution and expectation etc..

Thank you.

share|cite|improve this question
I guess you are interested in a 1D discrete random walk? – Fabian Mar 8 '11 at 21:26
Are you fixing the length or stopping the walk the first time it returns to the origin or what? What precisely is the random variable you're interested in? – Qiaochu Yuan Mar 8 '11 at 21:26
@Qiaochu: I am stopping the walk the first time it returns to the origin, if it started there too. The random variable I am considering is: the number of reverses of direction. – Qiang Li Mar 8 '11 at 21:28
@Fabian, yes, 1D discrete random walk. – Qiang Li Mar 8 '11 at 21:28
up vote 5 down vote accepted

In the symmetric case, one assumes that $X_0=0$ and that $X_n=Y_1+\cdots+Y_n$ for $n\ge1$, where $(Y_n)_{n\ge1}$ is i.i.d. Bernoulli and centered. For $n\ge1$, let $R_n$ denote the number of reversals of $(X_k)_{0\le k\le n}$. Then $R_1=0$ and $R_n=U_2+\cdots+U_n$ where $U_k=[Y_kY_{k-1}=-1]$.

The conditional expectation of $R_{n+1}$ with respect to the $\sigma$-algebra $F_n=\sigma(X_k;0\le k\le n)$ is $R_n+P(Y_nY_{n+1}=-1|F_n)=R_n+\frac12$, hence $M_n=2R_n-n$ defines a martingale $(M_n)_{n\ge1}$ starting from $M_1=-1$.

In particular, for every uniformly integrable stopping time such as the first hitting time $T_h$ of the set $\{0,h\}$ with $h\ge1$ by $(X_n)_n$, $E(M_{T_h})=-1$, hence $$ 2E(R_{T_h})=E(T_h)-1. $$ When $h\to+\infty$, $T_h$ converges to the first return time $T$ to $0$ and $T$ is not integrable hence $R_T$ is not integrable.

In the asymmetric case, assume that $P(Y_n=+1)=p$ and $P(Y_n=-1)=1-p$ for a given $p$ in $(0,1)$. If $p\ne\frac12$, $(X_n)_n$ has a positive probability to never hit $0$ again, in which case the total number of reversals of its path is almost surely infinite, hence not integrable.

One way to save the day is to assume that $p<\frac12$ (for example) and to condition on the event $[X_1=1]$. Write $P^+$ for this conditioned probability measure and $E^+$ for the expectation with respect to $P^+$. Then the first return time $T$ to $0$ is (at last!) integrable for $P^+$ and $R_T\le T-1$ hence $R_T$ is integrable for $P^+$.

To compute the value of $E^+(R_T)$, one can mimick the argument given in the symmetric case to show that the formula $$ M_n=2R_n-n-(1-2p)X_{n-1} $$ defines a martingale $(M_n)_{n\ge1}$ with respect to $P^+$, starting from $M_1=-1$. Since $X_{T-1}=+1$ almost surely for $P^+$, this yields $$ 2E^+(R_{T})=E^+(T)-2p, $$ and it remains to compute $E^+(T)$. This can be done by the usual first-step decomposition: on $[Y_2=-1]$, $T=2$, and on $[Y_2=+1]$, $T=T'+T''$ for two independent copies of $T$. Hence $E^+(T)=2(1-p)+2E^+(T)p$, which yields the value of $E^+(T)$. Finally the mean number of reversals is $$ E^+(R_T)=\frac{1-2p(1-p)}{1-2p}. $$

share|cite|improve this answer
Nice answer! Wish I could vote it up again. – Byron Schmuland Mar 9 '11 at 13:25
+1, I wish I could +Infty. :) – Qiang Li Mar 9 '11 at 19:39
(+1) Especially for the asymmetric case. Nice. – cardinal Mar 19 '11 at 4:29

For the symmetric random walk with $X_0=0$ and conditioned on $X_{2n}=0$, the average number of reversals should be $n$. Each outcome is a random ordering of $n$ plus signs and $n$ minus signs. A reversal takes place at any of the $2n-1$ time points from $1$ to $2n-1$, when the neighboring signs are opposite. Given the sign of one neighbor, the chance that the other neighbor has an opposite sign is ${n\over 2n-1}$. Adding up over the time points shows that the average number of sign changes is $n$.

The original question however is about the average number of reversals up to the first return $T$ to the origin. The argument above can be modified to show that, for $n>1$, $$E(\mbox{reversals}\ |\ T=2n) = n - 1 = T/2-1,$$ so that the expected number of reversals is infinite.

share|cite|improve this answer
It might be worth noting (given there is no finite mean) that the probability there is exactly 1 reversal is $\frac{2}{3}$ so 1 is both the median and the mode. – Henry Mar 9 '11 at 1:06
@Henry, (+1) on the comment. How did you calculate that? I have a pretty easy way, but was curious if there might be another straightforward approach. – cardinal Mar 18 '11 at 14:58
@cardinal: For every first return possibility taking time $2n$, there are 2 routes with only one reversal, and each of them has probability $1/2^{2n}$ of happening, so the probability of exactly one reversal is $\sum_{n=1}^{\infty}2/4^n = 2/3$ – Henry Mar 18 '11 at 17:58
@Henry, that's nice and actually easier than my approach. The runs of a random walk are geometrically distributed. The event that there is only one reversal before returning to zero is thus the same as the probability of the event $\{X_2 \geq X_1\}$ for i.i.d. $\mathrm{Geom}(1/2)$ random variables. Symmetry and a straightforward calculation shows $\mathbb{P}(X_2 \geq X_1) = \frac{1}{2}(1+\mathbb{P}(X_2 = X_1)) = \frac{2}{3}$. – cardinal Mar 19 '11 at 4:26

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.