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.

A typical approach to estimate an unknown quantity /spl mu/ is to design an experiment that produces a random variable Z distributed in [O,1] with E[Z]=/spl 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 AA which, given /spl epsiv/ and /spl delta/, when running independent experiments with respect to any Z, produces an estimate that is within a factor 1+/spl epsiv/ of /spl mu/ with probability at least 1-/spl delta/. We prove that the expected number of experiments ran by AA (which depends on Z) is optimal to within a constant factor for every Z.

When a new computer software package is developed, a testing procedure is often put into effect to eliminate the faults, or bugs, in the package. One common procedure is to try the package on a set of well-known problems to try to see if any errors result. This goes for some fixed time with all detected errors being noted. Then the testing stops and the package is carefully checked to determine the specific bugs that were responsible for the observed errors, and the package is then altered to remove these bugs. A problem of great importance is the estimation of the error rate of this revised software package.

When a new computer software package is developed and all obvious erros removed, a testing procedure is often put into effect to eliminate the remaining errors in the package. One common procedure is to try the package on a set of randomly chosen problems. We suppose that whenever a program encounters an error, a system failure results. At this point the software is inspected to determine and remove the error responsible for the failure. This goes on for some time and two problems of interest are 1) to estimate the error rate of the software at a given time t, and 2) to develop a stopping rule for determining when to discontinue the testing and declare that the software is ready for use. In this paper, a model for the above is proposed as an estimation and stopping rule procedure.