7
$\begingroup$

This is a very basic doubt, something I've always swept under the carpet.

The definition of BPP allows a machine access to random bits, which are 0 and 1 with equal probability. Many a randomized algorithms need to sample points from a space/set of size $n$, where $n$ need not be a power of two, and sampling from such a space using random bits would typically yield Las Vegas sort of behaviour as far as running time is concerned i.e. at best, the expected running time can be bounded by polynomial.

Am I missing something here (like there being a way to sample from arbitrary sets using random bits without having to make the running time expected polynomial time), or is this something that is swept under the carpet for convenience sake i.e. BPP actually requires only expected running time being polynomial?

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ expected running time is never a problem. if you have an algorithm with expected running time $T$, run $t$ instances of it in parallel for $2T$ steps. if any of the $t$ instances terminated, output its answer (say of the one that terminated first, or take a majority vote of all instances that did terminate). if none terminated, output abort (or output something arbitrary). the probability that no instance terminated is at most $2^{-t}$. $\endgroup$
    – Sasho Nikolov
    Commented Aug 20, 2013 at 17:12

1 Answer 1

Reset to default
9
$\begingroup$

Use $k=\lceil\log n\rceil$ random bits to get a random number $r$ between $0$ and $2^k$. With probability at least $\tfrac{1}{2}$, $0\leq r < n$ so use that as your answer; otherwise, try again. If you've not succeeded after $t$ attempts, reject your input. The probability of this happening is at most $2^{-t}$, which can be made as small as you like and is a component of the probability that the machine gives the wrong answer.

Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ It remains to note that since for BPP the running time is poly(n), the added component in the probability of error is at most 2^(-t) poly(n). This value can be made arbitrarily small, since the value of t is just a factor in the total running time, and can be made, let's say, linear in n. $\endgroup$
    – dd1
    Commented Aug 20, 2013 at 13:41

Your Answer

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