# number of reverses of direction to return in random walk

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.

-
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

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

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