A Phase Transition and Stochastic Domination in Pippenger's Probabilistic Failure Model for Boolean Networks with Unreliable Gates
| dc.creator | Raginsky, Maxim | |
| dc.date | 2003-11-04 | |
| dc.date | 2003-11-24 | |
| dc.date.accessioned | 2026-07-07T05:02:36Z | |
| dc.date.available | 2026-07-07T05:02:36Z | |
| dc.description | We study Pippenger's model of Boolean networks with unreliable gates. In this model, the conditional probability that a particular gate fails, given the failure status of any subset of gates preceding it in the network, is bounded from above by some $ε$. We show that if we pick a Boolean network with $n$ gates at random according to the Barak-Erdős model of a random acyclic digraph, such that the expected edge density is $c n^{-1}\log n$, and if $ε$ is equal to a certain function of the size of the largest reflexive, transitive closure of a vertex (with respect to a particular realization of the random digraph), then Pippenger's model exhibits a phase transition at $c=1$. Namely, with probability $1-o(1)$ as $n\to\infty$, we have the following: for $0 \le c \le 1$, the minimum of the probability that no gate has failed, taken over all probability distributions of gate failures consistent with Pippenger's model, is equal to $o(1)$, whereas for $c >1$ it is equal to $\exp(-\frac{c}{e(c-1)}) + o(1)$. We also indicate how a more refined analysis of Pippenger's model, e.g., for the purpose of estimating probabilities of monotone events, can be carried out using the machinery of stochastic domination. | |
| dc.description | 20 pages, 1 eps figure; made some cosmetic changes, corrected a few errors | |
| dc.identifier | https://arxiv.org/abs/math/0311045 | |
| dc.identifier | http://arxiv.org/abs/math/0311045 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/69069 | |
| dc.subject | Probability | |
| dc.subject | Disordered Systems and Neural Networks | |
| dc.subject | Mathematical Physics | |
| dc.subject | Combinatorics | |
| dc.subject | 82B26; 94C10; 60K10; 05C20; 05C80 | |
| dc.title | A Phase Transition and Stochastic Domination in Pippenger's Probabilistic Failure Model for Boolean Networks with Unreliable Gates | |
| dc.type | text |