Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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!

share|improve this question
$\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
add comment

3 Answers 3

up vote 0 down vote accepted

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

share|improve this answer
add comment

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

share|improve this answer
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
add comment

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?

share|improve this answer
The first inequality is wrong... it seems that it should be of order n. –  user11870 Apr 18 '12 at 19:25
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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