# An FPRAS for #nFBDD ††thanks:  The authors decided to forgo the old
convention of alphabetical ordering of authors in favor of a randomized
ordering, denoted by ⓡ. The publicly verifiable record of the randomization is
available at https://www.aeaweb.org/journals/policies/random-author-
order/search

Kuldeep S. Meel1 ⓡ Alexis de Colnet2
1University of Toronto  Canada
2TU Wien  Austria

###### Abstract

#nFBDD is the problem of counting the number of satisfying assignments, or
models, of a non-deterministic free binary decision diagram (nFBDD). The
problem is #P-hard. We study the approximate variant of this problem where one
seeks an estimate of the model count. It is known that there exists a quasi-
polynomial-time randomized approximation scheme (QPRAS) for #nFBDD. We provide
the first FPRAS for #nFBDD.

##  1 Introduction

We study the problem #nFBDD of approximating the number of satisfying
assignments of non-deterministic free binary decision diagrams (nFBDDs).
nFBDDs represent Boolean functions as decision diagrams with additional nodes
called guess nodes, where every path from the source to a sink (True or False)
reads each variable at most once. Contrary to non-deterministic ordered binary
decision diagrams (nOBDDs), variables can appear in any order in nFBDD paths.
Counting the number of satisfying assignments, or models, when there is no
guess node in the nFBDD (making it an FBDD), is feasible in linear time.
However, the same task becomes #P-hard when even a single guess node (of
unbounded arity) is allowed, as the problem of counting the models of a DNF
formula reduces to it.

Prior work on approximate model counting for nFBDDs includes a proof that
there is a quasi-polynomial-time randomized algorithm [GJK+97]. In a recent
work, there was fully polynomial randomized approximation scheme (FPRAS) for
model counting for nOBDDs [ACJR21a]. The FPRAS for #nOBDD has a rather
intimidating running time, which was improved in [MCM24]. Neither the proof in
[ACJR21a] nor the one in [MCM24] for #nOBDD extends to #nFBDD.

Yet, demonstrating that an FPRAS for #nFBDD exists would be valuable, as
nFBDDs are generally exponentially smaller than nOBDDs [ACMS20], making them
more attractive in practice. In this paper, we address this gap by providing
an FPRAS called approxMC_nFBDDfor #nFBDD.

######  Theorem 1.

Let $B$ be an nFBDD over $n$ variables. Let $\varepsilon>0$ and $\delta>0$.
$\textup{{approxMC\\_nFBDD}}(B,\varepsilon,\delta)$ runs in time
$O(n^{6}|B|^{4}(1/\varepsilon)^{4}\log(|B|)^{2}\log(1/\delta))$ and returns
$\mathsf{Est}$ with the guarantee that

$\displaystyle\Pr\left[\mathsf{Est}\in(1\pm\varepsilon)|B^{-1}(1)|\right]\geq
1-\delta$

##  2 Background

Given a positive integer $n$, $[n]$ denotes the set $\\{1,2,\dots,n\\}$. For
$m$ an integer with $m\leq n$ (potentially $m=0$), $[m,n]$ denotes the set
$\\{m,m+1,\dots,n\\}$. For $a$, $b$ and $\varepsilon$ three real numbers with
$\varepsilon>0$, we use $a\in(1\pm\varepsilon)b$ to denote that
$(1-\varepsilon)b\leq a\leq(1+\varepsilon)b$ holds and, similarly, we use
$a\in\frac{b}{1\pm\varepsilon}$ to denote that $\frac{b}{1+\varepsilon}\leq
a\leq\frac{b}{1-\varepsilon}$ holds.

Boolean variables can take value $0$ (False) or $1$ (True). A literal for a
Boolean variable $x$ is either $x$ or its negation $\neg x$. A (truth)
assignment $\alpha$ to a set $X$ of Boolean variables is a mapping from $X$ to
$\\{0,1\\}$. We also see $\alpha$ as the set of literals $\\{x\mid
x\in\alpha^{-1}(1)\\}\cup\\{\neg x\mid x\in\alpha^{-1}(0)\\}$. With this set
notation, we can define the empty assignment $\alpha_{\emptyset}$ as the only
assignment to an empty set of variable. The set representation of
$\alpha_{\emptyset}$ is $\emptyset$. For two assignments $\alpha$ and $\beta$
to $X$ and $Y$, respectively, such that $X\cap Y=\emptyset$, we denote by
$\alpha\cup\beta$ the assignment to $X\cup Y$ that reduces to $\alpha$ when
restricted to $X$, and that reduces to $\beta$ when restricted to $Y$. For $A$
a set of assignments to $X$ and $B$ a set of assignments to $Y$, again with
$X\cap Y=\emptyset$, we write $A\otimes B:=\\{\alpha\cup\beta\mid\alpha\in
A,\,\beta\in B\\}$.

#### FPRAS.

For a counting problem that, given an input $x$, aims at computing some
integer value $N(x)$, a fully polynomial-time randomized approximation scheme
(FPRAS) is an algorithm $\mathscr{A}$ that, given $x$, $0<\varepsilon$ and
$0<\delta<1$, runs in time polynomial in $|x|$ (the size of the input),
$1/\varepsilon$, and $\log(1/\delta)$, and returns $\tilde{N}$ with the
guarantee that

$\Pr_{\mathscr{A}}\left[\tilde{N}\in(1\pm\varepsilon)N(x)\right]\geq
1-\delta.$

###  2.1 Non-deterministic FBDD

A _non-deterministic BDD_ is a directed acyclic graph with a single _source_ ,
two _sinks_ called the $0$-sink and the $1$-sink, and two types of internal
nodes: _decision nodes_ and _$\lor$ -nodes_. A decision node $q$ is labeled
with a Boolean variable $x$ and has two children $q_{0}$ and $q_{1}$. It is
written as $q=ite(x,q_{1},q_{0})$ (if $x$ then $q_{1}$ else $q_{0}$) and
interpreted as a Boolean function $\langle q\rangle=(\neg x\land\langle
q_{0}\rangle)\lor(x\land\langle q_{1}\rangle)$ over
$\mathit{var}(q)=\\{x\\}\cup\mathit{var}(q_{0})\cup\mathit{var}(q_{1})$. An
$\lor$-node $q$ is labeled with the symbol $\lor$, has an unbounded number of
children $q_{1},\dots,q_{k}$, and is interpreted as a Boolean function
$\langle q\rangle=\langle q_{1}\rangle\lor\dots\lor\langle q_{k}\rangle$ over
$\mathit{var}(q)=\mathit{var}(q_{1})\cup\dots\cup\mathit{var}(q_{k})$. The
$0$-sink is interpreted as $0$ (False) and the $1$-sink is interpreted as $1$
(True). The non-deterministic BDD $B$ with source node $q$ represents the
function $\langle q\rangle$ over $\mathit{var}(B):=\mathit{var}(q)$. The set
$M(B):=B^{-1}(1)$ is the set of _models_ of $B$. Graphically, the models of
$B$ are the truth assignments $\alpha$ to the variables such that there is a
path from the source to the $1$-sink that, on each decision node
$ite(x,q_{1},q_{0})$ encountered, follows the child $q_{1}$ if $\alpha(x)=1$,
and $q_{0}$ if $\alpha(x)=0$.

An example of an nBDD is shown in Figure 1. In the figure, the children
$q_{0}$ and $q_{1}$ of a decision node $q=ite(x,q_{1},q_{0})$ are
distinguished by connecting $q$ to $q_{0}$ with a dashed edge and $q$ to
$q_{1}$ with a solid edge. For every node $q$ in $B$, we denote by $M(q)$ the
set of models of $\langle q\rangle$. Thus, when $q$ is the source node of $B$,
$M(q)=M(B)$. By convention, the empty assignment $\alpha_{\emptyset}$ is the
only assignment to the empty set of variables, and
$M(1\text{-sink})=\\{\alpha_{\emptyset}\\}$ (whereas
$M(0\text{-sink})=\emptyset$). The size of $B$, denoted by $|B|$, is its
number of nodes.

$1$$x_{4}$$x_{4}$$x_{2}$$x_{2}$$x_{1}$$x_{1}$$\lor$$\lor$$\lor$$\lor$$\lor$$\lor$$\lor$$x_{2}$$x_{2}$$x_{2}$$x_{4}$$x_{4}$$x_{4}$$x_{4}$$\lor$$\lor$$\lor$$\lor$$\lor$$x_{3}$$x_{3}$$x_{1}$$x_{1}$$x_{2}$$\lor$$\lor$$\lor$$\lor$$\lor$$x_{1}$$x_{1}$$x_{3}$$x_{3}$$\lor$$Q^{0}:$$Q^{1}:$$Q^{2}:$$Q^{3}:$$Q^{4}:$$Q^{5}:$$Q^{6}:$$Q^{7}:$$Q^{8}:$
Figure 1: A complete alternating nFBDD. The $0$-sink is omitted. All missing
edges go to the $0$-sink (possibly through a chain of decision nodes and fan-
in-1 $\lor$-nodes to preserve completeness and alternation).

A _non-deterministic free BDD_ (nFBDD) is a non-deterministic BDD where, on
every path from the source to a sink, every variable appears at most once. An
nFBDD is _complete_ when, on every path from the source to a sink, every
variable appears _exactly_ once. An nFBDD is _alternating_ when its source
node is an $\lor$-node, and when every child of every $\lor$-node is a
decision node, and when every child of every decision node is an $\lor$-node
or a sink. Every nFBDD $B$ over $n$ variables can be made complete and
alternating in time $O(n|B|)$ by adding $\lor$-nodes with a single child and
decision nodes of the form $ite(x,q,q)$. A complete alternating nFBDD over $n$
variables thus has $2n+1$ _layers_ :

$Q^{0},Q^{1},Q^{2},\dots,Q^{2n}$

where $Q^{2n}$ contains only the source $\lor$-node, $Q^{i}$ contains the
children of $Q^{i+1}$ for every $i\geq 0$, and $Q^{0}$ contains only the two
sinks. Thus, the $Q^{2j}$s with $j\geq 1$ are layers of $\lor$-nodes and the
$Q^{2j+1}$s are layers of decision nodes. Therefore, in this paper, we
consider nFBDDs that are complete and alternating.

The nBDD of Figure 1 is actually a complete alternating nFBDD. We write
$Q^{\leq i}:=Q^{0}\cup\dots\cup Q^{i}$ and $Q^{<i}:=Q^{0}\cup\dots\cup
Q^{i-1}$. For every node $q$, we denote by $\mathit{children}(q)$ its set of
children. The children of every single $\lor$-node $q$ are ordered in an
arbitrary way. We denote by $\mathit{children}_{<}(q)$ the sequence of ordered
children of $q$.

##  3 Algorithm

To compute a good estimate of $|M(B)|$, the algorithm constructs in a bottom-
up manner an estimate $p(q)$ of $|M(q)|^{-1}$ and _sample sets_ $S(q)\subseteq
M(q)$ for every node $q$ of the nFBDD $B$. In fact, for every $q$ we construct
several samples sets $S^{1}(q),\dots,S^{n_{s}n_{t}}(q)$, all subsets of
$M(q)$, where the values of $n_{s}$ and $n_{t}$ are given in approxMC_nFBDD.
The $S^{r}(q)$s and $p(q)$s are computed through random processes, thus they
are random variables. For some $q$ though the values of $p(q)$ and $S^{r}(q)$
are fixed. In particular, $p(1\text{-sink})=1$ and
$S^{r}(1\text{-sink})=\\{\alpha_{\emptyset}\\}$ for every $r$ and, for every
$q\in B$ such that $M(q)=0$, we set $p(q)=\infty$ and $S^{r}(q)=\emptyset$ for
every $r$. In the algorithm, the rules for manipulating $\infty$ are the
followings: $\infty+\infty=\infty$, $1/\infty=0$ and $1/0=\infty$. Finding all
nodes $q$ such that $M(q)=0$ can be done in time $O(|B|)$.

At the heart of the process to generate the $S^{r}(q)$ and the $p(q)$ is a
technique from [MVC21]. We break it into two procedures: reduce and union.
Given a set $S$ and some rational number $0\leq p\leq 1$, reduce returns a
subset of $S$ where each element of $S$ is kept with probability $p$.

1: $S^{\prime}\leftarrow\emptyset$

2: for $s\in S$ do

3: add $s$ to $S^{\prime}$ with probability $p$

4: return $S^{\prime}$

Algorithm 1 $\textup{{reduce}}(S,p)$

1: Let $\mathit{children}_{<}(q)=(q_{1},\dots,q_{k})$

2: for $1\leq i\leq k$ do

3: $S^{\prime}_{i}=S_{i}\setminus(M(q_{1})\cup\dots\cup M(q_{i-1}))$

4: return $S^{\prime}_{1}\cup\dots\cup S^{\prime}_{k}$

Algorithm 2 $\textup{{union}}(q,S_{1},\dots,S_{k})$

union takes in an $\lor$-node $q$ with
$\mathit{children}_{<}(q)=(q_{1},\dots,q_{k})$ and sets of samples
$S_{i}\subseteq M(q_{i})$. It computes $S^{\prime}_{1}=S_{1}$ and
$S^{\prime}_{i}=S_{i}\setminus(M(q_{1})\cup\dots\cup M(q_{i-1}))$ for all
$i\geq 2$. It then returns $S^{\prime}_{1}\cup\dots\cup S^{\prime}_{k}$.
Computing $S^{\prime}_{i}$ takes time polynomial in $|S_{i}|$ and $|B|$ since
checking whether an assignment $\alpha$ satisfies an nFBDD is takes time
linear in $|B|$. We often remove $q$ from the argument of union.

Based on reduce and union. We have two procedures that, assuming the
$p(q^{\prime})$s and $S^{r}(q^{\prime})$s have been computed for all
$q^{\prime}\in Q^{i-1}$ and all $r\in[n_{s}n_{t}]$, constructs all $p(q)$s and
$S(q)$s for $q\in Q^{i}$. The procedure OR_estimateSample deals with the
layers of $\lor$-nodes, and the procedure DEC_estimateSample deals with the
layers of decision nodes. The layer $Q^{0}$, that contains only the sinks, is
handled beforehand by setting $p(1\text{-sink})=1$ and
$S^{r}(1\text{-sink})=\\{\alpha_{\emptyset}\\}$ for every $r\in[n_{s}n_{t}]$.

1: for all $q\in Q^{i}$ with $M(q)>0$ do

2: Let $\mathit{children}_{<}(q)=(q_{1},\dots,q_{k})$

3: $\rho=\min(p(q_{1}),\dots,p(q_{k}))$

4: for $1\leq r\leq n_{s}n_{t}$ do

5:
$\widehat{S}^{r}(q)=\textup{{union}}\left(q,\textup{{reduce}}\left(S^{r}(q_{1}),\frac{\rho}{p(q_{1})}\right),\dots,\textup{{reduce}}\left(S^{r}(q_{k}),\frac{\rho}{p(q_{k})}\right)\right)$

6: $\hat{\rho}=\underset{0\leq
j<n_{t}}{\mathsf{Median}}\left(\frac{1}{\rho\cdot n_{s}}\sum\limits_{r=j\cdot
n_{s}+1}^{(j+1)n_{s}}|\widehat{S}^{r}(q)|\right)^{-1}$

7: $p(q)=\min(\rho,\hat{\rho})$

8: for $1\leq r\leq n_{s}n_{t}$ do

9:
$S^{r}(q)=\textup{{reduce}}\left(\widehat{S}^{r}(q),\frac{\rho}{p(q)}\right)$

Algorithm 3 $\textup{{OR\\_estimateSample}}(Q^{i})$ with $Q^{i}$ a layer of
$\lor$-nodes

1: for all $q\in Q^{i}$ with $M(q)>0$ do

2: $p(q)=1/(p(q_{0})^{-1}+p(q_{1})^{-1})$

3: for $1\leq r\leq n_{s}n_{t}$ do

4:
$S^{r}(q)=\left(\textup{{reduce}}\left(S^{r}(q_{0}),\frac{p(q)}{p(q_{0})}\right)\otimes\\{\bar{x}\\}\right)\cup\left(\textup{{reduce}}\left(S^{r}(q_{1}),\frac{p(q)}{p(q_{1})}\right)\otimes\\{x\\}\right)$

Algorithm 4 $\textup{{DEC\\_estimateSample}}(Q^{i})$ with $Q^{i}$ a layer of
decision nodes

Note that when $M(q_{0})=0$ (resp. $M(q_{1})=0$), DEC_estimateSample computes
$p(q)=p(q_{1})$ (resp. $p(q)=p(q_{0})$) and $S^{r}(q)=S^{r}(q_{1})$ (resp.
$S^{r}(q)=S^{r}(q_{0})$).

With these two procedures, the core part of the algorithm, described in
approxMC_nFBDD_core, is straightforward: after initializing $p(1\text{-sink})$
the $S^{r}(1\text{-sink})$, process the layers of nodes one after the other,
from bottom to top. The idea is that, after processing $Q^{i}$, all $p(q)$ for
$q\in Q^{i}$ should be good estimates of $1/|M(q)|$. Once all layers have been
processed the value $1/p(q)$ is returned. However, if at any point, some
sample set $S^{r}(q)$ contains more than $\theta=poly(|B|+1/\varepsilon)$
elements (the exact value of $\theta$ is given in approxMC_nFBDD), then we
interrupt the algorithm and returns $0$. This _sanity check_ allows us to
ensure that the algorithm works in polynomial time. We will later argue that
the probability of this event happening can be made as small as desired.

1: $n=|\mathit{var}(B)|$

2: $p(1\text{-sink})=1$ // initialize for the $1$-sink

3: $S^{r}(1\text{-sink})=\\{\alpha_{\emptyset}\\}$ for all $r\in[n_{s}n_{t}]$

4: for $q\in B$ with $M(q)=0$ do

5: $p(q)=\infty$

6: $S^{r}(q)=\emptyset$ for all $r\in[n_{s}n_{t}]$ // initialize for
unsatisfiable nodes

7: for $1\leq i\leq 2n$ do

8: if $i$ is odd then

9: $\textup{{DEC\\_estimateSample}}(Q^{i})$ //process layer of decision nodes

10: else

11: $\textup{{OR\\_estimateSample}}(Q^{i})$ //process layer of $\lor$-nodes

12: $Q^{i}=$ the $i$th layer of $B$ (from sinks (layer $0$) to source)

13: for $q\in Q^{i}$ and  $1\leq r\leq n_{s}$ do

14: if $|S^{r}(q)|\geq\theta$ then

15: return $0$ // interrupt when sample sets become too big

16: $q=$ source node of $B$

17: return $1/p(q)$

Algorithm 5 $\textup{{approxMC\\_nFBDD\\_core}}(B,n_{s},n_{t},\theta)$

The full FPRAS is approxMC_nFBDD. The algorithm takes in the nFBDD $B$, and
the real numbers $\varepsilon>0$ and $0<\delta<1$. After setting the values of
$n_{s}$ and $n_{t}$ (which give the number of sample sets to be computed per
node) and the value of $\theta$ (the size limit that sample sets must not
exceed), approxMC_nFBDD calls approxMC_nFBDD_core $m$ times and returns the
median of the $m$ outputs as final estimate for $|M(B)|$.

1: if $B$ has no model then return $0$

2: Make $B$ complete and alternating

3: $n=|var(B)|$

4: $\kappa=\frac{\varepsilon}{1+\varepsilon}$

5: $n_{s}=\lceil 16n/\kappa^{2}\rceil$

6: $n_{t}=\lceil 8\ln(16|B|)\rceil$

7: $\theta=16n_{s}n_{t}(1+\kappa)$

8: $m=\lceil 8\ln(1/\delta)\rceil$

9: for $1\leq j\leq m$ do

10: $\widehat{L}_{j}=\textup{{approxMC\\_nFBDD\\_core}}(B,n_{s},n_{t},\theta)$
// $m$ independent runs

11: return $\mathsf{Median}(\widehat{L}_{1},\dots,\widehat{L}_{m})$

Algorithm 6 $\textup{{approxMC\\_nFBDD}}(B,\varepsilon,\delta)$

##  4 Derivation paths

Derivation paths are an important concept for the analysis of the algorithms.
Paths in the nFBDD are represented by sequences of nodes that are connected in
_bottom-up_ fashion. If $q$ is the last node in a path $\pazocal{P}$ and
$q^{*}$ is a parent of $q$, then $\pazocal{P}\cdot q^{*}$ is the path where
$q^{*}$ is appended to $\pazocal{P}$. Assuming $\pazocal{P}$ contains at least
$k$ nodes, $\pazocal{P}[1,k]$ is the path restricted to the first $k$ nodes of
$\pazocal{P}$. $\pazocal{P}[1,k]$ is called a _prefix_ of $\pazocal{P}$. If
$\pazocal{P}$ has less than $k$ nodes, then $\pazocal{P}[1,k]$ equals
$\pazocal{P}$.

Let $q$ be a node of the nFBDD and let $\alpha\in M(q)$. We associate to the
pair $(\alpha,q)$ a unique _derivation path_ denoted by
$\path(\alpha,q)$.Thispathgoesfromthe$1$-sinkto$q$.Itisconstructedasfollows:\begin{itemize}\item[•]if$q$isthe$1$-sink,then$M(q)=\\{\alpha_{\emptyset}\\}$
and the only derivation path is $\path(\alpha_\emptyset,q)=(q)$.

if $q\in Q^{i}$ is a decision node $ite(x,q_{1},q_{0})$, and $\alpha\in M(q)$,
then $\alpha$ assigns the variable $x$. Let $\alpha^{\prime}$ be the
assignment $\alpha$ restricted to $\mathit{var}(\alpha)\setminus\\{x\\}$. If
$\alpha(x)=0$ then $\alpha^{\prime}\in M(q_{0})$ and the derivation path of
$\alpha$ is $\path(\alpha,q)=\path(\alpha^{\prime},q_{0})\cdot q$. If
otherwise $\alpha(x)=1$ then $\alpha^{\prime}\in M(q_{1})$ and the derivation
path of $\alpha$ is $\path(\alpha,q)=\path(\alpha^{\prime},q_{1})\cdot q$.

If $q$ is an $\lor$-node. Since its children are ordered, we define
$q^{\prime}$ as the first child of $q$ where $\alpha\in M(q^{\prime})$ and
$\path(\alpha,q)=\path(\alpha,q^{\prime})\cdot q$.

Derivation paths are defined independently of the algorithm. However, the
algorithm respects derivation paths: for every $r$, the assignment $\alpha\in
M(q)$ can end up in the sample set $S^{r}(q)$ only if it is derived through
the derivation path
$\path(\alpha,q)$.Forinstance,supposethat$q$isan$\lor$-nodewith$\prev_<(q)=(q_{1},q_{2})$
and suppose $\alpha\in M(q_{1})\cap M(q_{2})$. The derivation path
$\path(\alpha,q)$contains$q$and$q_1$butnot$q_2$because$q_1$isthefirstchildof$q$ofwhich$\alpha$isamodel.Thus,foranysetofsamples$S^r(q)$
constructed by the algorithm, $\alpha\in S^{r}(q)$ may occur only if
$\alpha\in S^{r}(q_{1})$ (note that this is a necessary condition but not a
sufficient condition). If the algorithm finds itself in the situation where
$\alpha\not\in S^{r}(q_{1})$ and $\alpha\in S^{r}(q_{2})$ hold, then $\alpha$
will not be in $S^{r}(q)$.

######  Lemma 1.

For $q\in Q^{i+1}$ and $\alpha\in M(q)$, let
$\path(\alpha,q)=(q_{0},q_{1},\dots,q_{i},q_{i+1}=q)$ and let $\alpha_{i}$ be
the restriction of $\alpha$ to $\mathit{var}(q_{i})$. Then, in every run of
approxMC_nFBDD_core, $\alpha\in S^{r}(q)$ holds only if $\alpha_{j}\in
S^{r}(q_{j})$ holds for every $0\leq j\leq i$.

###### Proof.

Suppose, toward a contradiction, that $\alpha\in S^{r}(q)$ and
$\alpha_{j}\not\in S^{r}(q_{j})$ for some $j\leq i$. We can assume that $j>0$
since $\alpha_{0}=\alpha_{\emptyset}$ and
$S^{r}(q_{0})=S^{r}(1\text{-sink})=\\{\alpha_{\emptyset}\\}=\\{\alpha_{0}\\}$.
Consider the largest $j$ such that $\alpha_{j}\not\in S^{r}(q_{j})$. Suppose
$q_{j+1}$ is a decision node for $x$ and let $b=\alpha(x)$, then $q_{j}$ is
the $b$-child of $q_{j+1}$. For $\beta\in M(q_{j+1})$, let $\beta^{\prime}$ be
its restriction to $\mathit{var}(\beta)\setminus\\{x\\}$. Looking at
DEC_estimateSample$(Q^{j+1})$, one sees that, if $\beta(x)=b$, then $\beta$ is
added to $S^{r}(q_{j+1})$ only if $\beta^{\prime}$ is in the $S^{r}(q_{j})$.
Since $\alpha^{\prime}_{j+1}=\alpha_{j}$, it follows that $\alpha_{j+1}\not\in
S^{r}(q_{j+1})$, a contradiction. Now suppose $q_{j+1}$ is an $\lor$-node with
children $q^{\prime}_{1},q^{\prime}_{2},\dots,q^{\prime}_{k}$. Here we have
$\alpha_{j+1}=\alpha_{j}$. Recall that the children of $q_{j+1}$ are ordered
and that $q_{j}$ is, by definition of a derivation path, the first child of
$q_{j+1}$ of which $\alpha_{j+1}$ is a model. Say $q_{j}=q^{\prime}_{h}$.
OR_estimateSample$(Q^{j+1})$ constructs $S^{r}(q_{j+1})$ by sampling from the
$S^{r}(q^{\prime}_{\ell})$s, $1\leq\ell\leq k$, but rejects every assignment
sampled from $S^{r}(q^{\prime}_{\ell})$ that belong to $M(q^{\prime}_{l})$ for
some $l<\ell$. Now the assignment $\alpha_{j+1}$ cannot be sampled from
$S^{r}(q^{\prime}_{\ell})$ for $\ell<h$ because $\alpha_{j+1}\not\in
M(q^{\prime}_{1})\cup\dots\cup M(q^{\prime}_{h-1})$ by definition of $h$. But
neither can it be sampled from $S^{r}(q^{\prime}_{h})$ because
$\alpha_{j+1}=\alpha_{j}\not\in S^{r}(q_{j})=S^{r}(q^{\prime}_{h})$ by
assumption. And if $\alpha_{j+1}$ is sampled from $S^{r}(q^{\prime}_{\ell})$
for $\ell>h$, then it is rejected. So $\alpha_{j+1}\not\in S^{r}(q_{j+1})$, a
contradiction. ∎

Given two different derivation paths $\pazocal{P}$ and $\pazocal{P}^{\prime}$
of the nFBDD $B$. We call their _last common prefix node_ denoted by
$\mathit{lcpn}(\pazocal{P},\pazocal{P}^{\prime})$, the highest node in the
nFBDD contained in both $\pazocal{P}$ and $\pazocal{P}^{\prime}$ such that the
two paths are consistent up to that node. In other words,
$\mathit{lcpn}(\pazocal{P},\pazocal{P}^{\prime})$ is the $k$-th node in
$\pazocal{P}$ if and only if $\pazocal{P}[1,k]=\pazocal{P}^{\prime}[1,k]$ but
$\pazocal{P}[1,k+1]\neq\pazocal{P}^{\prime}[1,k+1]$. Note that every
derivation path contains the $1$-sink, so the last common prefix node is well-
defined when $\pazocal{P}\neq\pazocal{P}^{\prime}$. And if
$\pazocal{P}=\pazocal{P}^{\prime}$, then
$\mathit{lcpn}(\pazocal{P},\pazocal{P}^{\prime})$ is simply defined as the
last node of $\pazocal{P}$. Let $q\in Q^{i+1}$ and
$\path(\alpha,q)=(q^{0}_{\alpha},q^{1}_{\alpha},\dots,q^{i}_{\alpha},q^{i+1}_{\alpha})$
with $q=q^{i+1}_{\alpha}$. For every $0\leq\ell\leq i+1$ we define the set

$I(\alpha,q,\ell):=\\{\alpha^{\prime}\in
M(q)\mid\mathit{lcpn}(\path(\alpha,q),\path(\alpha^{\prime},q))=q^{\ell}_{\alpha}\\}.$

######  Lemma 2.

For every $\alpha\in M(q)$ and
$0\leq\ell\leq|\path(\alpha,q)|$,$|I(\alpha,q,\ell)|\leq\frac{|M(q)|}{|M(q^{\ell}_{\alpha})|}$.

###### Proof.

Let $I(\alpha,q,\ell)=\\{\alpha_{1},\alpha_{2},\dots\\}$. Let $\alpha^{*}$ be
the restriction of $\alpha$ to $\mathit{var}(q^{\ell}_{\alpha})$. By
definition, every $\alpha_{i}$ is of the form $\alpha^{*}\cup\beta_{i}$. If
$\alpha^{\prime}$ is an assignment in $M(q^{\ell}_{\alpha})$, then every
$\alpha^{\prime}\cup\beta_{i}$ is in $M(q)$. But since the $\alpha_{i}$s must
differ on the $\beta_{i}$, we have $|I(\alpha,q,\ell)|$ distinct assignments
in $M(q)$. Considering all $|M(q^{\ell}_{\alpha})|$ possible values for
$\alpha^{\prime}$, we end up with
$|M(q^{\ell}_{\alpha})|\cdot|I(\alpha,q,\ell)|$ distinct assignments in
$M(q)$. ∎

##  5 Random Process

We will analyse our FPRAS using a random process that simulates
approxMC_nFBDD_core. Basically, our intuition is that, for every $\alpha\in
M(q)$, we should have statement similar to “$\textsf{Pr}[\alpha\in
S^{r}(q)]=p(q)$” holds by construction of $S^{r}(q)$ and $p(q)$. The problem
is that this equality makes no sense because $\textsf{Pr}[\alpha\in S^{r}(q)]$
is a real value between $0$ and $1$ whereas $p(q)$ is a random variable. The
random process allows us to circumvent this issue. The idea is a coupling
argument that allows us to replace the random variables $S^{r}(q)$ by ideally
behaved random variables. The random process actually simulates the version
approxMC_nFBDD_core without the test of Lines 14 and 15. That is,
approxMC_nFBDD_core where the sets $S^{r}(q)$ are allowed to grow very large.
This modified algorithm will later be referred to as
$\textup{{approxMC\\_nFBDD\\_core}}^{*}$.

###  5.1 Definition of the Random Process

The random process is defined with respect to the nFBDD $B$. Before defining
the random process, we need the notion of _history_.

#### History.

Informally, an history $h$ for a node $q$ corresponds to information in a
possible run of the algorithm necessary to compute $p(q)$. Formally, an
history $h$ of node $q$ is a set

$h=\\{(q^{\prime},t^{h}(q^{\prime}))\mid q^{\prime}\text{ a strict descendant
of }q\\}$

with $t^{h}(q^{\prime})\in(\mathbbm{Q}\cap(0,1])\cup\\{\infty\\}$. We only
consider histories that are _realizable_ , that is, such that there is a run
of the algorithm that gives the value $t^{h}(q^{\prime})$ to $p(q^{\prime})$.
The only history of a sink is the empty set (because no descendants). An
history $h$ of $q$ and an history $h^{\prime}$ of $q^{\prime}$ are
_compatible_ when $t^{h}(q^{\prime\prime})=t^{h^{\prime}}(q^{\prime\prime})$
for all $q^{\prime\prime}$ that are descendants of $q$ and $q^{\prime}$. A
_global history before layer $i$_ is a set $\\{h_{q}\mid q\in Q^{\leq i-1}\\}$
of pairwise compatible histories. For $h$ a global history before layer $i$
and $q\in Q^{\leq i}$, we define by $p^{h}(q)$, $S^{r,h}(q)$ and
$\widehat{S}^{r,h}(q)$ the random variables for the value given to $p(q)$,
$S^{r}(q)$ and $\widehat{S}^{r}(q)$ by a run of the algorithm that has given
the value $t^{h}(q^{\prime})$ to $p(q^{\prime})$ for all $q^{\prime}\in
Q^{\leq i-1}$. Note that if $q\in Q^{\leq i-1}$, then $p^{h}(q)$ is the random
variable that takes value $t^{h}(q)$ with probability $1$ (do note that
$t^{h}(q)$ is a constant, not a random variable).

#### Random variables.

The random process comprises a random variable $Y^{r}_{q,t,h}$ which domain is
the subsets of $M(q)$ for every $q\in B$, every $r\in[n_{s}n_{t}]$,
$t\in(\mathbb{Q}\cap(0,1])\cup\\{\infty\\}$ and every history $h$ of $q$. The
point of $Y^{r}_{q,t,h}$ is to simulate $S^{r,h}(q)$ when the run of the
algorithm is compatible with $h$ and when $p(q)$ is given the value $t$. For
the $1$-sink there is a single variable
$Y^{r}_{1\text{-sink},1,\emptyset}=\\{\alpha_{\emptyset}\\}$ for each $r$. For
the $0$-sink there also is a single nodes $q$ with $M(q)=0$, there also is a
single variable $Y^{r}_{0\text{-sink},\infty,\emptyset}=\emptyset$ for each
$r$. For $i>O$, the variables $Y^{r}_{q,t,h}$ for $q\in Q^{i}$, are defined
from the variables $Y^{r}_{q^{\prime},t^{\prime},h^{\prime}}$ for
$q^{\prime}\in Q^{i-1}$. We distinguish the case of decision nodes and
$\lor$-nodes.

  1. •

Let $Q^{i}$ be a layer of $\lor$-nodes. Let $q=q_{1}\lor\dots\lor q_{k}$ be a
node in $Q^{i}$ and consider

$Y^{r}_{q_{1},t_{1},h_{1}},Y^{r}_{q_{2},t_{2},h_{2}},\cdots,Y^{r}_{q_{k},t_{k},h_{k}}$

where the $h_{j}$s are pairwise compatible. Let $h$ be the history
$h_{1}\cup\dots\cup h_{k}\cup\\{(q_{1},t_{1}),\dots,(q_{k},t_{k})\\}$. Let
$t_{\min}=\min(t_{1},\dots,t_{k})$. We define a random variable $Z^{r}_{q,h}$
by

$Z^{r}_{q,h}=\textup{{union}}(q,\textup{{reduce}}(Y^{r}_{q_{1},t_{1},h_{1}},t_{\min}/t_{1}),\textup{{reduce}}(Y^{r}_{q_{2},t_{2},h_{2}},t_{\min}/t_{2}),\dots,\textup{{reduce}}(Y^{r}_{q_{k},t_{k},h_{k}},t_{\min}/t_{k})).$

$Z^{r}_{q,h}$ is meant to simulate $\widehat{S}^{r,h}(q)$. For every $t\leq
t_{\min}$, $Y^{r}_{q,t,h}$ is defined as
$\textup{{reduce}}(Z^{r}_{q,h},t/t_{\min})$.

  2. •

Now suppose $Q^{i}$ is a layer of decision nodes and let
$q=ite(x,q_{1},q_{0})$ in $Q^{i}$. Consider $Y^{r}_{q_{0},t_{0},h_{0}}$ and
$Y^{r}_{q_{1},t_{1},h_{1}}$ such that $h_{0}$ and $h_{1}$ are compatible, and
define $h=h_{0}\cup h_{1}\cup\\{(q_{0},t_{0}),(q_{1},t_{1})\\}$. Then, for
every $t\leq\min(t_{0},t_{1})$, $Y^{r}_{q,t,h}$ is defined as
$(\textup{{reduce}}(Y^{r}_{q_{0},t_{0},h_{0}},t/t_{0})\otimes\\{\neg
x\\})\cup(\textup{{reduce}}(Y^{r}_{q_{1},t_{1},h_{1}},t/t_{1})\otimes\\{x\\})$.

We will abuse notation and use the variables $Y^{r}_{q,t,h}$ and $Z^{r}_{q,h}$
for histories $h$ that are not histories of $q$. When $q\in Q^{i}$ and $h$ is
an history of an ancestor of $q$, or a global history before layer $j\geq i$,
$Y^{r}_{q,t,h}$ and $Z^{r}_{q,h}$ should be thought of as the variables
$Y^{r}_{q,t,h^{\prime}}$ and $Z^{r}_{q,h^{\prime}}$ where $h^{\prime}$ is the
history for $q$ compatible with $h$.

###  5.2 Analysis of the Random Process

We first make a key observation that motivates the interest of the random
process for analyzing the algorithms.

######  Observation 1.

Let $\mathscr{A}^{*}$ be approxMC_nFBDD_core without the interrupt mechanism
of Lines 14 and 15 (so $\mathscr{A}^{*}$ keeps going even when the sample sets
grow big). Let $i\in[0,2n+1]$ and let $H$ be a the random variable over all
realizable histories of $\mathscr{A}^{*}$ before layer $i$. Then, for every
$q\in Q^{\leq i}$ and every $r\in[n_{s}n_{t}]$,

$(H,p^{H}(q),S^{r,H}(q))=(H,p^{H}(q),Y^{r}_{q,p^{H}(q),H})$

and if $q$ is an $\lor$-node then

$(H,p^{H}(q),\widehat{S}^{r,H}(q))=(H,p^{H}(q),Z^{r}_{q,H})$

A second key observation is that, for a fixed history $h$, the random
variables $Y^{r}_{q,t,h}$ and $Z^{r}_{q,h}$ are independent of the random
variable $H$. This is because $H$ is a random variable defined with respect to
$\mathscr{A}^{*}$ while the $Y^{r}_{q,t,h}$ and $Z^{r}_{q,h}$ are defined
within the random process that is separate of $\mathscr{A}^{*}$.

######  Observation 2.

Let $\mathscr{A}^{*}$ be approxMC_nFBDD_core without the interrupt mechanism
of Lines 14 and 15. Let $i\in[0,2n+1]$ and let $H$ be a the random variable
over all realizable histories of $\mathscr{A}^{*}$ before layer $i$. Then, for
every $q\in B$, every $t$, every $r$ and every fixed history $h$ for $q$ the
random variable $H$ is independent of the variables $Y^{r}_{q,t,h}$ and
$Z^{r}_{q,h}$ (defined when $q$ is an $\lor$-node).

Now we study the properties of the $Y^{r}_{q,t,h}$ and $Z^{r}_{q,h}$
variables.

######  Lemma 3.

For every $q\in B$ with $M(q)>0$, every $r\in[n_{s}n_{t}]$, every
$t\in(\mathbbm{Q}\cap(0,1])\cup\infty$, every $\alpha\in M(q)$ and every
history $h$ for $q$, we have

$\Pr\left[\alpha\in Y^{r}_{q,t,h}\right]=t.$

And if $q$ is a $\lor$-node $q_{1}\lor\dots\lor q_{k}$, then
$\Pr\left[\alpha\in Z^{r}_{q,h}\right]=\min(t^{h}(q_{1}),\dots,t^{h}(q_{k}))$.

###### Proof.

The only history for the $1$-sink is $\emptyset$. Since
$Y^{r}_{1\text{-sink},1,\emptyset}=\\{\alpha_{\emptyset}\\}$ the claim holds
for the layer $Q^{0}$. Now we proceed by induction. Suppose that the claim
holds for all $q^{\prime}\in Q^{\leq i-1}$, all $t^{\prime}$, $r$,
$\alpha^{\prime}\in M(q^{\prime})$ and all histories $h^{\prime}$ for
$q^{\prime}$. For convenience we drop the superscript $r$.

  1. •

Suppose $Q^{i}$ is a layer of decision nodes and let $q\in Q^{i}$ be the
decision node $ite(x,q_{1},q_{0})$. By definition, $Y_{q,t,h}$ follows the
distribution given by

$(\textup{{reduce}}(Y_{q_{0},t_{0},h_{0}},t/t_{0})\otimes\\{\neg
x\\})\cup(\textup{{reduce}}(Y_{q_{1},t_{1},h_{1}},t/t_{1})\otimes\\{x\\})$

where $h=h_{0}\cup h_{1}\cup\\{(q_{0},t_{0}),(q_{1},t_{1})\\}$. Let
$\alpha^{\prime}$ be the restriction of $\alpha$ to
$\mathit{var}(q)\setminus\\{x\\}=\mathit{var}(q_{0})=\mathit{var}(q_{1})$ (by
completeness of the nFBDD). If $\alpha(x)=0$ then $\alpha^{\prime}\in
M(q_{0})$, then the induction hypothesis gives that $\Pr[\alpha^{\prime}\in
Y_{q_{0},t_{0},h_{0}}]=t_{0}$ and therefore $\Pr[\alpha\in
Y_{q,t,h}]=\frac{t}{t_{0}}\Pr[\alpha^{\prime}\in Y_{q_{0},t_{0},h_{0}}]=t$. If
$\alpha(x)=1$ then $\alpha^{\prime}\in M(q_{1})$, then the induction
hypothesis gives that $\Pr[\alpha^{\prime}\in Y_{q_{1},t_{1},h_{1}}]=t_{1}$
and therefore $\Pr[\alpha\in Y_{q,t,h}]=\frac{t}{t_{1}}\Pr[\alpha^{\prime}\in
Y_{q_{1},t_{1},h_{1}}]=t$.

  2. •

Suppose $Q^{i}$ is a layer of $\lor$-nodes and let $q\in Q^{i}$ with
$\mathit{children}_{<}(q)=(q_{1},\dots,q_{k})$. All $q_{j}$ are in $Q^{i-1}$.
By definition, $Y_{q,t,h}$ follows the distribution
$\textup{{reduce}}(Z_{q,h},t/t_{\min})$ where $h=h_{1}\cup\dots\cup
h_{k}\cup\\{(q_{1},t_{1}),\dots,(q_{k},t_{k})\\}$ and $t\leq
t_{\min}=\min(t_{1},\dots,t_{k})$. By definition, $Z_{q,h}$ follows the
distribution given by

$\textup{{union}}(\textup{{reduce}}(Y_{q_{1},t_{1},h_{1}},t_{\min}/t_{1}),\textup{{reduce}}(Y_{q_{2},t_{2},h_{2}},t_{\min}/t_{2}),\dots,\textup{{reduce}}(Y_{q_{k},t_{k},h_{k}},t_{\min}/t_{k})).$

There is a unique smallest $j$ such that $\alpha\in
M(q_{j})\setminus(M(q_{1})\cup\dots\cup M(q_{j-1}))$ holds. It follows from
the induction hypothesis that $\Pr\left[\alpha\in
Z_{q,h}\right]=\Pr\left[\alpha\in\textup{{reduce}}(Y_{q_{j},t_{j},h_{j}},t_{\min}/t_{j})\right]=\frac{t_{\min}}{t_{j}}\Pr\left[\alpha\in
Y_{q_{j},t_{j},h_{j}}\right]$ $=t_{\min}$. Finally, $\Pr\left[\alpha\in
Y_{q,t,h}\right]=\Pr\left[\alpha\in\textup{{reduce}}(Z_{q,h},t/t_{\min})\right]=\frac{t}{t_{\min}}\Pr\left[\alpha\in
Z_{q,h}\right]=t$.

∎

######  Lemma 4.

For every $q\in B$ every $r\in[n_{s}n_{t}]$,
$t\in(\mathbbm{Q}\cap(0,1])\cup\infty$, $\alpha,\alpha^{\prime}\in M(q)$ with
$\alpha\neq\alpha^{\prime}$ and every history $h$ for $q$ we have that,

$\Pr\left[\alpha\in Y^{r}_{q,t,h}\mid\alpha^{\prime}\in
Y^{r}_{q,t,h}\right]\leq\frac{t}{t^{*}}$

where
$t^{*}=t^{h}(\mathit{lcpn}(\path(\alpha,q),\path(\alpha^{\prime},q)\setminus\\{q\\})$.
Moreover, if $q$ is a $\lor$-node, then

$\Pr[\alpha\in Z^{r}_{q,h}\mid\alpha^{\prime}\in
Z^{r}_{q,h}]\leq\frac{\min(t^{h}(q_{1}),\dots,t^{h}(q_{k}))}{t^{*}}$

###### Proof.

We are going to prove a stronger statement, namely, that for every $i$ and
every $q$ and $q^{\prime}$ two nodes in $Q^{i}$ (potentially $q=q^{\prime}$),
and every $t$ and $t^{\prime}$ such that $t=t^{\prime}$ when $q=q^{\prime}$,
and every $\alpha\in M(q)$ and $\alpha^{\prime}\in M(q^{\prime})$, and $h$ and
$h^{\prime}$ two compatible histories for $q$ and $q^{\prime}$, respectively,
we have that

$\Pr\left[\alpha\in Y^{r}_{q,t,h}\text{ and }\alpha^{\prime}\in
Y^{r}_{q^{\prime},t^{\prime},h^{\prime}}\right]\leq\frac{tt^{\prime}}{t^{*}}$
(1)

where $t^{*}=t$ if $q=q^{\prime}$ and $\alpha=\alpha^{\prime}$, and
$t^{*}=t^{h}(\mathit{lcpn}(\path(\alpha,q),\path(\alpha^{\prime},q^{\prime})\setminus\\{q\\})$
otherwise. This statement is straightforward when $q=q^{\prime}$ and
$\alpha=\alpha^{\prime}$ because then $t=t^{\prime}$ and we can use Lemma 3.
In particular, the statment holds when $q$ and $q^{\prime}$ both are the
$1$-sink. Now we assume $(\alpha,q)\neq(\alpha^{\prime},q^{\prime})$ and
proceed by induction on $i$. The hypothesis $\mathscr{H}$ is that the
statement holds up to layer $i-1$ (included). For convenience, we drop the
superscript $r$.

  1. •

Suppose $Q^{i}$ is a layer of decision nodes. Let $q\in Q^{i}$ be the decision
node $ite(x,q_{1},q_{0})$ and $q^{\prime}\in Q^{i}$ be the decision node
$ite(y,q^{\prime}_{1},q^{\prime}_{0})$ (possibly with $x=y$). By definition

$\displaystyle Y_{q,t,h}$
$\displaystyle=(\textup{{reduce}}(Y_{q_{0},t_{0},h_{0}},t/t_{0})\otimes\\{\neg
x\\})\cup(\textup{{reduce}}(Y_{q_{1},t_{1},h_{1}},t/t_{1})\otimes\\{x\\})$
$\displaystyle Y_{q^{\prime},t^{\prime},h^{\prime}}$
$\displaystyle=(\textup{{reduce}}(Y_{q^{\prime}_{0},t^{\prime}_{0},h^{\prime}_{0}},t^{\prime}/t^{\prime}_{0})\otimes\\{\neg
y\\})\cup(\textup{{reduce}}(Y_{q^{\prime}_{1},t^{\prime}_{1},h^{\prime}_{1}},t^{\prime}/t^{\prime}_{1})\otimes\\{y\\})$

where $h=h_{0}\cup h_{1}\cup\\{(q_{0},t_{0}),(q_{1},t_{1})\\}$ and
$h^{\prime}=h^{\prime}_{0}\cup
h^{\prime}_{1}\cup\\{(q^{\prime}_{0},t^{\prime}_{0}),(q^{\prime}_{1},t^{\prime}_{1})\\}$.
Let $\beta$ be the restriction of $\alpha$ to
$\mathit{var}(q)\setminus\\{x\\}$ and $\beta^{\prime}$ be the restriction of
$\alpha^{\prime}$ to $\mathit{var}(q^{\prime})\setminus\\{y\\}$. Let
$j=\alpha(x)$, $k=\alpha^{\prime}(y)$ and
$q^{\star}=\mathit{lcpn}(\path(\beta,q_j),\path(\beta^{\prime},q^{\prime}_{k}))$,
then

$\displaystyle\Pr\left[\alpha\in Y_{q,t,h}\text{ and }\alpha^{\prime}\in
Y_{q^{\prime},t^{\prime},h^{\prime}}\right]$
$\displaystyle=\frac{tt^{\prime}}{t_{j}t^{\prime}_{k}}\Pr\left[\beta\in
Y_{q_{j},t_{j},h_{j}}\text{ and }\beta^{\prime}\in
Y_{q^{\prime}_{k},t^{\prime}_{k},h^{\prime}_{k}}\right]$
$\displaystyle\leq\frac{tt^{\prime}}{t^{h}(q^{\star})}$ (by $\mathscr{H}$)

We have $q=\mathit{lcpn}(\path(\alpha,q),\path(\alpha^{\prime},q^{\prime}))$
only if $q=q^{\prime}$ and $\alpha=\alpha^{\prime}$, which goes against
assumption. So
$\mathit{lcpn}(\path(\alpha,q),\path(\alpha^{\prime},q^{\prime}))=q^{\star}$
and $t^{*}=t^{h}(q^{\star})$.

  2. •

Suppose $Q^{i}$ is a layer of $\lor$-nodes and let $q,q^{\prime}\in Q^{i}$ be
satisfiable nodes with $\mathit{children}_{<}(q)=(q_{1},\dots,q_{m})$ and
$\mathit{children}_{<}(q^{\prime})=(q^{\prime}_{1},\dots,q^{\prime}_{\ell})$.
All $q_{j}$s and $q^{\prime}_{j^{\prime}}$s are in $Q^{i-1}$ (potentially some
$q_{j}$ equal to some $q^{\prime}_{j^{\prime}}$). Let $h=h_{1}\cup\dots\cup
h_{m}\cup\\{(q_{1},t_{1}),\dots,(q_{m},t_{m})\\}$ and
$h^{\prime}=h^{\prime}_{1}\cup\dots\cup
h^{\prime}_{m}\cup\\{(q^{\prime}_{1},t^{\prime}_{1}),\dots,(q^{\prime}_{\ell},t^{\prime}_{\ell})\\}$.
Let $t_{\min}=\min(t_{1},\dots,t_{m})$ and
$t^{\prime}_{\min}=\min(t^{\prime}_{1},\dots,t^{\prime}_{\ell})$. By
definition, $Y_{q,t,h}=\textup{{reduce}}(Z_{q,h},t/t_{\min})\text{ and
}Y_{q^{\prime},t^{\prime},h^{\prime}}=\textup{{reduce}}(Z_{q^{\prime},h^{\prime}},t^{\prime}/t^{\prime}_{\min})$
where $t\leq t_{\min}$ and $t^{\prime}\leq t^{\prime}_{\min}$. By definition,

$\displaystyle
Z_{q,h}=\textup{{union}}(q,\textup{{reduce}}(Y_{q_{1},t_{1},h_{1}},t_{\min}/t_{1}),\textup{{reduce}}(Y_{q_{2},t_{2},h_{2}},t_{\min}/t_{2}),\dots,\textup{{reduce}}(Y_{q_{m},t_{m},h_{m}},t_{\min}/t_{m}))$
$\displaystyle
Z_{q^{\prime},h^{\prime}}=\textup{{union}}(q^{\prime},\textup{{reduce}}(Y_{q^{\prime}_{1},t^{\prime}_{1},h^{\prime}_{1}},t^{\prime}_{\min}/t^{\prime}_{1}),\textup{{reduce}}(Y_{q^{\prime}_{2},t^{\prime}_{2},h^{\prime}_{2}},t^{\prime}_{\min}/t^{\prime}_{2}),\dots,\textup{{reduce}}(Y_{q^{\prime}_{\ell},t^{\prime}_{\ell},h^{\prime}_{\ell}},t^{\prime}_{\min}/t^{\prime}_{\ell}))$

There is a unique $j\in[m]$ and a unique $k\in[\ell]$ such that $\alpha\in
Z_{q,h}$ only if $\alpha\in Y_{q_{j},t_{j},h_{j}}$ and $\alpha^{\prime}\in
Z_{q^{\prime},h^{\prime}}$ only if $\alpha^{\prime}\in
Y_{q^{\prime}_{k},t^{\prime}_{k},h^{\prime}_{k}}$. So

$\displaystyle\Pr$ $\displaystyle\left[\alpha\in Y_{q,t,h}\text{ and
}\alpha^{\prime}\in Y_{q^{\prime},t^{\prime},h^{\prime}}\right]$
$\displaystyle=\frac{tt^{\prime}}{t_{\min}t^{\prime}_{\min}}\Pr\left[\alpha\in
Z_{q,h}\text{ and }\alpha^{\prime}\in Z_{q^{\prime},h^{\prime}}\right]$
$\displaystyle=\frac{tt^{\prime}}{t_{\min}t^{\prime}_{\min}}\Pr\left[\alpha\in\textup{{reduce}}(Y_{q_{j},t_{j},h_{j}},t_{\min}/t_{j})\text{
and
}\alpha^{\prime}\in\textup{{reduce}}(Y_{q^{\prime}_{k},t^{\prime}_{k},h^{\prime}_{k}},t^{\prime}_{\min}/t^{\prime}_{k})\right]$
$\displaystyle=\frac{tt^{\prime}}{t_{j}t^{\prime}_{k}}\Pr\left[\alpha\in
Y_{q_{j},t_{j},h_{j}}\text{ and }\alpha^{\prime}\in
Y_{q^{\prime}_{k},t^{\prime}_{k},h^{\prime}_{k}}\right]$
$\displaystyle\leq\frac{tt^{\prime}}{t^{h}(q^{\star})}$ ($\mathscr{H}$)

where
$p^{\star}=\mathit{lcpn}(\path(\alpha,q_j),\path(\alpha^{\prime},q^{\prime}_{k}))$.
We have $q=\mathit{lcpn}(\path(\alpha',q),\path(\alpha^{\prime},q^{\prime}))$
or
$q^{\prime}=\mathit{lcpn}(\path(\alpha',q),\path(\alpha^{\prime},q^{\prime}))$
only if $q=q^{\prime}$ and $\alpha=\alpha^{\prime}$, which goes against
assumption. So
$\mathit{lcpn}(\path(\alpha',q),\path(\alpha^{\prime},q^{\prime}))=q^{\star}$
and $t^{*}=t^{h}(q^{\star})$.

This finishes the proof of statement (1). Back to the statement of the Lemma,
the part on $Y^{r}_{q,t,h}$ follows from (1) by choosing $q=q^{\prime}$,
$t=t^{\prime}$, $h=h^{\prime}$ and using Lemma 3. For the part of
$Z^{r}_{q,t}$ we have that

$\Pr[\alpha\in Y^{r}_{q,t,h},\alpha^{\prime}\in
Y^{r}_{q,t,h}]=\frac{t^{2}}{t_{\min}}\Pr[\alpha\in
Z^{r}_{q,h},\alpha^{\prime}\in Z^{r}_{q,h}]\leq\frac{t^{2}}{t^{*}}$

where $t_{\min}=\min(t^{h}(q_{1}),\dots,t^{h}(q_{k}))$. We conclude using
Lemma 3. ∎

##  6 Analysis of approxMC_nFBDD

We finally conduct the analysis of approxMC_nFBDD. The hardest part to analyze
is the core algorithm approxMC_nFBDD_core, for which we will prove the
following.

######  Lemma 5.

Let $B$ be a complete alternating nFBDD over $n$ variables. Let
$\varepsilon>0$ and $\kappa=\frac{\varepsilon}{1+\varepsilon}$. Let
$n_{s}\geq\frac{16n}{\kappa^{2}}$, $n_{t}\geq 8\ln(16|B|)$ and
$\theta=16n_{s}n_{t}(1+\kappa)$.
$\textup{{approxMC\\_nFBDD\\_core}}(B,n_{s},n_{t},\theta)$ runs in time
$O(|B|^{4}n^{2}_{s}n^{2}_{t})$ and returns $\mathsf{Est}$ with the guarantee

$\displaystyle\Pr\left[\mathsf{Est}\notin(1\pm\varepsilon)|M(B)|\right]\leq\frac{1}{4}$

The probability $1/4$ is decreased down to any $\delta>0$ with the median
technique. Thus giving our main result. See 1

###### Proof.

Let $\widehat{L}_{1},\dots,\widehat{L}_{m}$ be the estimates returned by $m$
independent calls to $\textup{{approxMC\\_nFBDD\\_core}}(B,n_{s},$
$n_{t},\theta)$, with $\kappa$, $n_{s}$, $n_{t}$ and $\theta$ set as in Lemma
5. Let $X_{i}$ be the indicator variable that takes value $1$ if and only if
$\widehat{L}_{i}\not\in(1\pm\varepsilon)|M(B)|$. Let
$\bar{X}=X_{1}+\dots+X_{m}$. By Lemma 5, $\textsf{E}[\bar{X}]\leq m/4$. Using
Hoeffding bound, we have

$\Pr\left[\underset{1\leq i\leq
m}{\mathsf{Median}(X_{i})}\not\in(1\pm\varepsilon)|M(B)|\right]=\Pr\left[\bar{X}>\frac{m}{2}\right]\leq\Pr\left[\bar{X}-\textsf{E}[\bar{X}]>\frac{m}{4}\right]\leq\exp(-m/8)\leq\delta$

For the running time, approxMC_nFBDD_core is actually called on an nFBDD that
is complete and alternating, so $B$ is first turned into an equivalent
complete and alternating nFBDD $B^{\prime}$, with $|B^{\prime}|=O(n|B|)$.
Using Lemma 5, we find that computing a single $\widehat{L}_{j}$ takes time
$O(n^{6}|B|^{4}(1/\varepsilon)^{4}\log(|B|)^{2})$. We just multiply by
$m=O(\log(1/\delta))$ and we are done. ∎

Algorithm approxMC_nFBDD_core has a feature that is not convenient for the
analysis, namely, it stops whenever a sample set $S^{r}(q)$ has size greater
than $\theta$. This corresponds to Lines 14 and 15 in approxMC_nFBDD_core. Let
approxMC_nFBDD_core∗ be the same algorithm without these two lines. So the
same algorithm, but it does not stop when $S^{r}(q)$ grows big. We argue that
working with approxMC_nFBDD_core∗ is enough to prove Lemma 5 without the
running time requirement. In particular, it will be enough to prove the
following two lemmas. For these lemmas and after, $B$ is a complete
alternating nFBDD over $n$ variables, $\varepsilon>0$ and
$\kappa=\frac{\varepsilon}{1+\varepsilon}$, $n_{s}\geq\frac{16n}{\kappa^{2}}$,
$n_{t}\geq 8\ln(16|B|)$ and $\theta=16n_{s}n_{t}(1+\kappa)$.

######  Lemma 6.

The probability that
$\textup{{approxMC\\_nFBDD\\_core}}^{*}(B,n_{s},n_{t},\theta)$ computes
$p(q)\not\in(1\pm\kappa)|M(q)|^{-1}$ for some $q\in B$ is at most $1/8$.

######  Lemma 7.

The probability that
$\textup{{approxMC\\_nFBDD\\_core}}^{*}(B,n_{s},n_{t},\theta)$ constructs a
set $S^{r}(q)$ with $|S^{r}(q)|\geq\theta$ for some $q\in B$ and some
$r\in[n_{s}n_{t}]$ is at most $1/8$.

Equipped with Lemmas 6 and 7, Lemma 5 follows.

###### Proof of Lemma 5.

For convenience we do some renaming:
$\mathscr{A}:=\textup{{approxMC\\_nFBDD\\_core}}(B,n_{s},n_{t},\theta)$ and
$\mathscr{A}^{*}:=\textup{{approxMC\\_nFBDD\\_core}}^{*}(B,n_{s},n_{t},\theta)$.

$\displaystyle\Pr_{\mathscr{A}}$
$\displaystyle\left[\mathsf{Est}\not\in(1\pm\varepsilon)|M(B)|\right]$
$\displaystyle=\Pr_{\mathscr{A}^{*}}\left[\bigcup_{r}\bigcup_{q}|S^{r}(q)|\geq\theta\right]+\Pr_{\mathscr{A}^{*}}\left[\bigcap_{r}\bigcap_{q}|S^{r}(q)|<\theta\text{
and }\mathsf{Est}\not\in(1\pm\varepsilon)|M(B)|\right]$
$\displaystyle\leq\Pr_{\mathscr{A}^{*}}\left[\bigcup_{r}\bigcup_{q}|S^{r}(q)|\geq\theta\right]+\Pr_{\mathscr{A}^{*}}\left[\mathsf{Est}\not\in(1\pm\varepsilon)|M(B)|\right]$
$\displaystyle\leq\Pr_{\mathscr{A}^{*}}\left[\bigcup_{r}\bigcup_{q}|S^{r}(q)|\geq\theta\right]+\Pr_{\mathscr{A}^{*}}\left[\bigcup_{q}p(q)\not\in\frac{1}{(1\pm\varepsilon)|M(q)|}\right]$

where $q$ ranges over all nodes in $B$ and $r$ ranges in $[n_{s}n_{t}]$. Now
$\kappa$ has been set so that $p(q)\not\in\frac{1\pm\kappa}{|M(q)|}$ implies
$p(q)\not\in\frac{1}{(1\pm\varepsilon)|M(q)|}$ so, using Lemmas 6 and 7:

$\Pr_{\mathscr{A}}\left[\mathsf{Est}\not\in(1\pm\varepsilon)|M(B)|\right]\leq\Pr_{\mathscr{A}^{*}}\left[\bigcup_{r}\bigcup_{q}|S^{r}(q)|\geq\theta\right]+\Pr_{\mathscr{A}^{*}}\left[\bigcup_{q}p(q)\not\in\frac{1\pm\kappa}{|M(q)|}\right]\leq\frac{1}{4}$

Now we bound the running time of $\mathscr{A}$. The algorithm stops as soon as
a sample set grows in size beyond $\theta$. For each layer $i>0$—assuming the
algorithm has not stopped yet—when processing $q\in Q^{i}$ with
DEC_estimateSample or OR_estimateSample, up to $|Q^{i-1}|\theta
n_{s}n_{t}=O(|Q^{i-1}|n_{s}^{2}n_{t}^{2})$ samples are processed. For each
sample, it is decided whether it survives the reduce and whether it survives
the union. In the union, up to $|Q^{i-1}|$ queries of the form
$\alpha\in_{?}M(q^{\prime})$, $q^{\prime}\in Q^{i-1}$, are done to determine
the first child of $q$ of which $\alpha$ is a model. Each query takes time at
most $O(|B|)$. So the total running time for processing $Q^{i}$ is at most
$O(|B|\cdot n^{2}_{s}n^{2}_{t}\cdot|Q^{i}|\cdot|Q^{i-1}|^{2})$. So the running
time for all $2n+1$ layers is at most $O(|B|^{4}n^{2}_{s}n^{2}_{t})$ ∎

It remains to prove Lemmas 6 and 7, that is, to show that the following two
probabilities

$\Pr\left[\bigcup_{q\in
B}p(q)\not\in\frac{1\pm\kappa}{|M(q)|}\right]\qquad\text{ and
}\qquad\Pr\left[\bigcup_{r\in[n_{s}n_{t}]}\bigcup_{q\in
B}|S^{r}(q)|\geq\theta\right]$

are both fewer than $1/8$ when running
approxMC_nFBDD_core${}^{*}(B,n_{s},n_{t},\theta)$. The next two sections are
dedicated to the proof of these upper bounds.

###  6.1 Proof of Lemma 6

Here we show that, given the guarantees on $n_{s}$, $n_{t}$ and $\theta$ from
Lemma 6’s statement, the event $\bigcup_{q\in
B}p(q)\not\in\frac{1\pm\kappa}{|M(q)|}$ occurs with probability at most $1/8$
when running approxMC_nFBDD_core${}^{*}(B,n_{s},n_{t},\theta)$.

$\Pr\left[\bigcup_{q\in
B}p(q)\not\in\frac{1\pm\kappa}{|M(q)|}\right]=\Pr\left[\bigcup_{i}\bigcup_{q\in
Q^{i}}p(q)\not\in\frac{1\pm\kappa}{|M(q)|}\right]$ (2)

######  Claim 1.

The event $\left(\bigcup_{i}\bigcup_{q\in
Q^{i}}p(q)\not\in\frac{1\pm\kappa}{|M(q)|}\right)$ occurs if and only if the
event

$\left(\bigcup_{i>0}\bigcup_{q\in
Q^{i}}p(q)\not\in\frac{1\pm\kappa}{|M(q)|}\text{ and for all }q^{\prime}\in
Q^{<i},\,p(q^{\prime})\in\frac{1\pm\kappa}{|M(q^{\prime})|}\right)$

occurs

###### Proof.

The “if” direction is trivial. For the other direction, suppose that for a run
of the algorithm, we have some $q$ such that
$p(q)\in\not\in\frac{1\pm\kappa}{|M(q)|}$. Let $i$ be the smallest integer
such that there is $q\in Q^{i}$ and $p(q)\not\in(1\pm\kappa)/|M(q)|$. $i$
cannot be $0$ because the only nodes in $Q^{0}$ are the $1$-sink and the
$0$-sink and $p(q)=1/|M(q)|$ for the sinks (using that $1/0$ is $\infty$). So
$Q^{<i}$ is defined and, by minimality of $i$, we have that
$p(q^{\prime})\in(1\pm\kappa)/|M(q^{\prime})|$. ∎

So the probability (2) equals

$\displaystyle\Pr\left[\bigcup_{i>0}\bigcup_{q\in
Q^{i}}p(q)\not\in\frac{1\pm\kappa}{|M(q)|}\text{ and for all }q^{\prime}\in
Q^{<i},\,p(q^{\prime})\in\frac{1\pm\kappa}{|M(q^{\prime})|}\right]$ (3)
$\displaystyle\leq$ $\displaystyle\sum_{i>0}\sum_{q\in
Q^{i}}\Pr\left[p(q)\not\in\frac{1\pm\kappa}{|M(q)|}\text{ and for all
}q^{\prime}\in
Q^{<i},\,p(q^{\prime})\in\frac{1\pm\kappa}{|M(q^{\prime})|}\right]$

Let $P(q)$ be the probability
$\Pr\left[p(q)\not\in\frac{1\pm\kappa}{|M(q)|}\text{ and for all
}q^{\prime}\in
Q^{<i},\,p(q^{\prime})\in\frac{1\pm\kappa}{|M(q^{\prime})|}\right]$. We bound
this probability from above in the case where $q$ is a $\lor$-node and in the
case where $q$ is a decision node. The case when $q=ite(x,q_{1},q_{0})$ is a
decision node is easy by construction, if
$p(q_{0})\in\frac{1\pm\kappa}{|M(q_{0})|}$ and
$p(q_{1})\in\frac{1\pm\kappa}{|M(q_{1})|}$ then
$p(q)\in\frac{1\pm\kappa}{|M(q)|}$ with probability $1$. So there really is
only the case $q$ a $\lor$-node that is not straightforward. Let
$q=q_{1}\lor\dots\lor q_{k}$, we can assume that $M(q_{i})>0$ for all $i$.
First we use the total probability law to introduce the history in the
probability. We consider all realizable histories before $i$ and denote by
$H=h$ the event that the history $h$ occurs, that is, the event that the
algorithm sets $p(q^{\prime})$ to $p^{h}(q^{\prime})$ for all $q^{\prime}\in
Q^{<i}$.

$P(q)=\Pr\left[\bigcup_{h}H=h\text{ and
}p(q)\not\in\frac{1\pm\kappa}{|M(q)|}\text{ and for all }q^{\prime}\in
Q^{<i},\,p(q^{\prime})\in\frac{1\pm\kappa}{|M(q^{\prime})|}\right]$

where $h$ ranges over all realizable global histories before layer $i$. Recall
that $q\in Q^{i}$ so $p^{h}(q)$ is a random variable but $p^{h}(q^{\prime})$
is constant for all $q^{\prime}\in Q^{\leq i-1}$. Now the probability is the
same as

$P(q)=\Pr\left[\bigcup_{h}H=h\text{ and
}p^{h}(q)\not\in\frac{1\pm\kappa}{|M(q)|}\text{ and for all }q^{\prime}\in
Q^{<i},\,p^{h}(q^{\prime})\in\frac{1\pm\kappa}{|M(q^{\prime})|}\right].$

The probabilities are zero when $p^{h}(q^{\prime})$ is not in
$(1\pm\kappa)/|M(q^{\prime})|$. So let $\pazocal{H}$ be the set of realizable
global histories before layer $i$ such that
$p^{h}(q^{\prime})\in\frac{1\pm\kappa}{|M(q^{\prime})|}$ holds for every
$q^{\prime}\in Q^{<i}$. Then

$\displaystyle P(q)$ $\displaystyle=\sum_{h\in\pazocal{H}}\Pr\left[H=h\text{
and }p^{h}(q)\not\in\frac{1\pm\kappa}{|M(q)|}\text{ and for all }q^{\prime}\in
Q^{<i},\,p^{h}(q^{\prime})\in\frac{1\pm\kappa}{|M(q^{\prime})|}\right]$ (4)
$\displaystyle=\sum_{h\in\pazocal{H}}\Pr\left[H=h\text{ and
}p^{h}(q)\not\in\frac{1\pm\kappa}{|M(q)|}\right]$

Let $\rho:=\min(p^{h}(q_{1}),\dots,p^{h}(q_{k}))$. $\rho$ is fixed because all
$p^{h}(q_{j})$s are constant. We have that $p^{h}(q)=\min(\rho,\hat{\rho})$
for $\hat{\rho}^{-1}=\underset{0\leq
j<n_{t}}{\mathsf{Median}}\left(\frac{1}{\rho\cdot n_{s}}\sum_{r=j\cdot
n_{s}+1}^{(j+1)n_{s}}|\widehat{S}^{r,h}(q)|\right)$ where
$\widehat{S}^{r,h}(q)$ are random variables.

######  Claim 2.

$\hat{\rho}\in\frac{1\pm\kappa}{|M(q)|}$ implies that
$p^{h}(q)\in\frac{1\pm\kappa}{|M(q)|}$.

###### Proof.

If $p^{h}(q)=\hat{\rho}$ then, trivially,
$\hat{\rho}\in\frac{1\pm\kappa}{|M(q)|}$ implies that
$p^{h}(q)\in\in\frac{1\pm\kappa}{|M(q)|}$. Otherwise if $p^{h}(q)=\rho$ then
$\hat{\rho}\in\frac{1\pm\kappa}{|M(q)|}$ implies that
$p^{h}(q)\leq\hat{\rho}\leq\frac{1+\kappa}{|M(q)|}$ and, since
$h\in\pazocal{H}$ guarantees that
$\rho\geq\frac{1-\kappa}{\max_{j\in[k]}|M(q_{j})|}\geq\frac{1-\kappa}{|M(q)|}$,
we have that $p^{h}(q)\in\frac{1\pm\kappa}{|M(q)|}$. ∎

Now the key observation is that the joint distributions
$(H,p^{H}(q),\widehat{S}^{r,H}(q))$ and $\left(H,p^{H}(q),Z^{r}_{q,H}\right)$
are equal (Observation 1). So, for $h\in\pazocal{H}$,

$\displaystyle\Pr$ $\displaystyle\left[H=h\text{ and
}p^{h}(q)\not\in\frac{1\pm\kappa}{|M(q)|}\right]$ (5)
$\displaystyle\leq\Pr\left[H=h\text{ and
}p^{h}(q)\not\in\frac{1\pm\kappa}{|M(q)|}\text{ and }\underset{0\leq
j<n_{t}}{\mathsf{Median}}\left(\frac{1}{\rho\cdot n_{s}}\sum\limits_{r=j\cdot
n_{s}+1}^{(j+1)n_{s}}|Z^{r}_{q,h}|\right)\not\in\frac{|M(q)|}{1\pm\kappa}\right]$
$\displaystyle\leq\Pr\left[\underset{0\leq
j<n_{t}}{\mathsf{Median}}\left(\frac{1}{\rho\cdot n_{s}}\sum\limits_{r=j\cdot
n_{s}+1}^{(j+1)n_{s}}|Z^{r}_{q,h}|\right)\not\in\frac{|M(q)|}{1\pm\kappa}\,\Bigg{|}\,H=h\right]\Pr\left[H=h\right]$
$\displaystyle=\Pr\left[\underset{0\leq
j<n_{t}}{\mathsf{Median}}\left(\frac{1}{\rho\cdot n_{s}}\sum\limits_{r=j\cdot
n_{s}+1}^{(j+1)n_{s}}|Z^{r}_{q,h}|\right)\not\in\frac{|M(q)|}{1\pm\kappa}\right]\Pr\left[H=h\right]$

The last line follows because $Z^{r}_{q,h}$ is independent of $H$. So,
finally, we can forget about the algorithm and work only in the random
process. We bound

$\Pr\left[\underset{0\leq j<n_{t}}{\mathsf{Median}}\left(\frac{1}{\rho\cdot
n_{s}}\sum\limits_{r=j\cdot
n_{s}+1}^{(j+1)n_{s}}|Z^{r}_{q,h}|\right)\not\in\frac{|M(q)|}{1\pm\kappa}\right]$
(6)

using Chebyshev’s inequality followed by Hoeffding bound. From Lemma 3 we have
that $\mu:=\textsf{E}[|Z^{r}_{q,h}|]=\rho|M(q)|$ for every $r$.

$\displaystyle\sigma^{2}$
$\displaystyle:=\textsf{Var}\left[|Z^{r}_{q,h}|\right]\leq\textsf{E}\left[|Z^{r}_{q,h}|^{2}\right]=\mu+\sum_{\begin{subarray}{c}\alpha,\alpha^{\prime}\in
M(q),\,\alpha\neq\alpha^{\prime}\end{subarray}}\Pr\left[\alpha\in
Z^{r}_{q,h}\text{ and }\alpha^{\prime}\in Z^{r}_{q,h}\right]$
$\displaystyle=\mu+\sum_{\begin{subarray}{c}\alpha,\alpha^{\prime}\in
M(q),\,\alpha\neq\alpha^{\prime}\end{subarray}}\Pr\left[\alpha\in
Z^{r}_{q,h}\mid\alpha^{\prime}\in
Z^{r}_{q,h}\right]\Pr\left[\alpha^{\prime}\in Z^{r}_{q,h}\right]$
$\displaystyle\leq\mu+\sum_{\begin{subarray}{c}\alpha,\alpha^{\prime}\in
M(q),\,\alpha\neq\alpha^{\prime}\end{subarray}}\frac{\rho^{2}}{p^{h}(\mathit{lcpn}(\path(q,\alpha),\path(q,\alpha^{\prime}))}$
$\displaystyle(\text{Lemmas~{}\ref{lemma:proba_first_order}
and~{}\ref{lemma:proba_second_order}})$

Let
$\pazocal{P}=\path(\alpha,q)=(q^{0}_{\alpha},q^{1}_{\alpha},q^{2}_{\alpha},\dots,q^{i-1}_{\alpha},q)$,
with $q^{0}_{\alpha}$ the $1$-sink. For every $\alpha^{\prime}\in
M(q)\setminus\\{\alpha\\}$,
$\pazocal{P}^{\prime}=\path(\alpha',q)$,$\lcpn(\pazocal{P},\pazocal{P}^{\prime})$
is one of the $q^{j}_{\alpha}$. Recall that $I(\alpha,q,j)$ is the set of
$\alpha^{\prime}\in M(q)$ such that
$\mathit{lcpn}(\pazocal{P},\pazocal{P}^{\prime})=q^{j}_{\alpha}$.

$\displaystyle\sigma^{2}$ $\displaystyle\leq\mu+\sum_{\alpha\in
M(q)}\sum_{j\in[0,i-1]}|I(\alpha,q,j)|\frac{\rho^{2}}{p^{h}(q^{j}_{\alpha})}\leq\mu+\rho^{2}\sum_{\alpha\in
M(q)}\sum_{j\in[0,i-1]}\frac{|M(q)|}{|M(q^{j}_{\alpha})|p^{h}(q^{j}_{\alpha})}$
$\displaystyle\quad(\text{Lemma~{}\ref{lemma:derivation_path}})$

Because $h\in\pazocal{H}$ and $q^{j}_{\alpha}\in Q^{<i}$, we have
$|M(q^{j}_{\alpha})|p^{h}(q^{j}_{\alpha})\geq 1-\kappa$.

$\displaystyle\sigma^{2}$
$\displaystyle\leq\mu+\frac{\rho^{2}}{1-\kappa}\sum_{\alpha\in
M(q)}\sum_{j\in[0,i-1]}|M(q)|\leq\mu+\frac{2n\rho^{2}}{1-\kappa}\sum_{\alpha\in
M(q)}|M(q)|=\mu+\frac{2n\mu^{2}}{1-\kappa}$

Let $W_{j}:=\frac{1}{\rho
n_{s}}\sum\limits_{r=j*n_{s}+1}^{(j+1)n_{s}}|Z^{r}_{q,h}|$. By independence of
the $Z^{r}_{q,h}$ for different $r$ we have

  * •

$\textsf{E}[W_{j}]=\mu/\rho=|M(q)|$

  * •

$\textsf{Var}[W_{j}]=\frac{1}{\rho^{2}n_{s}^{2}}\sum_{r=1}^{n_{s}}\textsf{Var}[|Z^{r}_{q,h}|]\leq\frac{1}{\rho^{2}n_{s}}\left(\mu+\frac{2n\mu^{2}}{1-\kappa}\right)=\frac{1}{n_{s}}\left(\frac{|M(q)|}{\rho}+\frac{2n|M(q)|^{2}}{1-\kappa}\right)$

Now, $W_{j}\in\frac{|M(q)|}{1\pm\kappa}$ occurs if and only if
$\frac{-\kappa|M(q)|}{1+\kappa}\leq
W_{j}-|M(q)|\leq\frac{\kappa|M(q)|}{1-\kappa}$, which is subsumed by
$|W_{j}-|M(q)||\leq\frac{\kappa|M(q)|}{1+\kappa}$. So Chebyshev’s inequality
gives us

$\displaystyle\Pr\left[W_{j}\notin\frac{|M(q)|}{1\pm\kappa}\right]$
$\displaystyle\leq\Pr\left[\big{|}W_{j}-|M(q)|\big{|}>\frac{\kappa|M(q)|}{1+\kappa}\right]\leq\frac{(1+\kappa)^{2}}{\kappa^{2}|M(q)|^{2}}\textsf{Var}(W_{j})$
$\displaystyle\leq\frac{(1+\kappa)^{2}}{\kappa^{2}n_{s}}\left(\frac{1}{|M(q)|\rho}+\frac{2n}{1-\kappa}\right)$
$\displaystyle\leq\frac{(1+\kappa)^{2}}{\kappa^{2}n_{s}}\left(\frac{1}{1-\kappa}+\frac{2n}{1-\kappa}\right)$
($\rho\geq\frac{1-\kappa}{\max_{j}|M(q_{j})|}\geq\frac{1-\kappa}{|M(q)|}$)
$\displaystyle\leq\frac{4n}{\kappa^{2}n_{s}}$
($\frac{(1+\kappa)^{2}}{1-\kappa}$ decreases to 1)
$\displaystyle\leq\frac{1}{4}$ ($n_{s}\geq 16n/\kappa^{2}$)

where the last inequality holds when $\kappa$ is small enough and $n$ is large
enough. We can now bound the probability (6) from above. Let $E_{j}$ be the
indicator variable taking value $1$ if and only if
$W_{j}\not\in\frac{|M(q)|}{1\pm\kappa}$ and let
$\bar{E}=\sum_{j=0}^{n_{t}-1}E_{j}$. We have
$\textsf{E}[\bar{E}]\leq\frac{n_{t}}{4}$ so applying Hoeffding bound gives

$\Pr\left[\underset{0\leq
j<n_{t}}{\mathsf{Median}}(W_{j})\not\in\frac{|M(q)|}{1\pm\kappa}\right]=\Pr\left[\bar{E}>\frac{n_{t}}{2}\right]\leq\Pr\left[\bar{E}-\textsf{E}(\bar{E})\geq\frac{n_{t}}{4}\right]\leq\exp\left(-\frac{n_{t}}{8}\right)\leq\frac{1}{16|B|}.$

where the last inequality uses that $n_{t}\geq 8\ln(16|B|)$. Plugging this
into (5) and (4), it follows that

$P(q)\leq\sum_{h\in\pazocal{H}}\frac{1}{16|B|}\Pr[H=h]\leq\frac{1}{16|B|}$

Finally, using this in (3) and (2) we conclude that

$\Pr\left[\bigcup_{i}\bigcup_{q\in
Q^{i}}p(q)\not\in\frac{1\pm\kappa}{|M(q)|}\right]\leq\frac{1}{16}$ (7)

This finishes the proof of Lemma 6.

###  6.2 Proof of Lemma 7

In this section, the event to avoid is that of some $S^{r}(q)$ growing too
large in size.

$\Pr\left[\bigcup_{r\in[n_{s}n_{t}]}\bigcup_{q\in
B}|S^{r}(q)|\geq\theta\right]\leq\underbrace{\Pr\left[\bigcup_{r}\bigcup_{q}|S^{r}(q)|\geq\theta\text{
and
}\bigcap_{q}p(q)\in\frac{1\pm\kappa}{|M(q)|}\right]}_{P_{1}}+\underbrace{\Pr\left[\bigcup_{q}p(q)\not\in\frac{1\pm\kappa}{|M(q)|}\right]}_{P_{2}}$

We have already shown how to bound $P_{2}$ in the previous section so we focus
on $P_{1}$:

$P_{1}=\sum_{h}\Pr\left[H=h\text{ and
}\left(\bigcup_{r}\bigcup_{q}|S^{r}(q)|\geq\theta\right)\text{ and
}\left(\bigcap_{q}p^{h}(q)\in\frac{1\pm\kappa}{|M(q)|}\right)\right]$

where $h$ ranges over all realizable global histories for a complete run of
approxMC_nFBDD_core∗. Since all $p^{h}(q)$ are constant, we can restrict
ourselves to the $h\in\pazocal{H}$, the set of histories such that
$p^{h}(q)\in\frac{1\pm\kappa}{|M(q)|}$ for all $h$ (otherwise the probability
is zero). Using again that $(H,p^{H},S^{r,H}(q))=(H,p^{H},Y^{r}_{q,p^{H},H})$
(Observation 1), $P_{1}$ becomes

$\displaystyle P_{1}$ $\displaystyle=\sum_{h\in\pazocal{H}}\Pr\left[H=h\text{
and }\left(\bigcup_{r}\bigcup_{q}|Y^{r}_{q,p^{h},h}|\geq\theta\right)\text{
and }\left(\bigcap_{q}p^{h}(q)\in\frac{1\pm\kappa}{|M(q)|}\right)\right]$
$\displaystyle\leq\sum_{h\in\pazocal{H}}\Pr\left[H=h\text{ and
}\bigcup_{r}\bigcup_{q}|Y^{r}_{q,p^{h}(q),h}|\geq\theta\right]$
$\displaystyle=\sum_{h\in\pazocal{H}}\Pr\left[\bigcup_{r}\bigcup_{q}|Y^{r}_{q,p^{h}(q),h}|\geq\theta\right]\Pr\left[H=h\right]$
($Y^{r}_{q,t,h}$ independent of $H$)
$\displaystyle\leq\sum_{h\in\pazocal{H}}\sum_{r,q}\Pr\left[|Y^{r}_{q,p^{h}(q),h}|\geq\theta\right]\Pr\left[H=h\right]$
(union bound)
$\displaystyle\leq\sum_{h\in\pazocal{H}}\sum_{r,q}\frac{\textsf{E}\left[|Y^{r}_{q,p^{h}(q),h}|\right]}{\theta}\Pr\left[H=h\right]$
(Markov’s inequality)
$\displaystyle\leq\sum_{h\in\pazocal{H}}\sum_{r,q}\frac{1+\kappa}{\theta}\Pr\left[H=h\right]$
(Lemma 3 and $p^{h}(q)\in\frac{1\pm\kappa}{|M(q)|}$)
$\displaystyle\leq\frac{n_{s}\cdot n_{t}\cdot(1+\kappa)\cdot|B|}{\theta}$
$\displaystyle\leq\frac{1}{16}$

Combining this with (7) gives
$\Pr\left[\bigcup_{r\in[n_{s}n_{t}]}\bigcup_{q\in
B}|S^{r}(q)|\geq\theta\right]\leq P_{1}+P_{2}\leq\frac{1}{8}$. This finishes
the proof of Lemma 7.

## References

  * [ACJR21a] Marcelo Arenas, Luis Alberto Croquevielle, Rajesh Jayaram, and Cristian Riveros.  #NFA admits an FPRAS: efficient enumeration, counting, and uniform generation for logspace classes.  J. ACM, 68(6):48:1–48:40, 2021.
  * [ACJR21b] Marcelo Arenas, Luis Alberto Croquevielle, Rajesh Jayaram, and Cristian Riveros.  When is approximate counting for conjunctive queries tractable?  In Samir Khuller and Virginia Vassilevska Williams, editors, STOC ’21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021, pages 1015–1027. ACM, 2021.
  * [ACMS20] Antoine Amarilli, Florent Capelli, Mikaël Monet, and Pierre Senellart.  Connecting knowledge compilation classes and width parameters.  Theory Comput. Syst., 64(5):861–914, 2020.
  * [GJK+97] Vivek Gore, Mark Jerrum, Sampath Kannan, Z. Sweedyk, and Stephen R. Mahaney.  A quasi-polynomial-time algorithm for sampling words from a context-free language.  Inf. Comput., 134(1):59–74, 1997.
  * [KLM89] Richard M. Karp, Michael Luby, and Neal Madras.  Monte-carlo approximation algorithms for enumeration problems.  J. Algorithms, 10(3):429–448, 1989.
  * [MCM24] Kuldeep S. Meel, Sourav Chakraborty, and Umang Mathur.  A faster FPRAS for #NFA.  Proc. ACM Manag. Data, 2(2), may 2024.