Return to Answer

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$, define 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|=\left|\frac{Y_n}{n} - \frac{2R_n}{Y_n}\frac{Y_n}{n}\right|=0$$

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

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.

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$, define 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|=\left|\frac{Y_n}{n} - \frac{2R_n}{Y_n}\frac{Y_n}{n}\right|=0$$

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.

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.