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

  • $\begingroup$ I did indeed mean $k>j>i$. Thanks for spotting that. $\endgroup$ – Till Hoffmann Sep 17 '15 at 7:59
  • $\begingroup$ 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)$ $\endgroup$ – Till Hoffmann Dec 23 '16 at 22:55

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.