# Calculate covariance of function of sample efficiently

Let $\phi(x, x')$ be a real-valued, continuous function that is symmetric with respect to exchange of its arguments. Let $X,X',X''$ be i.i.d random variables with distribution function $F$. I am interested in computing the two quantities \begin{align} \mu &= \mathrm{E}\phi(X,X')\\ \sigma^2 &= \mathrm{Cov}\left[\phi(X,X'),\phi(X,X'')\right]. \end{align}

If we can sample from $F$, we can easily compute $\mu$ and $\sigma$ by Monte Carlo integration: \begin{align} \hat{\mu}&=n^{-1}\sum_{i=1}^n\phi(x_i,x'_i)\\ \hat{\sigma}^2&=n^{-1}\sum_{i=1}^n\left[\phi(x_i,x'_i)-\hat{\mu}\right]\left[\phi(x_i,x''_i)-\hat{\mu}\right], \end{align} where $x,x',x''$ are $n$ i.i.d. samples drawn from $F$.

However, I only have a single sample $x$ of $X$ and would like to compute the quantities above. My current approach is to use the following estimators \begin{align} \hat{\mu}&=\frac{1}{\binom n2}\sum_{i<j}\phi(x_i,x_j)\\ \hat{\sigma}^2&=\frac{1}{\binom n3}\sum_{i<j<k}\left[\phi(x_i,x_j)-\hat{\mu}\right]\left[\phi(x_i,x_k)-\hat{\mu}\right]. \end{align}

Unfortunately, I need to compute $\mu$ and $\sigma^2$ a large number of times (inside a Metropolis-Hastings loop) and the combinatorial factor of $\binom n3$ is causing me a headache.

Do you have suggestions how to estimate the quantities I am concerned with more efficiently from a single sample?

Factorise $$\sum_{j>i,k>i}\left[\phi(x_i,x_j)-\hat{\mu}\right]\left[\phi(x_i,x_k)-\hat{\mu}\right] \ =\ \left( \sum_{t>i}\left[\phi(x_i,x_t)-\hat{\mu}\right] \right)^2$$
Or did you want $\sum_{k>j>i}\ldots$ ? If so, same principle applies. Let $A_{i,t}=\phi(x_i,x_t)-\hat{\mu}$, then: $$\sum_{k>j>i}A_{i,j}A_{i,k} \ =\ \frac{1}{2}\left( (\sum_{t>i}A_{i,t})^2 - \sum_{t>i} (A_{i,t})^2 \right)$$
• I did indeed mean $k>j>i$. Thanks for spotting that. – Till Hoffmann Sep 17 '15 at 7:59
• It turns out the last expression should read $\frac{1}{2}\sum_i\left(\left[\sum_{j:j>i}A_{ij}\right]^2-\sum_{j:j>i}A_{ij}^2\right)$ – Till Hoffmann Dec 23 '16 at 22:55