Let $\epsilon\_1, \dots, \epsilon\_n$ be random signs, equiprobably in $\{-1, 1\}$, independently.
Let $S\_k = \sum\_{j=1}^k \epsilon\_j$. I am wondering what is known about the expectation
$$
\mathbb{E}\Big[\max\_{k \leq n} |S\_k| \Big]. 
$$


It can be seen as the maximum distance from the origin over $n$ steps of a simple random walk which moves left or right from the origin with equal probability.


A naive bound is via Lévy's maximal inequality, which implies that the quantity above is bounded above by $2 \sqrt{n}$. Can the constant $2$ be improved?



Maximum distance from origin of simple random walk
If you just care about the asymptotics, it is indeed just $(1+o(1))\sqrt{\pi n/2}$, where the $o(1)$ term decays like $\tilde{O}(1/n^{1/4})$; this can be done using the approach that I suggested of using the natural embedding to compare to Brownian motion at the obvious stopping times, the fact that the Brownian motion does not fluctuate by more than 1 between stopping times, and the fact that $\vert T\_n - n\vert=\tilde{O}(\sqrt{n})$ with very high probability by Bernstein's inequality applied to the (subexponential) increments in stopping times. I can make this more rigorous if needed.


If you really do care about the best constant $C^\*$ such that $\mathbb{E}[\max\_{k\leq n} S\_k]\leq C\sqrt{n}$ for *every* $n$, not just for large enough $n$, there's a couple of approaches; it's true that $C^\*$ is at most twice the optimal constant when you take the absolute values outside the max because $\max\_{k\leq n}\vert \sum\_{i=1}^k \varepsilon\_i\vert\leq \vert\max\_{k\leq n} \sum\_{i=1}^k \varepsilon\_i\vert+\vert\min\_{k\leq n} \sum\_{i=1}^k \varepsilon\_i\vert$, which can be treated exactly via the reflection principle. This should (at least morally) get you something like $2\sqrt{2/\pi}\approx 1.596$. Just for variety, here's a slightly different approach that gives a slightly better constant of $\pi/2\approx 1.571$.


Simply note that if $g\_1,\ldots,g\_n$ are i.i.d. standard Gaussians, then by Jensen's inequality,
\begin{align\*}
\mathbb{E}\left[\max\_{k\leq n} \left\vert \sum\_{i=1}^k \varepsilon\_i \right\vert\right] &= \sqrt{\frac{\pi}{2}} \mathbb{E}\left[\max\_{k\leq n} \left\vert \sum\_{i=1}^k \varepsilon\_i \mathbb{E}[\vert g\_i\vert] \right\vert\right]\\
&\leq \sqrt{\frac{\pi}{2}}\mathbb{E}\left[\max\_{k\leq n} \left\vert \sum\_{i=1}^k \varepsilon\_i\vert g\_i\vert \right\vert\right]\\
&=\sqrt{\frac{\pi}{2}}\mathbb{E}\left[\max\_{k\leq n} \left\vert \sum\_{i=1}^k g\_i \right\vert\right]\\
&\leq \sqrt{\frac{\pi}{2}}\mathbb{E}\left[\max\_{t\leq n} \left\vert B\_t\right\vert\right]\\
&=\pi/2\cdot \sqrt{n},
\end{align\*}
using the symmetry of standard Gaussians and upper bounding by a coupled Brownian motion and appealing to the MSE solution.


