# Timeline for Estimating Average in Polynomial Time

### Current License: CC BY-SA 2.5

22 events
when toggle format what by license comment
Oct 11 '10 at 19:19 history edited
Oct 8 '10 at 16:10 history rollback
Rollback to Revision 7
Oct 8 '10 at 16:10 history edited
deleted 1 characters in body
Oct 3 '10 at 18:46 answer timeline score: 3
Oct 3 '10 at 7:05 history edited
deleted 21 characters in body
Oct 2 '10 at 21:57 history edited
added 104 characters in body; edited tags
Oct 2 '10 at 21:52 history edited
Oct 2 '10 at 19:50 comment @sadeq : I meant pick uniformly at random X inputs, and use a Chernov bound, but as Robin says, it does not satisfy the constraint on the precision. There is a paper of Karp, Luby and Madras (Monte-Carlo algorithms for enumeration problem) with a sampler that is adaptive (by analysis of the variance), maybe it works for the precision but I guess it violates the constraint on the running time.
Oct 2 '10 at 19:34 history edited
deleted 46 characters in body
Oct 2 '10 at 19:10 comment @Sylvain: How many samples do you take before you stop? If you take a fixed number of samples, you'll get an estimate that will not satisfy the precision condition.
Oct 2 '10 at 18:59 comment @Sylvain: Could you please describe more, or provide a link? (P.S: I know what Chernoff bound is.)
Oct 2 '10 at 17:57 comment I think I don't clearly understand the question. Why a naive sampler with a chernoff bound is not a good estimator ?
Oct 2 '10 at 17:04 comment Just a wild guess: Fix some polynomial p(n). Keep choosing an n-bit string uniformly at random with replacement and summing the value of f at the chosen point until the sum becomes at least p(n). Let T be the number of the tries made, and output p(n)/T. I do not have a provable bound on the expected running time or the precision, but this might work.
Oct 2 '10 at 16:56 answer timeline score: 15
Oct 2 '10 at 16:49 comment @Tsuyoshi: Yes, the estimator is randomized. I edited the question to reflect the meaning of such conditions.
Oct 2 '10 at 16:48 history edited
Oct 2 '10 at 16:35 comment It seems that p(n)=q(n)=O(1) and the trivial algorithm $E^f(1^n)$ that outputs "1" should work. It's running time is O(1), which is bounded by $\frac{p(n)}{\mathbb{E}[f(n)]}$. And it's precision is <=1, which is less than q(n).