Definition:A Fully Polynomial Randomized Approximation Scheme (FPRAS) for v is a randomized algorithm which, given e, outputs v such that and runs in time polynomial in 1/e and in the input size.
If a bound p is known then we have the following, so the sample size is polynomial in 1/e, provided p is polynomial in the input size.
