Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $\mathbf{x}$ be a vector of $n$ numbers in the range $[0, p]$, where $p$ is a positive real number.

What's is the maximum of the variance function of this $n$ numbers?

The variance of the vector $\mathbf{x}$ is given by:

$$ \operatorname{var} (\mathbf{x}) = \frac{1}{n} \sum_{i=1}^{n} {\left( {x}_{i} - \overline{\mathbf{x}} \right )}^2 $$

Where the mean $\overline{\mathbf{x}}$ is given by:

$$ \overline{\mathbf{x}} = \frac{1}{n} \sum_{i=1}^n x_i .$$

Thank You.

share|improve this question
    
What is the variance function of a set? The maximum with respect to what? Please try to rephrase your question using more standard terminology. –  joriki Nov 17 '11 at 13:44
1  
If $X$ takes on values in an interval of length $c$, then its variance is bounded above by $c^2/4$ with equality when half the probability mass is at one end of the interval and half at the other (assuming the interval is closed at both ends; else we have strict inequality) –  Dilip Sarwate Nov 17 '11 at 13:47
    
@DilipSarwate, Does it work just like Entropy? What if I have only 3 samples in the range [0 1], which variance could they achieve at most? It seems you neglected the factor of how many samples there are. –  Drazick Nov 17 '11 at 14:24
    
@joriki, I've updated the question. Thank You. –  Drazick Nov 17 '11 at 14:25
1  
"What if I have only 3 samples in the range [0 1], which variance could they achieve at most?" The maximum is still bounded above by $c^2/4$ which is $1/4$ in this instance. The bound cannot be attained with equality in this instance but that does not invalidate the bound. For odd $n$ and $c = 1$, putting one point at the center (mean) and the rest at the end points gives $\frac{1}{4}\times \frac{n-1}{n}$ which, when $n$ is large, is close enough to the upper bound of $\frac{1}{4}$for gummint purposes. –  Dilip Sarwate Nov 17 '11 at 15:50

1 Answer 1

up vote 3 down vote accepted

Since $x_i \leq c$, $\displaystyle \sum_i x_i^2 = \sum_i x_i\cdot x_i \leq \sum_i c\cdot x_i = cn\bar{x}.$ Note also that $0 \leq \bar{x} \leq c$. Then, $$ \begin{align*} n\cdot \text{var}(\mathbf{x}) &= \sum_i (x_i - \bar{x})^2= \sum_i x_i^2 - 2x_i\bar{x} + \bar{x}^2\\ &= \sum_i x_i^2 - 2\bar{x}\sum_i x_i + n\bar{x}^2= \sum_i x_i^2 - n\bar{x}^2\\ &\leq cn\bar{x} - n\bar{x}^2 = n\bar{x}(c-\bar{x}) \end{align*} $$ and thus $$\text{var}(\mathbf{x}) \leq \bar{x}(c-\bar{x}) \leq \frac{c^2}{4}.$$

Added note: (second edit)
The result $\text{var}(X) \leq \frac{c^2}{4}$ also applies to random variables taking on values in $[0,c]$, and, as my first comment on the question says, putting half the mass at $0$ and the other half at $c$ gives the maximal variance of $c^2/4$. For the vector $\mathbf x$, if $n$ is even, the maximal variance $c^2/4$ occurs when $n/2$ of the $x_i$ have value $0$ and the rest have value $c$. Someone else posted an answer -- it has since been deleted -- which said the same thing and added that if $n$ is odd, the variance is maximized when $(n+1)/2$ of the $x_i$ have value $0$ and $(n-1)/2$ have value $c$, or vice versa. This gives a variance of $(c^2/4)\cdot(n^2-1)/n^2$ which is slightly smaller than $c^2/4$. Putting the "extra" point at $c/2$ instead of at an endpoint gives a slightly smaller variance of $(c^2/4)\cdot(n-1)/n$, but both choices have variance approaching $c^2/4$ asymptotically as $n \to \infty$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.