Effect of permutation on sum of conditional variances

18 Views Asked by At

Let $X = (X_1, X_2, \dots, X_n)$ be a set of jointly Gaussian random variables with zero mean and covariance matrix $\Sigma$. All the diagonal elements of $\Sigma$ are $1$, i.e., $\mathrm{var}(X_i) = 1$ for all $i \in \{1,2, \dots, n\}$. The covariance matrix $\Sigma$ is assumed to be known and $n$ is a fixed natural number assumed to be known.

Let $\pi$ be a permutation of the set $\{1,2, \dots, n\}$. We denote the $i^{\text{th}}$ element in $\pi$ as $\pi(i)$. Define the sum $S(\pi)$ as \begin{align*} S(\pi) := \sum_{i = 1}^n \mathrm{var}(X_{\pi(i)} | X_{\pi(1)}, X_{\pi(2)}, \dots, X_{\pi(i-1)}) \end{align*} where for notation purposes $\pi(0) = 0$ and $\mathrm{var}(X_j| X_0) = \mathrm{var}(X_j)$ for all $j \in \{1,2, \dots, n\}$. Clearly, this sum depends on the permutation $\pi$. However, intuitively, this sum cannot change too much with $\pi$, that is, just by changing the order in which the conditional variances of the random variables are evaluated. I am trying to formalize this intuition, that is, if $S_{\max} = \max_{\pi} S(\pi)$ and $S_{\min} = \min_{\pi} S(\pi)$, then I am looking for non-trivial upper bounds on either $S_{\max} - S_{\min}$ or $S_{\max}/S_{\min}$.

I have tried several ideas by none of have helped me obtain a concrete progress as such. Any help or references will be really appreciated. Thank you!