Exercise 2.15 from Boyd & Vandenberghe's Convex Optimization:
Let $x$ be a real random variable with $\textbf{prob}(x=a_i) = p_i$, where $a_1 < a_2 < \cdots < a_n$. In this case, show whether $$\textbf{quart}(x)\leq \alpha$$ is convex in $p$ or not. (where $\textbf{quart}(x)=\inf\{\beta~ |~\textbf{prob}(x\leq\beta)\geq.25\}$).
The answer to this question in the solution manual is as follows:
The constraint $\textbf{quart}(x)\leq \alpha$ is equivalent to $$\textbf{prob}(x\leq \beta)\geq .25~\text{for all }\beta\geq \alpha.~~~~~(1)$$
This can be expressed as a linear inequality $$\sum_{i=k+1}^np_i\geq.25,~~~~~(2)$$ where $k=\max\{i~|~a_i<\alpha\}$.
My question:
In my view equation (1) should mean that, assuming that $a_m$ is the smallest value which is $\geq \alpha$ that random variable $x$ can take, $$p_1+p_2+\cdots p_m\geq .25\\p_1+p_2+\cdots p_m+p_{m+1}\geq .25\\ \vdots \\ p_1+p_2\cdots+p_n\geq.25.$$(please check if this is a right set of inequalities for equation (1).) And I think these set of inequalities can be replaced by following inequality $$p_1+p_2+\cdots p_m\geq .25$$ which is $$\sum_{i=1}^{k+1}p_i\geq .25.$$ But this does not matches with equation (2) above. Where is my thinking wrong? Any help in this regard will be much appreciated. Thanks in advance.
Best Answer
Your new sum should be up to $k$, but yes, otherwise, the linear inequality for $p$ to show that it belongs into this set is:
$\sum_{i=1}^k p_i \geq 0.25$ where $k = \max \{ i \mid a_i \leq \alpha\}$ (pick $k$ to be $0$ if $a_1 < \alpha$; the inequality is definitely violated in that case anyway).
To see this, note that if the inequality is violated, then we have that sum of the probabilities of $a_i$s below $\alpha$ is strictly less than $0.25$, and thus the quartile is bigger than $\alpha$. The converse proof is exactly the same.