0
$\begingroup$

Given a Monte-Carlo algorithm (called A) that given a binary array with b 'on' bits (one-bits) returns a, where in a probability of 1/2: $\frac b 3 \leq a \leq 3b$

How can I use A to build an algorithm that does the same, but with probability $poly(\frac 1 n)$ of success (success means $\frac b 3 \leq a \leq 3b$ ), using A? if A runs in $O(T(n))$ time ($T(n)$ is much smaller than $n$), what's the runtime of the new algorithm?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

This is a standard technique. Run the algorithm multiple times and take the median answer. The median will be a success unless there are many failures; use a Chernoff bound to show that this many failures has the low probability you require. Typically, a constant number of runs will give a constant (but better than $1/2$) failure probability, poly-log runs will give polynomially small failure probability and a polynomial number of runs will give exponentially small failure probability.

Improve this answer
$\endgroup$
1
  • $\begingroup$ what am I doing wrong? $Pr(success) = \sum_{i=1}^{num-of-trials} {Pr(success | we-chose-the-ith-result) * Pr(we-chose-the-ith-result)} =$ (since every trial has an equal probability of being the median) $= \sum_{i=1}^{num-of-trials} \frac1 2 * \frac 1 {num-of-trials} = \frac 1 2$ $\endgroup$
    – Daniel Hoch
    Commented Sep 25, 2018 at 16:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.