Let $(x_1,...,x_N)$ be points in $R^d$, and $\sigma=(\sigma_1,...,\sigma_N)$ are i.i.d. Rademacher variables (+1 or -1 with probability 0.5 each). (Or alternatively, $\sigma$ could be a standard Gaussian vector.) Also let $z$ in an infinite subset of $R^d$, and $\|\cdot\|_2$ will denote the Euclidean norm. I am looking for a good upper estimate of:

$E_{\sigma} \sup_z \| \sum_{n=1}^N \sigma_n \frac{x_n-z}{\|x_n-z\|_2} \|_2$.

So far I only got the upper bound of $N$ (by triangle inequality), and the lower bound $\sqrt{N}$ by Jensen inequality, and I would like to know if there is a way to improve on the upper estimate or the lower estimate?

If not, are there conditions (on the domain of $z$) under which the upper bound would reduce to ${\mathcal O}(\sqrt{N})$?

Edit: The points $x_1,...,x_N$ are assumed to be in general position (in a ball of radius $R$).

Edit2: The domain of values of $z$ is an infinite set in $R^d$. Can be assumed to be bounded.

Edit3: The domain of $z$ is allowed to depend on $N$, $R$ (or on other assumed characteristics of the point set), but not on the individual points.

Edit4: I also want to avoid dependence on $d$.

  • $\begingroup$ So is the domain of $z$ allowed to depend on the $x_i$? $\endgroup$ – Bjørn Kjos-Hanssen Apr 22 '17 at 6:02
  • $\begingroup$ Preferably not, but it's okay to let it depend on inter-point distances. $\endgroup$ – axk Apr 22 '17 at 6:07

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.