# Running time of randomized algorithms

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?

• 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}$. – Sasho Nikolov Aug 20 '13 at 17:12

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.