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
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented Jul 10, 2015 at 4:42

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .