3
$\begingroup$

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!

Improve this question
$\endgroup$
4
  • $\begingroup$ $\varepsilon $? $\endgroup$
    – cardinal
    Apr 18, 2012 at 18:06
  • $\begingroup$ where is $\varepsilon$? $\endgroup$
    – user11870
    Apr 18, 2012 at 18:39
  • $\begingroup$ First line. Should be $t$? $\endgroup$
    – cardinal
    Apr 18, 2012 at 18:48
  • 1
    $\begingroup$ 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. $\endgroup$
    – George Lowther
    May 2, 2012 at 23:08

3 Answers 3

Reset to default
0
$\begingroup$

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

Improve this answer
$\endgroup$
0
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • $\begingroup$ At the beginning, I also think so. However, I did not find a mistake in my answer provided below... So I doubt.. $\endgroup$
    – user11870
    Apr 18, 2012 at 19:00
  • $\begingroup$ 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. $\endgroup$
    – tipanverella
    Apr 18, 2012 at 19:29
  • $\begingroup$ actually, $Var(\xi(x)) \le 1$. $\endgroup$
    – tipanverella
    Apr 18, 2012 at 19:40
0
$\begingroup$

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?

Improve this answer
$\endgroup$
1
  • $\begingroup$ The first inequality is wrong... it seems that it should be of order n. $\endgroup$
    – user11870
    Apr 18, 2012 at 19:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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