Consider the ordered set $\mathcal{S}$ $=$ $\{0,a_i,a_2,\ldots,a_n\}$, where $a_i$ are all stricly positive real numbers and $a_i< a_{i+1}$ forall indices i. What is the random variable $X$ which takes values in this set, has mean $\mathbb{E}(X) = \alpha$, where $0 \leq \alpha \leq a_n$ and has minimum second moment $\mathbb{E}(X^2)$.

I posed the problem as a following linear program

Find $p = (p_0,p_1,\ldots,p_n)$ which minimizes \begin{eqnarray} \sum_{i=1}^n a_i^2p_i \end{eqnarray} such that \begin{eqnarray} \sum_{i=1}^n a_ip_i = \alpha, \quad \sum_{i=0}^n p_i=1, \quad p\geq 0. \end{eqnarray} I think the answer to the above LP is the distribution $p^*$ which satisfies

$$p^{*}_j= \begin{cases} \frac{a_{k+1} - \alpha}{a_{k=1}-a_k},& \text{if } j = k = \operatorname{argmax}\limits_r \{a_r \leq \alpha\} \\[4pt] 1 - p^*_k ,& \text{if } j = k + 1 \\[4pt] 0,& \text{otherwise}. \end{cases} $$ Is this true?

A partial proof???: Observe that as the mean is fixed, minimizing the second moment is equivalent to minimizing the variance. Now for any random variable $X$ with support set lying between $a$ and $b$ ($\infty>b>a>-\infty$), we have Var$(X)< \frac{(b-a)^2}{4}$. To prove this observe that $Var(X)\leq E(X-c)^2$ for any $c \in \mathbb{R}$. Now choose $c = (b+a)/2$ and observe that $|X-c|\leq (b-a)/2$, hence for this $c$, we get Var$(X)< \frac{(b-a)^2}{4}$.

For the above problem, we want to find a random variable $X \in {\mathcal{S}}$, which minimizes the variance with mean fixed to be $\alpha$. Let the boundaries of the support set of any random variable $Y\in {\mathcal{S}}$ with mean fixed to be $\alpha$ be $Y_{m}$ and $Y^{m}$ respectively. Then $Var(Y)\leq \frac{(Y^{m}-Y_{m})^2}{4}$. Note that $Y^m, Y_m$ both belong to the set ${\mathcal{S}}$. To find the minimum variance random variable $X$, we first minimize $\frac{(X^{m}-X_{m})^2}{4}$, but this is minimized when $X_m = a_k$ where $k = \operatorname{argmax}\limits_r \{a_r \leq \alpha\}$ and $X^m = a_{k+1}$ if $\alpha \neq a_k$ otherwise $X^{m} = X_{m}$. Now the solution presented above can be computed directly.

  • $\begingroup$ I think you are correct, but I don't want to write out KKT details to prove it. You can test it with Matlab; for example, n=10; x=[0;rand(n-1,1)]; Beq=[rand;1]; fmincon(@(p) p.*x.^2,ones(n,1)/n,-eye(n),zeros(n,1),[x';ones(1,n)],Beq); What you find indeed appears to be what you get. The key thing is that your assumptions mean that there is always either $i$ such that $a_i=\alpha$ or $a_{i-1}<\alpha<a_i$. If you tweak the assumptions, e.g. do not assume $0 \in \mathcal{S}$, then this doesn't work and problems ensue. $\endgroup$ – Ian May 12 '16 at 15:53
  • $\begingroup$ I am slightly confused about this comment. In the case that $0 \notin {\mathcal{S}}$, i would have changed the assumption to $a_1 \leq \alpha \leq a_n$, hence always ensuring the existence of a feasible solution for the lp. Even in this case, intuitively, i think the ans remains the same. $\endgroup$ – Nubres May 12 '16 at 16:26
  • $\begingroup$ Yes, you can tweak the assumptions. But you need $\alpha $ between the min and max element definitely...though I only just now realized that otherwise it is impossible to satisfy the constraints. $\endgroup$ – Ian May 12 '16 at 16:32
  • $\begingroup$ I have tightened the assumptions that the numbers $a_i$ be strictly increasing. $\endgroup$ – Nubres May 12 '16 at 17:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.