Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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
1  
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

1 Answer 1

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

Your Answer

 
discard

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.