<p>Impagliazzo and Zuckerman proved (FOCS'89, see <a href="http://www.computer.org/csdl/proceedings/focs/1989/1982/00/063486.pdf">here</a>) 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. (<em>Note:</em> while the authors use the specific constant 2/3 in the abstract, it can be replaced with any other constant greater than 1/2.)</p>

<p>If we take $k=r$, this means  that <strong>any</strong> BPP algorithm that achieves a constant error probability $&lt; 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 <em>every</em> problem in BPP.</p>

CC BY-SA 3.0
2015-06-11T14:58:33.150Z
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...
Dana Moshkovitz
CC BY-SA 3.0
2015-06-11T04:21:31.927Z
2015-06-11T04:21:31.927Z
Andras Farago
<p>I'm not sure this is what you're looking for, but it's related:</p>

<p>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}$.</p>

<p>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}).$$</p>

<p>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 <i>only one repetition</i> of the test!</p>

<p>See <a href="http://www.jstor.org/stable/2008231" rel="nofollow">Erdös and Pomerance (1986)</a>, <a href="http://www.jstor.org/stable/2008733" rel="nofollow">Kim and Pomerance (1989)</a>, and <a href="http://www.jstor.org/stable/2152945" rel="nofollow">Dåmgard, Landrock, and Pomerance (1993)</a> for more details.</p>

<p>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.</p>

CC BY-SA 3.0
2015-06-19T08:10:43.293Z
2015-06-19T08:17:15.270Z
2015-06-19T08:17:15.270Z
Thomas Steinke
<p>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?</p>

<p>A couple of examples that come to mind are: </p>

<ul>
<li>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. </li>
<li>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).</li>
</ul>

<p>Can you think of other examples?</p>

<p><strong>Following Andras' answer below:</strong> Indeed, every polynomial time algorithm can be converted to a <em>slower</em> 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 <em>deterministic</em> polynomial time algorithms that solve the problems. The interest in the randomized algorithms is due to their efficiency. </p>

CC BY-SA 3.0
2015-06-11T01:50:22.830Z
Not a complete answer, but there has been some work in randomized numerical linear algebra. https://www.youtube.com/watch?v=VTroCeIqDVc
Baby Dragon
CC BY-SA 3.0
2015-06-12T06:50:58.630Z
@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?
Sasho Nikolov
CC BY-SA 3.0
2015-06-19T11:35:54.250Z
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)$.
Sariel Har-Peled
<randomized-algorithms>
Which randomized algorithms have exponentially small error probability?
Dana Moshkovitz
# Which randomized algorithms have exponentially small error probability?

(Asked by: username_0 on 2015-06-11)

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.

**Tags:** randomized-algorithms
> **Comments:**
> **username_1**: Not a complete answer, but there has been some work in randomized numerical linear algebra. https://www.youtube.com/watch?v=VTroCeIqDVc  
> **username_2**: @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?  
> **username_3**: 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)$.  

---

## 2 answers

### Answer by username_4 on 2015-06-11. Score: 18

Impagliazzo and Zuckerman proved (FOCS'89, see [here](http://www.computer.org/csdl/proceedings/focs/1989/1982/00/063486.pdf)) 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.

> **Comments:**
> **username_0**: 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...  

---

### Answer by username_5 on 2015-06-19. Score: 2

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)](http://www.jstor.org/stable/2008231), [Kim and Pomerance (1989)](http://www.jstor.org/stable/2008733), and [Dåmgard, Landrock, and Pomerance (1993)](http://www.jstor.org/stable/2152945) 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.


---

