15
$\begingroup$

Suppose that a randomized algorithm uses $r$ random bits. The lowest error probability one can expect (falling short of a deterministic algorithm with 0 error) is $2^{-\Omega(r)}$. Which randomized algorithms achieve such minimal error probability?

A couple of examples that come to mind are:

  • Sampling algorithms, e.g., where one wants to estimate the size of a set for which one can check membership. If one samples uniformly at random the elements to check, the Chernoff bound guarantees an exponentially small error probability.
  • The Karger-Klein-Tarjan algorithm for computing minimum spanning tree. The algorithm picks each edge with probability 1/2, and recursively finds the MST in the sample. One can use Chernoff to argue that it's exponentially unlikely there'll be 2n+0.1m of the edges that are better than the tree (i.e., one would prefer to take them over one of the tree edges).

Can you think of other examples?

Following Andras' answer below: Indeed, every polynomial time algorithm can be converted to a slower polynomial time algorithm with exponentially small error probability. My focus is on algorithms that are as efficient as possible. In particular, for the two examples I gave there are deterministic polynomial time algorithms that solve the problems. The interest in the randomized algorithms is due to their efficiency.

$\endgroup$
  • 1
    $\begingroup$ Not a complete answer, but there has been some work in randomized numerical linear algebra. youtube.com/watch?v=VTroCeIqDVc $\endgroup$ – Baby Dragon Jun 11 '15 at 1:50
  • $\begingroup$ Perhaps one can't expect it, but one can certainly hope (still "falling short of a deterministic algorithm with 0 error") that for all real numbers $c\hspace{-0.02 in}$, if $\: c<1 \:$ then there is an algorithm $\hspace{.34 in}$ whose error probability is $2^{-\hspace{.01 in}c\cdot r}\hspace{-0.03 in}$. $\:$ I believe Polynomial Identity Testing is such a problem. $\hspace{.49 in}$ $\endgroup$ – user6973 Jun 12 '15 at 6:06
  • $\begingroup$ @RickyDemer I don't understand your comment. The usual randomized algorithm for PIT has error which is not exponential in the randomness. So what are you saying? Are you saying that there may exist such an algorithm for any BPP problem? $\endgroup$ – Sasho Nikolov Jun 12 '15 at 6:50
  • $\begingroup$ I now realize that I don't actually see any way of showing that PIT is in the class I described. $\:$ On the other hand, letting $S$ be super-polynomial in $d$ (i.e., letting length(S) be superlinear in length(d)) would suffice for the Schwartz-Zippel lemma $\:$ (continued ...) $\;\;\;\;$ $\endgroup$ – user6973 Jun 13 '15 at 1:28
  • 1
    $\begingroup$ Many probabilsitic method constructions have such behavior, no? For example, picking a random set of binary strings, and looking on their closest pair - the probability that there would be two strings in distance smaller than $n/4$ is very small. ------------------------------------------------------------------------- In the spirit of the BPP answer below: Given a constant degree expander, with n vertices, and $n/2$ marked vertices, the probability of a random walk of length $O( t )$ to miss a marked vertex is $2^{-\Omega(t)}$, if $t = \Omega( \log n)$. $\endgroup$ – Sariel Har-Peled Jun 19 '15 at 11:35
18
$\begingroup$

Impagliazzo and Zuckerman proved (FOCS'89, see here) that if a BPP algorithm uses $r$ random bits to achieve a correctness probability of at least 2/3, then, applying random walks on expander graphs, this can be improved to a correctness probability of $1-2^{-k}$, using $O(r+k)$ random bits. (Note: while the authors use the specific constant 2/3 in the abstract, it can be replaced with any other constant greater than 1/2.)

If we take $k=r$, this means that any BPP algorithm that achieves a constant error probability $< 1/2$, using $r$ random bits, can be (non-trivially) improved to have error probability $2^{-\Omega(r)}$. Thus, (unless I misunderstood something), the error probability of $\leq 2^{-\Omega(r)}$ is achievable for every problem in BPP.

$\endgroup$
  • 6
    $\begingroup$ The problem with such amplification techniques is that they slow down the algorithm. The new algorithm may only use O(r) random bits, but its running time is r times (original-run-time). If r is, say, at least linear in the input size n (which it usually is), you just slowed down the algorithm by a factor n. That's not something that most algorithmists would be happy about... $\endgroup$ – Dana Moshkovitz Jun 11 '15 at 14:58
2
$\begingroup$

I'm not sure this is what you're looking for, but it's related:

Suppose I want to find a random $k$-bit prime number. The usual algorithm is to pick a random (odd) $k$-bit integer and run the Miller-Rabin primality test for $t$ rounds on it and repeat until a probable prime is found. What is the probability that this procedure returns a composite number? Call this probability $p_{k,t}$.

The standard analysis of the Miller-Rabin primality test shows that $t$ rounds gives a failure probability of at most $4^{-t}$. This, along with the prime number theorem, implies $$p_{k,t} \leq O(k\cdot 4^{-t}).$$

However, we are running the Miller-Rabin test on random inputs, so we can use an average-case error guarantee. We get a much better bound. In particular, for $t=1$, $$p_{k,1} \leq 2^{-(1-o(1))\frac{k \ln\ln k}{\ln k}} \leq 2^{-\tilde\Omega(k)}.$$ That is to say, we get an exponentially-small failure probability with only one repetition of the test!

See Erdös and Pomerance (1986), Kim and Pomerance (1989), and Dåmgard, Landrock, and Pomerance (1993) for more details.

This is not a decision problem and the amount of randomness used is $O(k^2)$ bits (although I suspect this can be easily reduced to $O(k)$). However, it's an interesting example where we get exponentially-small failure probability naturally.

$\endgroup$

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.