How is the variance equivalent to the following?

Question

I am working through a problem that asks if the set, $P$ is convex.

Note that $P$ is a set of pdfs. Each member $p \in P$ describes a pdf - a vector of real numbers that are probabilities. The assignment is to determine if the set of all pdfs (all $p$'s) subject to a restriction on the variance, is a convex set.

These are the restrictions on $p$, including the inequality for the variance of all of all of the $p$'s:

• $p$ is a vector of probabilities, $p \in \mathbb{R}^+$

• probability simplex, which is of course a restriction on $p$ $P = \{p \, \vert \sum_{i=1}^{n}{p_i} = 1 , p \ge 0\}$

• $p_i$ is the probability that random variable $x$ is $x=a_i$ with $x \in \mathbb{R}$

• $var(x) \ge \alpha\ $and$ \,\,var(x) = \sum_{i=1}^n{(x_i-E[x])^2}\}$

• $\alpha \in \mathbb{R}$ and $var(x) = \sum_{i=1}^n{(x_i-E[x])^2}$ and $E[x]=\sum_{i=1}^np_ix_i$

Now, in the Solutions to the homework I see

In the solutions to my homework, it says that that "$var(x) \ge \alpha$ can be reformulated as $\sum_{i=1}^np_ia_i^2+(\sum_{i=1}^np_ia_i)^2 \le \alpha$".

This is obviously convex...so I can see the answer from there.

But, my question is how can this inequality $var(x) \ge \alpha$ be reformulated as $\sum_{i=1}^np_ia_i^2+(\sum_{i=1}^np_ia_i)^2 \le \alpha$ ?

EDIT Here is the homework question in full. I am particularly asking about parts (f) and (g):

And here is the solution:

If you'd like any more information, please let me know.

Answer 1

This question cannot be answered as is, because we lack a proper definition of "convex" in this setting.

For a complete answer, the full homework text is needed.

Setup

Let's write in here all the assumptions ans appreciations:

Definitions:

• $\mathscr P$ is a infinite set of discrete pdfs, for a fixed set of numbers $a_i \in \mathbb{R}$,
• $f_j$ is a discrete pdf for the random variable $x_j$, described through the vector $p_j \in \mathbb{R}^n$, $j=1...m$: $$ f_j(x)=\sum_{i=1}^np_{ij}\delta(x-a_{i}), \sum_{i=1}^np_{ij}=1, p_{ij}\ge 0 $$

Constraint:

• $\text{var}(x) \ge \alpha, \alpha \gt 0$

Applying the definition of variance to the $j$th pdf: $$ \text{var}\{f_j\}= \sum_{i=1}^np_{ij}a_{i}^2-\left(\sum_{i=1}^np_{ij}a_{i}\right)^2 \ge \alpha $$

Question

To determine if the set of all $p \in \mathscr P$ subject to a restriction on the variance, is a convex set.

Possible Interpretations

• Over the set $\mathscr P$ it is trivial to apply convex combinations, if we assume $\mathscr P$ is infinite,
• Over the domain $\mathbb{R}$, for the area defined by each function $f_j(x)$ it is not possible to interpolate a line, because each pdf is discrete, made of delta impulses, hence the interpolations, if valid, are always above the area, hence not being convex.

Best interpretation

A Convex Combination over a set of pdfs or also called a Mixture Distribution is the pdf obtained by weighting every pdf through non-negative numbers with sum equal to 1: $$ f_m(x)=\sum_{j=1}^mb_jf_j(x), \sum_{j=1}^mb_j=1, b_j\ge 0 $$

Hence: $$ f_m(x)=\sum_{i=1}^n \left(\sum_{j=1}^m b_jp_{ij} \right) \delta(x-a_{i}) = \sum_{i=1}^n \beta_{ij} \delta(x-a_{i}) $$ Note that $\sum \beta_{ij}>1, \beta_{ij}>0$ (why?).

Thus, it is possible to build convex combinations from elements of $\mathscr P$ with or without the given constraint, by definition.

Assuming also than the set $\mathscr P$ is not finite, but $p_i \in \mathbb{R}$ we found from the given operation that $\mathscr P$ is closed under convex combinations, hence $\mathscr P$ is convex trivially. But this is independent on the given constraint, and keeps being a void question.

Main Comment

EDIT: - As pointed out, the expression is equivalent to: $$ \text{var}\{f_j\}= \sum_{i=1}^np_{ij}a_{i}^2-\left(\sum_{i=1}^np_{ij}a_{i}\right)^2 \ge \alpha \\ \sum_{i=1}^np_{ij}a_{i}^2+\left(\sum_{i=1}^np_{ij}a_{i}\right)^2 \ge \alpha + 2\left(\sum_{i=1}^np_{ij}a_{i}\right)^2 \ge \alpha $$ Which is the opposite to the given answer in (g), hence the set is not convex.

Answer 2

I think there might be a mistake in the solutions you were given (in fact, I suspect this problem is from a class I TA'd, EE364A, due to the similarities in formatting, etc).

The idea is that we can write $\text{var}(x)$ as $$ \text{var}(x) = \sum_i p_ia_i^2 - \left(\sum_i p_ia_i\right)^2 $$ but note that your expression in this case is wrong in both the inequality direction and sign, since you can't sum both of the terms to get an expression for variance. Additionally, note that we're asking for convexity w.r.t. $p$. This is now not a convex function, but rather a concave one. Both notions should be easy to prove from here.

Answer 3

First we know that $$ \mathbf{Var}(x) = Ex^2 - (E(x))^2 = \sum_{i=1}^np_i a_i^2 - (\sum_{i=1}^np_ia_i) ^2 \geq \alpha $$ The set is equilvalent to $$ - \sum_{i=1}^np_i a_i^2 + (\sum_{i=1}^np_ia_i) ^2 \leq \alpha $$ Define $b = [-a_1^2,-a_2^2,...,-a_n^2], A = aa^T $​​​, then it is equilvalent to $$ -b^Tp + p^TAp \leq \alpha $$ With $-b^p, p^TAp$ are both convex function about $x$, $f(p) = -b^Tp + p^TAp $ is also convex. With the image of $f$ with $f(x) \leq \alpha$, the image of $f$ is convex. Then the inverse image $p$ is also convext.

Proof done.

Note: A is positive semidefinite, such that $p^TAP$ is convex .