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



Random optimization problem
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. 


