Let $V$ be a set of $n$-dimensional vectors such that, for each ${\bf v}\in V$ and for each index $i\in [n-1]$, we have $0\le v_{i+1}\le v_i$. Let $P(\cdot)$ be a discrete probability distribution over $V$.

We are given the expected number $\mu$ of positive (i.e. non-null) vector components of a vector selected from $V$ with $P(\cdot)$.

Question: What is the maximum value of $\alpha$ for which the following inequality always holds? $$\max_{{\bf u}\in V} \sum_{i=1}^{\lceil \mu \rceil} u_i \ge \alpha\,\mathbb{E}_{P({\bf v})} ||{\bf v}||_1$$

(Does it always hold even for $\alpha=1$?)

  • 1
    $\begingroup$ You mean the maximum value of $\alpha$? $\endgroup$ – Iosif Pinelis May 3 '19 at 14:36
  • $\begingroup$ As @IosifPinelis mentioned, a minimal $\alpha$ doesn't make that much sense here. For the maximal one, you can easily construct an example that breaks for all $\alpha > 1$, e.g. by having only a single vector in $V$. $\endgroup$ – Dirk May 3 '19 at 14:47
  • $\begingroup$ Sorry, it was a typo. $\endgroup$ – Penelope Benenati May 3 '19 at 15:17

Your inequality holds with $\alpha=1/2$. Indeed, let $U=(U_1,\dots,U_n)$ be a random vector in $V$ with $N$ non-null coordinates, so that $U_1\ge\dots\ge U_N>0=U_{N+1}=\dots=U_n$; here $N$ is also random. Let $\nu:=\lceil \mu \rceil$. Let $$M:=\max_{{\bf u}\in V} \sum_{i=1}^\nu u_i. $$ Then $$M\ge \sum_{i=1}^\nu U_i\ge\Big(1\wedge\frac\nu N\Big)\sum_{i=1}^N U_i =\Big(1\wedge\frac\nu N\Big)\sum_{i=1}^n U_i. $$ So, $$\|U\|_1=\sum_{i=1}^n U_i\le\Big(1\vee\frac N\nu\Big)M\le\Big(1+\frac N\nu\Big)M $$ and hence $$E\|U\|_1\le\Big(1+\frac{EN}\nu\Big)M=\Big(1+\frac{\mu}\nu\Big)M\le2M, $$ so that $$M\ge\tfrac12\,E\|U\|_1,$$ as claimed.

  • $\begingroup$ Thank you losif Pinelis! $\endgroup$ – Penelope Benenati May 3 '19 at 16:26

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.