0
$\begingroup$

I have a basket $X$ of items to choose from. Each $x_i$ is a normally distributed random variable $x_i \sim\mathcal{N}(\mu_i, \sigma_i^2)$. Each $x_i$ is independent and uncorrelated from every other in $X$.

I then create various combinations $Y$ of $X$, where $y_j = \sum_{s\in{S_j}} x_{s}$ . Since all $X$ are uncorrelated $y_j \sim\mathcal{N}(\sum_{s\in S_j} \mu_{s}, \sum_{s\in S_j} \sigma_{s}^2)$. It can be assumed that every $S_j$ is the same size.

I need to calculate the covariance (or correlation) matrix of $Y$.

I can manually calculate the covariance for each pair by $Cov_{ij} = \sum_{s\in(S_i \cap S_j})\sigma_s^2$.

Is there a faster way to calculate the entire covariance matrix other than pair-by-pair?

Some more details to hopefully clarify:

Each set $S_j$ has a size of 10. There are about 300 items in $X$. I can create a matrix where each row is a representation of each $Y_j$, where there is a 1 (or $\sigma_i$ or $\sigma^2_i$) in column $i$ if $i \in S_j$, but I don't know how I can use this (very sparse) matrix to quickly calculate the covariance matrix. I'm doing it now by doing pair-wise multiplication of the $\sigma$ matrix (each row multiplied by every other row), then sum, to calculate the covariance for each pair. But is there a faster way?

For example, the initial matrix of the standard deviations from each set could be: $$ \begin{matrix} \text{} & \sigma_1 & \sigma_2 & \sigma_3 & \sigma_4 & \sigma_5 \\ y_1 & 10 & 0 & 40 & 20 & 0\\ y_2 & 10 & 5 & 0 & 20 & 0\\ y_3 & 0 & 5 & 40 & 0 & 30\\ y_4 & 10 & 0 & 0 & 20 & 30\\ \end{matrix} $$

So $y_1$ has elements from the set $S_1 \in [1,3,4]$, and $y_2$ has elements from the set $S_2 \in [1,2,4]$. The pairwise multiplication of each row gives: $$ \begin{matrix} \text{} & \sigma_1^2 & \sigma_2^2 & \sigma_3^2 & \sigma_4^2 & \sigma_5^2 &\sum\sigma^2\\ y_1*y_1 & 100 & 0 & 1600 & 400 & 0 & 2100\\ y_1*y_2 & 100 & 0 & 0 & 400 & 0 & 500\\ y_1*y_3 & 0 & 0 & 1600 & 0 & 0 & 1600\\ y_1*y_4 & 100 & 0 & 0 & 400 & 0 & 500\\ y_2*y_2 & 100 & 25 & 0 & 400 & 0 & 525\\ y_2*y_3 & 0 & 25 & 0 & 0 & 0 & 25\\ y_2*y_4 & 100 & 0 & 0 & 400 & 0 & 500\\ y_3*y_3 & 0 & 25 & 1600 & 0 & 900 & 2525\\ y_3*y_4 & 0 & 0 & 0 & 0 & 90 & 90\\ y_4*y_4 & 100 & 0 & 0 & 400 & 900 & 1400\\ \end{matrix} $$

Resulting in the covariance matrix:

$$ \begin{matrix} \text{} & y_1 & y_2 & y_3 & y_4\\ y_1 & 2100 & 500 & 1600 & 500\\ y_2 & 500 & 525 & 25 & 500\\ y_3 & 1600 & 25 & 2525 & 90\\ y_4 & 500 & 500 & 90 & 1400\\ \end{matrix} $$

I'm hoping to go straight from the first matrix to the covariance matrix somehow.

Thanks!

$\endgroup$
  • 1
    $\begingroup$ It comes down to comparing pairs of sets in the collection $\{S_1,\ldots, S_n\}$. If there's any way to avoid looking at all possible pairs, that would be because there is some kind of systematic, known structure to these sets, which you would need to disclose if you want good answers. If by "faster" you are referring to computer implementations, then exploit built-in matrix operations (sparse matrices if the $S_j$ are sparse). $\endgroup$ – whuber Sep 26 '17 at 20:24
  • $\begingroup$ Thanks whuber! There is some known structure in that they draw from the same elements, and are the same size. I'm not sure if that's enough though. And yes, looking for some-way to use built in matrix operations to calculate the covariance matrix faster, but I don't know how to do so. I added some more details that hopefully clarifies things. $\endgroup$ – Albeit Sep 27 '17 at 17:24
  • $\begingroup$ "Draw from the same elements" is no structure at all, but being the same size is a considerable restriction. $\endgroup$ – whuber Sep 27 '17 at 18:09

Your Answer

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

Browse other questions tagged or ask your own question.