Probability in Computer Science · Randomized Algorithms

Lesson 10

Nikolai Chukhin · Alexander S. Kulikov

Error Amplification of Randomized Algorithms

Suppose we have a randomized algorithm \(\mathcal{A}\) for some computational problem that has a unique correct (numerical) answer. The algorithm \(\mathcal{A}\) outputs the correct answer with probability exactly \(2/3\) (of course, we do not know the correct answer in advance, so we cannot tell just by looking at the algorithm's output whether it is correct or not). Thus, our algorithm makes an error with probability \(1/3\). Such a large error probability is unsatisfactory, and we would like to reduce it, for example, to \(1/20\). To do this, we proceed as follows: run our algorithm \(2k+1\) times and return the median of the answers. (One can also return the mode (majority) of the answers. In English, this is called the median/majority trick.) More formally:

  1. run the algorithm \(2k+1\) times;
  2. let \(a_{1}, \dotsc, a_{2k+1}\) be the answers produced by the algorithm;
  3. let \(a'_{1} \le a'_{2} \le \dotsb \le a'_{2k+1}\) be the sorted sequence of \(a_{1}, \dotsc, a_{2k+1}\);
  4. return \(a'_{k+1}\) (the median).
Why do we expect the error probability to decrease in this way? Since our algorithm outputs the correct answer with probability \(2/3\), about \(2(2k+1)/3\) of the runs should produce the correct answer. We assumed that the correct answer in our problem is unique. Hence, all correct answers in the sequence \(a'_{1} \le a'_{2} \le \dotsb \le a'_{2k+1}\) form a contiguous subsequence. A simple but key observation: if \(a'_{k+1}\) is incorrect, then the total number of correct answers is at most \(k\). This means that the random variable “number of correct answers” has deviated significantly from its mean (which, recall, equals \(2(2k+1)/3\)). Indeed, as \(k\) grows, the probability of such an error decreases.

Let us experimentally check for which \(k\) the error probability becomes less than \(1/20\). Let \(\alpha\) denote the number of correct answers among the \(2k+1\) runs. We are interested in \(\Pr[\alpha \le k]\). It equals \[\sum_{i=0}^{k}\Pr[\alpha=i]=\sum_{i=0}^{k}\binom{2k+1}{i}\left(\frac{2}{3}\right)^{i} \left(\frac{1}{3}\right)^{2k+1-i}\ .\] The code below plots this probability. One can see that already for \(k=11\) the error probability becomes less than \(0.05\), that is, 23 repetitions suffice. 

import matplotlib.pyplot as plt
from scipy.special import comb

p = 2 / 3
trials = []

for k in range(20):
    prob = .0
    for i in range(k + 1):
        prob += (p ** i) * ((1 - p) ** (2 * k + 1 - i)) \
                * comb(2 * k + 1, i)
    trials.append(prob)

plt.plot(trials)
plt.savefig('amplification.png')

In general, this effect can be formulated as follows. The bound follows from Chernoff estimates. Theorem (error amplification). Suppose a randomized algorithm outputs the correct answer with probability \(p > 1/2\). To reduce its error probability to an arbitrary \(\delta>0\), it suffices to repeat it \(O(\log 1/\delta)\) times and return the median of the answers.

This is a strong result: to reduce the error probability to \(1/10^{6}\), it suffices to repeat the algorithm roughly (up to a constant hidden in the \(O(\cdot)\)) \(\log 10^{6} \approx 20\) times!