Consider a vector $V$ of length $2n-1$ whose entries are either $1$ or $0$, chosen independently and uniformly at random. Let $X_i$ be the number of $1$s in subvector $V[i,i+n-1]$. We know $\mathbb{E}(X_i)=n/2$ and we can consider the $X_i$ as representing a 1d discrete random walk (with $i$ as the time variable). The difference $X_{i+1}-X_i$ can be $-1$, $0$ or $1$. What is the expected maximum distance of the $X_i$ from $n/2$? (My interest is in large $n$ results.)

Intuitively it seems that the dependency between successive $X_i$ values will reduce the expected maximum distance of the random walk. Had we just sampled $n$ vectors uniformly at random with no dependency then the answer would be asymptotically something like $\sqrt{\frac{n}{c} \ln n}$, for some constant $2 < c < 2.5$. However our random walk "reverts to the mean".

The Theory of Stochastic Processes$\endgroup$ – wolfies Dec 4 '13 at 15:47