3
$\begingroup$

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!

$\endgroup$

1 Answer 1

1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Thank you! The characteristic polynomial was very helpful in proving what I wanted to prove. $\endgroup$ Jun 11, 2019 at 8:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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