# How to bound the sup norm of a Rademacher process or equivalently a Gaussian process?

I want to know how to find an upper bound of the following expectation taken for both $t$ and $y$ as

$$\mathbb{E}\sup_{x \in D} \left|\sum_{k=1}^n t_k x^T y_k\right|,$$ where $D$ is the set of vectors defined by $$D = ( x \in \mathbb{R}^m \mid 0\leq x_i \leq 1, \forall 1\leq i\leq m ),$$

$\left(t_k\right)_{k=1}^n$ is the Rademacher sequence, that is, $t_1, \cdots, t_n$ are i.i.d. copies of a random variable $t$ taking values $\pm 1$ with $\mathbb{P}(t=1)=\mathbb{P}(t=-1)=1/2$, and $(y_k)$ are i.i.d. copies of a random vector $y \in \mathbb{R}^m$ taking values $e_1,\cdots,e_m$ with $\mathbb{P}(y = e_i)=p_i$. Here, $e_i$ denotes the vector from the standard basis with $i$-th component being 1 and the others being 0.

I first get rid of the absolute value as \begin{align} & \mathbb{E}\sup_x \left|\sum t_k x^T y_k\right| \leq \mathbb{E}_y\left(\sqrt{\frac{\pi}{2}} \mathbb{E}_s \sup_x\left| \sum s_k x^T y_k\right|\right) \\\\ \leq & \sqrt{2\pi} \mathbb{E}_y\left(\mathbb{E}_s \sup_x\left(\sum s_k x^T y_k \right)\right) = \sqrt{2\pi} \mathbb{E} \sup_x\left(\sum s_k x^T y_k \right), \end{align} where $s_k$ are i.i.d copies of a standard normal random variable.

Then, how to continue? My guess is that the upper bound seems to be of order $O(\sqrt{n})$. Is that correct? Thanks!

-
$\varepsilon$? –  cardinal Apr 18 '12 at 18:06
where is $\varepsilon$? –  user11870 Apr 18 '12 at 18:39
First line. Should be $t$? –  cardinal Apr 18 '12 at 18:48
Yes, thanks for pointing –  user11870 Apr 18 '12 at 18:59
This is a random walk, so yes, it is $O(\sqrt{n})$ and furthermore, in the limit, the distribution will approach a d-dimensional Brownian motion. –  George Lowther May 2 '12 at 23:08

The quantity is of the order $n$ (at least without any additional restriction on the $p_i$'s).

To see the upper bound:

$$\mathbb{E}\sup_{x \in D} \left|\sum_{k=1}^n t_k x^T y_k\right| \leq \sum_{k=1}^n \mathbb{E} \left| 1^T y_k\right| \leq n$$

where $1^T$ denotes the $1$'s vector.

To see the lower bound, set $p_i=1/n$. Now with at least constant probability the $y_k$'s will include at least $.1 n$ distinct vectors. Also, with large probability, at least, say, 40% of the $k$'s with distinct $y_k$ vectors will be such that $t_k = +1$. Let $S$ denote the resulting set of at least $.36 n$ indices / $k$'s. We can then define $x \in D$ such that $x_k =1$ if $k \in S$ and $x_k=0$ otherwise. When this occurs (which happens with constant / non-zero probability) the expression is $\gg .36 n$.

(It is possible to choose $p_i$'s such that the quantity is significantly smaller. Take $p_1 =1$ and $p_i=0$ (for $i>1$), then the sum is essentially that of $n$ Rademacher functions, and the expectation should be around $\sqrt{n}$).

-

$t$ is symmetric, but $y$ is not necessarily so. My intuition is that an upper bound would have to depend on the set of $p_i, i \in \{1, \ldots, m\}$, for . Does that make sense?

-
At the beginning, I also think so. However, I did not find a mistake in my answer provided below... So I doubt.. –  user11870 Apr 18 '12 at 19:00
If you write $\xi(x) = tx^Ty$, you should be able to write down the pmf of $\xi(x)$ given $x$. In particular, $\mathbb{E}\xi(x) = 0$ and $Var(\xi) \le m$. You could then say that $f_n(x) = \sum_{i=1}^n \xi_k(x)$ with $\xi_k(x)$ iid; which means that you have a WLLN for $\frac{f_n(x)}{n}$ and also large deviations bounds. I am thinking that these little pieces should start to give a decent picture towards a bound, since $$\mathbb{E}\sup_{x\in D} |f_n(x)| is what you are interested in. – tipanverella Apr 18 '12 at 19:29 actually, Var(\xi(x)) \le 1. – tipanverella Apr 18 '12 at 19:40 Is the following correct? Notice that t and y are independent, we have \mathbb{E} = \mathbb{E}_y\mathbb{E}_t. Then we focus on the inner expectation \mathbb{E}_t for some fixed y_1=e_{(1)},\cdots, y_n=e_{(n)}.$$\mathbb{E} \sup_{x\in D}\left|\sum_{k=1}^n t_k x^T y_k\right| = \mathbb{E} \sup_{x\in D} \left|\sum_{k=1}^n t_kx_{(k)} \right|\leq \mathbb{E}\left|\sum_{k=1}^n t_k \right|\leq \sqrt{\frac{\pi}{2n}} \quad ???

The above upper bound does not depend on $y$. Thus, it is also an upper bound for the expectation of both $y$ and $t$. Is this correct?

-
The first inequality is wrong... it seems that it should be of order n. –  user11870 Apr 18 '12 at 19:25