= Parity construction of pairwise independent bits
{title2=$X=U,\ Y=V,\ Z=U\mathbin\oplus V$}
The <parity construction of pairwise independent bits> turns two <independent> fair <bits> into three <pairwise independent random variables>. With $X=U$, $Y=V$, and $Z=U\mathbin\oplus V$, their allowed triples are $000,011,101,110$, each of <probability> $1/4$. Every coordinate has the <Bernoulli distribution> with parameter $1/2$. Every pair has the same <joint probability mass function>:
$$
\begin{array}{c|cccc}
(a,b)&(0,0)&(0,1)&(1,0)&(1,1)\\\hline
\mathbb P(X=a,Y=b)&1/4&1/4&1/4&1/4\\
\mathbb P(X=a,Z=b)&1/4&1/4&1/4&1/4\\
\mathbb P(Y=a,Z=b)&1/4&1/4&1/4&1/4
\end{array}
$$
All twelve pair cells equal the product of the corresponding <probabilities> in their <marginal distributions>. This establishes <pairwise independent random variables>, a requirement involving every pair of value-<events>, rather than merely one chosen <event> per coordinate. For general real-valued <random variables> $R_i$, the requirement is
$$
\mathbb P(R_i\in D,R_j\in E)=\mathbb P(R_i\in D)\mathbb P(R_j\in E)
\qquad(i\ne j)
$$
for every pair of <Borel sets> $D,E$. For these binary <random variables>, checking all four cells of each pair suffices: any value-<event> is a union of the checked cells. In fact, for binary <random variables>, <independence> of their one-value <events> also gives the other cells by taking complements. Siegrist gives the all-set definition and its connection to <indicator random variables> in https://www.randomservices.org/random/prob/Independence.html[Random Services: independence of random variables].
The full <joint probability mass function> tells a different story:
$$
\begin{array}{c|cccccccc}
(x,y,z)&000&001&010&011&100&101&110&111\\\hline
\mathbb P(X=x,Y=y,Z=z)&1/4&0&0&1/4&0&1/4&1/4&0\\
\mathbb P(X=x)\mathbb P(Y=y)\mathbb P(Z=z)&1/8&1/8&1/8&1/8&1/8&1/8&1/8&1/8
\end{array}
$$
The <integer parity> of $X+Y+Z$ is always even. Any two <bits> determine the third: $Z=X\mathbin\oplus Y$, $X=Y\mathbin\oplus Z$, and $Y=X\mathbin\oplus Z$. Each coordinate is <independent> of either other coordinate individually, but is dependent on the pair together. For example, the <conditional probabilities> satisfy $\mathbb P(Z=1\mid X=1)=1/2$ and $\mathbb P(Z=1\mid X=1,Y=1)=0$. See also <pairwise independence does not imply joint independence> for the general distinction.
The constraint changes the sum's <probability distribution> without changing its <expected value> or <variance>. Let $S=X+Y+Z$. Only $000$ gives $S=0$; each other allowed triple gives $S=2$. Direct calculation gives
$$
\mathbb P(S=0)=\frac14,\qquad \mathbb P(S=2)=\frac34,\qquad
\mathbb E[S]=0\cdot\frac14+2\cdot\frac34=\frac32,\qquad
\mathbb E[S^2]=4\cdot\frac34=3,\qquad
\operatorname{Var}(S)=3-\left(\frac32\right)^2=\frac34.
$$
The same <variance> follows from the <variance of a sum>: each <Bernoulli distribution> has <variance> $1/4$, and <pairwise independent random variables> have zero cross <covariances>. <Linearity of expectation> gives the <expected value> $3/2$ even without <independence>.
For comparison, the sum $T$ of three mutually <independent> fair <bits> has the <binomial distribution> $\operatorname{Binomial}(3,1/2)$:
$$
\begin{array}{c|cccc}
t&0&1&2&3\\\hline
\mathbb P(T=t)&1/8&3/8&3/8&1/8
\end{array}
\qquad \mathbb E[T]=\frac32,\qquad \operatorname{Var}(T)=\frac34.
$$
Both sums have identical <expected values> and <variances>, but $S$ never takes the values one or three. Even their third <moments> differ: $\mathbb E[S^3]=6$, whereas $\mathbb E[T^3]=27/4$. <Pairwise independence> preserves these first two sum summaries while allowing a different <joint probability distribution> and a different sum law. The calculation is an exact finite example.
\Image[/pairwise-independence-sum-distributions.png]
{title=Pairwise independence preserves the mean and variance but changes the sum distribution}
{description=The <parity construction of pairwise independent bits> gives sum <probabilities> $(1/4,0,3/4,0)$; three mutually <independent> fair <bits> give the <binomial distribution> <probabilities> $(1/8,3/8,3/8,1/8)$. Both <expected values> are $3/2$ and both <variances> are $3/4$.}
Back to article page
