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](https://projecteuclid.org/euclid.aop/1176988477) 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).$$



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}$?
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](https://en.wikipedia.org/wiki/Hoeffding%27s_inequality#General_case_of_bounded_random_variables), 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. 


