随机算法 (Spring 2014)/The Monte Carlo Method

Parameter Estimation

Consider the following abstract problem of parameter estimation.

Let [math]\displaystyle{ U }[/math] be a finite set of known size, and let [math]\displaystyle{ G\subseteq U }[/math]. We want to estimate the parameter [math]\displaystyle{ |G| }[/math], i.e. the size of [math]\displaystyle{ G }[/math], or equivalently, the density (or frequency) [math]\displaystyle{ \frac{|G|}{|U|} }[/math].

We assume two devices:

• A uniform sampler [math]\displaystyle{ \mathcal{U} }[/math], which uniformly and independently samples a member of [math]\displaystyle{ U }[/math] upon each calling.
• A membership oracle of [math]\displaystyle{ G }[/math], denoted [math]\displaystyle{ \mathcal{O} }[/math]. Given as the input an [math]\displaystyle{ x\in U }[/math], [math]\displaystyle{ \mathcal{O}(x) }[/math] indicates whether or not [math]\displaystyle{ x }[/math] is a member of [math]\displaystyle{ G }[/math].

Equipped by [math]\displaystyle{ \mathcal{U} }[/math] and [math]\displaystyle{ \mathcal{O} }[/math], we can have the following Monte Carlo method:

• Choose [math]\displaystyle{ N }[/math] independent samples from [math]\displaystyle{ U }[/math] by the uniform sampler [math]\displaystyle{ \mathcal{U} }[/math], represented by the random variables [math]\displaystyle{ X_1,X_2,\ldots, X_N }[/math].
• Let [math]\displaystyle{ Y_i }[/math] be the indicator random variable defined as [math]\displaystyle{ Y_i=\mathcal{O}(X_i) }[/math], namely, [math]\displaystyle{ Y_i }[/math] indicates whether [math]\displaystyle{ X_i\in G }[/math].
• Define the estimator random variable

[math]\displaystyle{ Z=\frac{|U|}{N}\sum_{i=1}^N Y_i. }[/math]

It is easy to see that [math]\displaystyle{ \mathbf{E}[Z]=|G| }[/math] and we might hope that with high probability the value of [math]\displaystyle{ Z }[/math] is close to [math]\displaystyle{ |G| }[/math]. Formally, [math]\displaystyle{ Z }[/math] is called an [math]\displaystyle{ \epsilon }[/math]-approximation of [math]\displaystyle{ |G| }[/math] if

[math]\displaystyle{ (1-\epsilon)|G|\le Z\le (1+\epsilon)|G|. }[/math]

The following theorem states that the probabilistic accuracy of the estimation depends on the number of samples and the ratio between [math]\displaystyle{ |G| }[/math] and [math]\displaystyle{ |U| }[/math]

Theorem (estimator theorem)

Let [math]\displaystyle{ \alpha=\frac{|G|}{|U|} }[/math]. Then the Monte Carlo method yields an [math]\displaystyle{ \epsilon }[/math]-approximation to [math]\displaystyle{ |G| }[/math] with probability at least [math]\displaystyle{ 1-\delta }[/math] provided [math]\displaystyle{ N\ge\frac{4}{\epsilon^2 \alpha}\ln\frac{2}{\delta} }[/math].

Proof. Recall that [math]\displaystyle{ Y_i }[/math] indicates whether the [math]\displaystyle{ i }[/math]-th sample is in [math]\displaystyle{ G }[/math]. Let [math]\displaystyle{ Y=\sum_{i=1}^NY_i }[/math]. Then we have [math]\displaystyle{ Z=\frac{|U|}{N}Y }[/math], and hence the event [math]\displaystyle{ (1-\epsilon)|G|\le Z\le (1+\epsilon)|G| }[/math] is equivalent to that [math]\displaystyle{ (1-\epsilon)\frac{|G|}{|U|}N\le Y\le (1+\epsilon)\frac{|G|}{|U|}N }[/math]. Note that each [math]\displaystyle{ Y_i }[/math] is a Bernoulli trial that succeeds with probability [math]\displaystyle{ \frac{|G|}{|U|} }[/math], thus [math]\displaystyle{ \mathbb{E}[Y]=\frac{|G|}{|U|}N }[/math]. Then the rest is due to Chernoff bound. [math]\displaystyle{ \square }[/math]

A counting algorithm for the set [math]\displaystyle{ G }[/math] has to deal with the following three issues:

1. Implement the membership oracle [math]\displaystyle{ \mathcal{O} }[/math]. This is usually straightforward, or assumed by the model.
2. Implement the uniform sampler [math]\displaystyle{ \mathcal{U} }[/math]. This can be straightforward or highly nontrivial, depending on the problem.
3. Deal with exponentially small [math]\displaystyle{ \alpha=\frac{|G|}{|U|} }[/math]. This requires us to cleverly choose the universe [math]\displaystyle{ U }[/math]. And this part usually uses some beautiful ideas.

Counting DNFs

A disjunctive normal form (DNF) formular is a disjunction (OR) of clauses, where each clause is a conjunction (AND) of literals. For example:

[math]\displaystyle{ (x_1\wedge \overline{x_2}\wedge x_3)\vee(x_2\wedge x_4)\vee(\overline{x_1}\wedge x_3\wedge x_4) }[/math].

Note the difference from the conjunctive normal forms (CNF).

Given a DNF formular [math]\displaystyle{ \phi }[/math] as the input, the problem is to count the number of satisfying assignments of [math]\displaystyle{ \phi }[/math]. This problem is #P-complete. So we do not expect to have a polynomial-time algorithm for exact solving the problem. Instead we are seeking for approximation algorithms. Interestingly, even though the computational complexity of the problem is so high, it admits some very nice approximation algorithm which has very good approximation ratio (theoretically speaking). We need to introduce some general concepts for approximation algorithms.

FPTAS (Fully Polynomial-Time Approximation Scheme)

Consider a computational problem [math]\displaystyle{ f:\{0,1\}^*\to \mathbb{Z}^+ }[/math] whose outputs are positive integers. A FPTAS (fully polynomial-time approximation scheme) for [math]\displaystyle{ f }[/math] is an algorithm [math]\displaystyle{ \mathcal{A} }[/math] that takes the following inputs: an input instance [math]\displaystyle{ x }[/math] of problem [math]\displaystyle{ f }[/math], which we use [math]\displaystyle{ n=|x| }[/math] to denote its length; a real number [math]\displaystyle{ 0\lt \epsilon\lt 1 }[/math]; and in time polynomial in both [math]\displaystyle{ n }[/math] and [math]\displaystyle{ \frac{1}{\epsilon} }[/math], returns an output [math]\displaystyle{ \mathcal{A}(x,\epsilon) }[/math] such that [math]\displaystyle{ (1-\epsilon)f(x)\le\mathcal{A}(x,\epsilon)\le (1+\epsilon)f(x). }[/math]

The adverb "fully" stresses the polynomial reliance on not just the input size [math]\displaystyle{ n }[/math] but also the approximation parameter [math]\displaystyle{ \frac{1}{\epsilon} }[/math]. An FPTAS may approximate the true value of the output within any accuracy in polynomial time, though the polynomial becomes larger when the approximation is more accurate. Moreover, the running time grows just polynomially with repeat to the accuracy bounds. Theoretically speaking, FPTAS is the best we can get for computational hard problems, though in practice sometimes the polynomial bound might be too large even for a moderate [math]\displaystyle{ \epsilon }[/math].

The FPRAS (fully polynomial-time randomized approximation scheme), on the other hand, is the randomized relaxation of FPTAS.

FPRAS (Fully Polynomial-time Randomized Approximation Scheme)

Consider a computational problem [math]\displaystyle{ f:\{0,1\}^*\to \mathbb{Z}^+ }[/math] whose outputs are positive integers. A FPRAS (fully polynomial-time randomized approximation scheme) for [math]\displaystyle{ f }[/math] is a randomized algorithm [math]\displaystyle{ \mathcal{A} }[/math] that takes the following inputs: an input instance [math]\displaystyle{ x }[/math] of problem [math]\displaystyle{ f }[/math], which we use [math]\displaystyle{ n=|x| }[/math] to denote its length; two real numbers [math]\displaystyle{ 0\lt \epsilon,\delta\lt 1 }[/math]; and in time polynomial in [math]\displaystyle{ n }[/math], [math]\displaystyle{ \frac{1}{\epsilon} }[/math], and [math]\displaystyle{ \log\frac{1}{\delta} }[/math], returns an output [math]\displaystyle{ \mathcal{A}(x,\epsilon,\delta) }[/math] such that [math]\displaystyle{ \Pr\left[(1-\epsilon)f(x)\le\mathcal{A}(x,\epsilon,\delta)\le (1+\epsilon)f(x)\right]\ge 1-\delta. }[/math]

Note that the reliance on the confidence error [math]\displaystyle{ \delta }[/math] is polynomial in [math]\displaystyle{ \log\frac{1}{\delta} }[/math], instead of [math]\displaystyle{ \frac{1}{\delta} }[/math]. This is because due to the Chernoff bound, the confidence error can be reduced in an exponential rate by independent repetitions. This motivates the following simpler but equivalent definition of FPRAS, which only considers the special confidence error [math]\displaystyle{ \delta=\frac{1}{3} }[/math]. Apparently, this is a more natural way to relax the FPTAS to randomized algorithms as it mimics the way of generalizing class P to BPP for decision problems. If you are familiar with the Chernoff bound, it is quite easy to observe the equivalence between the following definition and the above one. And this simple definition is also easier to check (you only need to verify the case for the error [math]\displaystyle{ \delta=\frac{1}{3} }[/math]), which makes it more convenient to apply.

FPRAS (equivalent simple version)

Consider a computational problem [math]\displaystyle{ f:\{0,1\}^*\to \mathbb{Z}^+ }[/math] whose outputs are positive integers. A FPRAS (fully polynomial-time randomized approximation scheme) for [math]\displaystyle{ f }[/math] is a randomized algorithm [math]\displaystyle{ \mathcal{A} }[/math] that takes the following inputs: an input instance [math]\displaystyle{ x }[/math] of problem [math]\displaystyle{ f }[/math], which we use [math]\displaystyle{ n=|x| }[/math] to denote its length; a real number [math]\displaystyle{ 0\lt \epsilon\lt 1 }[/math]; and in time polynomial in [math]\displaystyle{ n }[/math] and [math]\displaystyle{ \frac{1}{\epsilon} }[/math], returns an output [math]\displaystyle{ \mathcal{A}(x,\epsilon) }[/math] such that [math]\displaystyle{ \Pr\left[(1-\epsilon)f(x)\le\mathcal{A}(x,\epsilon)\le (1+\epsilon)f(x)\right]\ge \frac{2}{3}. }[/math]

The Monte Carlo method for the parameter estimation problem would give us an FPRAS if the sampler and membership oracle are poly-time realizable and the fraction [math]\displaystyle{ \alpha=\frac{|G|}{|U|} }[/math] is bounded from below by a [math]\displaystyle{ \frac{1}{\mathrm{poly}(n)} }[/math].

However, for the DNF counting problem, naively applying the Monte Carlo method (treat the set of all [math]\displaystyle{ 2^n }[/math] truth assignments as [math]\displaystyle{ U }[/math] and the set of DNF solutions as [math]\displaystyle{ G }[/math]) will not give a good algorithm. The problem is that the fraction [math]\displaystyle{ \alpha=\frac{|G|}{|U|} }[/math] can be exponentially small:

Suppose that there are [math]\displaystyle{ n }[/math] variables. Let [math]\displaystyle{ U=\{\mathrm{true},\mathrm{false}\}^n }[/math] be the set of all truth assignments of the [math]\displaystyle{ n }[/math] variables. Let [math]\displaystyle{ G=\{x\in U\mid \phi(x)=\mathrm{true}\} }[/math] be the set of satisfying assignments for [math]\displaystyle{ \phi }[/math]. The straightforward use of Monte Carlo method samples [math]\displaystyle{ N }[/math] assignments from [math]\displaystyle{ U }[/math] and check how many of them satisfy [math]\displaystyle{ \phi }[/math]. This algorithm fails when [math]\displaystyle{ |G|/|U| }[/math] is exponentially small, namely, when exponentially small fraction of the assignments satisfy the input DNF formula.

So instead of naively considering the space of satisfying solutions and the space of all solutions, we represent the space of satisfying solutions to a DNF formula as a union of sets of satisfying solutions to the individual clauses, and count this union of sets. This gives us an abstract problem called the union of sets problem.

The union of sets problem

We reformulate the DNF counting problem in a more abstract framework, called the union of sets problem.

Let [math]\displaystyle{ V }[/math] be a finite universe. We are given [math]\displaystyle{ m }[/math] subsets [math]\displaystyle{ H_1,H_2,\ldots,H_m\subseteq V }[/math]. The following assumptions hold:

• For all [math]\displaystyle{ i }[/math], [math]\displaystyle{ |H_i| }[/math] is computable in poly-time.
• It is possible to sample uniformly from each individual [math]\displaystyle{ H_i }[/math].
• For any [math]\displaystyle{ x\in V }[/math], it can be determined in poly-time whether [math]\displaystyle{ x\in H_i }[/math].

The goal is to compute the size of [math]\displaystyle{ H=\bigcup_{i=1}^m H_i }[/math].

DNF counting can be interpreted in this general framework as follows. Suppose that the DNF formula [math]\displaystyle{ \phi }[/math] is defined on [math]\displaystyle{ n }[/math] variables, and [math]\displaystyle{ \phi }[/math] contains [math]\displaystyle{ m }[/math] clauses [math]\displaystyle{ C_1,C_2,\ldots,C_m }[/math], where clause [math]\displaystyle{ C_i }[/math] has [math]\displaystyle{ k_i }[/math] literals. Without loss of generality, we assume that in each clause, each variable appears at most once.

• [math]\displaystyle{ V }[/math] is the set of all assignments.
• Each [math]\displaystyle{ H_i }[/math] is the set of satisfying assignments for the [math]\displaystyle{ i }[/math]-th clause [math]\displaystyle{ C_i }[/math] of the DNF formular [math]\displaystyle{ \phi }[/math]. Then the union of sets [math]\displaystyle{ H=\bigcup_i H_i }[/math] gives the set of satisfying assignments for [math]\displaystyle{ \phi }[/math].
• Each clause [math]\displaystyle{ C_i }[/math] is a conjunction (AND) of literals. It is not hard to see that [math]\displaystyle{ |H_i|=2^{n-k_i} }[/math], which is efficiently computable.
• Sampling from an [math]\displaystyle{ H_i }[/math] is simple: we just fix the assignments of the [math]\displaystyle{ k_i }[/math] literals of that clause, and sample uniformly and independently the rest [math]\displaystyle{ (n-k_i) }[/math] variable assignments.
• For each assignment [math]\displaystyle{ x }[/math], it is easy to check whether it satisfies a clause [math]\displaystyle{ C_i }[/math], thus it is easy to determine whether [math]\displaystyle{ x\in H_i }[/math].

The coverage algorithm

We now introduce the coverage algorithm for the union of sets problem.

Consider the multiset [math]\displaystyle{ U }[/math] defined by

[math]\displaystyle{ U=H_1\uplus H_2\uplus\cdots \uplus H_m }[/math],

where [math]\displaystyle{ \uplus }[/math] denotes the multiset union. It is more convenient to define [math]\displaystyle{ U }[/math] as the set

[math]\displaystyle{ U=\{(x,i)\mid x\in H_i\} }[/math].

For each [math]\displaystyle{ x\in H }[/math], there may be more than one instances of [math]\displaystyle{ (x,i)\in U }[/math]. We can choose a unique representative among the multiple instances [math]\displaystyle{ (x,i)\in U }[/math] for the same [math]\displaystyle{ x\in H }[/math], by choosing the [math]\displaystyle{ (x,i) }[/math] with the minimum [math]\displaystyle{ i }[/math], and form a set [math]\displaystyle{ G }[/math].

Formally, [math]\displaystyle{ G=\{(x,i)\in U\mid \forall (x,j)\in U, j\le i\} }[/math]. Every [math]\displaystyle{ x\in H }[/math] corresponds to a unique [math]\displaystyle{ (x,i)\in G }[/math] where [math]\displaystyle{ i }[/math] is the smallest among [math]\displaystyle{ x\in H_i }[/math].

It is obvious that [math]\displaystyle{ G\subseteq U }[/math] and

[math]\displaystyle{ |G|=|H| }[/math].

Therefore, estimation of [math]\displaystyle{ |H| }[/math] is reduced to estimation of [math]\displaystyle{ |G| }[/math] with [math]\displaystyle{ G\subseteq U }[/math]. Then [math]\displaystyle{ |G| }[/math] can have an [math]\displaystyle{ \epsilon }[/math]-approximation with probability [math]\displaystyle{ (1-\delta) }[/math] in poly-time, if we can uniformly sample from [math]\displaystyle{ U }[/math] and [math]\displaystyle{ |G|/|U| }[/math] is suitably small.

An uniform sample from [math]\displaystyle{ U }[/math] can be implemented as follows:

• generate an [math]\displaystyle{ i\in\{1,2,\ldots,m\} }[/math] with probability [math]\displaystyle{ \frac{|H_i|}{\sum_{i=1}^m|H_i|} }[/math];
• uniformly sample an [math]\displaystyle{ x\in H_i }[/math], and return [math]\displaystyle{ (x,i) }[/math].

It is easy to see that this gives a uniform member of [math]\displaystyle{ U }[/math]. The above sampling procedure is poly-time because each [math]\displaystyle{ |H_i| }[/math] can be computed in poly-time, and sampling uniformly from each [math]\displaystyle{ H_i }[/math] is poly-time.

We now only need to lower bound the ratio

[math]\displaystyle{ \alpha=\frac{|G|}{|U|} }[/math].

We claim that

[math]\displaystyle{ \alpha\ge\frac{1}{m} }[/math].

It is easy to see this, because each [math]\displaystyle{ x\in H }[/math] has at most [math]\displaystyle{ m }[/math] instances of [math]\displaystyle{ (x,i) }[/math] in [math]\displaystyle{ U }[/math], and we already know that [math]\displaystyle{ |G|=|H| }[/math].

Due to the estimator theorem, this needs [math]\displaystyle{ \frac{4m}{\epsilon^2}\ln\frac{2}{\delta} }[/math] uniform random samples from [math]\displaystyle{ U }[/math].

This gives the coverage algorithm for the abstract problem of the union of sets. The DNF counting is a special case of it.