# 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}$?

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

$$\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).$$

• For the general case, apply concentration to each coordinate as you did for the independent case, but then use the union bound instead of taking the product. This should give you that sqrt d is impossible Apr 6, 2020 at 23:59

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.