An exercise question in the probability theory class

Question

I was asked a "simple" question by one of my students in the tutorial class, but I found myself struggling with this for about 2 hours already. Here is the question:

Assume there are $K$ constants: $0\leq C_{1}<C_{2}<...<C_{K-1}<C_{K}\leq1$; Let $X$ be a random variable with $Pr(X=C_{k})=\frac{1}{K}$, $k=1,...,K$. Find when the maximum of $Var(X)$ is attained, determine the value of $K$ and the value of $(C_{1},...,C_{K})$ when this happens.

Here are some of my ideas:

$E[X]=\sum_{k=1}^{K}C_{k}\frac{1}{K}=\frac{1}{K}\sum_{k=1}^{K}C_{k}$

$E[X^2]=\sum_{k=1}^{K}(C_{k})^2\frac{1}{K}=\frac{1}{K}\sum_{k=1}^{K}(C_{k})^2$

$Var(X)=E[X^2]-(E[X])^2=\frac{1}{K^2}\big(K\sum_{k=1}^{K}(C_{k})^2-(\sum_{k=1}^{K}C_{k})^2\big)\\~~~~~~~~~~~~=\frac{1}{K^2}\big((K-1)\sum_{k=1}^{K}(C_{k})^2-2\sum_{i\neq j}C_{i}C_{j}\big)$.

I am really wondering if it is possible to apply Lagrange multiplier method to this.

Any help and advice will be sincerely appreciated. Thank you very much in advance!

Answer 1

Let's first of all allow some of the $C$s to be equal.

The derivative of the variance w.r.t. $C_i$ is $\frac2K(C_i-m)$ where $m$ is the expectation of $X$ = the mean of the $C$s. Therefore, pushing any $C_i$ away from $m$ increases the variance, so a maximum-variance configuration has all the $C$ equal to either 0 or 1.

If it has $p$ 0s and $q$ 1s then the variance is $\frac{pq}{(p+q)^2}$ which, for fixed $p+q=K$, is biggest when $p,q$ are as close as possible.

So the biggest variance you can get is when "half" of the $C$s are 0 and "half" are 1. (If $K$ is odd, one of those groups will be 1 larger than the other.)

This maximum isn't attained, if you keep the restriction that all the $C$ have to be unequal. But you can get as close to it as you like by pushing "half" the values very close to (one another and to) 0 and the rest very close to (one another and to) 1.

(You didn't ask about this, but the minimum happens when all the $C$ are equal; this too isn't attained if you require them to be distinct but you can get as close as you like by making all the values very close together.)

Answer 2

This gives some formality to Gareth's answer (reaching the same conclusion).

Claim: If $X$ is any random variable that satisifes $0\leq X\leq 1$ surely, then $$Var(X)\leq 1/4$$ and this is achieved by $X \sim Bernoulli(1/2)$.

Proof: Suppose $0\leq X \leq 1$ surely. Note that $$ \left(0\leq X \leq 1\right) \implies 0\leq E[X] \leq 1$$ $$\left(X^2\leq X\right) \implies E[X^2]\leq E[X]$$ Define $m=E[X]$, so $m \in [0,1]$. Thus \begin{align} Var(X) &= E[X^2] - m^2\\ &\leq E[X] - m^2 \\ &=m-m^2\\ &\leq \sup_{v\in [0,1]}\{v-v^2\}\\ &=1/4 \end{align} $\Box$

Under the structure of your question, we can use $K=2$ and $C_1=0, C_2=1$ to achieve the max variance of $1/4$.

I'm not sure if your question also asks what to do if $K$ is fixed and cannot be chosen (so we cannot choose $K=2$). For any even integer $K$, we can approach the max variance $1/4$ arbitrarily closely by using $C_1=0$, $C_K=1$, and placing half the remaining $C_i$ values near $0$ and the other half near 1 (spacing them out by some small $\epsilon$ to ensure they are distinct). This is what is similar to Gareth's answer. The case when $K$ is odd is different.