bernoulli_sets/main.tex at main · queelius/bernoulli_sets · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
\documentclass[11pt,final,hidelinks]{article}
\usepackage{lmodern}
\usepackage[T1]{fontenc}
\usepackage[english]{babel}
\usepackage[utf8]{inputenc}
\usepackage[activate={true,nocompatibility},final,tracking=true,kerning=true,
    spacing=true,factor=1100,stretch=10,shrink=10]{microtype}
\microtypecontext{spacing=nonfrench}
\usepackage[margin=1in]{geometry}
\usepackage{graphicx}
\graphicspath{{img/}}
\usepackage{caption}
\usepackage{subcaption}
\usepackage{booktabs}
\usepackage{array}
\usepackage{mathtools}
\usepackage{enumitem}
\usepackage{commath}
\usepackage{appendix}
\renewcommand\appendixtocname{Appendices}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amssymb}
%\usepackage[intoc,english]{nomencl}
%\makenomenclature
\usepackage{pgfplots}
\usepackage{tikz}
\usepackage{tikzscale}
\usepackage[square,numbers]{natbib}
\bibliographystyle{plain}
\usepackage{siunitx}
\numberwithin{equation}{section}
\usepackage[hypertexnames=false]{hyperref}
\usepackage{cleveref}

\pgfplotsset{compat=newest}

\usepackage[fancy,section]{alex}

\hypersetup{
    pdftitle={Bernoulli sets: a model for random approximate sets},
    pdfauthor={Alexander Towell},               % author
    pdfsubject={computer science},              % subject of the %document
    pdfkeywords={
        probabilistic data structure,
        abstract data type,
        approximate set,
        bloom filter,
        perfect hash function,
        perfect hash filter},                   % keywords
    colorlinks=true,                            % false: boxed links;
    linkcolor=magenta,
    citecolor=green,                            % color of links to
    filecolor=blue,                             % color of file links
    urlcolor=green                              % color of external
}

\title
{
    Bernoulli sets: a model for random approximate sets
}
\author
{
    Alexander Towell\\
    \texttt{atowell@siue.edu}
}
\date{2026}

\begin{document}
\maketitle
\begin{abstract}
We introduce the \emph{Bernoulli set model}, a probabilistic framework for \emph{random approximate sets}---sets that approximate an objective set with independent, element-wise errors parameterized by false positive and false negative rates.
From two axioms---element-wise independence and conditional independence of block error rates---we derive the binomial distributions of error counts (false positives, false negatives, true positives, true negatives), their asymptotic normal limits, and confidence intervals for the realized error rates.
The model supports higher-order compositions: the $k$-fold composition of approximate identity functions yields a Bernoulli set whose rates are given by the product of binary channel transition matrices.
The framework is formulated as an abstract data type: any implementation satisfying the Bernoulli axioms---including Bloom filters, perfect hash filters, and their compositions---inherits the full theory automatically.
Companion papers develop the compositional set-theoretic algebra, classification measures, and entropy of the model.
\end{abstract}

\microtypesetup{protrusion=false}
\tableofcontents
\microtypesetup{protrusion=true}

\input{sections/intro}
\input{sections/algebra_of_sets}
\input{sections/bernoulli_model}
\input{sections/distributions}

\input{sections/conclusion}

\appendices
\input{sections/appendix}

\bibliography{references}

\end{document}