Relation between steps and turns in a simple symmetric random walk

combinatoricsexpected valuemartingalesprobabilityrandom walk

Let $S_0 = 0, S_n = X_1 + X_2 + \dots + X_n$, $n\ge 1$, be a simple symmetric random walk, i.e. $X_i$, $i\ge 1$, are iid random variables with $\mathrm P(X_i = 1) = \mathrm P(X_i = -1) = 1/2$. Denote $\tau = \inf\{n\ge 1: S_n = 0\}$ the time of steps the random walker makes before returning to zero, and let also $\sigma = \#\{1\le k\le \tau-1: X_k X_{k+1} = -1\}$ be the number of turns the walker made.

Is it true that
$$
\mathrm{E} [\tau – 2\sigma] = 1?\tag{1}
$$

The problem here is that $\mathrm{E} [\tau] = \mathrm{E} [\sigma] = \infty$.

Here are some ideas why $(1)$ may be true:

  1. For any $x\in \mathbb Z$, denote $\tau(x) = \#\{0\le k\le \tau-1: S_k = x \}$ the number of steps made from $x$ and $\sigma(x) = \#\{1\le k\le \tau-1: S_k = x, X_k X_{k+1} = -1\}$ the number of turns made in $x$, $\alpha(x) = \tau(x) – 2\sigma(x)$. Then, $\alpha(0) = 1$, and it is easy to show that $\mathrm{E} [\alpha(x)] = 0$, $x\neq 0$. However, despite that $\tau – 2\sigma = \sum_{x\in \mathbb Z} \alpha(x)$, this does not immediately imply $(1)$: something is needed to swap the sum and expectation signs.

  2. Denote $\sigma_n = \#\{1\le k\le n-1: X_k X_{k+1} = -1\}$, the number of turns before moment $n\ge 1$ and let $M_n = n – 2\sigma_n$. Then, $M_n$ is a martingale (actually, a simple symmetric random walk) starting from $M_1 = 1$, and $\tau – 2\sigma = M_\tau$. But this also does not imply $(1)$.

There are some related approaches, including certain direct enumeration, which confirm $(1)$ but lack rigor.

In order to validate these arguments, it suffices to prove that
$$
\mathrm{E} [|\tau – 2\sigma|]<\infty.
$$

Edit: the symmetry is false. Indeed, $\mathrm{P}(\tau-2\sigma=0) > \mathrm{P}(\tau=2) =1/2$.

Unfortunately, I can't edit the bounty description.

Best Answer

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.

Related Question