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?

$\endgroup$
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.

$\endgroup$
  • $\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 Sep 25 '18 at 16:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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