An Optimal Algorithm for Monte Carlo Estimation.
A typical approach to estimate an unknown quantity $\mu$ is to design an experiment that produces a random variable Z, distributed in [0,1] with  E[Z]=\mu$, run this experiment independently a number of times, and use the average of the outcomes as the estimate.  In this paper, we consider the case when no a priori information about Z is known except that is distributed in [0,1].  We describe an approximation algorithm ${\cal A}{\cal A}$ which, given $\epsilon$ and $\delta$, when running independent experiments with respect to any Z, produces an estimate that is within a factor $1+\epsilon$ of $\mu$ with probability at least $1-\delta$.  We prove that the expected number of experiments run by ${\cal A}{\cal A}$ (which depends on Z) is optimal to within a constant factor {for every} Z.
Introduction
The choice of experiment, or experimental design, forms an important aspect of statistics.
One of the simplest design problems is the problem of deciding when to stop sampling.
For example, suppose Z are independently and identically distributed according
to Z in the interval [0; 1] with mean -Z . From Bernstein's inequality, we know that if
N is fixed proportional to ln(1=ffi)=ffl 2 and with probability at
least approximates -Z with absolute error ffl. Often, however, -Z is small and
a good absolute error estimate of -Z is typically a poor relative error approximation of
-Z .
We say ~
-Z is an (ffl; ffi)-approximation of -Z if
In engineering and computer science applications we often desire an (ffl; ffi)-approximation
of -Z in problems where exact computation of -Z is NP-hard. For example, many
researchers have devoted substantial effort to the important and difficult problem of approximating
the permanent of valued matrices [1, 4, 5, 9, 10, 13, 14]. Researchers
have also used (ffl; ffi)-approximations to tackle many other difficult problems, such as approximating
probabilistic inference in Bayesian networks [6], approximating the volume
of convex bodies [7], solving the Ising model of statistical mechanics [11], solving for
network reliability in planar multiterminal networks [15, 16], approximating the number
of solutions to a DNF formula [17] or, more generally, to a GF[2] formula [18], and
approximating the number of Eulerian orientations of a graph [19].
and let oe 2
Z denote the variance of Z. Define
We first prove a slight generalization of the Zero-One Estimator Theorem [12, 15, 16, 17].
The new theorem, the Generalized Zero-One Estimator Theorem, proves that if
Z (1)
then S=N is an (ffl; ffi)-approximation of -Z .
To apply the Generalized Zero-One Estimator Theorem we require the values of the
unknown quantities -Z and oe 2
Z . Researchers circumvent this problem by computing an
upper bound - on ae Z =- 2
Z , and using - in place of ae Z =- 2
Z to determine a value for N in
Equation (1). An a priori upper bound - on ae Z =- 2
Z that is close to ae Z =- 2
Z is often very
difficult to obtain, and a poor bound leads to a prohibitive large bound on N .
To avoid the problem encountered with the Generalized Zero-One Estimator Theo-
rem, we use the outcomes of previous experiments to decide when to stop iterating.
This approach is known as sequential analysis and originated with the work of Wald
on statistical decision theory [22]. Related research has applied sequential analysis to
specific Monte Carlo approximation problems such as estimating the number of points
in a union of sets [17] and estimating the number of self-avoiding walks [20]. In other
related work, Dyer et al describe a stopping rule based algorithm that provides an upper
bound estimate on -Z [8]. With probability the estimate is at most (1
the estimate can be arbitrarily smaller than - in the challenging case when - is small.
We first describe an approximation algorithm based on a simple stopping rule. Using
the stopping rule, the approximation algorithm outputs an (ffl; ffi)-approximation of -Z
after expected number of experiments proportional to \Upsilon=- Z . The variance of the random
variable Z is maximized subject to a fixed mean -Z if Z takes on value 1 with probability
-Z and 0 with probability . In this case, oe 2
and the expected
number of experiments run by the stopping-rule based algorithm is within a constant
factor of optimal. In general, however, oe
Z is significantly smaller than -Z , and for small
values of oe 2
Z the stopping-rule based algorithm performs 1=ffl times as many experiments
as the optimal number.
We describe a more powerful algorithm, the AA algorithm, that on inputs ffl, ffi, and
independently and identically distributed outcomes Z generated from any random
variable Z distributed in [0; 1], outputs an (ffl; ffi)-approximation of -Z after an expected
number of experiments proportional to \Upsilon \Delta ae Z =- 2
Z . Unlike the simple, stopping-rule based
algorithm, we prove that for all Z, AA runs the optimal number of experiments to within
a constant factor. Specifically, we prove that if BB is any algorithm that produces an
(ffl; ffi)-approximation of -Z using the inputs ffl, ffi, and Z 1 runs an expected
number of experiments proportional to at least \Upsilon \Delta ae Z =- 2
Z . (Canetti, Evan and Goldreich
prove the related lower bound \Omega\Gammand (1=ffi)=ffl 2 ) on the number of experiments required to
approximate -Z with absolute error ffl with probability at least 1 \Gamma ffi [2].) Thus we show
that for any random variable Z, AA runs an expected number of experiments that is
within a constant factor of the minimum expected number.
The AA algorithm is a general method for optimally using the outcomes of Monte-Carlo
experiments for approximation-that is, to within a constant factor, the algorithm
uses the minimum possible number of experiments to output an (ffl; ffi)-approximation on
each problem instance. Thus, AA provides substantial computational savings in applications
that employ a poor upper bound - on ae Z =- 2
Z . For example, the best known a priori
bound on - for the problem of approximating the permanent of size n is superpolynomial
in n [13]. Yet, for many problem instances of size n, the number of experiments run by
AA is significantly smaller than this bound. Other examples exist where the bounds are
also extremely loose for many typical problem instances [7, 10, 11]. In all those applica-
tions, we expect AA to provide substantial computational savings, and possibly render
problems that were intractable, because of the poor upper bounds on ae Z =- 2
Z , amenable
to efficient approximation.
Approximation Algorithm
In Subsection 2.1, we describe a stopping rule algorithm for estimating -Z . This algorithm
is used in the first step of the approximation algorithm AA that we describe in
Subsection 2.2.
2.1 Stopping Rule Algorithm
Let Z be a random variable distributed in the interval [0; 1] with mean -Z . Let Z
be independently and identically distributed according to Z.
Stopping Rule Algorithm
Input Parameters: (ffl; ffi) with
Initialize N / 0, S / 0
While
Output: ~
Stopping Rule Theorem: Let Z be a random variable distributed in [0; 1] with
-Z be the estimate produced and let NZ be the number of experiments
that the Stopping Rule Algorithm runs with respect to Z on input ffl and ffi. Then,
The proof of this theorem can be found in Section 5.
2.2 Approximation Algorithm AA
The (ffl; ffi)-approximation algorithm AA consists of three main steps. The first step uses
the stopping rule based algorithm to produce an estimate -Z that is within a constant
factor of -Z with probability at least 1 \Gamma ffi. The second step uses the value of -
-Z to set
the number of experiments to run in order to produce an estimate -
ae Z that is within a
constant factor of ae with probability at least 1 \Gamma ffi. The third step uses the values of -Z
and -
ae Z produced in the first two steps to set the number of experiments and runs this
number of experiments to produce an (ffl; ffi)-estimate of ~
-Z of -Z .
Let Z be a random variable distributed in the interval [0; 1] with mean -Z and variance
Z . Let Z
two sets of random variables independently and
identically distributed according to Z.
Approximation Algorithm AA
Input Parameters: (ffl; ffi), with
1: Run the Stopping Rule Algorithm using Z parameters
fflg and ffi=3. This produces an estimate -Z of -Z .
Step 2: Set
-Z and initialize S / 0.
For
ae Z / maxfS=N; ffl -Z g.
Step 3: Set
ae Z =- 2
Z and initialize S / 0.
For
~
-Z / S=N .
Output: ~
-Z
AA Theorem: Let Z be any random variable distributed in [0; 1], let
be the mean of Z, oe 2
Z be the variance of Z, and ae
g. Let ~
-Z be the
approximation produced by AA and let NZ be the number of experiments run by AA
with respect to Z on input parameters ffl and ffi. Then,
(2) There is a universal constant c 0 such that Pr[NZ - c 0 \Upsilon
(3) There is a universal constant c 0 such that E[NZ
Z .
We prove the AA Theorem in Section 6.
3 Lower Bound
Algorithm AA is able to produce a good estimate of -Z using no a priori information
about Z. An interesting question is what is the inherent number of experiments needed
to be able to produce an (ffl; ffi)-approximation of -Z . In this section, we state a lower
bound on the number of experiments needed by any (ffl; ffi)-approximation algorithm to
estimate -Z when there is no a priori information about Z. This lower bound shows
that, to within a constant factor, AA runs the minimum number of experiments for
every random variable Z.
To formalize the lower bound, we introduce the following natural model. Let BB be any
algorithm that on input (ffl; ffi) works as follows with respect to Z. Let Z
independently and identically distributed according to Z with values in the interval [0; 1].
BB runs an experiment, and on the N th run BB receives the value ZN . The measure of
the running time of BB is the number of experments it runs, i.e., the time for all other
computations performed by BB is not counted in its running time. BB is allowed to
use any criteria it wants to decide when to stop running experiments and produce an
estimate, and in particular BB can use the outcome of all previous experiments. The
estimate that BB produces when it stops can be any function of the outcomes of the
experiments it has run up to that point. The requirement on BB is that is produces an
(ffl; ffi)-approximation of -Z for any Z.
This model captures the situation where the algorithm can only gather information
about -Z through running random experiments, and where the algorithm has no a priori
knowledge about the value of -Z before starting. This is a reasonable pair of assumptions
for practical situations. It turns out that the assumption about a priori knowledge can
be substantially relaxed: the algorithm may know a priori that the outcomes are being
generated according to some known random variable Z or to some closely related random
variable Z 0 , and still the lower bound on the number of experiments applies.
Note that the approximation algorithm AA fits into this model, and thus the average
number of experiments it runs with respect to Z is minimal for all Z to within a constant
factor among all such approximation algorithms.
Lower Bound Theorem: Let BB be any algorithm that works as described above on
input (ffl; ffi). Let Z be a random variable distributed in [0; 1], let -Z be the mean of Z, oe 2
Z
be the variance of Z, and ae
g. Let ~
-Z be the approximation produced by
BB and let NZ be the number of experiments run by BB with respect to Z. Suppose that
BB has the the following properties:
(1) For all Z with -Z ? 0, E[NZ
(2) For all Z with -Z ? 0,
Then, there is a universal constant c ? 0 such that for all Z, E[NZ
Z .
We prove this theorem in Section 7.
4 Preliminaries for the Proofs
We begin with some notation that is used hereafter. Let -
For fixed ff; fi - 0, we define the random variables
The main lemma we use to prove the first part of the Stopping Rule Theorem provides
bounds on the probabilities that the random variables
k are greater than zero.
We first form the sequences of random variables e di
real valued d. We prove that these sequences are supermartingales when 0 - d - 1 and
Z , i.e., for all k ? 0
and similarly,
We then use properties of supermartingales to bound the probabilities that the random
k are greater than zero. For these and subsequent proofs, we use the
following two inequalities:
Inequality 4.1 For all ff, e ff
Inequality 4.2 Let :72. For all ff with jffj - 1,
Lemma 4.3 For jdj - 1, E[e dZ
Z .
Proof: Observe that E[e dZ But from Inequality 4.2,
Taking expectations and applying Inequality 4.1 completes the proof. 2
Lemma 4.4 For 0 - d - 1, and for fi -doe 2
Z , the sequences of random variables
supermartingales.
Proof: For k - 1,
and thus,
Similarly, for k - 1
and thus from Lemma 4.3,
and
Thus, for fi -doe 2
Z ,
and
directly from the properties of conditional expectations and of
martingales.
Lemma 4.5 If j is a supermartingale then for all
This lemma is the key to the proof of the first part of the
Stopping Rule Theorem. In addition, from this lemma we easily prove a slightly more
general version of the Zero-One Estimator Theorem.
Lemma 4.6 For any fixed N ? 0, for any fi - 2-ae Z ,
\GammaN
and
\GammaN
Proof: Recall the definitions of i
N from Equations (3) and (4). Let
Then, the left-hand side of Equation (5) is equivalent to Pr[i
and the left-hand
side of Equation (6) is equivalent to Pr[i \Gamma
N and i 0\Gamma
N .
We now give the remainder of the proof of Equation (5), using i 0+
N , and omit the
remainder of the analogous proof of Equation (6) which uses i 0\Gamma
N in place of i 0+
N . For any
implies that d - 1. Note also that
since ae Z - oe 2
Z . Thus, by Lemma 4.4, e di 0+
N is a supermartingale.
Thus, by Lemma 4.5
E[e di 0+
\GammaN
Since e di 0+
0 is a constant,
E[e di 0+
completing the proof of Equation (5). 2
We use Lemma 4.6 to generalize the Zero-One Estimator Theorem [17] from f0; 1g-valued
random variables to random variables in the interval [0; 1].
Generalized Zero-One Estimator Theorem: Let Z
variables independent and identically distributed according to Z. If ffl ! 1 and
then
Pr
Proof: The proof follows directly from Lemma (4.6), using noting that
ffl- Z - 2-ae Z and that N \Delta (ffl- Z
5 Proof of the Stopping Rule Theorem
We next prove the Stopping Rule Theorem. The first part of the proof also follows
directly from Lemma 4.6. Recall that
Stopping Rule Theorem: Let Z be a random variable distributed in [0; 1] with
-Z be the estimate produced and let NZ be the number of experiments
that the Stopping Rule Algorithm runs with respect to Z on input ffl and ffi. Then,
Proof of Part (1): Recall that ~
It suffices to show that
We first show that Pr[NZ ! \Upsilon 1 =(- Z (1+ ffl))] - ffi=2. Let Assuming
that -Z (1 the definition of \Upsilon 1 and L implies that
Since NZ is an integer, NZ only if NZ - L. But NZ - L if and
only if SL - \Upsilon 1 . Thus,
Noting that ffl- Z - fi - 2-ae Z , Lemma (4.6) implies that
Using inequality (7) and noting that ae Z -Z , it follows that this is at most ffi=2.
The proof that Pr[NZ ? \Upsilon 1 =(- Z
Proof of Part (2): The random variable NZ is the stopping time such that
Using Wald's Equation [22] and E[NZ
and thus,
:Similar to the proof of the first part of the Stopping Rule Theorem, we can show that
and therefore with probability at least 1 \Gamma ffi=2 we require at most (1 experiments
to generate an approximation. The following lemma is used in the proof of the
AA Theorem in Section 6.
Stopping Rule Lemma:
Proof of the Stopping Rule Lemma: E[1=~- Z directly from
Part (2) of the Stopping Rule Theorem and the definition of NZ . E[1=~- 2
can be easily proved based on the ideas used in the proof of Part (2) of the Stopping
Rule Theorem. 2
6 Proof of the AA Theorem
AA Theorem: Let Z be any random variable distributed in [0; 1], let -Z be the mean
of Z, oe 2
Z be the variance of Z, and ae
g. Let ~
-Z be the approximation
produced by AA and let NZ be the number of experiments run by AA with respect to Z
on input parameters ffl and ffi. Then,
(2) There is a universal constant c 0 such that Pr[NZ - c 0 \Upsilon
(3) There is a universal constant c 0 such that E[NZ
Z .
Proof of Part (1): From the Stopping Rule Theorem, after Step (1) of AA, -Z
ffl) holds with probability at least 1 \Gamma ffi=3. Let
We show next that if -Z
ffl), then in Step (2) the choice of
\Upsilon 2 guarantees that -
ae Z - ae Z =2. Thus, after Steps (1) and (2), \Phi -
ae Z =- 2
Z with
probability at least 1 \Gamma ffi=3. But by the Generalized Zero-One Estimator Theorem, for
ae Z =- 2
ae Z =- 2
Z , Step (3)
guarantees that the output ~ -Z of AA satisfies Pr[-Z
For all i, let - and observe that,
Z . First assume that
Z . If oe 2
ffl)ffl- Z then from the Generalized Zero-One
Estimator Theorem, after at most (2=(1 \Gamma
experiments, ae Z =2 - S=N - 3ae Z =2 with probability at least 1 \Gamma 2ffi=3. Thus -
ae Z - ae Z =2.
If ffl- Z - oe 2
ffl)ffl- Z then ffl- Z - oe 2
ffl)), and therefore, -
ae Z - ffl -Z - ae Z =2.
Next, assume that oe 2
. But Steps (1) and (2) guarantee
that -
ae Z - ffl -
ffl), with probability at least 1 \Gamma ffi=3.
Proof of Part (2): AA may fail to terminate after O(\Upsilon \Delta ae Z =- 2
experiments either
because Step (1) failed with probability at least ffi=2 to produce an estimate -
-Z such
that -Z (1 \Gamma
ffl), or, because in Step (2), for oe 2
ffl)ffl- Z ,
and, S=N is not O(ffl- Z ) with probability at least 1 \Gamma ffi=2.
But Equation 8 guarantees that Step (1) of AA terminates after O(\Upsilon \Delta ae Z =- 2
with probability at least 1 \Gamma ffi=2. In addition, we can show, similarly to Lemma 4.6,
that if oe 2
Thus, for N - 2\Upsilon \Delta ffl=- Z , we have that Pr[S=N - 4ffl- Z
Proof of Part (3): Observe that from the Stopping Rule Theorem, the expected
number of experiments in Step (1) is O(ln(1=ffi)=(ffl- Z )). From the Stopping Rule Lemma,
the expected number of experiments in Step (2) is O(ln(1=ffi)=(ffl- Z )). Finally, in Step (3)
observe that E[-ae Z =- 2
Z
ae Z and -
-Z are computed from disjoint sets
of independently and identically distributed random variables. From the Stopping Rule
Lemma
Z ] is O(ln(1=ffi)=- 2
Furthermore, observe that E[-ae Z
Z and E[ffl- Z
Z and
Thus, the expected number of experiments in Step (3) is O(ln(1=ffi) 2.
7 Proof of Lower Bound Theorem
Lower Bound Theorem: Let BB be any algorithm that works as described above on
input (ffl; ffi). Let Z be a random variable distributed in [0; 1], let -Z be the mean of Z, oe 2
Z
be the variance of Z, and ae
g. Let ~
-Z be the approximation produced by
BB and let NZ be the number of experiments run by BB with respect to Z. Suppose that
BB has the the following properties:
(1) For all Z with -Z ? 0, E[NZ
(2) For all Z with -Z ? 0, Pr[-Z
Then, there is a universal constant c ? 0 such that for all Z, E[NZ
Z .
Let f Z (x) and f Z 0 (x) denote two given distinct probability mass (or in the continuous
case, the density) functions. Let Z independent and identically distributed
random variables with probability density f(x). Let HZ denote the hypothesis
and let H Z 0 denote the hypothesis denote the probability that we reject
HZ under f Z and let fi denote the probability that we accept H Z 0 under f Z 0 .
The sequential probability ratio test minimizes the number of expected sample size
both under HZ and H Z 0 among all tests with the same error probabilities ff and fi.
Theorem 7.1 states the result of the sequential probability ratio test. We prove the
result for completeness, although similar proofs exist [21].
Theorem 7.1 If T is the stopping time of any test of HZ against H Z 0 with error probabilities
ff and fi, and EZ [T ];
ff
and
ff
Proof: For the independent and identically distributed random variables Z 1
k .
For stopping time T , we get from Wald's first identity
and
Next,
let\Omega denote the space of all inputs on which the test rejects HZ , and
denotes its complement. Thus, by definition, we require that
Similarly, we require that Pr Z
From the properties
of expectations, we can show that
Z[\Omega
c ];
and we can decompose
T j\Omega\Gamma and observe that from
Inequality 4.1, EZ
But
I\Omega ]=Pr
where
I\Omega denotes the characteristic function for the
set\Omega\Gamma Thus, since
Y
we can show that
and finally,
ff
Similarly, we can show that
and,
Thus,
ff
and we prove the first part of the lemma. Similarly,
proves the second part of the lemma. 2
Corollary 7.2 If T is the stopping time of any test of HZ against H Z 0 with error probabilities
ff and fi such that ff
and
Proof: If ff
ff
ff
achieves a minimum at Substitution of completes the proof.
Lemma 7.5 proves the Lower Bound Theorem for oe 2
We begin with some
definitions. Let
Z .
use Inequality 4.2 to show that
Taking expectations completes the proof. 2
Lemma 7.4 2doe 2
Z =/.
denotes the derivative of / with respect to d,
the proof follows directly from Lemma 7.3. 2
Lemma 7.5 If oe 2
Proof: Let T denote the stopping time of any test of HZ against H Z 0 . Note that
Z then, by Lemmas 7.3
-). Thus, to test HZ against H 0
Z , we can use the BB
with input ffl   such that -Z (1
for ffl   we obtain ffl   - ffl=(2(2 ffl). But Corollary 7.2 gives a lower bound on the
expected number of experiments E[N
run by BB with respect the Z. We observe that
where the inequality follows from Lemma 7.3. We let
Z and substitute
to complete the proof. 2
We now prove the Lower Bound Theorem that holds also when oe 2
We
define the density
Lemma 7.6 If -Z - 1=4 then
Proof: Observe that E Z 0
Lemma 7.7 \GammaE Z
Proof: Observe that
Taking expectations completes the proof. 2
Lemma 7.8 If -Z - 1=4 then E[NZ
Proof: Let T denote the stopping time of any test of HZ against H Z 0 . From
Lemma 7.6, and since -Z - 1, =4. Thus, to test HZ against H 0
Z ,
we can use the BB with input ffl   such that -Z (1+ ffl
Solving for ffl   we obtain ffl   - ffl=(8 ffl). But Corollary 7.2 gives a lower bound on the expected
number of experiments E[N
run by BB with respect the Z. Next observe that,
by Lemma 7.7, \Gamma! Z in Corollary 7.2 is at most 2ffl- Z . Substitution of
completes the proof. 2
Proof of Lower Bound Theorem: Follows from Lemma 7.5 and Lemma 7.8. 2



--R

"How hard is it to marry at random? (On the approximation of the permanent)"
"Lower bounds for sampling algorithms for estimating the average "
"An optimal algorithm for Monte-Carlo estimation (extended abstract)"
"Polytopes, permanents and graphs with large factors"
"Approximating the Permanent of Graphs with Large Factors,"
"An optimal approximation algorithm for Bayesian inference"
"A random polynomial time algorithm for approximating the volume of convex bodies"
"A Mildly Exponential Time Algorithm for Approximating the Number of Solutions to a Multi-dimensional Knapsack Problem"
"An analysis of a Monte Carlo algorithm for estimating the permanent"
"Conductance and the rapid mixing property for Markov Chains: the approximation of the permanent resolved"
"Polynomial-time approximation algorithms for the Ising model"
"Random generation of combinatorial structures from a uniform distribution"
"A mildly exponential approximation algorithm for the permanent"
"A Monte-Carlo Algorithm for Estimating the Permanent"
"Monte Carlo algorithms for planar multiterminal network reliability problems"
"Monte Carlo algorithms for enumeration and reliability problems"
"Monte Carlo approximation algorithms for enumeration problems"
"Approximating the Number of Solutions to a GF[2] For- mula,"
"On the number of Eulerian orientations of a graph"
"Testable algorithms for self-avoiding walks"
Sequential Analysis
Sequential Analysis
--TR

--CTR
Michael Luby , Vivek K. Goyal , Simon Skaria , Gavin B. Horn, Wave and equation based rate control using multicast round trip time, ACM SIGCOMM Computer Communication Review, v.32 n.4, October 2002
Ronald Fagin , Amnon Lotem , Moni Naor, Optimal aggregation algorithms for middleware, Journal of Computer and System Sciences, v.66 n.4, p.614-656, 1 June
Fast approximate probabilistically checkable proofs, Information and Computation, v.189 n.2, p.135-159, March 15, 2004
monte carlo estimation;sequential estimation;stochastic approximation;stopping rule;approximation algorithm