Category: Side Quests

I took another detour into the world of binary neural networks. In the interests of evaluating dot-product-like functions of two binary vectors, I wanted to assess how the distributions of multiplied bits (equivalent to ANDed bits) relate to the distributions of the individual bits. This post captures the results of this side-trip.

Products of independent Bernoullis

The simplest case is in the light of independence, when $$X\sim Bern({\pi }_X)$$

$$Y\sim Bern({\pi }_Y)$$ and $$P(X,Y)=P(X)P(Y)$$

Let $Z=XY$ be the product of the two bits, equivalent to $Z=X\wedge Y$. As $Z\in \{0,1\}$ we can model $Z\sim Bern({\pi }_Z)$ for some ${\pi }_Z$.

The truth table for the four possible outcomes guides us here:

$X$	$Y$	$Z$	$P(X)$	$P(Y)$
0	0	0	$1-{\pi }_X$	$1-{\pi }_Y$
0	1	0	$1-{\pi }_X$	${\pi }_Y$
1	0	0	${\pi }_X$	$1-{\pi }_Y$
1	1	1	${\pi }_X$	${\pi }_Y$

$P(Z=1)=P(X=1)P(Y=1)={\pi }_X{\pi }_Y$; a bit of arithmetic also shows that $P(Z=0)=1–{\pi }_X{\pi }_Y$. With ${\pi }_X\in [0,1]\wedge {\pi }_Y\in [0,1]⟹{\pi }_X{\pi }_Y\in [0,1]$, we see that $$Z\sim Bern({\pi }_X{\pi }_Y)$$

Products of Non-Independent Bernoullis

Suppose that $X\sim Bern({\pi }_X)$. A second Bernoulli random variable will be dependent on $X$ only if its single parameter is a function of $X$, so let $Y|X\sim Bern(g(X))$ where $g:\{0,1\}\to [0,1]$ generates the parameter of $Y$’s distribution.

As there are only two possible outcomes from such a function $g$ we denote them individually as: $${\pi }_{Y|X=0}=g(0)$$ and $${\pi }_{Y|X=1}=g(1)$$

We again are interested in the distribution of a given $Z=XY=X\wedge Y$, and again the truth table leads us to a straightforward solution:

$X$	$Y$	$Z$	$P(X)$	$P(Y|X)$
0	0	0	$1-{\pi }_X$	$1-{\pi }_{Y|X=0}$
0	1	0	$1-{\pi }_X$	${\pi }_{Y|X=0}$
1	0	0	${\pi }_X$	$1-{\pi }_{Y|X=1}$
1	1	1	${\pi }_X$	${\pi }_{Y|X=1}$

$$P(Z=1)=P(X=1)P(Y=1|X=1)={\pi }_X{\pi }_{Y|X=1}={\pi }_{X}g(1)$$

A bit of arithmetic shows that $$P(Z=0)=1–{\pi }_X{\pi }_{Y|X=1}=1–{\pi }_{X}g(1)$$

With ${\pi }_X\in [0,1]\wedge {\pi }_{Y|X=1}\in [0,1]⟹{\pi }_X{\pi }_{Y|X=1}\in [0,1]$ we conclude that $$Z\sim Bern({\pi }_X{\pi }_{Y|X=1})$$

The parameter ${\pi }_{Y|X=0}=g(0)$ for the case where $X=0$ drops out; it is redundant as $Y=1|X=0$ is simply another way for $Z$ to equal zero.

In other words, the distribution of $Z$ depends only on the distributions of $X$ and of $Y|X=1$, not on $Y|X=0$. The constraint that all events must result in either one or the other of two outcomes allows the behavior of the combined system to be fully characterized with a constant number of parameters, and the distribution of the product / Boolean AND even of dependent Bernoullis is simply yet another Bernoulli.