A unit vector that maximizes variance in a discrete probability distribution

Question

this might be a dumb question, but I was working on a problem and ran into the following (sub)problem.

Suppose we have a nonnegative vector $\pi \in \mathbf{R}^n$ that satisfies $\sum_{i=1}^n \pi_i = 1$, i.e., it is a discrete probability density. We want to choose a unit vector $v \in \mathbf{R}^n$, $\|v\|=1$, where $\| \cdot \|$ is the Euclidean norm, such that the "variance"

$f(v) = \sum_{i=1}^n v_i^2 \pi_i - (\sum_{i=1}^n v_i \pi_i)^2$

is maximized. Of course there will be multiple maxima, because $f(v) = f(-v)$.

Is there any closed form solutions for the maximum $v$ or any ideas how to find it, or what is the maximum function value $f(v)$? Specifically, I want to show that if $\pi_1 > 0.5$, then any maximum $v$ satisfies ${\rm sign}(v_1) = -{\rm sign}(v_i)$ for all $i \neq 1$.

Any tips or ideas? Thank you very much!

Answer 1

Define the $n\times n$ symmetric matrix $M$ with elements $$M_{ij}=\pi_i \delta_{ij}-\pi_i\pi_j.$$ We seek to maximise the quadratic form $$f(v)=\sum_{ij} v_i M_{ij} v_j$$ where $v$ is a vector on the unit $n$-sphere. An extremum is reached for an eigenvector $v_0$ of $M$ and $f(v_0)=\mu_0$ is the corresponding eigenvalue $\mu_0$ of $M$. For the global maximum we should take the eigenvector $v_{\rm max}$ with the largest eigenvalue $\mu_{\rm max}$.
_{This is basically the min-max theorem, for an explicit proof see proposition 6 of these notes.}

The eigenvalues $\mu$ of $M$ are determined by the equation $$1+\sum_{i}\frac{\pi_i^2}{\mu-\pi_i}=0.$$ _{This follows from the Matrix determinant lemma, see this MO posting for a derivation.}

The smallest eigenvalue $\mu=0$ has eigenvector with all elements $1\sqrt n$. Since the eigenvectors are orthogonal, the desired $v_{\rm max}$ should satisfy $$\sum_{i}(v_{\rm max})_i=0.$$

I don't think a closed form expression for $v_{\rm max}$ exists for arbitrary $n$.

_{For $n=2$ one has simply $v_{\rm max}=(1/\sqrt 2,-1/\sqrt 2)$ independent of $\pi$, but already for $n=3$ the expression is complicated: $$v_{\rm max}=\{\pi_2(\pi_1-\pi_3)+\sqrt X,\pi_1(\pi_3-\pi_2)-\sqrt X, \pi_3(\pi_2-\pi_1)\}$$ $$X=\pi_1^4+2 \pi_1^3 (\pi_2-1)+\pi_1^2 (3\pi_2^2 -\pi_2+1)+\pi_1 (\pi_2-1) \pi_2 (2 \pi_2+1)+(\pi_2-1)^2 \pi_2^2,$$ where $v_{\rm max}$ is still to be normalized to unit length. The corresponding $\mu_{\rm max}$ is $$\mu_{\rm max}=\sqrt{\left(\pi_1^2- (1-\pi_2)(1-\pi_3)\right)^2-3 \pi_1 \pi_2 \pi_3}-\pi_1^2-\pi_2^2-\pi_1 \pi_2+\pi_1+\pi_2.$$}