1
$\begingroup$

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

$\endgroup$

1 Answer 1

1
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ Thanks! Note that by using the probability generating function we have: $Pr[Y=y]=\frac{1}{y!} \frac{d^{(y)} }{dz} \prod _{i=1}^{n}(1-2p_{i} (1-p_{i} )+2p_{i} (1-p_{i} )z)|z=0$, for $y:0...n$ $\endgroup$
    – Omri
    Jul 9, 2015 at 11:04
  • $\begingroup$ Note also that my ultimate goal is to find the correlation coefficient, but I guess this could be derived from the elements of your answer as well. What I really would like is to see how the correlation behaves with increasing $n$ (asymptotically). $\endgroup$
    – Omri
    Jul 9, 2015 at 11:18
  • $\begingroup$ I added a section that shows the correlation between $Y$ and $W$ is zero, where $W$ is the pure difference between the number of ones. Also I gave some comments on asympototics for $n\rightarrow\infty$. $\endgroup$
    – Michael
    Jul 9, 2015 at 15:56
  • $\begingroup$ Michael, did you mean above that $R$ is a sum of $n$ (not $Y$) i.i.d Bernoulli (so a Binomial($1/2,n$))? $\endgroup$
    – Omri
    Jul 9, 2015 at 19:10
  • $\begingroup$ No, $R \in \{0, 1, 2, \ldots, Y\}$. Given $Y=y$, $R$ is binomial $(1/2, y)$. Within the set of $Y$ bits that are different in the two compared strings, $R$ of those bits are "1" in the first string. $\endgroup$
    – Michael
    Jul 10, 2015 at 4:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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