Number of reversals of direction to return in random walk

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.


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