I've recently learned about the Pólya–Vinogradov inequality, or more specifically, its version for quadratic residues- for all primes $p$ and integers $m\le n$, $$\left | \sum_{a=m}^{n} \left ( \frac{a}{p} \right ) \right | = O(\sqrt{p} \log p).$$
Introducing this result, Wikipedia says that:
The values of $\left ( \frac{a}{p} \right )$ for consecutive values of a mimic a random variable like a coin flip.
which leads to the question, would a random sequence of 1 and -1 (representing a coin flip) behave similarly?
More formally, let $X_1,...,X_N$ be i.i.d variables with $\mathbb{P}(X_i=1)=\mathbb{P}(X_i=-1)=1/2$. Define:
$$Y:=\max_{1\le m\le n\le N}\left | \sum_{i=m}^{n}X_i \right |.$$
Then what can we say about the expected value of $Y$? Does it hold that $\mathbb{E}[Y] \approx \sqrt{N}\log N$, or maybe $\mathbb{E}[Y]$ is even smaller than that?