Stability of EP circuits

In this section we discuss the stability of the representation of positive Boolean functions through EP in presence of noise.

Consider the following scenario: Fixed $w$ ($0<w<1/2$) suppose that a generic assignment $z_1,\dots ,z_r$ is corrupted to $z_1',\dots, z_r'$, where $z_i'=z_i$ with probability $1-w$ independently for $i=1,\dots ,r$. The noise can induce errors on $\varphi$ with probability $P_w(\varphi)=P\{ \varphi(z_1, \dots , z_r)\neq \varphi(z_1', \dots , z_r') \}$. In particular, we show that for the majority functions the following result holds, independently from $r$.

Fact: $P_w(M(r))=\mathcal{O}(\sqrt{w})$.

Proof: Let $(z_1, \dots , z_r)$ a random assignment in $\{0,1\}^r$; the random variable $S=\sum_{k=1}^r z_k$ is approximately normal distributed with average $r/2$ and variance $r/4$, so that $S$ is concentrated with high probability in the range $\{ S$    s.t. $\vert S-\frac{r}{2}\vert\leq \frac{3}{2}\sqrt{r} \}$. Let $(z_1', \dots , z_r')$ be a random assignment s.t.  $P\{z_i' \neq z_i\} = w$ for each $i=1,\dots ,r$; the random variable $S'=\sum_{k=1}^r z_k'$ is approximately normal distributed with average $S-w(2S-r)$ and variance $rw(1-w)$ so that, for small $w$, for which $w \ll \sqrt{w}$ holds, and for $S$ in the interval $\vert S-\frac{r}{2}\vert\leq \frac{3}{2}\sqrt{r}$, $S'$ is concentrated in the interval $\{S'$    s.t. $\vert S-S'\vert\leq 3\sqrt{wr}\}$.

Since the error condition is $S \geq r/2$ and $S' < r/2$ or $S < r/2$ and $S' \geq r/2$, the values of $S$ with high probability of error are concentrated in the interval $\{ S$    s.t. $\vert S-\frac{r}{2}\vert\leq 3\sqrt{wr}\}$. It follows that the probability of error is $P_w(M(r))=\mathcal{O}(3\sqrt{wr}/\frac{3}{2}\sqrt{r})=\mathcal{O}(\sqrt{w})$.

As observed in [6], Boolean functions represented as simple majority (i.e. ES) are quite stable in presence of noise, while two-level majority (like the functions represented by EP) are less stable and, finally, the functions represented through a large number of levels are quite sensitive to noise.

We conclude that the representation through EP is a good compromise between stability in presence of noise and ability of representing in a compact way a large class of functions.