# Maximum of the Variance Function for Given Set of Bounded Numbers

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

What's is the maximum of the variance function of this $$n$$ numbers?
Maximum in the meaning what spread of the number will maximize the variance?
What would be a tighter bound for other assumptions on the spread of the numbers.

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

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

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

$$\overline{\boldsymbol{x}} = \frac{1}{n} \sum_{i = 1}^{n} {x}_{i}$$

• What is the variance function of a set? The maximum with respect to what? Please try to rephrase your question using more standard terminology. Commented Nov 17, 2011 at 13:44
• 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) Commented Nov 17, 2011 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.
– Royi
Commented Nov 17, 2011 at 14:24
• @joriki, I've updated the question. Thank You.
– Royi
Commented Nov 17, 2011 at 14:25
• "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. Commented Nov 17, 2011 at 15:50

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}.$$

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$.

• Could you explain the last part of your derivation? I don't understand where $\bar{x}(c - \bar{x}) \lt \frac{c^2}{4}$ comes from. Commented Feb 18, 2017 at 15:08
• I had a google and found a paper called "A Better Bound on the Variance" by Rajendra Bhatia and Chandler Davis which seemed helpful but it relied on the assumption that $\forall x\in \mathbb{R}$, $(M - m)^2 \geq 4(M -x)(x - m)$ where $M \geq m$ and [m, M] are the bounds individual values used to compute the arithmetic mean. That assumption would help here too but I don't understand where it comes from. Commented Feb 18, 2017 at 15:14
• $\bar x \in [0,c]$ and $\bar{x}(c-\bar{x})$ has maximum value $\frac{c^2}{4}$ when $\bar{x}=\frac c2$. With regard to the alleged better bound, if the range is $[m,M]$ instead of $[0,c]$, the variance works out to be $(M-\bar{x})(\bar{x}-m)$ and this is claimed to be smaller than $\frac{(M-m)^2}{4}$. Pardon me if I fail to be greatly impressed by the better bound that Google found for you. Commented Feb 18, 2017 at 19:42
• @delcypher Hi, you can treat x bar as the variable, and use completing the square to find the maximum of the univariate quadratic polynomial Commented Mar 19, 2018 at 22:02

An easier derivation can be done as follows (From [1]):

For any constant $$c$$, we have, $$$$E[(X-c)^2] = E[X^2] - 2E[X]c + c^2$$$$ The above quadratic is minimized when $$c=E[X]$$. It follows that, $$$$\sigma^2 = E[(X-E[X])^2] \leq E[(X-c)^2], \text{for all } c$$$$ By letting $$c = (a+b)/2$$, we obtain, $$$$\sigma^2 \leq E\left[\left(X-\frac{a+b}{2}\right)^2\right] = E[(X-a)(X-b)] + \frac{(b-a)^2}{4} \leq \frac{(b-a)^2}{4}$$$$

since for $$x$$ in $$[a,b]$$, $$(x-a)(x-b)<0$$

Further, the bound could be very conservative. However, in the absence of any other information about $$X$$, it can not be improved.

[1] D. P. Bertsekas and J. N. Tsitsiklis, Introduction to Probability. Athena Scientific, 2002.

• Could you point to me where this proof is in [1]? Commented Jun 8 at 18:20