# Random optimization problem

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

• You mean the maximum value of $\alpha$? – Iosif Pinelis May 3 at 14:36
• 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$. – Dirk May 3 at 14:47
• Sorry, it was a typo. – Penelope Benenati May 3 at 15:17

## 1 Answer

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.

• Thank you losif Pinelis! – Penelope Benenati May 3 at 16:26