The Bernoulli Model
Random approximate computation in one model: the Bernoulli model, its preprints, the monograph that unifies them, and the prior work it builds on.
The one-sentence version. A Bernoulli set is a set you can store far below the information-theoretic cost of the exact set, in exchange for a known, tunable rate of false positives and false negatives. The Bernoulli model is the framework that makes that trade precise and then carries it everywhere: from sets to maps, relations, and arbitrary algebraic types, with the error propagation worked out operation by operation, including where two error rates stop being enough.
A Bloom filter is the special case everyone already knows: false positives, no false negatives, one of the two error rates pinned to zero. The model generalizes it. Both error rates are first-class and tunable, and the same algebra that governs a single membership test governs unions, intersections, joins, function composition, and the Boolean post-processing of noisy measurements.
Few of the individual results are new. Most have named predecessors, credited below. What the program adds is the unification.
The monograph: the center of gravity
Everything below is being drawn together into one book.
Bernoulli Types: Two-Sided Error in Approximate Membership, Retrieval, and Computation builds the model from a single atom, the Bernoulli Boolean, and composes outward: random approximate sets, their entropy and the constructions that approach the space bound, maps, relations, and an algebra of approximate data types. It is explicit about where the model breaks: two-rate summaries do not compose through Boolean formulas (the book computes error per latent input instead), and rates that vary across elements, correlated noise, and adversarial inputs each get their own treatment. Every chapter closes with notes crediting the established results it builds on. The preprints below are superseded by it; it is the thing I most want read.
Read it: online in the browser or as a PDF (335 pages, October 2026 edition, CC BY 4.0).
Lineage and prior art
The pieces have a long history. The main predecessors:
- The noisy bit. Warner’s randomized response (1965) reports a bit through a known, asymmetric flip channel and corrects for it afterward, which is the Bernoulli Boolean. Bloom (1970) gave the data-structure version: a membership bit with false positives and no false negatives.
- Parity of independent flips. Gallager’s Lemma 1 (1962): if bit \(i\) is set independently with probability \(p_i\), an odd number are set with probability \(\frac{1}{2}\left(1 - \prod_i (1 - 2p_i)\right)\). That is the parity and syndrome-bit formula.
- Error through circuits. Parker and McCluskey (1975) propagated signal probabilities through combinational logic. The noisy-gate algebra for AND, OR, and NOT is their analysis.
- Space bounds. Carter, Floyd, Gill, Markowsky, and Wegman (1978) proved the \(\log_2(1/\varepsilon)\) bits-per-element lower bound for approximate membership. Pagh and Rodler’s lossy dictionaries (2001) extended it to structures that also allow false negatives, a case the entropy preprint describes as open.
- Perfect hash plus fingerprints. Dietzfelbinger and Pagh (2008) describe approximate membership as a minimal perfect hash function plus \(\log_2(1/\varepsilon)\)-bit fingerprints. The perfect hash filter is that construction.
- Probability types. Decaf (Boston, Sampson, Grossman, and Ceze,
OOPSLA 2015) gave each type a
probability of being correct and inferred how it composes through a program.
bernoulli<T>is that idea with two error rates in place of one. - Probabilistic relational algebra. Fuhr and Rölleke (1997) carried probabilities through selection, projection, and join. The approximate-relation work belongs to that line and to the probabilistic-database literature that followed it.
- Cipher-map properties. On the trapdoor side, totality echoes honey encryption (Juels and Ristenpart, 2014), where decrypting under a wrong key still yields a plausible message; representation uniformity is homophonic substitution (treated information-theoretically by Jendal, Kuhn, and Massey, EUROCRYPT ‘89); and a retrieval structure whose encoding hides its keys is an oblivious key-value store (Garimella et al., 2021).
What the program contributes. The unifying model, not a stream of new theorems: one per-element error model that holds these pieces in a single algebra; its stated limits, the places where per-element rates stop being enough (rates that vary across elements, correlated noise, adversarial inputs, and Boolean compositions whose error two rates no longer determine); the monograph that carries the argument through at book length; and an executable companion that checks the formulas. The program’s verified new finding so far is a security result, the GBFPlus counterexample under Applications.
The papers
A family of preprints, each a self-contained piece of the argument that the monograph consolidates. All carry minted Zenodo DOIs. They are preprints, not peer-reviewed publications. On 2026-10-21 each received a final, corrected version (an errata box after the abstract lists every change and the predecessors it credits) and was frozen in favor of the monograph; the DOIs below resolve to all versions, newest first.
Foundations
| Paper | What it covers |
|---|---|
| Bernoulli Sets: A Model for Random Approximate Sets | The model itself: the two axioms (element-wise independence and conditional block independence), the false-positive / false-negative parameterization, the error-count distributions, and higher-order composition. The hub the rest build on. |
| Composition of Bernoulli Sets | Closed-form error propagation through union, intersection, complement, and difference, the monoid structure, and the relational subset and equality predicates. |
| Binary Classification Measures for Random Approximate Sets | PPV, NPV, accuracy, and Youden’s J as random variables, with prevalence sensitivity by the delta method. |
| Entropy and Space Complexity of Random Approximate Sets | The lower bound on bits per element and the space-accuracy trade-off, stated in the model’s terms (the bound itself is Carter et al.’s). |
| The Bernoulli Model: A Probabilistic Framework for Data Structures and Types | The type-theoretic generalization: Bool as the atom, approximate sum and product types, and the computational basis from which the rest is built. |
Constructions
| Paper | What it covers |
|---|---|
| The Bernoulli Hash Function: Optimal Bernoulli Sets and Bernoulli Maps | A seed-search construction aimed at the entropy bound: the threshold predicate, generalized acceptance, and a unified set/map framework. |
| The Perfect Hash Filter | The positive Bernoulli set and map built from perfect hashing and fingerprints, with a ranked-search application. |
Extensions
| Paper | What it covers |
|---|---|
| The Algebra of the Random Approximate Map Model | Functions from X to Y as first-class approximate objects, and the error rates of map composition. |
| Error contracts for approximate relations | Why per-tuple false-positive and false-negative rates do not determine query error once operands share dependence: scoped operator and invariant-preservation formulas, sharp worst-case error for monotone queries (elementary consequences of established certificate theory), and a reproducible stored-filter calibration study. Retitled; the current Zenodo version still carries the earlier title, The Abstract Data Type of the Approximate Relation. |
Applications
| Paper | What it covers |
|---|---|
| A Forward (ε, ω) Calculus for Quantum Readout Error | The model applied to the classical post-processing of quantum measurement, worked on real device calibration data. A preprint, not under journal review. Its propagation formulas are the classical results credited above (Gallager; Parker and McCluskey), and the material is being folded into the monograph. |
| Adjacent-Domain Disclosure from Public Occupancy in GBFPlus | The program’s verified security finding: a confidentiality counterexample to GBFPlus (Qin et al., Entropy 2026), a scheme for attesting cross-domain data flows on a public ledger that treats the adjacent-domain identifier as protected. Public occupancy identifies every share of an inserted word, and their XOR reconstructs it, so an allowed one-insertion attestation reveals that identifier exactly. Proved, and reproduced with exhaustive finite checks; a Zenodo preprint with its evidence archive. |
The software
The Python package is the reference implementation and the book’s executable
companion: pure Python with no runtime dependencies, covering the atom and its
Boolean algebra, Bloom-style sets and their composition, perfect hash filters and
retrieval, relations, and sketches, in phases that mirror the monograph’s parts.
Its bernoulli.formula module computes exact error per latent input for Boolean
formulas over noisy bits, the calculation that two-rate summaries cannot do.
pip install bernoulli-types
Version 0.4.0 on PyPI; source in
bernoulli-py/.
Notes and posts
Shorter writing on the model, tagged bernoulli-model. The
Bernoulli Types series collects the introductory
posts.
- maph: Maps Based on Perfect Hashing for Sub-Microsecond Key-Value Storage · June 2024A key-value store built on memory-mapped I/O, approximate perfect hashing, and lock-free atomics. Sub-100ns median latency, 10M ops/sec single-threaded.
- Entropy Maps · February 2024Entropy maps use prefix-free hash codes to approximate functions without storing the domain, achieving information-theoretic space bounds with controllable error.
- Perfect Hashing: Space Bounds, Entropy, and Cryptographic Security · February 2024Space bounds, entropy requirements, and cryptographic security properties of perfect hash functions.
- A Boolean Algebra Over Trapdoors · June 2023A Boolean algebra framework over trapdoors for cryptographic operations. Introduces a homomorphism from powerset Boolean algebra to n-bit strings via cryptographic hash functions, enabling secure …
- Noisy Turing Machines: Noisy Logic Gates · June 2023Analyzing how Bernoulli Boolean types propagate through logic circuits, with correctness probabilities for noisy AND gates and interval arithmetic for composed circuits.
- The Bernoulli Model: A Probabilistic Framework for Data Structures and Types · June 2023The Bernoulli Model is a framework for reasoning about probabilistic data structures by treating noisy outputs as Bernoulli-distributed approximations of latent values, from Booleans to set-indicator …
- Rank-Ordered Encrypted Search · June 2021Rank-ordered search over encrypted documents using entropy maps built over trapdoors, enabling relevance scoring without revealing document contents.
- Bloom Filters · March 2015Bloom filters trade perfect recall for extraordinary space efficiency. How they work and why they matter.
Connection to trapdoor computing
The Bernoulli model is also the error model for Trapdoor Computing. At the mathematical level a Bernoulli map is a cipher map: the construction’s salt is the trapdoor key, the acceptance predicate implements the cipher map, and the space formula \(-\log_2(\varepsilon) + \mu\) governs both. The composition theorem \(\eta_{\text{total}} = 1 - \prod_i (1 - \eta_i)\) is the same law on both sides. If you came here from the cryptography, that is the bridge.
Alexander Towell, metafunctor.com.