Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Say 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.

Are $X$ and $Y$ correlated? If so, given $n$ and $p_i$, $i:1...n$, what is the covariance?

share|cite|improve this question
When you speak of the difference between the trait values, are you interested in the signed difference or the absolute difference? Also, how familiar are you with the binomial and Bernoulli distributions? – cardinal May 26 '12 at 23:33
The absolute difference (just corrected). Indeed, the 0/1 digits are Bernoulli RVs, but the trait value (X) and the distance (Y) are not binomial... – Omri May 27 '12 at 6:17
The 0/1 digits of the strings are Bernoulli RVs with parameters p1,p2,...,pn. This defines the global distribution of the strings. – Omri May 27 '12 at 23:04
Certainly not, this only confirms that the digits are 0/1 valued (which we already knew). What is missing is a description of their dependency. – Did May 28 '12 at 0:52
As Didier says, you need to specify if the bits are independent or not. BTW, your Y is commonly called the Hamming distance. – leonbloy May 28 '12 at 1:43
up vote 1 down vote accepted

Thus, $X=\left|\sum\limits_iZ_i\right|$ and $Y=\sum\limits_i|Z_i|$ where the random variables $(Z_i)$ are independent and $Z_i=0$, $+1$ or $-1$ with probability $1-a_i$, $\frac12a_i$ and $\frac12a_i$ respectively, with $a_i=2p_i(1-p_i)$.

The covariance of $X$ and $Y$ is not easy to compute but the covariance of $X^2$ and $Y$ is. To begin with, $\mathrm E(Z_i)=0$ and $\mathrm E(Z_i^2)=a_i$ hence $\mathrm E(X^2)=\sum\limits_ia_i$. Likewise, $Z_i^2=|Z_i|$ with full probability hence $Y=\sum\limits_iZ_i^2$ and $\mathrm E(Y)=\sum\limits_ia_i$. Finally, $$ X^2Y=\sum\limits_iZ_i^4+2\sum\limits_{i,j}Z_i^2Z_j^2+2\sum\limits_{i,j}Z_i^3Z_j+2\sum\limits_{i,j,k}Z_i^2Z_jZ_k, $$ where the sums are over $i$ and $j$ distinct and over $i$, $j$ and $k$ distinct. Since $Z_i^4=|Z_i|$ with full probability, $$ \mathrm E(X^2Y)=\sum\limits_ia_i+2\sum\limits_{i\ne j}a_ia_j, $$ and finally, $$ \mathrm{Cov}(X^2,Y)=\sum\limits_ia_i(1-a_i)=\sum\limits_i2p_i(1-p_i)(1-2p_i(1-p_i)). $$ Edit: For each $i$, introduce $$ A_i=\mathrm E\left|\sum\limits_{j\ne i}Z_j\right|,\qquad B_i=\mathrm E\left|1+\sum\limits_{j\ne i}Z_j\right|. $$ Decomposing the expectations along the values of $Z_i$, one gets $\mathrm E(X\cdot|Z_i|)=a_iB_i$ and $\mathrm E(X)=a_iB_i+(1-a_i)A_i$. By convexity, $B_i\geqslant1+A_i$ hence $$ \mathrm E(X)\mathrm E(|Z_i|)=a_i(a_iB_i+(1-a_i)A_i)\leqslant a_iB_i-a_i(1-a_i)=\mathrm E(X\cdot|Z_i|)-a_i(1-a_i). $$ Summing up, this yields $$ \mathrm{Cov}(X,Y)=\sum_i\mathrm E(X\cdot|Z_i|)-\mathrm E(X)\mathrm E(|Z_i|)\geqslant\sum\limits_ia_i(1-a_i)\gt0. $$

share|cite|improve this answer
Thanks much. So we get that $\mathrm{Cov}(X^2,Y)>0$, which is rather intuitive. It follows that $\mathrm{Cov}(X,Y)>0$ as well, right? Also, I am still quite interested in finding how strong the correlation would be, so to find $\mathrm{Corr}(X,Y)$. – Omri May 28 '12 at 13:40
Thanks again... so we now have a lower bound on the covariance, and in extension on the correlation. – Omri Jun 9 '12 at 18:37
Any way I could get [a] a good upper bound on $Cov(X,Y)$, and [b] the lower/upper bound on $r(X,Y)$, the correlation coefficient? – Omri Jul 23 '12 at 20:20
I went back to this problem (actually using the proof for a paper in genetics) and it seems the inequality in your "By convexity $B_i\geqslant1+A_i$" should be the other way around. Please let me know what you think. – Omri Jul 6 '15 at 10:57
Please see my recent concern, @Did... – Omri Jul 7 '15 at 10:39

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.