Suppose I have two discrete independant random variables $X$ and $Y$, and that I'm interested in the expected value of the random variable $W$, where: $$ W= \text{sign}(X-Y). $$ So, W is 1 if $X>Y$, -1 if $Y>X$ and 0 otherwise.

I sample the distributions of $X$ and $Y$ ten times each, giving me $\{X_1, \dots, X_{10}\}$ and $\{Y_1, \dots, Y_{10}\}$.
Consider these two ways to estimate $\text{E}\{W\}$ $$ \quad\quad\bar{W} = \frac{1}{10}\sum_{i=1}^{10} W_{i,i}, \\ \text{and, } \quad\quad \bar{W}' = \frac{1}{100}\sum_{i=1}^{10}\sum_{j=1}^{10} W_{i,j}, \\ \text{where } \quad W_{i,j} = \text{sign}(X_i - Y_j) $$ I know that $\text{Var}\{\bar{W}\} = \frac{1}{10}\text{Var}\{W\}$, but what is $\text{Var}\{\bar{W}'\}$, and how can I estimate it from my 20 samples?

  • 1
    $\begingroup$ I think it would be less confusing to simply write $W = \text{sign}(X – Y)$. $\endgroup$ – Alexis Jun 11 '14 at 2:47
  • $\begingroup$ Keep it clean and simple: just generate $W_i$ from $(X_i, Y_i)$, and leave alone the $(X_i, Y_j)$ combinations. $\endgroup$ – wolfies Jun 11 '14 at 7:30
  • 1
    $\begingroup$ Thanks @wolfies. That's what $\bar{W}$ is, but my question is to specifically address the case of $\bar{W}'$ $\endgroup$ – Edward Newell Jun 11 '14 at 17:32
  • $\begingroup$ This is a dup of my question from math.stackexchange.com. It stayed open for very long, but eventually did get answered. math.stackexchange.com/questions/821968/… $\endgroup$ – Edward Newell Jun 16 '14 at 23:18

Use the generic formula for the variance of a sum of random variables. For some random variables $A_i$, this can be stated as: $$ \text{Var}\left\{\sum_{i=1}^n A_i\right\} = \sum_{i=1}^n\text{Var}\{A_i\} + \sum_{i \neq j} \text{Cov}\{A_i,A_j\} \\ $$ In this case, we get: $$ \text{Var}\{\bar{W}'\} = \text{Var}\left\{\frac{1}{100}\sum_{k\in \{1,...,10\}^2}W_{k}\right\} \\ = \frac{1}{10000}\left(\sum_{k \in \{1,...,10\}^2}\text{Var}\{W_k\} + \sum_{k,\ell \in \{1,...,10\}^2; k\neq \ell}\text{Cov}\{W_k,W_\ell\}\right) $$ Note that above, the subscripts $k$ and $\ell$ represent pairs, i.e. $k= (i,j)$, which I'm using because the notation for the indices gets too complicated otherwise!

The trick is that $\text{Cov}\{W_k, W_\ell\}$ is not zero if one of the indicies is the same. This can happen in two different ways. Either the first index is the same --- $k = (i,j)$ and $\ell = (i,m)$ --- or the second index is the same --- $k = (i,j)$ and $\ell=(m,j)$. Otherwise $W_k$ and $W_j$ are based on different, and independent samples, and so are independent.

Therefore, you need to estimate $\text{Cov}\{W_{i,j},W_{i,m}\}$ and $\text{Cov}\{W_{i,j},W_{m,j}\}$. Note that it doesn't matter what the specific indices are --- all that matters is which of the indices are shared. (this is because all $X_i$'s are i.i.d, and all $Y_i$'s are too.)

You could estimate $\text{Cov}\{W_{i,j},W_{i,m}\}$ using your samples by calculating $\text{Cov}\{W_{i,1}, W_{i,2}\}$:

$$ \text{Cov}\{W_{i,1}, W_{i,2}\} = \sum_{i\in\{1,...,10\}}\left(W_{i,1} - \text{E}\{W_{\cdot,1}\}\right)\left(W_{i,2} - \text{E}\{W_{\cdot,2}\}\right) $$

You could also calculate $\text{Cov}\{W_{i,3},W_{i,4}\}$ from your samples. Both $\text{Cov}\{W_{i,1}, W_{i,2}\}$, and $\text{Cov}\{W_{i,3},W_{i,4}\}$ provide independent estimates of $\text{Cov}\{W_{i,j},W_{i,m}\}$. You can refine your estimate of $\text{Cov}\{W_{i,j},W_{i,m}\}$ by taking the mean of various independent estimators. But be careful not to also include something like $\text{Cov}\{W_{i,2},W_{i,3}\}$ along with the others already mentioned, since it would not be independent from them.

Then, do similarly to estimate $\text{Cov}\{W_{i,j},W_{m,j}\}$. For example: $$ \text{Cov}\{W_{1,j}, W_{2,j}\} = \sum_{j\in\{1,...,10\}}\left(W_{1,j} - \text{E}\{W_{1,\cdot}\}\right)\left(W_{2,j} - \text{E}\{W_{2,\cdot}\}\right) $$

To take the sum of the covariances, note that each of these types of covariance term arises $10{10\choose2}=450$ times so, for your particular shape of sample sets,

$$ \text{Var}\{\bar{W}'\} = \frac{\text{Var}\{W_k\}}{100} + \frac{9}{200}\left(\text{Cov}\{W_{i,j},W_{i,m}\} + \text{Cov}\{W_{i,j},W_{m,j}\}\right) $$

  • $\begingroup$ This is my best answer based on the research I've done. I don't feel confident enough to accept it though -- I would really appreciate if someone who has a deep grasp could sanity-check this! $\endgroup$ – Edward Newell Jun 12 '14 at 3:04

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.