Correlation between two distance measures on bitstrings I have an infinite collection of $0/1$ random strings of length $n$ (i.e., say 010001110101), where each digit is an independent Bernoulli RV, with parameter $p_i$,  $i:1...n$. 
Define the "trait value" of a string to be the number of "1"s. Define $X$ to be a RV representing the absolute difference between the trait values of a sample of two strings. 
Define $Y$ to be a RV representing the "distance" between two sampled strings, where this distance is simply the number of mismatched digits (i.e., so 01101-00111=2), also known as the Hamming distance. 
Given $n$ and $p_i$, $i:1...n$, what is the correlation of $X$ and $Y$? (or at least, their covariance)? 
 A: Well, I don't see any way to get easy expressions.  But for messy expressions, we have: 
$$E[Y] =\sum_{i=1}^n 2p_i(1-p_i) $$
Now suppose two strings differ by $y\geq 1$ bits. Enumerate these $\{1, \ldots, y\}$.  For $k \in \{1, \ldots, y\}$ define $A_k=1$ if the first string has a 1 in the $k$th different bit, and $A_k=0$ else. Then $A_1, \ldots, A_y$ are i.i.d. Bernoulli with $Pr[A_k=1]=1/2$, and, given $Y=y$: 
$$ X|_{Y=y} = \left|\sum_{k=1}^y A_k - \left(y - \sum_{k=1}^y A_k\right)\right| = \left|y-2\sum_{k=1}^y A_k\right| $$
So: 
$$ E[X|Y=y] = \sum_{r=0}^y {y \choose r} (1/2)^y\left|y-2r\right|$$ 
Then: 
$$ E[X] = 0 + \sum_{y=1}^n \underbrace{Pr[Y=y]}_{complicated}E[X|Y=y]$$
Also: 
$$ E[XY] = E[YE[X|Y]] = 0 + \sum_{y=1}^{n} yPr[Y=y]E[X|Y=y] $$

Perhaps a more useful relationship is just the observation: 
$$ X = |Y-2R| $$
where $R = 0$ if $Y=0$ and $R$ is a sum of $Y$ iid Bernoulli $(1/2,1/2)$ variables else. 

If you define $W$ as the pure difference between the number of ones (so $W \in \{-n, \ldots, n\}$ and $X=|W|$) then the answer is easier: 
$$ W = Y-2R $$
So $E[W]=E[Y]-2E[R]=0$ and, 
\begin{align} 
E[YW] &= E[Y^2] - 2E[YR]\\
&= E[Y^2] - 2\sum_{y=0}^n Pr[Y=y]yE[R|Y=y]\\
&=E[Y^2] - 2\sum_{y=0}^n Pr[Y=y]y^2/2 \\
&= E[Y^2] - E[Y^2]\\
&=0
\end{align} 
So $W$ and $Y$ are uncorrelated. 

Asymptotically for large $n$, write $X\equiv X_n$, $Y\equiv Y_n$, $R\equiv R_n$. Suppose there is a constant $\alpha \in (0,1)$ such that: 
\begin{align} 
\lim_{n\rightarrow\infty} \frac{1}{n}\sum_{i=1}^n 2p_i(1-p_i) = \alpha
\end{align} 
Then with probability 1: 
\begin{align} 
&\lim_{n\rightarrow\infty} \frac{Y_n}{n} = \alpha\\
&\lim_{n\rightarrow\infty} \frac{R_n}{Y_n} = 1/2 \\
&\lim_{n\rightarrow\infty} \frac{X_n}{n} = 0
\end{align} 
where the last can be derived by: 
$$ \lim_{n\rightarrow\infty} \frac{X_n}{n} = \lim_{n\rightarrow\infty} \left|\frac{Y_n-2R_n}{n}\right|=\lim_{n\rightarrow\infty}\left|\frac{Y_n}{n} - \frac{2R_n}{Y_n}\frac{Y_n}{n}\right|=0$$
