Expected maximum distance of a random walk

Question

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

Answer 1

Define $S_i$, $i=1,\ldots,2n$ to be the number of $1$s in the interval $[0,i]$, minus $i/2$. Then, with your notation, $Y_i:=X_{i+1}-n/2=S_{n+i}-S_i$. You are interested in $M^*_n:=\max_{i=1}^n |Y_i|/\sqrt{n}$. Since $\{S_{[nt]}\}/\sqrt{n}$, $t\geq 0$, converges to one half times a Brownian motion $\{W_t\}$, it follows that $M_n^*$ converges to the random variable $X^*=0.5 \max_{t\in [0,1]} |W_{t+1}-W_t|$. Since this random variable is of order $1$, the expectation you are after is of order $\sqrt{n}$.