Is there an i.i.d sequence in the unit cube $[-1,1]^d$ with $\mathbb E \left[ \Big \| \sum_{i=1}^N X_N \Big \|_\infty\right] = \sqrt {dN}$?

Question

There are loads of concentration results for sums of scalar-valued independent sums $X_1,X_2,\ldots, X_N$ with $\mathbb E[X_n]=0$. For example Hoeffding's Inequality says if all $|X_1|\le 1$ then $\mathbb E\left[ \left|\sum_{i=1}^N X_i\right|\right] = O (\sqrt N)$.

These concentration results can be generalised for example to vector-valued random variables with $\|X_n\| \le 1$ for $\| \cdot \|$ the Euclidean norm.

Suppose instead we have $\|\cdot\|_\infty$ norm bounds. That means $X_1,X_2,\ldots, X_N \in \mathbb R^d$ are independent with $\mathbb E[X_n]=0$ and $\|X_n\|_\infty \le 1$. Since $\|X_n\|_2 \le \sqrt d \|X_n\|_\infty \le \sqrt d$ we can use concentration results for the Euclidean norm to get $\mathbb E\left[ \left\|\sum_{i=1}^N X_i\right\|_\infty\right] = O (\sqrt {dN})$.

Does anyone know an example of when this dependence on $\sqrt d$ actually occurs?

Note: This is a bit informal. What I'm really asking is if the $O(\sqrt{dN})$ bound can be improved. I imagine a negative answer would be a family of examples of i.i.d sequences $X_n^{(d)}$, one for each value of $d$, such that $\mathbb E\left[ \left\|\sum_{i=1}^N X_i^{(d)}\right\|_\infty\right] \ge F(\sqrt {dN})$ for some common $\Omega(\sqrt{dN})$ function $F$.

I suspected such an example might be $X_n = (B_1^1,\ldots, B^1_d)$ for all $B^i_j$ independent and taking values $\pm 1$ with probability $1/2$. However the expectation seems more like $O (\sqrt {\log(d)N})$. To see this apply scalar concentration to each $j$ coordinate to get, up to coefficients:

$$P\left( \Big\|\sum_{i=1}^N X_i \Big\|_\infty <t\right)= P\left(\text{all } \Big|\sum_{i=1}^N X_i(j)\Big| <t \right)=\prod_{j=1}^d P\left(\Big|\sum_{i=1}^N X_i(j)\Big| <t \right) \ge (1-e^{-t^2 /N})^d.$$

$$\mathbb E \Big\|\sum_{i=1}^N X_i \Big\|_\infty = \int_0^\infty P\left( \Big\|\sum_{i=1}^N X_i(j)\Big\|_\infty >t\right)dt \le \int_0^\infty (1-(1-e^{-t^2/N})^d )dt$$

I don't know if the integral has a closed form. What I do know is the same argument gives $$\mathbb E \Big\|\sum_{i=1}^N X_i \Big\|_\infty ^2 \le \int_0^\infty (1-(1-e^{-t/N})^d )dt$$

which I do know how to solve. Substitute $x = e^{-t/N}$ to get $dt = - (N/x)dx$ and the integral becomes

$$ N \int_0^1 \frac{(1-(1-x)^d )}{x}dx$$

which equals $N$ times the $d$-th harmonic number, which is $O(N \log d)$. So we have $$\mathbb E \Big\|\sum_{i=1}^N X_i \Big\|_\infty ^2 \le O\left(N \log(d) \right)$$ and by the Jensen inequality $$\mathbb E \Big\|\sum_{i=1}^N X_i \Big\|_\infty \le O\left(\sqrt{\log(d) N}\right).$$

Answer 1

Let $X_i=(X_{i,1},\dots,X_{i,d})$, $S:=(S_1,\dots,S_d)$, $S_j:=\sum_{i=1}^d X_{i,j}/\sqrt n$. Then, by Hoeffding's inequality, for $s\ge0$ $$P(|S_j|\ge s)\le2e^{-s^2/2},$$ whence $$E\|S\|_\infty=\int_0^\infty ds\,P(\|S\|_\infty\ge s) \le\int_0^\infty ds\,\min(1,2d\,e^{-s^2/2}) =O(1+\sqrt{\ln d});$$ here we used the inequality $$\int_t^\infty ds\,e^{-s^2/2}\le e^{-t^2/2}/2$$ for $t\ge0$. So, for $d\ge2$ you get $$E\Big\|\sum_{i=1}^n X_i\Big\|_\infty=O(\sqrt{n\ln d}),$$ without the assumption of the independence of the coordinates and without any other additional assumptions.