Return to Answer

First, if the subset $Z$ of $R^d$ of allowed values for $z$ is a singleton, then writing $e_n=(x_n-z)/\|x_n-z\|_2=(e_{n,j})_{j=1}^d$, we have $$E_\sigma \left\|\sum\sigma_ne_n\right\|_2=E_\sigma\sqrt{\sum_j \left(\sum_n\sigma_ne_{n,j}\right)^2}\le\sqrt{E_\sigma\sum_j\left(\sum_n\sigma_ne_{n,j}\right)^2}$$ $$%=\sqrt{\sum_jE_\sigma\left[\left(\sum_n\sigma_ne_{n,j}\right)^2\right]} =\sqrt{\sum_j\mathrm{Var}_\sigma\left[\sum_n\sigma_ne_{n,j}\right]} =\sqrt{\sum_j\sum_n\mathrm{Var}_\sigma\left[\sigma_ne_{n,j}\right]}$$ $$=\sqrt{\sum_j\sum_ne_{n,j}^2}=\sqrt{\sum_n \|e_n\|_2^2}=\sqrt{N}.$$ Second, if $Z$ is allowed to depend on $N$, then let $Z$ be of very small diameter, relative to

• the distances $\|x_i-x_j\|_2$,
• $N$, and
• the modulus of continuity of the function $z\mapsto \left\| \sum \sigma_n e_n\right\|_2$,

then we should be able to get we get for a fixed $z_0\in Z$, $$E_\sigma \left(\sup_z\left\|\sum\sigma_ne_n\right\|_2\right) \le E_\sigma\left( \left\|\sum\sigma_ne_n\text{ (for $z_0$)}\right\|_2 + \epsilon\right) = \mathcal O(\sqrt{N}).$$

First, if the subset $Z$ of $R^d$ of allowed values for $z$ is a singleton, then writing $e_n=(x_n-z)/\|x_n-z\|_2=(e_{n,j})_{j=1}^d$, we have $$E_\sigma \left\|\sum\sigma_ne_n\right\|_2=E_\sigma\sqrt{\sum_j \left(\sum_n\sigma_ne_{n,j}\right)^2}\le\sqrt{E_\sigma\sum_j\left(\sum_n\sigma_ne_{n,j}\right)^2}$$ $$%=\sqrt{\sum_jE_\sigma\left[\left(\sum_n\sigma_ne_{n,j}\right)^2\right]} =\sqrt{\sum_j\mathrm{Var}_\sigma\left[\sum_n\sigma_ne_{n,j}\right]} =\sqrt{\sum_j\sum_n\mathrm{Var}_\sigma\left[\sigma_ne_{n,j}\right]}$$ $$=\sqrt{\sum_j\sum_ne_{n,j}^2}=\sqrt{\sum_n \|e_n\|_2^2}=\sqrt{N}.$$ Second, if $Z$ is allowed to depend on $N$, then let $Z$ be of very small diameter $\delta>0$, relative to

• the distances $\|x_i-x_j\|_2$,
• $N$, and
• the modulus of continuity of the function $z\mapsto \left\| \sum \sigma_n e_n\right\|_2$,

then we should be able to get for a fixed $z_0\in Z$, and for all $\sigma$, $$\sup_{z\in Z}\left\|\sum\sigma_ne_n\right\|_2 \le \left\|\sum\sigma_ne_n\text{ (for $z_0$)}\right\|_2 + \epsilon$$ and hence $$E_\sigma \left(\sup_z\left\|\sum\sigma_ne_n\right\|_2\right) \le E_\sigma\left( \left\|\sum\sigma_ne_n\text{ (for $z_0$)}\right\|_2 + \epsilon\right) = \mathcal O(\sqrt{N}).$$

First, if the subset $Z$ of $R^d$ of allowed values for $z$ is a singleton, then writing $e_n=(x_n-z)/\|x_n-z\|_2=(e_{n,j})_{j=1}^d$, we have $$E_\sigma \left\|\sum\sigma_ne_n\right\|_2=E_\sigma\sqrt{\sum_j \left(\sum_n\sigma_ne_{n,j}\right)^2}\le\sqrt{E_\sigma\sum_j\left(\sum_n\sigma_ne_{n,j}\right)^2}$$ $$%=\sqrt{\sum_jE_\sigma\left[\left(\sum_n\sigma_ne_{n,j}\right)^2\right]} =\sqrt{\sum_j\mathrm{Var}_\sigma\left[\sum_n\sigma_ne_{n,j}\right]} =\sqrt{\sum_j\sum_n\mathrm{Var}_\sigma\left[\sigma_ne_{n,j}\right]}$$ $$=\sqrt{\sum_j\sum_ne_{n,j}^2}=\sqrt{\sum_n \|e_n\|_2^2}=\sqrt{N}.$$ Second, if $Z$ is allowed to depend on $N$, then let $Z$ be of very small diameter, relative to

• the distances $\|x_i-x_j\|_2$,
• $N$, and
• the modulus of continuity of the function $z\mapsto \left\| \sum \sigma_n e_n\right\|_2$,

then we should be able to get we get for a fixed $z_0\in Z$, $$E_\sigma \left(\sup_z\left\|\sum\sigma_ne_n\right\|_2\right) \le E_\sigma\left( \left\|\sum\sigma_ne_n\text{ (for $z_0$)}\right\|_2 + \epsilon\right) = \mathcal O(\sqrt{n}).$$

First, if the subset $Z$ of $R^d$ of allowed values for $z$ is a singleton, then writing $e_n=(x_n-z)/\|x_n-z\|_2=(e_{n,j})_{j=1}^d$, we have $$E_\sigma \left\|\sum\sigma_ne_n\right\|_2=E_\sigma\sqrt{\sum_j \left(\sum_n\sigma_ne_{n,j}\right)^2}\le\sqrt{E_\sigma\sum_j\left(\sum_n\sigma_ne_{n,j}\right)^2}$$ $$%=\sqrt{\sum_jE_\sigma\left[\left(\sum_n\sigma_ne_{n,j}\right)^2\right]} =\sqrt{\sum_j\mathrm{Var}_\sigma\left[\sum_n\sigma_ne_{n,j}\right]} =\sqrt{\sum_j\sum_n\mathrm{Var}_\sigma\left[\sigma_ne_{n,j}\right]}$$ $$=\sqrt{\sum_j\sum_ne_{n,j}^2}=\sqrt{\sum_n \|e_n\|_2^2}=\sqrt{N}.$$ Second, if $Z$ is allowed to depend on $N$, then let $Z$ be of very small diameter, relative to

• the distances $\|x_i-x_j\|_2$,
• $N$, and
• the modulus of continuity of the function $z\mapsto \left\| \sum \sigma_n e_n\right\|_2$,

then we should be able to get we get for a fixed $z_0\in Z$, $$E_\sigma \left(\sup_z\left\|\sum\sigma_ne_n\right\|_2\right) \le E_\sigma\left( \left\|\sum\sigma_ne_n\text{ (for $z_0$)}\right\|_2 + \epsilon\right) = \mathcal O(\sqrt{N}).$$

I guess you also have to assume something about the subset of $R^d$ of allowed values for $z$.

If it is just a singleton, then writing $e_n=(x_n-z)/\|x_n-z\|_2=(e_{n,j})_{j=1}^d$, we have $$E_\sigma \left\|\sum\sigma_ne_n\right\|_2=E_\sigma\sqrt{\sum_j \left(\sum_n\sigma_ne_{n,j}\right)^2}\le\sqrt{E_\sigma\sum_j\left(\sum_n\sigma_ne_{n,j}\right)^2}$$ $$%=\sqrt{\sum_jE_\sigma\left[\left(\sum_n\sigma_ne_{n,j}\right)^2\right]} =\sqrt{\sum_j\mathrm{Var}_\sigma\left[\sum_n\sigma_ne_{n,j}\right]} =\sqrt{\sum_j\sum_n\mathrm{Var}_\sigma\left[\sigma_ne_{n,j}\right]}$$ $$=\sqrt{\sum_j\sum_ne_{n,j}^2}=\sqrt{\sum_n \|e_n\|_2^2}=\sqrt{N}.$$

First, if the subset $Z$ of $R^d$ of allowed values for $z$ is a singleton, then writing $e_n=(x_n-z)/\|x_n-z\|_2=(e_{n,j})_{j=1}^d$, we have $$E_\sigma \left\|\sum\sigma_ne_n\right\|_2=E_\sigma\sqrt{\sum_j \left(\sum_n\sigma_ne_{n,j}\right)^2}\le\sqrt{E_\sigma\sum_j\left(\sum_n\sigma_ne_{n,j}\right)^2}$$ $$%=\sqrt{\sum_jE_\sigma\left[\left(\sum_n\sigma_ne_{n,j}\right)^2\right]} =\sqrt{\sum_j\mathrm{Var}_\sigma\left[\sum_n\sigma_ne_{n,j}\right]} =\sqrt{\sum_j\sum_n\mathrm{Var}_\sigma\left[\sigma_ne_{n,j}\right]}$$ $$=\sqrt{\sum_j\sum_ne_{n,j}^2}=\sqrt{\sum_n \|e_n\|_2^2}=\sqrt{N}.$$ Second, if $Z$ is allowed to depend on $N$, then let $Z$ be of very small diameter, relative to

• the distances $\|x_i-x_j\|_2$,
• $N$, and
• the modulus of continuity of the function $z\mapsto \left\| \sum \sigma_n e_n\right\|_2$,

then we should be able to get we get for a fixed $z_0\in Z$, $$E_\sigma \left(\sup_z\left\|\sum\sigma_ne_n\right\|_2\right) \le E_\sigma\left( \left\|\sum\sigma_ne_n\text{ (for $z_0$)}\right\|_2 + \epsilon\right) = \mathcal O(\sqrt{n}).$$