Relation between steps and turns in a simple symmetric random walk

Solution 1:

The expectation does not exist (i.e., $E|2\sigma-\tau|=+\infty$). To see it, condition upon $\tau=n$ (an event of probability about $n^{-3/2}$). Fix now a very small $\alpha>0$ and consider the sequence $S_{4k}$, $k<n/4$.

Claim Typically there are at least $\alpha n$ values of $k$ with $S_{4k}=S_{4(k+1)}$ ("level" intervals of length $4$).

Proof The total number of admissible paths is about $2^nn^{-3/2}$. Consider all paths in which the condition in the claim is violated. Then we have at least $\frac n4-\alpha n$ pieces of length $4$ that cannot be "level", so the total number of such paths is at most ${n/4\choose \alpha n}10^{n/4-\alpha n}16^{\alpha n}$, which gives a $2^{-cn}$ reduction over the trivial bound $2^n$ if $\alpha>0$ is small enough.

Now consider the "good part" of the probability space and condition upon the values of $S_{4k}$. Then pick up $\frac\alpha 2 n$ separated "level" intervals of length $4$ and condition upon all values $S_m$ except the ones inside those intervals. Then the contributions of those intervals to the total number of turns become independent integer-valued bounded non-constant random variables, so their sum has a constant probability to deviate from any given number by $c\sqrt{\alpha n}$, whence $E[1_{\tau=n}|2\sigma-\tau|]\ge c/n$, so the series diverges.