Let $X$ be a random variable that is uniformly distributed on the set $\Theta\equiv\left\{ 0,\frac{1}{n},\frac{2}{n},...,\frac{n-1}{n},1\right\} $ for some large $n$. Suppose that the set $\Theta$ is split into $I\geq2$ subsets $S_{1},\ldots,S_{I}$ such that each element $\theta\in\Theta$ is assigned into one subset $S_{i}$.

Denote the probability of set $S_{i}$ by $p_{i}=\sum_{\theta\in S_{i}}\frac{1}{n+1}$, the expectation of $X$ on $S_{i}$ by $\mu_{i}=\frac{\frac{1}{n+1}\sum_{\theta\in S_{i}}\theta}{p_{i}}$, and the variance of $X$ on $S_{i}$ by $VAR_{i}=\frac{\sum_{\theta\in S_{i}}\left(\theta-\mu_{i}\right)^{2}}{(n+1)p_{i}}$. Assume without loss that $\mu_{1}\leq\mu_{2}\leq\cdots\leq\mu_{I}$.

Suppose that the split is subject to the following constraints:

$\frac{\mu_{i}+\mu_{i+1}}{2}-\theta_{max}^{i}\geq c\qquad\forall i\in\left\{ 1,\ldots,I-1\right\}$

where $\theta_{max}^{i}\in S_{i}$ denotes the largest element in $S_{i}$ and $c>0$ is a parameter. Suppose that $c$ is small enough such that a split that satisfies the constraints exists.

My question: It seems that the split that minimizes the weighted variance

$ \sum_{i=1}^{I}p_{i}VAR_{i}=\frac{1}{n+1}\sum_{\theta\in\Theta}\theta^{2}-\sum_{i=1}^{I}p_{i}\mu_{i}^{2}, $

subject to the constraints is such that all the sets $S_{i}$ satisfy the following "convexity" property:

For every $i\in \left\{ 1,...,I\right\} $, if $\theta ^{\prime }\in \Theta $ and $\theta ^{\prime \prime }\in \Theta $ are elements in $S_{i}$ such that $% \theta ^{\prime }<\theta ^{\prime \prime }$, then every $\theta \in \Theta $ that satisfies $\theta ^{\prime }<\theta <\theta ^{\prime \prime }$ is also an elements in $S_{i}$.

Any idea of how to prove this will be greatly appreciated.


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.