Variance of sample mean for dependent samples 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?
 A: 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) 
$$
